Recyclable locking for multi-threaded computing environments

• US 6,836,887 B1
• Filed: 12/21/1998
• Issued: 12/28/2004
• Est. Priority Date: 12/21/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Such, Ondrej
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): ZHEN, LI B
• Application Number:
  US09/217,389
• Time in Patent Office: 2,199 Days
• Field of Search: 718/104, 718/106, 707/8, 709/316, 709/104, 719/316
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Recyclable locking for multi-threaded computing environments is disclosed. In one embodiment, a system includes at least one thread, a pool of locks, at least one object, and a recyclable locking mechanism. Each object has an associated variable. The mechanism associates a lock with an object using the associated variable of the object as a pointer, upon a first request by a thread.

Claims

1. A system comprising:

at least one thread;

a pool of locks;

at least one object that is capable of representing a resource needed by the at least one thread, the at least one object having a variable, the variable of the at least one object comprising a set of high bits defining the pointer to a lock and a set of low bits defining a status variable; and

,

a recyclable locking mechanism for associating a lock from the pool of locks with the at least one object using the variable as a pointer when requested by the at least one thread, the lock returning to the pool of locks without having to destroy the at least one object when the at least one thread no longer needs to access the resource.

2. The system of claim 1, wherein the set of high bits comprises 27 bits and the set of low bits comprises 5 bits.

3. The system of claim 1, wherein the set of low bits is initially set to −

1.

4. The system of claim 1, wherein upon the first request the set of low bits is incremented by 1.

5. The system of claim 4, wherein upon the set of low bits after incrementation by one being greater than 0, the variable has an in-use status by a thread such that the set of high bits points to a lock.

6. The system of claim 4, wherein upon the variable after incrementation by one being less than 32, the variable has a spin status such that the set of high bits is currently in the process of being set to a lock.

7. The system of claim 1, wherein the recyclable locking mechanism further is to deassociate the lock from the object upon a second request by the thread,

such that upon the second request the set of low bits is decremented by 1.

8. A method comprising:

asserting an instruction by a thread to lock an object;

increasing a variable of the object, the variable having a set of high bits for representing a pointer to a lock and a set of low bits for representing a lock status;

determining whether the variable is greater than a boundary value so as to allocate the lock; and

recycling the lock by returning the lock to a pool of locks when the thread no longer needs the object regardless of whether the object persists after the lock returns to the pool of locks.

9. The method of claim 8, further comprising initially setting the variable of the object to −

1.

10. The method of claim 8, further comprising upon determining that the variable is less than the boundary value, waiting until the variable is greater than the boundary value.

11. The method of claim 8, further comprising upon determining that the variable is greater than the boundary value, using the set of high bits of the variable as a pointer to a lock for the object.

12. The method of claim 11, further comprising:

decrementing the variable of the object; and

, determining whether the variable is less than a minimum threshold.

13. The method of claim 12, upon determining that the variable is less than the minimum threshold, recycling the lock.

14. A computer comprising:

a processor;

a computer-readable medium; and

,

a recyclable locking mechanism program executed by the processor from the computer-readable medium to associate a lock with an object using a variable of the object as a pointer when requested by a thread, the variable of the object comprising a set of high bits defining the pointer to a lock and a set of low bits defining a status variable, the lock returning to a pool of locks without having to destroy the object when the object is no longer needed by the thread.

15. A computer-readable medium having a recyclable locking mechanism program stored thereon for execution on a computer to associate a lock with an object using a variable of the object as a pointer when requested by a thread the variable of the object comprising a set of high bits defining the pointer to a lock and a set of low bits defining a status variable, the lock returning to a pool of locks without having to destroy the object when the object is no longer needed by the thread.