Mechanism for implementing thread synchronization in a priority-correct, low-memory safe manner

• US 7,886,300 B1
• Filed: 09/26/2006
• Issued: 02/08/2011
• Est. Priority Date: 09/26/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Lam, Yin Zin Mark, Zhou, Jiangli, Long, Dean R. E.
• Primary Examiner(s): Wu; Qing
• Assistant Examiner(s): Truong; Camquy
• Application Number:
  US11/528,188
• Time in Patent Office: 1,596 Days
• Field of Search: 718/104, 710/200, 711/152
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A mechanism is disclosed for implementing fast locking in a multi-threaded system. This mechanism enables fast locking to be performed even on an operating system platform that does not allow one thread to assign ownership of a lock on a mutex to another thread. In addition, the mechanism performs locking in a manner that ensures priority correctness and is low-memory safe. In one implementation, the priority correctness is achieved by using operating system mutexes to implement locking, and the low-memory safe aspect is achieved by pre-allocating a memory section to each thread. This pre-allocated memory section ensures that a thread will have sufficient memory to obtain a lock, even when a system is in a low-memory state. With this mechanism, it is possible to implement locking in a safe and efficient manner.

Claims

1. A machine implemented method, comprising:

initializing a first thread, wherein initializing the first thread comprises allocating a first mutex and causing the first thread to obtain a lock on the first mutex, and allocating a first memory portion which is associated with the first thread as a first boost record;

initializing a second thread, wherein initializing the second thread comprises allocating a second mutex and causing the second thread to obtain a lock on the second mutex, and allocating a second memory portion which is associated with the second thread as a second boost record;

granting the first thread a lock on a target object;

detecting that the second thread wishes to lock the target object while the first thread owns the lock on the target object;

creating a heavy-weight lock (HL) data structure, which is associated with the target object;

disassociating the second boost record from the second thread and associating the second boost record with the HL data structure;

updating a boost queue in the second boost record to include the second thread; and

causing the second thread to wait on the first mutex and a cancel object, wherein the second thread is awakened if either the lock on the first mutex is released or the cancel object is signaled.

2. The method of claim 1, further comprising:

causing a target mutex to be allocated and associated with the HL data structure, wherein the target mutex is currently not locked by any thread.

3. The method of claim 2, further comprising:

updating the HL data structure to indicate that a boost condition currently exists.

4. The method of claim 3, further comprising:

detecting that a boost condition currently exists;

determining, by the first thread, that it currently owns the lock on the target object;

obtaining, by the first thread, a lock on the target mutex;

updating the HL data structure to indicate that a boost condition no longer exists; and

causing, by the first thread, the cancel object to be signaled.

5. The method of claim 4, wherein the first thread does not release the lock on the first mutex.

6. The method of claim 1, further comprising:

updating, by the second thread after being awakened, the second boost record to remove the second thread from the boost queue;

determining that the second thread currently has no boost record associated therewith;

determining whether the boost queue currently comprises any threads; and

in response to a determination that the boost queue does not currently comprise any threads, disassociating the second boost record from the HL data structure and associating the second boost record with the second thread.

7. The method of claim 1, further comprising:

initializing a third thread, wherein initializing the third thread comprises allocating a third mutex and causing the third thread to obtain a lock on the third mutex, and allocating a third memory portion which is associated with the third thread as a third boost record;

detecting that the third thread wishes to lock the target object while the first thread owns the lock on the target object;

updating the boost queue in the second boost record to include the third thread; and

causing the third thread to wait on the first mutex and the cancel object, wherein the third thread is awakened if either the lock on the first mutex is released or the cancel object is signaled.

8. The method of claim 7, further comprising:

updating, by the second thread after being awakened, the second boost record to remove the second thread from the boost queue;

determining that the second thread currently has no boost record associated therewith;

determining that the boost queue currently comprises at least the third thread; and

disassociating the third boost record from the third thread and associating the third boost record with the second thread.

9. The method of claim 8, further comprising:

updating, by the third thread after being awakened, the second boost record to remove the third thread from the boost queue;

determining that the third thread currently has no boost record associated therewith;

determining whether the boost queue currently comprises any threads; and

in response to a determination that the boost queue does not currently comprise any threads, disassociating the second boost record from the HL data structure and associating the second boost record with the third thread.

