Hierarchical queue-based locks

• US 7,945,912 B1
• Filed: 06/02/2006
• Issued: 05/17/2011
• Est. Priority Date: 06/02/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Luchangco, Victor M., Nussbaum, Daniel S., Shavit, Nir N.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): KUMABE, BLAKE K
• Application Number:
  US11/445,962
• Time in Patent Office: 1,810 Days
• Field of Search: 718/107, 718/104
• US Class Current: 718/104
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In general, in one aspect, the invention relates to a method of establishing a queue-based lock including inserting a first qnode into a local queue, where the first qnode is associated with a first thread, splicing the local queue into the global queue, obtaining a lock for the first thread when the first qnode is at the head of the global queue, and executing a critical section of the first thread after obtaining the lock.

Claims

1. A method of managing queue-based locks, comprising:

obtaining, within a first cluster of a system, a first thread comprising a critical section requiring a lock to access a shared resource of the system;

initializing, by the first thread executing on a processor in the first cluster, a first qnode representing the first thread in response to the critical section requiring the lock, wherein the first qnode is a data structure referenced by a first pointer of the first thread;

inserting, by the first thread and in response to the critical section requiring the lock, the first qnode into a local queue of the first cluster by setting a tail pointer of the local queue to reference the first qnode, wherein the first thread comprises a second pointer referencing a predecessor qnode of the first qnode;

determining, by the first thread and based on a first qnode in the predecessor qnode, the first qnode is at a head of the local queue;

splicing, by the first thread and in response to the first field being at the head of the local queue, the local queue into a global queue of the system for the shared resource,

wherein splicing the local queue into the global queue comprises setting a tail pointer of the global queue to reference a tail qnode in the local queue;

determining, by the first thread and based on a second field in the predecessor qnode, the first qnode is at a head of the global qnode;

obtaining, by the first thread and in response to the first qnode being at the head of the global queue, the lock for the shared resource; and

executing the critical section of the first thread after obtaining the lock.

2. The method of claim 1, wherein setting the tail pointer of the local queue to reference the first qnode comprises using a compare-and-swap (CAS) operation.

3. The method of claim 1, further comprising:

initiating a combination delay after determining the first qnode is at the head of the local queue,

wherein splicing the local queue into the global queue occurs following the combining delay.

4. The method of claim 1, further comprising:

setting, after executing the critical section of the first thread, the first pointer of the first thread to reference the predecessor qnode.

5. The method of claim 1, further comprising:

inserting a second qnode into the local queue after inserting the first qnode into the local queue,

wherein the second qnode is a data structure representing a second thread,

wherein the first qnode and the second qnode corresponds to a first-in-first-out (FIFO) order in the local queue, and

wherein the FIFO order of the first qnode and the second qnode is preserved after splicing the local queue and the global queue.

6. The method of claim 5, further comprising:

releasing the lock following the execution of the critical section of the first thread by setting a field in the first qnode;

determining, by the second thread and based on the field in the first qnode, the second qnode is at the head of the global qnode;

obtaining, by the second thread and in response to the second qnode being at the head of the global queue, the lock for the shared resource; and

executing a critical section of the second thread after obtaining the lock.

7. The method of claim 1, wherein determining the first qnode is at the head of the local queue comprises:

comparing a value in the first field of the predecessor qnode with an identification of the first cluster stored in the first qnode; and

identifying the value and the identification are not equal,

wherein the predecessor node represents a second thread executing on a second processor in a second cluster of the system, and

wherein the first field of the predecessor qnode comprises an identification of the second cluster.

8. The method of claim 1, wherein the first field of the predecessor qnode is a flag indicating the predecessor node is a tail qnode of the global queue.

9. The method of claim 1, wherein the second field of the predecessor qnode is a flag indicating the predecessor node has released the lock.

10. A system for managing queue-based locks, comprising:

a shared resource;

a first processor located in a first cluster of the system and configured to execute a first thread comprising a first critical section requiring a lock to access the shared resource;

a second processor located in a second cluster of the system and configured to execute a second thread comprising a second critical section requiring the lock to access the shared resource;

