Centralized management of resources shared by multiple processing units

• US 6,009,275 A
• Filed: 10/15/1996
• Issued: 12/28/1999
• Est. Priority Date: 04/04/1994
• Status: Expired due to Term

• Current Assignee: Taiwan Semiconductor Manufacturing Company Limited
• Original Assignee: NCR Corporation (NCR Voyix Corporation), Hyundai Electronics America Incorporated (SK Hynix Inc.)
• Inventors: DeKoning, Rodney A., Hoglund, Timothy E.
• Primary Examiner(s): Sheikh, Ayaz R.
• Assistant Examiner(s): Myers, Paul R.
• Application Number:
  US08/729,193
• Time in Patent Office: 1,169 Days
• Field of Search: 395/727-732, 395/293-305, 395/974
• US Class Current: 710/220
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

Resource allocation logic for a computer system including a plurality of processors which share access to, and control of, a plurality of resources, such as disk drive units or busses. The resource allocation logic coordinates the execution of requests received from the processors to avoid resource sharing inefficiencies and deadlock situations. The allocation logic maintains a "request" queue for each processor, seeking to satisfy all requests quickly and fairly. The queues contain an entry corresponding to each request received from its corresponding processor and an identification of resources that are required by the entry'"'"'s corresponding request. The allocation logic also maintains a "resources available" status array of resources which are not currently in use by any processors, or are not reserved for future use by any processors. The logic repeatedly compares each entry in the request queues with the entries in the resources available status array to detect an entry in the request queue identifying resources all of which are contained in the resources available status array. Once the allocation logic can satisfy a particular request, it signals a grant to the requesting processor for the resources requested. The requested resources are removed from the resources available status array. Upon conclusion of execution of the granted request, the resources are again released to the resource allocation logic for utilization by other resource requests. Additionally, each request queue contains a list age indicating the relative age of each request queue with respect to the other request queues, and each entry in the request queues includes a request age indicating the relative age of each entry in a request queue with respect to other entries in the request queue. In examining the request queues to identify I/O requests for execution, priority is awarded to entries based on the relative ages of the request queues and request queue entries.

Claims

1. In a computer system including a plurality of requesting agents and a plurality of resources, said requesting agents sharing access to and control over said resources, a method for coordinating the execution of I/O requests received from requesting agents to avoid resource sharing inefficiencies and deadlock situations, said method comprising the steps of:

(A) establishing a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received from said requesting agents, and wherein each of said entries includes an identification of resources that are required by the corresponding I/O request;

(B) maintaining a resources available status array, said resources available status array including an entry for each resource which is not currently in use by any requesting agent and is not currently reserved for future use by any requesting agent;

(C) systematically comparing each entry in said request queue with the entries in said resources available status array to detect an entry in said request queue identifying resources all of which are contained in said resources available status array;

(D) granting control of the resources associated with said entry detected in step C to the requesting agent providing the I/O request; and

(E) executing the I/O request corresponding to the entry identified in step C.

2. The method for coordinating the execution of I/O requests according to claim 1, further comprising the step of:

removing from said resources available status array the entries for each resource which is associated with said entry detected in step C upon the completion of step C.

3. The method for coordinating the execution of I/O requests according to claim 2, further comprising the step of:

returning to said resources available status array the entries for each resource which is associated with said entry detected in step C upon the completion of step E.

4. The method for coordinating the execution of I/O requests according to claim 1, wherein each entry in said request queue includes a request age indicating the relative age of each entry in the request queue with respect to other entries in the request queue, said method further including the step of:

granting priority to an entry in the request queue based on the relative ages.

5. The method for coordinating the execution of I/O requests according to claim 1, wherein:

said resources include disk drives within a disk array; and

said requesting agents comprise disk array controllers each of which share access to and control over said disk drives.

7. The method for coordinating the execution of I/O requests according to claim 1, wherein:

