Low-contention lock

• US 7,500,242 B2
• Filed: 09/08/2003
• Issued: 03/03/2009
• Est. Priority Date: 09/08/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Haab, Grant E., Petersen, Paul M., Shah, Sanjiv M.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): WU, QING YUAN
• Application Number:
  US10/658,626
• Publication Number:
  US 20050055593A1
• Time in Patent Office: 2,003 Days
• Field of Search: 713/200, 718/105, 718/104, 707/8, 710/200, 710/240, 711150-151, 709/225
• US Class Current: 718/104
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The present disclosure relates to acquiring and releasing a shared resource via a lock semaphore and, more particularly, to acquiring and releasing a shared resource via a lock semaphore utilizing a state machine.

Claims

1. A method of managing a lock utilized by a plurality of threads executing on a computing device to coordinate access to a shared resource, the method comprising:

selecting by one of the threads, an action to be performed by the thread upon the lock, wherein the action is selected from a group comprising;

acquiring the lock,

trying to acquire the lock, and

releasing the lock;

asynchronously querying and receiving a first state of the lock as a current state of the lock by the thread, the lock being considered to be in any one of at least four states in any point in time, the states defined by a state machine associated with the lock;

speculatively determining by the thread, a second state of the lock based at least in part on the first state and the selected action; and

attempting to perform by the thread, the selected action to transition the lock from the first state to the speculatively determined second state, the attempting including determining if the first state remains the current state of the lock, and, if the first state remains the current state, performing the selected action to transition the current state of the lock to the second state.

2. The method of claim 1, further including, if the state transition fails and if the selected action was either acquiring or releasing the lock, repeating, until the state transition succeeds:

asynchronously querying the first state of the lock;

speculatively determining the second state of the lock;

attempting to transition the lock from the queried first state to the speculatively determined second state.

3. The method of claim 2, further including, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state represents the acquisition of the lock, indicating the acquisition of the lock.

4. The method of claim 3, further including, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state does not represent the acquisition of the lock, adding the thread to the end of a queue of threads waiting to acquire the lock;

waiting to receive notification that the thread may acquire the lock; and

indicating the acquisition of the lock.

5. The method of claim 2, further including, if

the state transition succeeds, and

the selected action is releasing the lock, determining the number of threads in a queue to acquire the lock utilizing the speculatively determined second state of the lock.

6. The method of claim 5, further including, if the queue includes at least a first thread,

removing the first thread from the queue;

and

notifying the first thread that the first thread has acquired the lock.

7. The method of claim 1, further including, if

the selected action is trying to acquire the lock and

the state transition fails, indicating that the lock was unable to be acquired.

8. The method of claim 1, further including, if

the state transition succeeds and

the selected action is trying to acquire the lock, indicating the acquisition of the lock.

9. The method of claim 1, further including, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state represents the acquisition of the lock, indicating the acquisition of the lock.

10. The method of claim 9, further including, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state does not represent the acquisition of the lock, adding the thread to the end of a queue of threads waiting to acquire the lock;

waiting to receive notification that the thread may acquire the lock; and

indicating the acquisition of the lock.

11. The method of claim 1, further including, if

the state transition succeeds, and

the selected action is releasing the lock, determining the number of threads in a queue to acquire the lock utilizing the speculatively determined second state of the lock.

12. The method of claim 11, further including, if the queue includes at least a first thread,

removing the first thread from the queue;

and

notifying the first thread that the first thread has acquired the lock.

13. The method of claim 1, wherein the thread includes:

a unique thread identifier;

a next thread field to facilitate access to the next thread in a queue of threads waiting to acquire the lock; and

the thread is only capable of waiting for a single lock at a time.

14. The method of claim 1, wherein the action of acquiring the lock includes the inability to timeout or fail to acquire the lock.

15. The method of claim 1, wherein the lock'"'"'s current state may change between

asynchronously querying the first state of the lock;

and

attempting to transition the lock from the queried first state to the speculatively determined second state.

16. The method of claim 1, wherein each of the first and second states is a selected one of:

