Priority arbiter with shifting sequential priority scheme

• US 6,073,132 A
• Filed: 03/27/1998
• Issued: 06/06/2000
• Est. Priority Date: 03/27/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Gehman, Judy M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/049,500
• Time in Patent Office: 802 Days
• Field of Search: 707/1, 707/9, 707/10, 707/200, 707/201, 707/202, 707/203, 707/204, 710/100, 710/111, 710/116, 710/117, 710/119, 710/200, 710/241, 710/244
• US Class Current: 1/1
• CPC Class Codes: G06F 13/362 with centralised access control
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

An improved data processing system and in particular an improved data processing system that more effectively manages a shared resource within a data processing system. More specifically, a method and apparatus for managing access to a shared resource between a plurality of devices simultaneously requesting access to the shared resource. The present invention implements a design that combines a priority configuration and a shifting sequential configuration. The access is controlled by an arbiter that determines access to the shared resource by granting first, to priority devices and then to the highest priority shifting sequential device requesting access within one clock cycle of a device terminating its request for access to the shared resource. In addition, the present invention employs a dynamic shifting sequential priority scheme by assigning lowest priority to a shifting sequential device once the device terminates its request to access the shared resource while simultaneously incrementally increasing the priority levels of the remaining shifting sequential devices.

Claims

1. A method in a data processing system for arbitrating access to a shared resource by a plurality of devices, wherein each of the plurality of devices is associated with a priority, the method comprising:

receiving requests from a number of devices within the plurality of devices for access to the shared resource;

identifying each device within the number of devices;

in response to one of the devices within the number of devices being identified as a priority device, granting the priority device to access the shared resource;

in response to the number of devices being identified as a number of devices with shifting priorities, granting access to the shared resource to a device within the number of devices having a highest priority among the number of devices from which the requests were received; and

shifting the priority of the device having the highest priority to a lowest priority and shifting the priority of remaining devices within the plurality of devices having shifting priorities after granting the device access to the shared resource.

2. The method of claim 1, wherein a number of devices within the plurality of devices having shifting priorities and further comprising:

receiving a single request from a device within the number of devices;

in response to receiving a single request from a device having a shifting priority, granting the device access to the shared resource, wherein the device is a selected device; and

shifting the priority of the selected device to a lowest priority among the plurality of devices.

3. The method of claim 2, wherein the selected device has a priority other than the highest priority among the number of devices and wherein the selected device is granted access to the shared resource without having to wait for the priority of the selected device to shift to the highest priority among the number of devices.

4. The method of claim 2 further comprising:

shifting priorities of devices within the number of devices other than the selected device relative to the selected device.

5. The method of claim 4, wherein priorities of the number of devices remain fixed with respect to each other as the priorities of the number of devices shift.

6. The method of claim 1, wherein the shared resource is a bus.

7. The method of claim 1, wherein a device granted access to the shared resource maintains control of the bus until the device releases the shared resource.

8. The method of claim 1 further comprising:

detecting a release of the shared resource by the device granted access to the shared resource by detecting a deassertion of the request from the device.

9. A data processing system comprising:

a priority device;

a plurality of devices having shifting priorities, wherein each device within the plurality of devices has a priority relative to other devices within the plurality of devices;

detection means for detecting requests from a number of devices within the plurality of devices for access to the shared resource;

identification means for identifying each device within the number of devices;

first granting means, responsive to detecting a request from the priority device, for granting the priority device to access the shared resource;

second granting means, responsive to detecting requests from a number of devices within the plurality of devices, for granting access to a device within the number of devices having a highest priority among the number of devices from which the requests were detected; and

shifting means, responsive to the second granting means granting access to a device, for shifting the priority of the device having the highest priority to a lowest priority and for shifting the priority of remaining devices within the plurality of devices having shifting priorities.

10. The data processing system of claim 9 further comprising:

means, responsive to receiving a single request from a device within the plurality of devices, for granting the device access to the shared resource, wherein the device is a selected device; and

second shifting means for shifting the priority of the selected device to a lowest priority among the plurality of devices.

11. The data processing system of claim 10, wherein the selected device has a priority other than a highest priority among the plurality of devices and wherein the selected device is granted access to the shared resource without having to wait for the priority of the device to shift to the highest priority among the number of devices.