each entry within said request queue further includes a request age indicating the relative age of each entry in said request queue with respect to other entries in the request queue; and

said method further includes the steps of;

examining said request ages to identify any entry having a request age which exceeds a predetermined request age value; and

removing from said resources available status array the entries for each resource which is associated with said entry having a request age which exceeds said predetermined request age value, reserving the resources for use with the requesting agent and request associated with the entry having a request age which exceeds said predetermined request age value.

8. The method for coordinating the execution of I/O requests according to claim 1, wherein:

a request queue is maintained for each requesting agent in said computer system; and

said step of systematically comparing each entry in said request queue with the entries in said resources available status array includes the step of alternately examining the entries in each request queue to detect an entry in said request queues identifying resources all of which are contained in said resources available status array.

20. The method of claim 1 wherein said method further comprises the step of:

(F) releasing said resources associated with said entry detected in step C in response to completion of execution of said I/O request in step E.

21. The method of claim 20 wherein one of said plurality of requesting agents is designated as a master and each of the remainder of said plurality of requesting agents is designated as a slave, and wherein the method further comprises the step of:

exchanging messages between said master and said slaves to perform steps B, C, D, and F of the method.

6. In a computer system including a plurality of requesting agents and a plurality of resources, said requesting agents sharing access to and control over said resources, a method for coordinating the execution of I/O requests received from requesting agents to avoid resource sharing inefficiencies and deadlock situations, said method comprising the steps of:

(A) establishing a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received from said requesting agents, and wherein each of said entries includes an identification of resources that are required by the corresponding I/O request;

(B) maintaining a resources available status array, said resources available status array including an entry for each resource which is not currently in use by any requesting agent and is not currently reserved for future use by any requesting agent;

(C) systematically comparing each entry in said request queue with the entries in said resources available status array to detect an entry in said request queue identifying resources all of which are contained in said resources available status array;

(D) granting control of the resources associated with said entry detected in step C to the requesting agent providing the I/O request; and

(E) executing the I/O request corresponding to the entry identified in step C,

wherein said resources include busses within said computer system.

18. The computer system of claim 6, wherein a request queue is maintained for each requesting agent in said computer system;

and

said step of systematically comparing each entry in said request queue with the entries in said resources available status array includes the step of alternately examining the entries in each request queue to detect an entry in said request queues identifying resources all of which are contained in said resources available status array.

9. In a computer system including a plurality of requesting agents and a plurality of resources, said requesting agents sharing access to and control over said resources, a method for coordinating the execution of I/O requests received from requesting agents to avoid resources sharing inefficiencies and deadlock situations, said method comprising the steps of:

(A) establishing a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received from said requesting agents, and wherein each of said entries includes an identification of resources that are required by the corresponding I/O request;

(B) maintaining a resources available status array, said resources available status array including an entry for each resource which is not currently in use by any requesting agent and is not currently reserved for future use by any requesting agent;

(C) systematically comparing each entry in said request queue with the entries in said resources available status array to detect an entry in said request queue identifying resources all of which are contained in said resources available status array;

(D) granting control of the resources associated with said entry detected in step C to the requesting agent providing the I/O request; and

(E) executing the I/O request corresponding to the entry identified in step C,

wherein said requesting agents are disk array controllers within a disk array subsystem within said computer system; and

said resources are disk drives and busses within said disk array subsystem.

19. The computer system of claim 9, wherein a request queue is maintained for each requesting agent in said computer system;

and

said step of systematically comparing each entry in said request queue with the entries in said resources available status array includes the step of alternately examining the entries in each request queue to detect an entry in said request queues identifying resources all of which are contained in said resources available status array.

10. In a disk array system including a plurality of disk array controllers and a plurality of disk drives and busses under the control of a plurality of processors, a method for coordinating the operation of said disk array controllers, said method comprising the steps of:

