Method and apparatus for managing resource contention in a multisystem cluster

• US 20040128385A1
• Filed: 12/31/2002
• Published: 07/01/2004
• Est. Priority Date: 12/31/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Arwe, John E.
• Granted Patent: US 7,228,351 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method and apparatus for managing contention among users for access to resources in a multisystem cluster by identifying contention chains in which each user is waiting for a resource held by the user(s) before it in the chain and allocating system resources to the user(s) at the head of the chain as if their need were at least that of the neediest waiter in the chain. The contention data necessary for optimal resource allocation is effectively distributed across the system cluster, even though the data flow between systems is minimal and no system has a complete view of cross-system contention. Each system tracks resources in contention having local users as either holders or waiters and groups such resources into clusters of resources involved in contention chains in which each resource is either held by a local user waiting for another resource in the cluster or being waited for by a local user holding another resource in the cluster. Each system stores cluster data grouping the resources into clusters on the basis of its own local contention data and indicating for each cluster the need of the neediest waiter on that system for any resource in the cluster. Whenever a local resource manager notifies a system of a change in the contention status of a resource having local holders or waiters, the system updates its cluster data for the affected resources. The system broadcasts the updated cluster data by transmitting for each affected resource the cluster assignment based on local contention data and the need of the neediest local waiter for that resource. Upon receiving cluster data from another system, a system combines the received cluster data with its own cluster data to generate a composite grouping of resources into clusters on the basis of cross-system contention and indicating for each composite cluster the need of the neediest waiter across the systems for any resource in the cluster. The system uses this information to allocate system resources to a local user that is holding a resource in a cluster but not waiting for any other resource as if its need were at least that of the neediest waiter for any resource in the cluster.

Claims

1. A method for managing contention among users for access to one or more resource in a system cluster containing a plurality of systems, each of said users having an assigned need and being capable of being either a holder or a waiter for a resource it is seeking to access, said method being performed on at least one of said systems as a local system and comprising the steps of:

storing local cluster data indicating a grouping of said resources into one or more local clusters on the basis of contention on said local system and indicating for each of said local clusters a need for one or more resources in said local cluster;

receiving remote cluster data from another system in said system cluster as a remote system indicating a grouping of said resources into one or more remote clusters on the basis of contention on said remote system and indicating for each of said remote clusters a need for one or more resources in said remote cluster;

combining said local cluster data and said remote cluster data to generate composite cluster data indicating a grouping of said resources into one or more composite clusters on the basis of contention across said systems and indicating for each of said composite clusters a need for one or more resources in that composite cluster; and

managing a holder on said local system of a resource in one of said composite clusters in accordance with the composite cluster data for said cluster.

2. The method of claim 1 in which said need for one or more resources in any of said clusters is the need of a neediest waiter for any resource in the cluster.

3. The method of claim 1 in which said managing step comprises the steps of:

identifying a holder on said local system of a resource in one of said composite clusters that is not waiting for any other resource; and

allocating system resources to said holder of said resource on said local system as if its need were at least that of a neediest waiter for any resource in said composite cluster.

4. The method of claim 1 in which said receiving step is performed for each of a plurality of other systems in said system cluster as remote systems.

5. The method of claim 1 in which said local system assigns a pair of resources to a common local cluster if a user on said local system is holding one of the resources while waiting for the other of the resources.

6. The method of claim 1 in which said local system updates said local cluster data in response to receiving a notification of a change in the contention status of a resource with regard to a user on said local system.

7. The method of claim 6 in which said local system transmits the updated local cluster data to said remote system.

8. The method of claim 1 in which said local system updates said composite cluster data upon receiving remote cluster data from said remote system.

9. The method of claim 1 in which said local system transmits local cluster data to said remote system.

10. The method of claim 9 in which the transmitted local cluster data indicates a resource, a cluster to which the resource is assigned on the basis of contention on the local system, and a need on said local system for said resource.

11. Apparatus for managing contention among users for access to one or more resource in a system cluster containing a plurality of systems, each of said users having an assigned need and being capable of being either a holder or a waiter for a resource it is seeking to access, said apparatus being associated with at least one of said systems as a local system and comprising:

logic for storing local cluster data indicating a grouping of said resources into one or more local clusters on the basis of contention on said local system and indicating for each of said local clusters a need for one or more resources in said local cluster;

logic for receiving remote cluster data from another system in said system cluster as a remote system indicating a grouping of said resources into one or more remote clusters on the basis of contention on said remote system and indicating for each of said remote clusters a need for one or more resources in said remote cluster;

logic for combining said local cluster data and said remote cluster data to generate composite cluster data indicating a grouping of said resources into one or more composite clusters on the basis of contention across said systems and indicating for each of said composite clusters a need for one or more resources in that composite cluster; and

logic for managing a holder on said local system of a resource in one of said composite clusters in accordance with the composite cluster data for said cluster.

12. The apparatus of claim 11 in which said managing logic comprises:

logic for identifying a holder on said local system of a resource in one of said composite clusters that is not waiting for any other resource; and

logic for allocating system resources to said holder of said resource on said local system as if its need were at least that of a neediest waiter for any resource in said composite cluster.

13. The apparatus of claim 11 in which said local system assigns a pair of resources to a common local cluster if a user on said local system is holding one of the resources while waiting for the other of the resources.

14. The apparatus of claim 11 in which said local system updates said local cluster data and transmits the updated local cluster data to said remote system in response to receiving a notification of a change in the contention status of a resource with regard to a user on said local system.

15. The apparatus of claim 11 in which said local system transmits local cluster data to said remote system, the transmitted local cluster data indicating a resource, a cluster to which the resource is assigned on the basis of contention on the local system, and a need on said local system for said resource.

16. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing contention among users for access to one or more resource in a system cluster containing a plurality of systems, each of said users having an assigned need and being capable of being either a holder or a waiter for a resource it is seeking to access, said method steps being performed on one of said systems as a local system and comprising:

storing local cluster data indicating a grouping of said resources into one or more local clusters on the basis of contention on said local system and indicating for each of said local clusters a need for one or more resources in said local cluster;

receiving remote cluster data from another system in said system cluster as a remote system indicating a grouping of said resources into one or more remote clusters on the basis of contention on said remote system and indicating for each of said remote clusters a need for one or more resources in said remote cluster;

combining said local cluster data and said remote cluster data to generate composite cluster data indicating a grouping of said resources into one or more composite clusters on the basis of contention across said systems and indicating for each of said composite clusters a need for one or more resources in that composite cluster; and

managing a holder on said local system of a resource in one of said composite clusters in accordance with the composite cluster data for said cluster.

17. The program storage device of claim 16 in which said managing step comprises the steps of:

identifying a holder on said local system of a resource in one of said composite clusters that is not waiting for any other resource; and

allocating system resources to said holder of said resource on said local system as if its need were at least that of a neediest waiter for any resource in said composite cluster.

18. The program storage device of claim 16 in which said local system assigns a pair of resources to a common local cluster if a user on said local system is holding one of the resources while waiting for the other of the resources.

19. The program storage device of claim 16 in which said local system updates said local cluster data and transmits the updated local cluster data to said remote system in response to receiving a notification of a change in the contention status of a resource with regard to a user on said local system.

20. The program storage device of claim 16 in which said local system transmits local cluster data to said remote system, the transmitted local cluster data indicating a resource, a cluster to which the resource is assigned on the basis of contention on the local system, and a need on said local system for said resource.