Queue-based spin lock with timeout

• US 6,965,961 B1
• Filed: 03/03/2003
• Issued: 11/15/2005
• Est. Priority Date: 03/01/2002
• Status: Expired due to Fees

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Scott, Michael L.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): DINH, NGOC V
• Application Number:
  US10/377,024
• Time in Patent Office: 988 Days
• Field of Search: 710/39, 710/40, 710/45, 710/54, 710/200, 710/263, 718/102, 718/108
• US Class Current: 710/310
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A queue-based spin lock with timeout allows a thread to obtain contention-free mutual exclusion in fair, FIFO order, or to abandon its attempt and time out. A thread may handshake with other threads to reclaim its queue node immediately (in the absence of preemption), or mark its queue node to allow reclamation by a successor thread.

Claims

1. A method of implementing a queue-based spin lock with timeout in a computing device running a plurality of threads, the method comprising:

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer,

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue; and

(c) when a thread times out and abandons its attempt to acquire the lock, removing the node corresponding to the timed-out thread from the linked list, so that the nodes of the predecessor and the successor of the timed-out thread out become neighbors in the queue.

2. The method of claim 1, wherein each of the plurality of threads spins on its predecessor'"'"'s node.

3. The method of claim 2, wherein a thread that times out reclaims its own node, handshaking with neighbors in the queue to resolve any race conditions.

4. The method of claim 3, wherein the thread that times out performs the following:

(a) waits until its predecessor'"'"'s node is not marked;

(b) marks its predecessor'"'"'s node to prevent the predecessor from timing out concurrently;

(c) waits until its own node is not marked, then marks its own node;

(d) attempts to swing the tail pointer from its own node to its predecessor'"'"'s node;

(e) if step (d) is unsuccessful, waits until its successor marks the node of the timed-out thread to indicate that the successor has updated the successor'"'"'s predecessor pointer; and

(f) reclaims its node and returns.

5. The method of claim 2, wherein a thread that times out marks its node as abandoned, and the successor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

6. The method of claim 1, wherein each thread spins on its own queue node.

7. The method of claim 6, wherein a thread that times out reclaims its own queue node, handshaking with neighbors in the queue to resolve any race conditions, and giving priority for forward progress, where possible, to the thread closer to the head of the queue.

8. The method of claim 7, wherein the thread that times out performs the following:

(a) replaces the pointer from its node to the node of its successor, if any, with a special marker;

(b) replaces the pointer to its node from the node of its successor, if any, with a special marker;

(c) replaces the pointer from its node to the node of its predecessor with a special marker;

(d) replaces the pointer to its node from the node of its predecessor with a special marker;

(e) replaces (i) the marker in the successor'"'"'s queue node, if there is a successor, or (ii) the tail pointer of the list, if there is not a successor, with a pointer to the predecessor'"'"'s queue node;

(f) if the successor exists, waits for the successor to replace the marker in the predecessor'"'"'s queue node with a pointer to the successor'"'"'s queue node;

(g) if the successor does not exist, replaces the marker in the predecessor'"'"'s queue node with a nil pointer; and

(h) reclaims its node and returns.

9. The method of claim 6, wherein the thread that times out marks its queue node as abandoned, and the successor or predecessor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

10. The method of claim 9, wherein the thread that times out performs the following:

(a) replaces with nil the pointer to its queue node found in its predecessor'"'"'s queue node;

(b) marks its own queue node;

(c) marks the queue node of its successor, if any; and

(d) returns;

the successor updates the successor pointer in the queue node of the predecessor of the timed-out thread, and then reclaims the queue node of the timed-out thread; and

if the timed-out thread is unable to replace the successor pointer in its predecessor'"'"'s queue node due to a race condition,

(e) the timed-out thread informs its successor, if any, of the continued existence of the predecessor'"'"'s pointer;

(f) the successor uses a swap operation to mark the node of the timed-out thread when the successor has removed the node of the timed-out thread from the queue;

(g) the predecessor uses swap operations whenever it needs to mark the node of the timed-out thread; and

(h) both predecessor and successor threads reclaim the node of the timed-out thread if the result of the swap operation in (f) or (g) indicates that the other thread (successor or predecessor, respectively) has already completed its operation, and will not access the node again.

11. A method of implementing a queue-based spin lock with timeout in a computing device running a plurality of threads, the method comprising:

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer;

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue;

(c) causing each thread to spin on a queue node allocated by its predecessor; and

(d) indicating an unheld lock by a queue containing only one node, marked available, or by a queue containing zero nodes