(A) establishing a request queue for each disk array controller, each request queue including an entry corresponding to an I/O request received by said disk array system, each entry including an identification of resources that are required by said entry'"'"'s corresponding I/O request wherein said resources includes disk drives and busses within said disk array system;

(B) maintaining a status array, said status array including an entry for each disk drive and bus which is not currently in use by any disk array controller and is not currently reserved for future use by any disk array controller;

(C) systematically comparing each entry in said request queues with the entries in said status array to detect an entry in said request queues identifying resources all of which are contained in said status array;

(D) granting control of resources identified by said entry detected in step C to the disk array controller associated with the request queue; and

(E) executing the I/O request corresponding to the entry identified in step C.

11. The method for coordinating the execution of I/O requests according to claim 10, wherein:

each entry within said request queue further includes a request age indicating the relative age of each entry in said request queue with respect to other entries in the request queue; and

said method further includes the steps of;

examining said request ages to identify any stagnant entry having a request age which exceeds a predetermined request age value; and

removing from said status array the entries for each resource which is associated with said entry having a request age which exceeds said predetermined request age value, and reserving the disk drives for use with the I/O request associated with the stagnant entry.

12. The method for coordinating the execution of I/O requests according to claim 10, wherein:

said step of systematically comparing each entry in said request queue with the entries in said status array includes the step of alternately examining the entries in each request queue to detect an entry in said request queues identifying resources all of which are contained in said status array.

13. The method for coordinating the execution of I/O requests according to claim 10, wherein:

each request queue further includes a list age indicating the age of the oldest entry in the request queue;

said step of systematically comparing each entry in said request queue with the entries in said resources available status array includes the steps of;

examining said list ages to identify any request queue having a list age which exceeds a predetermined list age value; and

if a request queue is identified as having a list age which exceeds said predetermined list age, systematically comparing the entries in the request queue identified as having a list age which exceeds said predetermined list age only until the list age for the request queue is below said predetermined list age value.

22. The method of claim 10 wherein said method further comprises the step of:

(F) releasing said resources associated with said entry detected in step C in response to completion of execution of said I/O request in step E.

23. The method of claim 22 wherein one of said disk array controllers is designated as a master controller and each of the remainder of said plurality of disk array controllers is designated as a slave controller, and wherein the method further comprises the step of:

exchanging messages between said master and said slaves to perform steps B, C, D, and F of the method.

14. In a computer system including a plurality of requesting agents and a plurality of resources, said requesting agents sharing access to and control over said resources, a method for coordinating the execution of I/O requests received from requesting agents, said method comprising the steps of:

(A) establishing a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received from said requesting agents, and wherein each of said entries includes an identification of resources that are required by the corresponding I/O request;

(B) maintaining a status array, said status array including an entry for each resource which is available;

(C) systematically comparing each entry in said request queue with the entries in said status array to detect an entry in said request queue identifying resources all of which are available;

(D) executing the I/O request corresponding to the entry identified in step C.

15. The method for coordinating the execution of I/O requests according to claim 14, wherein each entry in said request queue includes a request age indicating the relative age of each entry in the request queue with respect to other entries in the request queue, said method further including the step of granting priority to an entry in the request queue based on the relative ages.

16. The method for coordinating the execution of I/O requests according to claim 14, wherein each entry within said request queue further includes a request age indicating the relative age of each entry in said request queue with respect to other entries in the request queue, said method further includes the steps of:

examining said request ages to identify any entry having a request age which exceeds a predetermined request age value; and

removing from said status array the entries for each resource which is associated with said entry having a request age which exceeds said predetermined request age value.

17. The method for coordinating the execution of I/O requests according to claim 14, wherein a request queue is maintained for each requesting agent in said computer system, said step of systematically comparing each entry in said request queue with the entries in said status array includes the step of alternately examining the entries in each request queue to detect an entry in said request queues identifying resources all of which are available.

24. A system for coordinating the activity of a plurality of controllers in a disk array subsystem having a plurality of disk drives, busses, and processors associated therewith, said system comprising:

