Locking and unlocking mechanism for controlling concurrent access to objects
First Claim
1. A method for controlling concurrent access to an object in a multi-threaded computer processing system, the method comprising the steps of:
- storing in memory a lock that is associated with said object, said lock comprising a thread identifier field and a flag field;
wherein, when said object is not locked by any thread, a portion of said lock is set to a predetermined value that indicates that the object is not locked by any thread;
wherein, when an object is locked by a particular thread, said thread identifier field is set to a value that identifies the particular thread, if no other threads are waiting to lock the object, said flag field is set to a predetermined value that indicates that no other threads are waiting to lock the object, and if other threads are waiting to lock the object, said flag field is set to a predetermined value which indicates that there is a non-empty queue of waiting threads associated with the object.
1 Assignment
0 Petitions
Accused Products
Abstract
A lock/unlock mechanism to control concurrent access to objects in a multi-threaded computer processing system comprises two parts: a thread pointer (or thread identifier), and a one-bit flag called a “Bacon bit”. Preferably, when an object is not locked (i.e., no thread has been granted access to the object), the thread identifier and Bacon bit are set to 0. When an object is locked by a particular thread (i.e., the thread has been granted access to the object), the thread identifier is set to a value that identifies the particular thread; if no other threads are waiting to lock the object, the Bacon bit is set to 0; however, if other threads are waiting to lock the object, the Bacon bit is set to ‘1’, which indicates the there is a queue of waiting threads associated with the object. To lock an object, a single CompareAndSwap operation is preferably used, much like with spin-locks; if the lock is already held by another thread, enqueueing is handled in out-of-line code. To unlock an object, in the normal case, a single CompareAndSwap operation may be used. This single operation atomically tests that the current thread owns the lock, and that no other threads are waiting for the object (i.e., the Bacon bit is ‘0’). A global lock is preferably used to change the Bacon bit of the lock. This provides an lock/unlock mechanism which combines many of the desirable features of both spin locking and queued locking, and can be used as the basis for a very fast implementation of the synchronization facilities of the Java language.
-
Citations
46 Claims
-
1. A method for controlling concurrent access to an object in a multi-threaded computer processing system, the method comprising the steps of:
-
storing in memory a lock that is associated with said object, said lock comprising a thread identifier field and a flag field;
wherein, when said object is not locked by any thread, a portion of said lock is set to a predetermined value that indicates that the object is not locked by any thread;
wherein, when an object is locked by a particular thread, said thread identifier field is set to a value that identifies the particular thread, if no other threads are waiting to lock the object, said flag field is set to a predetermined value that indicates that no other threads are waiting to lock the object, and if other threads are waiting to lock the object, said flag field is set to a predetermined value which indicates that there is a non-empty queue of waiting threads associated with the object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
upon determining that said thread identifier field of said lock corresponds to said first thread and said flag field of said lock is not set to a predetermined value that indicates that no other threads are waiting to lock the object, obtaining a global lock.
-
-
16. The method of claim 15, further comprising the steps of:
-
upon obtaining said global lock, evaluating said queue associated with said object to determine if no other threads are waiting to access said object; and
upon determining that no other threads are waiting to access said object, updating said lock associated with said object to indicate that said object is not locked by any thread, and releasing said global lock.
-
-
17. The method of claim 15, further comprising the steps of:
-
upon obtaining said global lock, evaluating said queue associated with said object to determine if other threads are waiting to access said object; and
upon determining that other threads are waiting to access said object, updating said queue to remove a second thread from said queue, resuming said second thread and releasing said global lock.
-
-
18. The method of claim 17, further comprising the steps of:
-
upon updating said queue to remove said second thread, determining if said queue is empty;
if it is determined that said queue is empty, updating said lock such that said thread identifier field of said lock is set to a thread identifier corresponding to said second thread and said flag field is set to said predetermined value that indicates that no other threads are waiting to lock the object; and
if it is determined that said queue is non-empty, updating said lock such that said thread identifier field of said lock is set to a thread identifier corresponding to said second thread and said flag field is set to said predetermined value that indicates that there is a non-empty queue of waiting threads associated with the object.
-
-
19. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for controlling concurrent access to an object in a multi-threaded computer processing system, said method steps comprising:
-
storing in memory a lock that is associated with said object, said lock comprising a thread identifier field and a flag field;
wherein, when said object is not locked by any thread, a portion of sail lock is set to a predetermined value that indicates that the object is not locked by any thread;
wherein, when an object is locked by a particular thread, said thread identifier field is set to a value that identifies the particular thread, if no other threads are waiting to lock the object, said flag field is set to a predetermined value that indicates that no other threads are waiting to lock the object, and if other threads are waiting to lock the object, said flag field is set to a predetermined value which indicates that there is a non-empty queue of waiting threads associated with the object. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
upon determining that said thread identifier field of said lock corresponds to said first thread and said flag field of said lock is not set to a predetermined value that indicates that no other threads are waiting to lock the object, obtaining a global lock.
-
-
34. The program storage device of claim 33, further comprising the steps of:
-
upon obtaining said global lock, evaluating said queue associated with said object to determine if no other threads are waiting to access said object; and
upon determining that no other threads are waiting to access said object, updating said lock associated with said object to indicate that said object is not locked by any thread, and releasing said global lock.
-
-
35. The program storage device of claim 33, further comprising the steps of:
-
upon obtaining said global lock, evaluating said queue associated with said object to determine if other threads are waiting to access said object; and
upon determining that other threads are waiting to access said object, updating said queue to remove a second thread from said queue, resuming said second thread and releasing said global lock.
-
-
36. The program storage device of claim 35, further comprising the steps of:
-
upon updating said queue to remove said second thread, determining if said queue is empty;
if it is determined that said queue is empty, updating said lock such that said thread identifier field of said lock is set to a thread identifier corresponding to said second thread and said flag field is set to said predetermined value that indicates that no other threads are waiting to lock the object; and
if it is determined that said queue is non-empty, updating said lock such that said thread identifier field of said lock is set to a thread identifier corresponding to said second thread and said flag field is set to said predetermined value that indicates that there is a non-empty queue of waiting threads associated with the object.
-
-
37. A method for controlling concurrent access to an object in a multi-threaded computer processing system, the method comprising the steps of:
-
storing in memory a lock that is associated with said object, said lock comprising a first flag field and a second flag field;
wherein, when said object is not locked by any thread, a portion of said lock is set to a predetermined value that indicates that the object is not locked by any thread;
wherein, when an object is locked by a particular thread, said first flag field is set to a value that indicates that the object is locked by a thread, if no other threads are waiting to lock the object, said second flag field is set to a predetermined value that indicates that no other threads are waiting to lock the object, and if other threads are waiting to lock the object, said second flag field is set to a predetermined value which indicates that there is a non-empty queue of waiting threads associated with the object. - View Dependent Claims (38, 39, 40, 41)
-
-
42. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for controlling concurrent access to an object in a multi-threaded computer processing system, said method steps comprising:
-
storing in memory a lock that is associated with said object, said lock comprising a first flag field and a second flag field;
wherein, when said object is not locked by any thread, a portion of said lock is set to a predetermined value that indicates that the object is not locked by any thread;
wherein, when an object is locked by a particular thread, said first flag field is set to a value that indicates that the object is locked by a thread, if no other threads are waiting to lock the object, said second flag field is set to a predetermined value that indicates that no other threads are waiting to lock the object, and if other threads are waiting to lock the object, said second flag field is set to a predetermined value which indicates that there is a non-empty queue of waiting threads associated with the object. - View Dependent Claims (43, 44, 45, 46)
-
Specification