(e) causing a thread that releases the lock (by marking its queue node available), or that times out and marks its queue node abandoned, to perform a compare-and-swap operation on the queue tail pointer in an attempt to remove its node from the queue.

12. An article of manufacture for implementing a queue-based spin lock with timeout in a computing device running a plurality of threads, the article of manufacture comprising:

a storage medium readable by the computing device; and

code, stored on the storage medium, for controlling the computing device to perform the following operational steps;

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer,

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue; and

(c) when a thread times out and abandons its attempt to acquire the lock, removing the node corresponding to the timed-out thread from the linked list, so that the nodes of the predecessor and the successor of the timed-out thread out become neighbors in the queue.

13. The article of manufacture of claim 12, wherein each of the plurality of threads spins on its predecessor'"'"'s node.

14. The article of manufacture of claim 13, wherein a thread that times out reclaims its own node, handshaking with neighbors in the queue to resolve any race conditions.

15. The article of manufacture of claim 14, wherein the thread that times out performs the following:

(a) waits until its predecessor'"'"'s node is not marked;

(b) marks its predecessor'"'"'s node to prevent the predecessor from timing out concurrently;

(c) waits until its own node is not marked, then marks its own node;

(d) attempts to swing the tail pointer from its own node to its predecessor'"'"'s node;

(e) if step (d) is unsuccessful, waits until its successor marks the node of the timed-out thread to indicate that the successor has updated the successor'"'"'s predecessor pointer; and

(f) reclaims its node and returns.

16. The article of manufacture of claim 13, wherein a thread that times out marks its node as abandoned, and the successor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

17. The article of manufacture of claim 12, wherein each thread spins on its own queue node.

18. The article of manufacture of claim 17, wherein a thread that times out reclaims its own queue node, handshaking with neighbors in the queue to resolve any race conditions, and giving priority for forward progress, where possible, to the thread closer to the head of the queue.

19. The article of manufacture of claim 18, wherein the thread that times out performs the following:

(a) replaces the pointer from its node to the node of its successor, if any, with a special marker;

(b) replaces the pointer to its node from the node of its successor, if any, with a special marker;

(c) replaces the pointer from its node to the node of its predecessor with a special marker;

(d) replaces the pointer to its node from the node of its predecessor with a special marker;

(e) replaces (i) the marker in the successor'"'"'s queue node, if there is a successor, or (ii) the tail pointer of the list, if there is not a successor, with a pointer to the predecessor'"'"'s queue node;

(f) if the successor exists, waits for the successor to replace the marker in the predecessor'"'"'s queue node with a pointer to the successor'"'"'s queue node;

(g) if the successor does not exist, replaces the marker in the predecessor'"'"'s queue node with a nil pointer; and

(h) reclaims its node and returns.

20. The article of manufacture of claim 17, wherein the thread that times out marks its queue node as abandoned, and the successor or predecessor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

21. The article of manufacture of claim 20, wherein the thread that times out performs the following:

(a) replaces with nil the pointer to its queue node found in its predecessor'"'"'s queue node;

(b) marks its own queue node;

(c) marks the queue node of its successor, if any; and

(d) returns;

the successor updates the successor pointer in the queue node of the predecessor of the timed-out thread, and then reclaims the queue node of the timed-out thread; and

if the timed-out thread is unable to replace the successor pointer in its predecessor'"'"'s queue node due to a race condition,

(e) the timed-out thread informs its successor, if any, of the continued existence of the predecessor'"'"'s pointer;

(f) the successor uses a swap operation to mark the node of the timed-out thread when the successor has removed the node of the timed-out thread from the queue;

(g) the predecessor uses swap operations whenever it needs to mark the node of the timed-out thread; and

(h) both predecessor and successor threads reclaim the node of the timed-out thread if the result of the swap operation in (f) or (g) indicates that the other thread (successor or predecessor, respectively) has already completed its operation, and will not access the node again.

22. An article of manufacture for implementing a queue-based spin lock with timeout in a computing device running a plurality of threads, the article of manufacture comprising:

a storage medium readable by the computing device; and

code, stored on the storage device, for controlling the computing device to perform the following operational steps;

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer;

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue;

(c) causing each thread to spin on a queue node allocated by its predecessor; and

(d) indicating an unheld lock by a queue containing only one node, marked available, or by a queue containing zero nodes

(e) causing a thread that releases the lock (by marking its queue node available), or that times out and marks its queue node abandoned, to perform a compare-and-swap operation on the queue tail pointer in an attempt to remove its node from the queue.

