Lingering locks with fairness control for multi-node computer systems

• US 6,480,918 B1
• Filed: 12/22/1998
• Issued: 11/12/2002
• Est. Priority Date: 12/22/1998
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Malige, Raghupathi, McKenney, Paul E., Closson, Kevin A.
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/219,229
• Time in Patent Office: 1,421 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 707/200, 707/202, 710/200, 710/240, 710/241, 710/244, 710/260, 710/261, 710/262, 710/263, 710/264
• US Class Current: 710/200
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The processors in a multiprocessor computer system are grouped into nodes. The processors can request a lock, but the lock is granted to only one processor at any given time to provide exclusive processor access to the resource protected by the lock. When a processor releases the lock, the lock is made available to another processor at the same node, even though a processor at a different node may have requested the lock earlier. To maintain fairness, the lock is forced to another node after granting a certain number of consecutive requests at a node or after a certain time period. In one embodiment, a specialized data structure representing a lock request from a processor at a particular node is placed into a queue. A later requesting processor can acquire a preemptive position in the queue by spinning on a data structure already in the queue if the data structure corresponds to the processor'"'"'s node. To maintain fairness, the data structure is limited to a certain number of uses, after which additional processors are not permitted to spin on it. When the data structure has no more active spinners, it is dequeued, and the lock is made available to a processor spinning on the next structure in the queue. Logic for handling interrupts is included, and the bitfield arrangement of the data structure is tailored to the locking scheme. Preallocating data structures for the queue increases performance.

Claims

1. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a node while maintaining fairness among the nodes, the method comprising:

providing a fairness control criterion;

tracking requests from processing units for a lock held by a processing unit at a first node; and

when the lock is released by the processing unit at the first node, if there is an outstanding lock request by a processing unit at a second node and the fairness control criterion has been met, forcing the lock to the second node.

2. A computer-readable medium on which are stored computer instructions for executing the steps of claim 1.

3. The method of claim 1 wherein the fairness control criterion is one of the following:

the lock has been kept at the first node for more than a predetermined maximum number of consecutive grants;

the lock has been kept at the first node for longer than a predetermined time; and

the lock has been released by a processing unit granted a last outstanding lock request in a set of lock requests grouped by node, wherein the set is limited to a predetermined size.

4. The method of claim 1 wherein forcing the lock to the second node comprises moving the lock to the second node in a round robin order, skipping nodes with no outstanding lock requests.

5. The method of claim 1 wherein the requests for the lock comprise conditional requests for the lock.

6. The method of claim 1 wherein the requests for the lock are grouped by associated node and stored in memory local to the associated node.

7. The method of claim 6 wherein the processing units spin on a data structure in the memory local to the associated node to determine when the lock is available.

8. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a node while maintaining fairness among the nodes, the method comprising:

tracking requests for the lock from requesting processing units by node;

when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node; and

overriding the keeping step by forcing the lock to a second node if there is an outstanding lock request by a processing unit residing at the second node and the lock has been kept at the first node for more than a predetermined number of consecutive grants.

9. The method of claim 8 further comprising:

when the lock moves to the processing unit at the first node, setting a consecutive grants value to indicate one consecutive grant at the first node, wherein

the keeping step comprises adjusting the consecutive grants value to indicate an additional consecutive grant; and

the overriding step determines when to force the lock to the second node by comparing the consecutive grants value and the predetermined number.

10. The method of claim 8 wherein a processing unit having an outstanding lock request spins on a variable local to the processing unit'"'"'s node, the variable indicating to the processing unit whether the lock is available.

11. The method of claim 8 further comprising:

blocking a thread after the thread has spun on the lock for more than a predetermined amount of spin time; and

unblocking the thread when the lock is made available to a processing unit at the node on which the thread was last spinning.

12. The method of claim 8 further comprising:

when processing units at the first node request the lock, checking a structure in memory local to the first node to determine if other processing units at the first node have outstanding lock requests; and