the lock is not held and there no threads waiting to access the shared resource,

the lock is held and there are no threads waiting to access the shared resource,

the lock is held and there is one thread waiting to access the shared resource, and the lock is held and there are at least two threads waiting to access the shared resource.

17. An apparatus comprising:

a processor;

a storage medium coupled to the processor, and having stored therein programming instructions to be operated by the processor to implement a lock acquirer to acquire a lock, having a multi-part state value defined by a state machine associated with the lock;

wherein the lock acquirer performs an acquisition of the lock via

asynchronously querying and receiving a first state of the lock as a current state of the lock, by the lock acquirer, the lock being considered to be in any one of at least four states in any point in time, and each state is represented by the multi-part state value;

speculatively determining by the lock acquirer, a second state of the lock based at least in part on the first state of the lock; and

attempting to perform, by the lock acquirer, the acquisition of the lock to transition the lock from the first state to the speculatively determined second state, the attempting including determining if the first state remains the current state of the lock, and, if the first state remains the current state, performing the acquisition to transition the current state of the lock to the second state.

18. The apparatus of claim 17, wherein the lock acquirer is further capable of performing two general actions, including acquiring the lock, trying to acquire the lock;

and

wherein, if the state transition fails and the general action is acquiring the lock, the lock acquirer is further capable of, repeating, until the state transaction succeeds;

asynchronously querying the first state of the lock;

speculatively determining the second state of the lock; and

attempting to transition the lock from the queried first state to the speculatively determined second state.

19. The apparatus of claim 18, wherein, if the state transition fails and the general action is trying to acquire the lock, the lock acquirer is further capable of,

indicating that the lock was unable to be acquired.

20. The apparatus of claim 19, wherein, if the state transition succeeds and the general action is trying to acquire the lock, the lock acquirer is further capable of,

indicating that the lock was acquired.

21. The apparatus of claim 18, wherein, if

the state transition succeeds,

the general action is acquire the lock, and

the speculatively determined second state represents the acquisition of the lock, the lock acquirer is further capable of,

indicating that the lock was acquired.

22. The apparatus of claim 21, wherein, if

the state transition fails,

the general action is acquire the lock, and

the speculatively determined second state does not represent the acquisition of the lock, the lock acquirer is further capable of,

adding the thread to the end of a queue of threads waiting to acquire the lock;

waiting to receive notification that the thread may acquire the lock; and

indicating the acquisition of the lock.

23. The apparatus of claim 22, wherein the lock acquirer is unable to timeout of fail if the selected general action is acquiring the lock.

24. An apparatus comprising:

a processor;

a storage medium coupled to the processor, and having stored therein programming instructions to be operated by the processor to implement a lock releaser to release a lock, the lock having a multi-part state value defined by a state machine associated with the lock;

wherein the lock releaser, release said hold on the lock via

asynchronously querying and receiving a first state of the lock as a current state of the lock, by the lock releaser, the lock being considered to be in any one of at least four states in any point in time, and each state is represented by the multi-part state value;

speculatively determining by the lock releaser, a second state of the lock based at least in part on the first state of the lock; and

attempting to perform, by the lock releaser, the releasing of the lock to transition the lock from the first state to the speculatively determined second state, the attempting including determining if the first state remains the current state of the lock, and, if the first state remains the current state, performing the releasing to transition the current state of the lock to the second state.

25. The apparatus of claim 24, wherein, if the state transition fails, the lock releaser is further capable of, repeating, until the state transaction succeeds:

asynchronously querying the first state of the lock;

speculatively determining the second state of the lock; and

attempting to transition the lock from the queried first state to the speculatively determined second state.

26. The apparatus of claim 24, wherein, if the state transition succeeds, the lock releaser is further capable of determining the number of threads in a queue of threads waiting to acquire the lock utilizing the speculatively determined second state of the lock.

27. The apparatus of claim 26, wherein, if the queue includes at least a first thread, the lock releaser is further capable of:

removing the first thread from the queue; and

notifying the first thread that the first thread has acquired the lock.