12. The data processing system of claim 9 further comprising:

third shifting means for shifting priorities of devices within the plurality of devices other than the selected device relative to the selected device.

13. The data processing system of claim 12, wherein priorities of the plurality of devices remain fixed with respect to each other as the priorities of the number of devices shift.

14. The data processing system of claim 9, wherein the shared resource is a bus.

15. The data processing system of claim 9, wherein a device granted access to the share resource maintains control of the bus until the device releases the shared resource.

16. The data processing system of claim 9, wherein the data processing system is located on a chip.

17. The method of claim 9, wherein the data processing system is a personal computer.

18. A method for arbitrating access to a shared resource among devices in a data processing system, wherein the devices include a device of a first type and a plurality of devices of a second type, the method comprising:

monitoring the devices for requests for the shared resource;

granting the device of the first type access to the shared resource in response to detecting a request from the first device;

granting access to a selected device within the plurality of second devices of the second type in response to a request from the selected device and an absence of a request from the device of the first type, wherein the selected device has a greater priority than other devices within the plurality devices of the second type; and

changing priorities among the plurality of devices of the second type, wherein the selected device has a lowest priority.

19. The method of claim 18, wherein the granting steps occur within a single clock cycle.

20. The method of claim 18, wherein the shared resource is a bus.

21. A data processing system comprising:

a shared resource;

a priority device coupled to the shared resource;

a plurality of shifting priority devices coupled to the shared resource;

an arbiter coupled to the shared resource, wherein the arbiter has a plurality of modes of operation including;

a first mode of operation in which the arbiter monitors for requests for the shared resource;

a second mode of operation, responsive to detecting at least one request for the shared resource in the first mode of operation, in which the arbiter identifies a device for each request detected;

a third mode of operation, in response to identifying a request from the priority device, in which the arbiter grants the priority device access to the shared resource;

a fourth mode of operation, responsive to detecting a request from a shifting priority device, in which the arbiter grants the shifting priority device access to the shared resource and shifts the shifting priority device to a lowest priority among the plurality of shifting priority devices;

a fifth mode of operation, responsive to detecting a request from at least two shifting devices from the plurality of shifting priority devices, in which the arbiter grants access to a shifting priority device having a highest priority among the at least two shifting priority devices; and

a sixth mode of operation, responsive to granting access to the shifting priority device having the highest priority, in which the arbiter assigns a lowest priority to the shifting priority device granted access to the shared resource.

22. The data processing system of claim 21, wherein the arbiter further includes:

a seventh mode of operation, responsive to the arbiter assigning the lowest priority to the shifting priority device granted access to the shared resource, in which the arbiter shifts priorities of remaining shifting priority devices relative to the shifting s priority device assigned the lowest priority.

23. The data processing system of claim 22, wherein the arbiter grants access to the shared resource after receiving at least one request within a single clock cycle.

24. A data processing system, comprising:

a plurality of devices, the plurality of devices including a plurality of shifting priority devices; and

an arbiter, wherein the arbiter receives requests from the plurality of devices for access to a shared resource, and wherein if one of the plurality of devices is a priority device, the arbiter chooses the priority device to access the shared resource, and if a priority device is absent, the arbiter chooses a device having a highest priority from of the plurality of shifting priority devices to access the shared resource.

25. The system of claim 24, wherein the requests are received approximately simultaneously.

26. The system of claim 24, wherein the requests are received within a single clock cycle.

27. The system of claim 24, wherein the shared resource is a bus.

28. The system of claim 24, wherein the data processing system is located on a chip.

29. The system of claim 24, wherein the data processing system is a personal computer.

30. The system of claim 24, wherein priorities of the plurality of shifting priority devices are shifted after choosing the device having the highest priority from the plurality of shifting priority devices to access the shared resource.

31. The system of claim 30, wherein the priorities of the plurality of shifting priority devices are shifted such that the priority of the device having the highest priority is shifted to a lowest priority within the plurality of shifting devices.

32. The system of claim 30, wherein the priorities of the plurality of shifting priority devices, other than the device having the highest priority, remain fixed with respect to each other as the priorities of the plurality of shifting priority devices shift.