Composite abortable locks

• US 7,984,444 B1
• Filed: 09/15/2005
• Issued: 07/19/2011
• Est. Priority Date: 09/15/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Marathe, Virendra J., Moir, Mark S., Shavit, Nir N.
• Primary Examiner(s): To; Jennifer N
• Application Number:
  US11/226,949
• Time in Patent Office: 2,133 Days
• Field of Search: 707/8, 711/145, 711/150, 711/151, 711/152, 711/155, 718/100
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A lock implementation has properties of both backoff locks and queue locks. Such a “composite” lock is abortable and is provided with a constant number of preallocated nodes. A thread requesting the lock selects one of the nodes, attempts to acquire the selected node, and, if successful, inserts the selected node in a wait-queue for the lock. Because there is only a constant number of nodes for the wait-queue, all requesting threads may not be queued. Requesting threads unable to successfully acquire a selected node may backoff and retry selecting and acquiring a node. A node at the front of the wait-queue holds the lock.

Claims

1. A method for acquiring a lock associated with a shared resource, comprising:

selecting, by a thread, a first node from a plurality of nodes preallocated for the lock, wherein the lock is configured to protect the shared resource such that the thread is required to acquire the lock prior to being able to access the shared resource, and wherein the plurality of nodes is constant and independent of a number of threads requesting the lock;

making a first node acquisition attempt, by the thread, to acquire the first node;

making a first node insertion attempt, by the thread, to insert the first node into a wait queue associated with the lock, upon success of the first node acquisition attempt;

acquiring the lock, by the thread, based on a position of the first node in the wait queue, upon success of the first node insertion attempt;

determining, by the thread, whether a first time period specified for the thread to acquire the lock has elapsed, upon failure of the first node acquisition attempt;

when the first time period has elapsed;

aborting, by the thread, any further attempts to acquire one of the plurality of nodes for the lock;

when the first time period has not elapsed;

waiting, by the thread, for a second time period;

when the first time period has not elapsed and the second time period has elapsed;

selecting, by the thread, a second node from the plurality of nodes for the lock; and

making, by the thread, a second node acquisition attempt to acquire the second node.

2. The method of claim 1, wherein the first node acquisition attempt comprises:

performing an atomic operation, by the thread, on the first node.

3. The method of claim 1, wherein the shared resource comprises at least one memory location.

4. The method of claim 1, further comprising:

releasing the lock by the thread; and

freeing the first node by the thread, wherein upon the releasing the first node is available for selecting and acquiring by another thread.

5. The method of claim 1, wherein the first node acquisition attempt comprises:

determining, by the thread, whether the first node is a last node in the wait queue for the lock and has one of an aborted state and a released state; and

acquiring the first node by the thread dependent on the determining.

6. The method of claim 1, further comprising:

determining, by the thread, whether the first time period specified for the thread to acquire the lock has elapsed, upon failure of the second node acquisition attempt;

when the first time period has not elapsed;

waiting, by the thread, for a third time period, wherein the third time period is greater than the second time period;

when the first time period has not elapsed and the third time period has elapsed;

selecting, by the thread, a third node from the plurality of nodes for the lock; and

making, by the thread, a third node acquisition attempt to acquire the third node.

7. The method of claim 1, further comprising:

determining, by the thread, whether a first time period specified for the thread to acquire the lock has elapsed, upon failure of the first node insertion attempt;

when the first time period has elapsed;

aborting, by the thread, any further attempt to insert the first node into the wait queue; and

when the first time period has not elapsed;

making a second attempt, by the thread, to insert the first node into the wait queue.

8. A system for providing concurrent access to a shared resource in a multi-threaded execution environment, comprising:

processor for executing instructions stored on a computer readable storage medium;

the shared resource; and

the computer readable storage medium, comprising;

instructions for implementing a lock to protect the shared resource such that each one of a plurality of threads executing in the multi-threaded execution environment is required to acquire the lock prior to accessing the shared resource, comprising functionality to;

allocate a plurality of nodes for the lock, wherein the plurality of nodes is constant and independent of the plurality of threads requesting the lock, and