a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received by a controller in said disk array subsystem, wherein each of said entries includes an identification of resources required to execute the corresponding I/O request, and wherein said resources includes disk drives and busses in said disk array subsystem;

a status array having a plurality of entries, each entry identifying a disk drive or bus not currently in use by any of said plurality of controllers;

control means, associated with said request queue and with said status array, for systematically comparing each entry in said request queue with the entries in said status array to detect an entry in said request queue identifying resources all of which are contained in entries of said status array; and

means, within said control means, for granting control to one of said plurality of controllers of said resources identified by the detected entry in said request queue.

25. The system of claim 24 further comprising:

means, within said one of said plurality of controllers, for releasing control of said resources granted to said one of said plurality of controllers.

26. The system of claim 25 further comprising:

communication means connecting each of said plurality of controllers for exchanging messages among said plurality of controllers.

27. The system of claim 26 wherein said messages include resource request messages, resource grant messages, and resource release messages.

28. The system of claim 27 wherein each of said plurality of controllers includes request means for transmitting a resource request message to said control means identifying the requesting one of said plurality of controllers and identifying the resources requested for use by said requesting one of said plurality of controllers.

29. The system of claim 28 wherein said means for granting includes means for transmitting resource grant message to said requesting one of said plurality of controllers.

30. The system of claim 24 further comprising:

a plurality of request queues, each having a plurality of entries and each of said plurality of request queues corresponding to one of said plurality of controllers,

wherein said control means is associated with each of said plurality of request queues and with said status array, for systematically comparing each entry in each of said plurality of request queues with the entries in said status array to detect an entry in one of said plurality of request queues identifying resources all of which are contained in entries of said status array.

31. In a computer system having a plurality of requesting agents and a plurality of resources, said plurality of requesting agents sharing access to and control over said plurality of resources, a system for coordinating the the execution of I/O requests received from said plurality of requesting agents to avoid resource sharing inefficiencies and deadlock situations, said system comprising:

a request queue comprising a list of entries wherein each of said entries corresponds to an I/O request received from said plurality of requesting agents, and wherein each of said entries includes an identification of resources required to execute the corresponding I/O request;

a status array having a plurality of entries, each entry identifying at least one of said plurality of resources not currently in use by any of said plurality of requesting agents;

control means, associated with said request queue and with said status array, for systematically comparing each entry in said request queue with the entries in said status array to detect an entry in said request queue identifying resources all of which are contained in entries of said status array; and

means, within said control means, for granting control to one of said plurality of requesting agents of said resources identified by the detected entry in said request queue.

32. The system of claim 31 further comprising:

means, within said one of said plurality of requesting agents, for releasing control of said resources granted to said one of said requesting agents.

33. The system of claim 32 further comprising:

communication means connecting each of said plurality of requesting agents for exchanging messages among said plurality of requesting agents.

34. The system of claim 33 wherein said messages include resource request messages, resource grant messages, and resource release messages.

35. The system of claim 34 wherein each of said plurality of requesting agents includes request means for transmitting a resource request message to said control means identifying the requesting one of said plurality of requesting agents and identifying the resources requested for use by said requesting one of said plurality of requesting agents.

36. The system of claim 35 wherein said means for granting includes means for transmitting resource grant message to said requesting one of said plurality of requesting agents.

37. The system of claim 35 wherein each of said plurality of requesting agents further includes release means for transmitting a resource release message to said control means identifying the resources no longer in use.

38. The system of claim 31 further comprising:

a plurality of request queues, each having a plurality of entries and each of said plurality of request queues corresponding to one of said plurality of requesting agents,

wherein said control means is associated with each of said plurality of request queues and with said status array, for systematically comparing each entry in each of said plurality of request queues with the entries in said status array to detect an entry in one of said plurality of request queues identifying resources all of which are contained in entries of said status array.