23. A computing device for implementing a queue-based spin lock with timeout while running a plurality of threads, the computing device comprising:

a memory; and

a plurality of processors, in communication with the memory, for running the plurality of threads and for performing the following operational steps;

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer,

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue; and

(c) when a thread times out and abandons its attempt to acquire the lock, removing the node corresponding to the timed-out thread from the linked list, so that the nodes of the predecessor and the successor of the timed-out thread out become neighbors in the queue.

24. The computing device of claim 23, wherein each of the plurality of threads spins on its predecessor'"'"'s node.

25. The computing device of claim 24, wherein a thread that times out reclaims its own node, handshaking with neighbors in the queue to resolve any race conditions.

26. The computing device of claim 25, wherein the thread that times out performs the following:

(a) waits until its predecessor'"'"'s node is not marked;

(b) marks its predecessor'"'"'s node to prevent the predecessor from timing out concurrently;

(c) waits until its own node is not marked, then marks its own node;

(d) attempts to swing the tail pointer from its own node to its predecessor'"'"'s node;

(e) if step (d) is unsuccessful, waits until its successor marks the node of the timed-out thread to indicate that the successor has updated the successor'"'"'s predecessor pointer; and

(f) reclaims its node and returns.

27. The computing device of claim 24, wherein a thread that times out marks its node as abandoned, and the successor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

28. The computing device of claim 23, wherein each thread spins on its own queue node.

29. The computing device of claim 28, wherein a thread that times out reclaims its own queue node, handshaking with neighbors in the queue to resolve any race conditions, and giving priority for forward progress, where possible, to the thread closer to the head of the queue.

30. The computing device of claim 29, wherein the thread that times out performs the following:

(a) replaces the pointer from its node to the node of its successor, if any, with a special marker;

(b) replaces the pointer to its node from the node of its successor, if any, with a special marker;

(c) replaces the pointer from its node to the node of its predecessor with a special marker;

(d) replaces the pointer to its node from the node of its predecessor with a special marker;

(e) replaces (i) the marker in the successor'"'"'s queue node, if there is a successor, or (ii) the tail pointer of the list, if there is not a successor, with a pointer to the predecessor'"'"'s queue node;

(f) if the successor exists, waits for the successor to replace the marker in the predecessor'"'"'s queue node with a pointer to the successor'"'"'s queue node;

(g) if the successor does not exist, replaces the marker in the predecessor'"'"'s queue node with a nil pointer; and

(h) reclaims its node and returns.

31. The computing device of claim 28, wherein the thread that times out marks its queue node as abandoned, and the successor or predecessor reclaims that node, allowing the timed-out thread to complete its operation within a bounded number of its own time steps.

32. The computing device of claim 31, wherein the thread that times out performs the following:

(a) replaces with nil the pointer to its queue node found in its predecessor'"'"'s queue node;

(b) marks its own queue node;

(c) marks the queue node of its successor, if any; and

(d) returns;

the successor updates the successor pointer in the queue node of the predecessor of the timed-out thread, and then reclaims the queue node of the timed-out thread; and

if the timed-out thread is unable to replace the successor pointer in its predecessor'"'"'s queue node due to a race condition,

(e) the timed-out thread informs its successor, if any, of the continued existence of the predecessor'"'"'s pointer;

(f) the successor uses a swap operation to mark the node of the timed-out thread when the successor has removed the node of the timed-out thread from the queue;

(g) the predecessor uses swap operations whenever it needs to mark the node of the timed-out thread; and

(h) both predecessor and successor threads reclaim the node of the timed-out thread if the result of the swap operation in (f) or (g) indicates that the other thread (successor or predecessor, respectively) has already completed its operation, and will not access the node again.

33. A computing device for implementing a queue-based spin lock with timeout while running a plurality of threads, the computing device comprising:

a memory; and

a plurality of processors, in communication with the memory, for running the plurality of threads and for performing the following operational steps;

(a) providing a queue as a linked list of nodes, the nodes in the linked list representing threads waiting for the lock, the list being accessed through a tail pointer;

(b) permitting a thread to acquire the lock when the thread reaches the head of the queue;

(c) causing each thread to spin on a queue node allocated by its predecessor; and

(d) indicating an unheld lock by a queue containing only one node, marked available, or by a queue containing zero nodes

(e) causing a thread that releases the lock (by marking its queue node available), or that times out and marks its queue node abandoned, to perform a compare-and-swap operation on the queue tail pointer in an attempt to remove its node from the queue.