instantiate a wait queue for the lock;

instructions for implementing each one of the plurality of threads, comprising functionality to;

select a first node from the plurality of nodes for the lock;

make a first node acquisition attempt to acquire the first node;

make a first node insertion attempt to insert the first node into the wait queue, upon success of the first node acquisition attempt;

acquire the lock based on a position of the first node in the wait queue, upon success of the first node insertion attempt;

determine whether a first time period specified for each one of the plurality of threads to acquire the lock has elapsed, upon failure of the first node acquisition attempt;

when the first time period has elapsed;

abort any further attempts to acquire one of the plurality of nodes for the lock

when the first time period has not elapsed;

wait for a second time period;

when the first time period has not elapsed and the second time period has elapsed;

select a second node from the plurality of nodes for the lock; and

make a second node acquisition attempt to acquire the second node.

9. The system of claim 8, wherein the instructions for implementing each one of the plurality of threads further comprise functionality to:

determine whether the first time period specified for each one of the plurality of threads to acquire the lock has elapsed, upon failure of the second node acquisition attempt;

when the first time period has not elapsed;

wait for a third time period, wherein the third time period is greater than the second time period;

when the first time period has not elapsed and the third time period has elapsed;

select a third node from the plurality of nodes for the lock; and

make a third node acquisition attempt to acquire the third node.

10. The system of claim 8, wherein the instructions for implementing each one of the plurality of threads further comprise functionality to:

release the lock;

free the first node, wherein upon the releasing of the lock the first node is eligible for acquisition by one of the plurality of threads.

11. The system of claim 8, wherein the instructions for implementing each one of the plurality of threads further comprise functionality to:

determine whether the first time period specified for each one of the plurality of threads to acquire the lock has elapsed, upon failure of the first node insertion attempt;

when the first time period has elapsed;

abort any further node insertion attempts;

free the first node; and

when the first time period has not elapsed;

make a second node insertion attempt to insert the first node into the wait queue.

12. A non-transitory computer readable storage medium comprising instructions for acquiring a lock associated with a shared resource, the instructions comprising functionality to:

select a first node from a plurality of preallocated nodes for the lock, wherein the lock is configured to protect the shared resource such that acquisition of the lock is required prior to being able to access the shared resource, and wherein the plurality of preallocated nodes is constant and independent of a plurality of threads requesting the lock;

make a first node acquisition attempt to acquire the first node;

make a first node insertion attempt to insert the first node into a wait queue associated with the lock, upon success of the first node acquisition attempt;

acquire the lock based on a position of the first node in the wait queue, upon success of the first node insertion attempt;

determine whether a first time period specified to acquire the lock has elapsed, upon failure of the first node acquisition attempt;

when the first time period has elapsed;

abort any further attempts to acquire one of the plurality of preallocated nodes for the lock

when the first time period has not elapsed;

wait for a second time period;

when the first time period has not elapsed and the second time period has elapsed;

select a second node from the plurality of preallocated nodes for the lock; and

make a second node acquisition attempt to acquire the second node.

13. The non-transitory computer readable storage medium of claim 12, the instructions further comprising functionality to:

determine whether the first time period specified to acquire the lock has elapsed, upon failure of the second node acquisition attempt;

when the first time period has not elapsed;

wait for a third time period, wherein the third time period is greater than the second time period;

when the first time period has not elapsed and the third time period has elapsed;

select a third node from the plurality of nodes preallocated for the lock; and

make a third node acquisition attempt to acquire the third node.

14. The non-transitory computer readable storage medium of claim 12, the instructions further comprising functionality to:

release the lock; and

free the first node, wherein, upon the releasing of the lock, the first node is eligible for acquisition by one of the plurality of threads.

15. The non-transitory computer readable storage medium of claim 12, the instructions further comprising functionality to:

determine whether a first time period specified to acquire the lock has elapsed, upon failure of the first node insertion attempt;

when the first time period has elapsed;

abort any further node insertion attempts;

free the first node; and

when the first time period has not elapsed;

make a second node insertion attempt to insert the first node into the wait queue.