Methods and apparatus providing non-blocking access to a resource
First Claim
1. In a computerized device, a method for controlling access to a resource by a group of threads requiring access to the resource via a monitor, the method comprising:
- providing exclusive access to the resource within the computerized device to a first thread by allowing the first thread exclusive access of the monitor;
maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism that allows threads to join the entry list of threads without threads having to exclusively lock the entry list of threads and without blocking operation of the threads during the process of joining the entry list of threads; and
upon completion of access to the resource by the first thread, operating the first thread to manipulate the entry list of threads to identify a successor thread within the entry list of threads as being a candidate thread to obtain exclusive access of the monitor for gaining exclusive access to the resource,wherein maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism comprises;
maintaining a list available indicator identifying if a second thread is presently accessing the entry list of threads to join the entry list of threads;
enabling a third thread to join the list of entry threads while the second thread is presently accessing the entry list of threads by performing the operations of;
determining that the list available indicator identifies that a second thread is presently accessing the list of threads;
determining if a join attempt thread identity area contains a thread identity of a former thread that attempted to join the list of entry threads while the second thread was presently accessing the entry list of threads, and if so, providing the thread identity of the former thread in a next thread identity area associated with the third thread; and
providing an identity of the third thread in the join attempt thread identity area to create a join list of threads that attempted to join the list of entry threads while the second thread is presently accessing the entry list of threads, the join list of threads including the third thread and any former threads that attempted to join the list of entry threads while the second thread was presently accessing the entry list of threads.
2 Assignments
0 Petitions
Accused Products
Abstract
A system to control access to a resource by a group of threads requiring access to the resource provides exclusive access to the resource within a computerized device on behalf of a first thread by allowing the first thread exclusive access of a monitor associated with the resource. An entry list of threads is maintained that are awaiting access to the monitor using block-free list joining mechanisms including a thread chaining technique, a push/pop technique, and a detach, modify, reattach technique to allow threads to join the entry list of threads without blocking operation of the threads. Upon completion of access to the resource by the first thread, the system operates the first thread to manipulate the entry list of threads to identify a successor thread as being a candidate thread to obtain exclusive access of the monitor to gain exclusive access to the resource.
120 Citations
12 Claims
-
1. In a computerized device, a method for controlling access to a resource by a group of threads requiring access to the resource via a monitor, the method comprising:
-
providing exclusive access to the resource within the computerized device to a first thread by allowing the first thread exclusive access of the monitor; maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism that allows threads to join the entry list of threads without threads having to exclusively lock the entry list of threads and without blocking operation of the threads during the process of joining the entry list of threads; and upon completion of access to the resource by the first thread, operating the first thread to manipulate the entry list of threads to identify a successor thread within the entry list of threads as being a candidate thread to obtain exclusive access of the monitor for gaining exclusive access to the resource, wherein maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism comprises; maintaining a list available indicator identifying if a second thread is presently accessing the entry list of threads to join the entry list of threads; enabling a third thread to join the list of entry threads while the second thread is presently accessing the entry list of threads by performing the operations of; determining that the list available indicator identifies that a second thread is presently accessing the list of threads; determining if a join attempt thread identity area contains a thread identity of a former thread that attempted to join the list of entry threads while the second thread was presently accessing the entry list of threads, and if so, providing the thread identity of the former thread in a next thread identity area associated with the third thread; and providing an identity of the third thread in the join attempt thread identity area to create a join list of threads that attempted to join the list of entry threads while the second thread is presently accessing the entry list of threads, the join list of threads including the third thread and any former threads that attempted to join the list of entry threads while the second thread was presently accessing the entry list of threads. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computerized device comprising:
- a memory;
at least one processor;
a resource;an interconnection mechanism coupling the memory, the at least one processor and the resource; wherein the memory is encoded with a group of threads and a synchronization subsystem that controls access to the resource by the group of threads requiring access to the resource via a monitor, when those threads execute on the processor by causing the computerized device to perform the operations of; providing exclusive access to the resource within the computerized device to a first thread by allowing the first thread exclusive access of the monitor; maintaining an entry list of threads in the memory that are awaiting access to the monitor using a block-free list joining mechanism in the synchronization subsystem that allows threads to join the entry list of threads without blocking operation of the threads during the process of joining the entry list of threads, the block-free list joining mechanism allowing threads to join the entry list of threads without threads having to exclusively lock the entry list of threads during the process of joining the entry list of threads; and upon completion of access to the resource by the first thread, operating the first thread to manipulate the entry list of threads to identify a successor thread within the entry list of threads as being a candidate thread to obtain exclusive access of the monitor for gaining exclusive access to the resource, wherein when the computerized device performs the operation of maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism, the computerized device performs the operation of; allowing any thread that requires to join the entry list of thread to perform a push operation to join the entry list of threads to allow at least two threads to concurrently push themselves onto the entry list of threads so that the at least two threads do not have the block execution when joining the entry list of threads. - View Dependent Claims (7)
- a memory;
-
8. In a computerized device, a method for controlling access to a resource by a group of threads requiring access to the resource via a monitor, the method comprising:
-
providing exclusive access to the resource within the computerized device to a first thread by allowing the first thread exclusive access of the monitor; maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism that allows threads to join the entry list of threads without blocking operation of the threads during the process of joining the entry list of threads; and upon completion of access to the resource by the first thread, operating the first thread to manipulate the entry list of threads to identify a successor thread within the entry list of threads as being a candidate thread to obtain exclusive access of the monitor for gaining exclusive access to the resource, wherein maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism comprises; enabling a second thread to join the list of entry threads while the first thread has exclusive access of a monitor associated with the resource by; determining if the list of entry threads is empty, and if so, adding the second thread as a first member of the list of entry threads, and if the list of entry threads is not empty, performing the operations of; detaching the non-empty list of entry threads from a starting location of the list of entry threads to create a private list of empty threads modifiable by the second thread; operating on the private list of entry threads to join the second thread to the private list of entry threads; and reattaching the private list of entry threads to the starting location of the list of entry threads so that the private list of entry threads to which the second thread has joined becomes the list of entry threads awaiting access to the monitor. - View Dependent Claims (9, 10, 11, 12)
-
Specification