Fast synchronization for programs written in the JAVA programming language

• US 6,349,322 B1
• Filed: 05/06/1998
• Issued: 02/19/2002
• Est. Priority Date: 05/06/1998
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Shaylor, Nik
• Primary Examiner(s): Courtenay, III, St. John
• Assistant Examiner(s): Opie, George L.
• Application Number:
  US09/073,637
• Time in Patent Office: 1,385 Days
• Field of Search: 709/100-108, 709/310-332, 717/4, 717/5
• US Class Current: 718/107
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method, system, and computer program product for synchronized thread execution in a multithreaded processor are described. Each synchronized thread refers to at least one object identified by an object identification (OID) that is shared among a plurality of synchronized threads. One of the synchronized threads is selected for execution. Upon entering the selected thread, an entry sequence indicates that the shared object should be locked by pushing its OID onto a lock stack. The operations defined by the selected thread are executed and the indication is removed by pushing the OID from the lock stack.

Claims

1. A method for execution in a processor having a plurality of threads executing thereon, the threads including synchronized operations that refer to at least one shared object, wherein the shared object is identified by an object identification (OID), the method comprising the steps of:

selecting a first thread of the plurality of threads including a synchronized operation for execution;

upon entering the selected thread, indicating that the at least one shared object should be locked by pushing the OID of the at least one shared object onto a lock stack accessible to all of the plurality of threads;

executing the synchronized operations defined by the selected thread; and

removing the indication by pushing the OID from the lock stack.

2. The method of claim 1 wherein during the step of executing the operations defined by the selected thread the selected thread blocks, and the method further comprises a step of locking the at least one shared object after the selected thread blocks.

3. The method of claim 2 further comprising the steps of creating an instance of a monitor object corresponding to the shared object.

4. The method of claim 3 wherein the monitor object comprises a queue header, a counter, and an owner field identifying the selected thread.

5. The method of claim 3 wherein the step of locking comprises creating the monitor object in application memory space.

6. The method of claim 4 wherein the step of locking comprises creating the monitor object in kernel memory space.

7. The method of claim 2 wherein the step of locking further comprises:

determining when the selected thread blocks; and

performing the locking operation in response to the determining step.

8. The method of claim 2 wherein the step of locking further comprises:

determining when the selected thread resumes after the block; and

performing the locking operation only if one other of the threads including a synchronized operation has blocked since the selected thread blocked.

9. The method of claim 1 further comprising the steps of:

selecting a second thread for execution, wherein the second thread includes an operation synchronized with the synchronized operation of the first thread;

upon entering the second thread, determining whether the shared object is locked.

10. The method of claim 9 wherein when it is determined that the shared object is locked the method further comprises the steps of creating a monitor object associated with the shared object to determine when the shared object is unlocked;

and

executing the operations defined by the second thread after it is determined that the shared object is unlocked.

11. The method of claim 9 wherein when it is determined that the shared object is unlocked the method further comprises the steps of indicating that the shared object should be locked by pushing its OID onto the lock stack;

and

executing the operations defined by the second thread; and

removing the indication by pushing the OID from the lock stack.

12. A computer system for executing an application comprising a plurality of synchronized threads of execution, wherein each synchronized thread refers to at least one object identified by an object identification (OID) that is shared among a plurality of synchronized threads, the computer system comprising:

a processor;

a memory coupled to the processor;

a multithreading operating system that supports multiple threads of execution in a shared address space of the memory;

a lock stack in the memory, the lock stack comprising a plurality of entries sized to hold an OID, the lock stack being accessible to all of the plurality of synchronized threads;

an instruction interpreter executing in the processor and coupled to receive a selected one synchronized thread and cause the selected thread to execute on the processor, wherein upon entering the selected thread the instruction interpreter indicates that the shared object should be locked by pushing its OID onto a lock stack and upon exiting the selected thread the instruction interpreter removes the indication by pushing the OID from the lock stack.

13. The computer system of claim 12 further comprising:

a thread block indicator operating within the processor to signal when the selected thread blocks during execution; and

object locking devices operating within the processor and responsive to the thread block indicator to lock the shared object identified by the OID in the lock stack.

14. The computer system of claim 12 wherein the object locking devices comprise an instance of a monitor object corresponding to the shared object wherein the monitor object includes a queue header, a counter, and an owner field identifying the selected thread.

15. The computer system of claim 14 wherein the monitor object is instantiated in an application memory space of the memory.

16. The computer system of claim 14 wherein the monitor object is instantiated in a kernel memory space of the memory.

17. The computer system of claim 14 further comprising:

a thread release indicator operating within the processor to signal when the selected thread releases from a block condition during execution; and

object locking devices operating within the processor and responsive to the thread block indicator to lock the shared object identified by the OID in the lock stack only if another of the synchronized threads has blocked since the selected thread blocked.

18. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for synchronized thread execution in a multithreaded processor, wherein each synchronized thread refers to at least one object identified by an object identification (OID) that is shared among a plurality of synchronized threads, the computer program product comprising;

computer program devices operating in the computer system and configured to cause a computer to select one of the synchronized threads for execution;

computer program devices operating in the computer system and configured to cause a computer to indicate that the shared object should be locked by pushing its OID onto a lock stack upon entering the selected thread, the lock stack being accessible by all of the plurality of synchronized threads;

computer program devices operating in the computer system and configured to cause a computer to execute the operations defined by the selected thread; and

computer program devices operating in the computer system and configured to cause a computer to remove the indication by pushing the OID from the lock stack.

19. The computer program product of claim 18 further comprising:

computer program devices configured to cause a computer to lock the shared object after the selected thread blocks.

20. The computer program product of claim 19 further comprising:

computer program devices configured to cause a computer to determine when the selected thread blocks; and

computer program devices configured to cause a computer to perform the locking operation in response to the determining step.

21. The computer program product of claim 19 further comprising:

computer program devices configured to cause a computer to determine when the selected thread resumes after the block; and

computer program devices configured to cause a computer to perform the locking operation only if another of the synchronized threads has blocked since the selected thread blocked.

22. The computer program product of claim 18 further comprising:

computer program devices configured to cause a computer to create an instance of a monitor object corresponding to the shared object wherein the monitor object comprises a queue header, a counter, and an owner field identifying the selected thread.

23. The computer program product of claim 18 further comprising:

computer program devices configured to cause a computer to create a monitor object associated with a shared object, the shared object being identified by an object identifier (OID), the monitor object comprising state information and methods to determine when the shared object is unlocked if the shared object is locked;

computer program devices configured to cause a computer to determine whether the shared object is locked upon entering the second thread;

computer program devices configured to cause a computer to create a monitor object associated with the shared object to determine when the shared object is unlocked if the shared object is locked;

computer program devices configured to cause a computer to indicate that the shared object should be locked by pushing its OID onto the lock stack if the shared object is unlocked;

computer program devices configured to cause a computer to execute the operations defined by the second thread; and

computer program devices configured to cause a computer to remove the indication by pushing the OID from the lock stack.

24. A computer data signal embodied in a carrier wave comprising:

a first code portion comprising code configured to cause a computer to create a monitor object associated with a shared object, the shared object being identified by an object identifier (OID), the monitor object comprising state information and methods to determine when the shared object is unlocked if the shared object is locked;

a second code portion comprising code configured to cause a computer to indicate that the shared object should be locked by pushing its OID onto the lock stack if the shared object is unlocked, the lock stack being accessible by the plurality of threads;

a third code portion comprising code configured to cause a computer to execute the operations defined by the second thread; and

a fourth code portion comprising code configured to cause a computer to remove the indication by pushing the OID from the lock stack.