28. The apparatus of claim 27, wherein the lock releaser is capable of removing the first thread from the queue utilizing a thread having:

a unique thread identifier; and

a next thread value to facilitate access to the next thread in the queue.

29. The apparatus of claim 24, wherein the lock is capable of changing state in between the time the lock releaser

asynchronously queries the first state of the lock;

and

attempts to transition the lock from the queried first state to the speculatively determined second state.

30. An article comprising:

a storage medium; and

a plurality of programming instructions stored on the storage medium and configured, when executed by a processor to coordinate access to a shared resource for a plurality of threads, by performing a method of;

selecting by one of the threads an action to be performed a thread upon a lock utilized by the thread, wherein the action is selected from a group comprising;

acquiring the lock,

trying to acquire the lock,

and releasing the lock;

asynchronously querying and receiving a first state of the lock as a current state of the lock, by the thread, the lock being considered to be in any one of at least four states in any point in time, and each state is represented by a multi-part state value defined by a state machine associated with the lock;

speculatively determining by the thread, a second state of the lock based at least in part on the first state of the lock and the selected action; and

attempting to perform by the thread, the selected action to transition the lock from the first state to the speculatively determined second state, the attempting including determining if the first state remains the current state of the lock, and, if the first state remains the current state, performing the selected action to transition the current state of the lock to the second state.

31. The article of claim 30, further including instructions providing for, if the state transition fails and if the selected action was either acquiring or releasing the lock, repeating, until the state transition succeeds:

asynchronously querying the first state of the lock;

speculatively determining the second state of the lock;

attempting to transition the lock from the queried first state to the speculatively determined second state.

32. The article of claim 31, further including instructions providing for, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state represents the acquisition of the lock, indicating the acquisition of the lock.

33. The article of claim 32, further including instructions providing for, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state does not represent the acquisition of the lock, adding the thread to the end of a queue of threads waiting to acquire the lock;

waiting to receive notification that the thread may acquire the lock; and

indicating the acquisition of the lock.

34. The article of claim 31, further including instructions providing for, if

the state transition succeeds, and

the selected action is releasing the lock, determining the number of threads in a queue to acquire the lock utilizing the speculatively determined second state of the lock.

35. The article of claim 34, further including instructions providing for, if the queue includes at least a first thread,

removing the first thread from the queue;

and

notifying the first thread that the first thread has acquired the lock.

36. The article of claim 30, further including instructions providing for, if

the selected action is trying to acquire the lock and

the state transition fails, indicating that the lock was unable to be acquired.

37. The article of claim 30, further including instructions providing for, if

the state transition succeeds and

the selected action is trying to acquire the lock, indicating the acquisition of the lock.

38. The article of claim 30, further including instructions providing for, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state represents the acquisition of the lock, indicating the acquisition of the lock.

39. The article of claim 38, further including instructions providing for, if

the state transition succeeds,

the selected action is acquiring the lock, and

the speculatively determined second state does not represent the acquisition of the lock, adding the thread to the end of a queue of threads waiting to acquire the lock;

waiting to receive notification that the thread may acquire the lock; and

indicating the acquisition of the lock.

40. The article of claim 30, further including instructions providing for, if

the state transition succeeds, and

the selected action is releasing the lock, determining the number of threads in a queue to acquire the lock utilizing the speculatively determined second state of the lock.

41. The article of claim 40, further including instructions providing for, if the queue includes at least a first thread,

removing the first thread from the queue;

and

notifying the first thread that the first thread has acquired the lock.

42. The article of claim 30, wherein the thread includes:

a unique thread identifier;

a next thread field to facilitate access to the next thread in a queue of threads waiting to acquire the lock; and

the thread is only capable of waiting for a single lock at a time.

43. The article of claim 30, wherein the action of acquiring the lock includes the inability to timeout or fail to acquire the lock.

44. The article of claim 30, wherein the lock'"'"'s current state may change between

asynchronously querying the first state of the lock;

and

attempting to transition the lock from the queried first state to the speculatively determined second state.