a first local queue located in the first cluster and configured to enqueue a first qnode representing the first thread, wherein the first qnode is a data structure referenced by a first pointer of the first thread;

a second local queue located in the second cluster and configured to enqueue a second qnode representing the second thread; and

a global queue corresponding to the shared resource and configured to enqueue the first qnode after the first local queue is spliced with the global queue and enqueue the second qnode after the second local queue is spliced with the global queue,

wherein the first thread obtains the lock and executes the first critical section after the first qnode is identified by the first thread as a head of the global queue, and

wherein the second thread obtains the lock and executes the second critical section after the second qnode is identified by the second thread as the head of the global queue.

11. The system of claim 10, wherein the first qnode comprises:

a first field identifying the first cluster;

a second field configured to indicate the first qnode is a tail qnode of the global cluster; and

a third field configured to indicate execution of the first critical section is complete and the lock is released.

12. The system of claim 10, further comprising:

a predecessor qnode of the first qnode,

wherein the first thread further comprises a second pointer referencing the predecessor qnode,

wherein the local thread is spliced with the global thread in response to the first qnode being at a head of the first local queue, and

wherein the first thread determines the first qnode is at the head of the first local queue based on a first value in the predecessor qnode.

13. The system of claim 12, wherein the first thread further determines the first qnode is at the head of the global thread based on a second value in the predecessor qnode.

14. A computer readable medium storing instructions for managing queue-based locks, the instructions when executed by a processor, comprising functionality to:

identify, within a first cluster of a system, a first thread comprising a critical section requiring a lock to access a shared resource of the system;

initialize a first qnode representing the first thread in response to the critical section requiring the lock, wherein the first qnode is a data structure referenced by a first pointer of the first thread;

insert, in response to the critical section requiring the lock, the first qnode into a local queue of the first cluster by setting a tail pointer of the local queue to reference the first qnode, wherein the first thread comprises a second pointer referencing a predecessor qnode of the first qnode;

determine, based on a first field in the predecessor qnode, the first qnode is at a head of the local queue;

splice, in response to the first qnode being at the head of the local queue, the local queue into a global queue of the system for the shared resource,

wherein splicing the local queue into the global queue comprises setting a tail pointer of the global queue to reference a tail qnode in the local queue;

determine, based on a second field in the predecessor qnode, the first qnode is at a head of the global qnode;

obtain, in response to the first qnode being at the head of the global queue, the lock on the shared resource for the first thread; and

execute the critical section of the first thread after obtaining the lock.

15. The computer readable medium of claim 14, the instructions further comprising functionality to:

set, after executing the critical section of the first thread, the first pointer of the first thread to reference the predecessor qnode.

16. The computer readable medium of claim 14, the instructions further comprising functionality to:

insert a second qnode into the local queue after inserting the first qnode into the local queue,

wherein the second qnode is a data structure representing a second thread,

wherein the first qnode and the second qnode corresponds to a first-in-first-out (FIFO) order in the local queue, and

wherein the FIFO order of the first qnode and the second qnode is preserved after splicing the local queue and the global queue.

17. The computer readable medium of claim 16, the instructions further comprising functionality to:

release the lock following the execution of the critical section of the first thread by setting a field in the first qnode;

determine, based on the field in the first qnode, the second qnode is at the head of the global qnode;

obtain, in response to the second qnode being at the head of the global queue, the lock for the shared resource; and

execute a critical section of the second thread after obtaining the lock.

18. The computer readable medium of claim 14, wherein the instructions comprising functionality to determine the first qnode is at the head of the local queue comprise functionality to:

compare a value in the first field of the predecessor qnode with an identification of the first cluster stored in the first qnode; and

identify the value and the identification are not equal,

wherein the predecessor node represents a second thread executing on a second processor in a second cluster of the system, and

wherein the first field of the predecessor qnode comprises an identification of the second cluster.

19. The computer readable medium of claim 14, wherein the first field of the predecessor qnode is a flag indicating the predecessor node is a tail qnode of the global queue.