if other processing units at the first node do not have outstanding lock requests, modifying the structure to indicate an unreleased lock request at the first node.

13. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a node while maintaining fairness among the nodes, the method comprising:

tracking requests for the lock from requesting processing units by node;

when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node; and

overriding the keeping step by forcing the lock to a second node if there is an outstanding lock request by the second node and the lock has been kept at the first node for more than a predetermined time.

14. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at the nodes while maintaining fairness among the nodes, the method comprising:

grouping lock requests into sets by node;

when the lock is released by a processing unit at a first node, keeping the lock at the first node if there is an outstanding lock request from a processing unit residing at the first node; and

overriding the keeping step by forcing the lock to a second node when releasing a last outstanding lock request in one of the sets.

15. The method of claim 14 wherein each of the sets is represented by a lock request data structure, the method further comprising:

before receiving any lock requests, preallocating in memory a number of lock request data structures sufficient to avoid allocating memory for a lock request data structure when a lock request is received.

16. The method of claim 14 further comprising:

if one of the received lock requests is passed by because a processing unit was interrupted when the lock became available, providing a passed by indication to the interrupted processing unit and reissuing the lock request.

17. The method of claim 14 wherein lock requests by an interrupted processing unit are not deemed to be outstanding lock requests.

18. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock at a specific node while maintaining fairness among the nodes by maintaining a queue of requests, the method comprising:

enqueuing a plurality of lock requests into the queue, each lock request originating from one of the processing units, wherein each processing unit is associated with a single node;

tracking from which node each lock request originates in the queue;

tracking the number of preemptive positions conferred for each node; and

upon receiving a lock request from a requesting processing unit at a node for which a lock request already exists in the queue, conferring a preemptive position in the queue to the requesting processing unit if the number of preemptive positions conferred for the node does not exceed a predetermined number.

19. The method of claim 18 further comprising:

when the lock becomes available, ignoring a lock request having a preemptive position in the queue for an interrupted processing unit next in the queue.

20. In a computer having a number of interconnected nodes each having at least one processing unit, a method of keeping a lock requestable by the processing units at a node while maintaining fairness among the nodes by maintaining a queue of node queue elements with a head and a tail to track lock requests, each node queue element corresponding to one of the nodes, the method comprising:

if the lock is requested by a first processing unit when the lock is available and the queue is empty, granting the lock to the first processing unit and placing a node queue element in the queue corresponding to the node of the first processing unit;

if the lock is requested by a second processing unit when the lock is unavailable and the queue contains a node queue element corresponding to the second processing unit'"'"'s node not used more than a predetermined maximum number of times, preemptively queuing the lock request at the node queue element and spinning the second processing unit on the element;

if the lock is requested by a third processing unit when the lock is unavailable and the queue does not contain a node queue element corresponding to the third processing unit'"'"'s node not used more than a predetermined number of times, queuing a node queue element at the tail of the queue and spinning the third processing unit on the element;

when the lock becomes available and the queue has at least one node queue element on which at least one processing unit is spinning, modifying the node queue element at the head of the queue to indicate that the lock is available to processing units spinning on the node queue element at the head of the queue, thereby granting the lock to a processing unit at a node corresponding to the node queue element at the head of the queue; and

when the lock is released by a releasing processing unit and a node queue element at the head of the queue indicates that no more processing units are spinning on the element, dequeueing the node queue element.

21. A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure comprising:

an ordered queue of spin state data structures with a head and a tail, each of the spin state data structures comprising;

an available field upon which requesting processing units can spin, indicative of when the lock is available;

a number-of-spinners field indicative of how many processing units are spinning on the spin state data structure; and

a uses field indicative of how many times the spin state data structure has been used to acquire a position in the queue and limited to a predetermined number to enforce fairness among the nodes, wherein each spin state data structure is associated with one of the interconnected nodes, wherein the spin state data structure at the head of the queue indicates to which node the lock should be next granted if the number-of-spinners field is greater than zero; and

