Methods and apparatus providing non-blocking access to a resource

• US 7,844,973 B1
• Filed: 12/09/2004
• Issued: 11/30/2010
• Est. Priority Date: 12/09/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Dice, David
• Primary Examiner(s): Zhen; Li B
• Assistant Examiner(s): Lee; Adam
• Application Number:
  US11/008,500
• Time in Patent Office: 2,182 Days
• Field of Search: 718/714, 718/102, 718/104, 718/108, 707/8, 707799-800, 710/200, 710/54, 719/314
• US Class Current: 718/108
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

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.

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.

2. The method of claim 1 wherein maintaining an entry list of threads that are awaiting access to the monitor using a block-free list joining mechanism comprises:

upon completion of the second thread joining the entry list of threads, the second thread identifying that the join list of threads identifies threads that attempted to join the list of entry threads while the second thread was presently accessing the entry list of threads, and in response, joining each thread identified in the join list of threads to the entry list of threads awaiting access to the monitor.

3. The method of claim 2 wherein joining each thread identified in the join list of threads to the entry list of threads awaiting access to the monitor comprises:

traversing the join list of threads, beginning with a thread identified in the join attempt thread identity area and extending to each thread identified by the next thread identity area associated with each former thread in a join list of thread, to join each thread in the list of former threads into the entry list of threads awaiting access to the monitor.

4. The method of claim 2 wherein:

the list available indicator is a storage location in memory associated with the computerized device;

the join attempt thread identity area is associated with the list available indicator;

the next thread identity area is a next thread field in a thread structure associated with each thread; and

wherein 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 collectively result in creating a list of thread identities including the third thread and the former thread, the list of thread identities allowing an identification of threads that attempted to join the list of entry threads while the second thread is presently accessing the entry list of threads.

5. The method of claim 1 wherein enabling a third thread to join the list of entry threads comprises:

enabling the third thread to join the list of entry threads while the second thread is presently accessing the entry list of threads without blocking the third thread from execution and without requiring the third thread to identify specific instructions to perform to join the list of entry threads.

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.

7. The computerized device of claim 6 wherein when the computerized device performs the operation of 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 to obtain exclusive access of the monitor to gain exclusive access to the resource, the computerized device performs the operation of:

allowing only a thread that has exclusive access of a monitor to perform a pop operation to pop the candidate thread off of the entry list of threads prior to releasing of the monitor.

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.

9. The method of claim 8 wherein reattaching the private list of entry threads to the starting location of the list of entry threads comprises identifying that a new list of entry threads containing at least one thread identity has been created since detaching the list of entry threads.

10. The method of claim 9 wherein reattaching the private list of entry threads to the starting location of the list of entry threads further comprises detaching the new list of entry threads.

11. The method of claim 10 wherein reattaching the private list of entry threads to the starting location of the list of entry threads further comprises merging the private list of entry threads with the new list of entry threads to add the new list of entry threads into the private list of entry thread.

12. The method of claim 11 wherein reattaching the private list of entry threads to the starting location of the list of entry threads further comprises attempting to reattach the private list of entry threads to the starting location of the list of entry threads by repeating the operations of identifying that a new list, detaching the new list, and merging the private list until no new list entry threads has been created since detaching the list of entry threads.