10. The method of claim 1, wherein the lock on the target object is a fast lock, which is not an operating system level lock.

11. A machine readable storage medium, comprising:

instructions for causing one or more processors to initialize a first thread, wherein initializing the first thread comprises allocating a first mutex and causing the first thread to obtain a lock on the first mutex, and allocating a first memory portion which is associated with the first thread as a first boost record;

instructions for causing one or more processors to initialize a second thread, wherein initializing the second thread comprises allocating a second mutex and causing the second thread to obtain a lock on the second mutex, and allocating a second memory portion which is associated with the second thread as a second boost record;

instructions for causing one or more processors to grant the first thread a lock on a target object;

instructions for causing one or more processors to detect that the second thread wishes to lock the target object while the first thread owns the lock on the target object;

instructions for causing one or more processors to create a heavy-weight lock (HL) data structure, which is associated with the target object;

instructions for causing one or more processors to disassociate the second boost record from the second thread and to associate the second boost record with the HL data structure;

instructions for causing one or more processors to update a boost queue in the second boost record to include the second thread; and

instructions for causing one or more processors to cause the second thread to wait on the first mutex and a cancel object, wherein the second thread is awakened if either the lock on the first mutex is released or the cancel object is signaled.

12. The machine readable storage medium of claim 11, further comprising:

instructions for causing one or more processors to cause a target mutex to be allocated and associated with the HL data structure, wherein the target mutex is currently not locked by any thread.

13. The machine readable storage medium of claim 12, further comprising:

instructions for causing one or more processors to update the HL data structure to indicate that a boost condition currently exists.

14. The machine readable storage medium of claim 13, further comprising:

instructions for causing one or more processors to detect that a boost condition currently exists;

instructions for causing one or more processors to determine, by the first thread, that the first thread currently owns the lock on the target object;

instructions for causing one or more processors to obtain, by the first thread, a lock on the target mutex;

instructions for causing one or more processors to update the HL data structure to indicate that a boost condition no longer exists; and

instructions for causing one or more processors to cause, by the first thread, the cancel object to be signaled.

15. The machine readable storage medium of claim 14, wherein the first thread does not release the lock on the first mutex.

16. The machine readable storage medium of claim 11, further comprising:

instructions for causing one or more processors to update, by the second thread after being awakened, the second boost record to remove the second thread from the boost queue;

instructions for causing one or more processors to determine that the second thread currently has no boost record associated therewith;

instructions for causing one or more processors to determine whether the boost queue currently comprises any threads; and

instructions for causing one or more processors to, in response to a determination that the boost queue does not currently comprise any threads, disassociate the second boost record from the HL data structure and to associate the second boost record with the second thread.

17. The machine readable storage medium of claim 11, further comprising:

instructions for causing one or more processors to initialize a third thread, wherein initializing the third thread comprises allocating a third mutex and causing the third thread to obtain a lock on the third mutex, and allocating a third memory portion which is associated with the third thread as a third boost record;

instructions for causing one or more processors to detect that the third thread wishes to lock the target object while the first thread owns the lock on the target object;

instructions for causing one or more processors to update the boost queue in the second boost record to include the third thread; and

instructions for causing one or more processors to cause the third thread to wait on the first mutex and the cancel object, wherein the third thread is awakened if either the lock on the first mutex is released or the cancel object is signaled.

18. The machine readable storage medium of claim 17, further comprising:

instructions for causing one or more processors to update, by the second thread after being awakened, the second boost record to remove the second thread from the boost queue;

instructions for causing one or more processors to determine that the second thread currently has no boost record associated therewith;

instructions for causing one or more processors to determine that the boost queue currently comprises at least the third thread; and

instructions for causing one or more processors to disassociate the third boost record from the third thread and associating the third boost record with the second thread.

19. The machine readable storage medium of claim 18, further comprising:

instructions for causing one or more processors to update, by the third thread after being awakened, the second boost record to remove the third thread from the boost queue;

instructions for causing one or more processors to determine that the third thread currently has no boost record associated therewith;

instructions for causing one or more processors to determine whether the boost queue currently comprises any threads; and

instructions for causing one or more processors to, in response to a determination that the boost queue does not currently comprise any threads, disassociate the second boost record from the HL data structure and to associate the second boost record with the third thread.

20. The machine readable storage medium of claim 11, wherein the lock on the target object is a fast lock, which is not an operating system level lock.