a header structure facilitating management of the queue, the header structure comprising a reference to the head of the ordered queue, a reference to the tail of the queue, and a reference to a queue element, if any, for each of the interconnected nodes.

22. The computer-readable medium of claim 21 wherein the ordered queue contains more than one spin state data structure for a node, the first spin state data structure for the node having a uses field equal to the predetermined maximum, wherein the header structure refers to the last spin state data structure in the queue for the node.

23. The computer-readable medium of claim 21 wherein each of the spin state data structures is stored in memory local to the node associated with the spin state data structure, whereby processing units at the associated node can spin on the data structure by referencing memory local to the processing units.

24. The computer-readable medium of claim 21 wherein the spin state data structure further comprises:

a future references field indicative of how many references will be made to the spin state data structure at a future time, whereby it can be determined when the spin state data structure is to be deallocated.

25. The computer-readable medium of claim 24 wherein the spin state data structure further comprises:

an interrupted-spinners field indicative of how many unfulfilled lock requests using the spin state data structure have been interrupted, wherein the interrupted-spinners field is equal to the future references field minus the number-of-spinners field minus one.

26. A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure comprising:

a local structure for each node, the local structure comprising;

a processing unit bit mask field comprising one bit per processing unit at the local structure'"'"'s node, wherein each bit is set to indicate processing units acquiring the lock and nodes having processing units holding the lock;

a spin state field indicating the number of consecutive times the local structure'"'"'s node has held the lock if the lock is being held by a processing unit at the local structure'"'"'s node, and indicating a maximum number of consecutive times if the lock is held by none of the processing units at the local structure'"'"'s node, whereby at least one processing unit at the local structure'"'"'s node can spin on the spin state field in order to acquire the lock;

a previous spin state field indicating the value of the spin state field immediately before a processing unit at the local structure'"'"'s node having the lock acquired the lock; and

a pointer to a global structure shared by the nodes; and

the global structure shared by the nodes, the global structure comprising;

a latch value for indicating whether the lock is available;

a field indicating whether the lock was conditionally acquired;

a node bit mask field with one bit per node, wherein each bit is set to indicate nodes acquiring the lock and processing units holding the lock; and

an array of pointers comprising a pointer for each node, the pointer pointing to the local structure for each node.

27. The computer-readable medium of claim 26 wherein the latch value is a lock available field for a simple spin lock encapsulated within the global structure to provide backwards compatibility.

28. The computer-readable medium of claim 26 wherein the local structure is stored in a location available locally to the local structure'"'"'s node and remotely accessible to other nodes.

29. A computer-readable medium having stored thereon a data structure for tracking requests for a lock in a computer having a number of interconnected nodes each having at least one processing unit, the data structure associated with one of the nodes and able to be enqueued into an ordered list, the data structure comprising:

a number-of-spinners bitfield indicative of how many processing units are actively spinning on the data structure;

a number-of-uses bitfield indicative of how many times processing units have acquired a position in the ordered list with the data structure;

a lock available field indicative of when the lock is available to one of the processing units actively spinning on the data structure;

a number-of-references bitfield indicative of how many processing units require future access to the data structure; and

a plurality of guard fields arranged within the data structure to guard underflows of at least two of the bitfields during atomic operations on the bitfields and the lock available field.

30. The computer-readable medium of claim 29 wherein the guard fields are positioned at locations adjacent to and more significant than the bitfields they guard.

31. The computer-readable medium of claim 30 further comprising:

an interrupted-spinners bitfield indicative of how many processing units have been interrupted while spinning on the data structure.

32. The computer-readable medium of claim 31 wherein the number-of-spinners bitfield is at a position more significant than the other bitfields in the data structure and a number-of-spinners underflow field is positioned adjacent to the number-of-spinners bitfield and at a most significant location in the data structure.