Expedited object locking and unlocking

• US 6,314,563 B1
• Filed: 03/31/1999
• Issued: 11/06/2001
• Est. Priority Date: 02/05/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Agesen, Ole, Garthwaite, Alex, Detlefs, David L.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/283,136
• Time in Patent Office: 951 Days
• Field of Search: 717/5, 717/9, 717/7, 717/1, 711/11, 711/152, 711/153
• US Class Current: 717/108
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

An object structure'"'"'s header (40) allocates a two-bit synchronization-state field (42) solely to monitor data for implementing synchronization on that object. When the object is locked by a particular execution thread, or when one or more execution threads are waiting for a lock or notification on that object, its header contains a pointer to monitor resources in the form of a linked list of lock records (50, 52, 54) associated with the threads involved. The synchronization-state field (42) ordinarily contains an indication of whether such a linked list exists and, if so, whether its first member is associated with a thread that has a lock on the object. When a thread attempts to gain access to that linked list, it employs an atomic swap operation to place a special busy value in that lock-state field (42) and write its execution-environment pointer into the object'"'"'s header (40). If the previous value of that field was not the special busy value, the thread uses the header'"'"'s previous contents to perform its intended synchronization operation. Otherwise, it obtains that information through its own execution environment (44, 46, or 48) or that of the thread whose identifier the object header previously contained. When the thread completes its synchronization operation, it employs an atomic compare-and-swap operation to write the results into the object'"'"'s header if that header still contains the thread identifier that the thread originally wrote there. Otherwise, it communicates that information to its successor thread if the thread identifier is different and thereby indicates that at least one successor is contending for access to the linked list.

Claims

1. A computer system configured by computer instructions to operate as a compiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, produces electrical signals representing object code that directs the processor in some circumstances to;

i) perform on the object'"'"'s lock-word field an atomic lock compare-and-swap operation that;

a) is successful, performing a lock operation by replacing prereplacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is locked and not meta-locked without first placing a meta-lock-indicating synchronization code in the synchronization-state field, only if the synchronization-state field in the pre-replacement lock-word-field contents indicate that the object is neither synchronized on nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the lock compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is meta-locked; and

b) thereafter perform a lock operation on the object.

2. A computer system as defined in claim 1 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

3. A computer system as defined in claim 1 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

4. A computer system as defined in claim 1 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

5. A computer system as defined in claim 4 wherein:

A) in response to electrical signals representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

6. A computer system as defined in claim 1 wherein:

A) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a preliminary-read operation in which it reads the contents of the lock-word field;

B) the lock compare-and-swap operation is performed only if the synchronization-state-field contents of the lock-record field read in the preliminary-read operation indicate that the object is neither synchronized on nor meta-locked; and

C) the lock compare-and-swap operation is successful if the lock-word field'"'"'s pre-replacement contents are the same as the contents of the lock-record field read in the preliminary-read operation.

7. A computer system as defined in claim 6 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

8. A computer system as defined in claim 6 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

9. A computer system as defined in claim 6 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

10. A computer system as defined in claim 9 wherein:

A) in response to electrical signal representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

11. A computer system as defined in claim 6 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

12. A computer system as defined in claim 1 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases the synchronizing execution thread'"'"'s lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

13. A computer system as defined in claim 12 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

14. A computer system as defined in claim 13 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has more than one thread synchronized on it, and, in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

15. A computer system configured by computer instructions to operate as acompiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) i n response to electrical signals representing source code that calls for a synchronizing execution th read to release its lock on the object, produces electrical signals representing object code that directs the processor to;

i) perform an atomic release compare-and-swap operation that;

a) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the release compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing the pre-replacement contents of the object'"'"'s synchronization state field with a synchronization-state code indicating that the object is meta-locked; and

b) thereafter release the lock on the object.

16. A computer system as defined in claim 15 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

17. A computer system as defined in claim 16 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has no more than one thread synchronized on it, and in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

18. For generating object code, a method comprising:

A) in response to source code that calls for allocation of an object on which thread execution can be synchronized, producing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to source code that calls for a synchronizing execution thread to lock the object, producing object code that directs the processor in some circumstances to;

i) perform on the object'"'"'s lock-word field an atomic lock compare and-swap operation that;

a) is successful, performing a lock operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is locked and not meta-locked without first placing a meta-lock-indicating synchronization code in the synchronization-state field, only if the synchronization-state field in the pre-replacement lock-word-field contents indicate that the object is neither synchronized on nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the lock compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is meta-locked; and

b) thereafter perform a lock operation on the object.

19. A method as defined in claim 18 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

20. A method as defined in claim 18 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

21. A method as defined in claim 18 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

22. A method as defined in claim 21 wherein:

A) in response to source code that calls for execution of multiple execution threads, the method produces object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

23. A method as defined in claim 18 wherein:

A) in response to source code that calls for a synchronizing execution thread to lock the object, the method produces object code that directs the processor to perform a preliminary-read operation in which it reads the contents of the lock-word field;

B) the lock compare-and-swap operation is performed only if the synchronization-state-field contents of the lock-record field read in the preliminary read operation indicate that the object is neither synchronized on nor meta-locked; and

C) the lock compare-and-swap operation is successful if the lock-word field'"'"'s pre-replacement contents are the same as the contents of the lock-record field read in the preliminary-read operation.

24. A method as defined in claim 23 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

25. A method as defined in claim 23 wherein:

A) the lock operation results a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

26. A method as defined in claim 23 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

27. A method as defined in claim 26 wherein:

A) in response to source code that calls for execution of multiple execution threads, the method produces object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

28. A method as defined in claim 23 wherein, in response to source code that calls for a synchronizing execution thread to release its lock on the object, the method produces object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

29. A method as defined in claim 18 wherein, in response to source code that calls for a synchronizing execution thread to release its lock on the object, the method produces object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases the synchronizing execution thread'"'"'s lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

30. A method as defined in claim 29 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

31. A method as defined in claim 30 wherein, in response to source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the method produces object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has more than one thread synchronized on it, and, in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

32. For generating object code, a method comprising:

A) in response to source code that calls for allocation of an object on which thread execution can be synchronized, producing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to source code that calls for a synchronizing execution thread to release its lock on the object, producing object code that directs the processor to;

i) perform an atomic release compare-and-swap operation that;

a) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the release compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

b) thereafter release the lock on the object.

33. A method as defined in claim 32 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

34. A method as defined in claim 33 wherein, in response to source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the method produces object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has no more than one thread synchronized on it, and in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

35. A computer data signal embodied in a carrier wave and representing a sequence of instructions that, when executed by a computer system, configures the computer system to operate as a compiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, produces electrical signals representing object code that directs the processor in some circumstances to;

i) perform on the object'"'"'s lock-word field an atomic lock compareand-swap operation that;

a) is successful, performing a lock operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is locked and not meta-locked without first placing a meta-lock-indicating synchronization code in the synchronization-state field, only if the synchronization-state field in the pre-replacement lock-word-field contents indicate that the object is neither synchronized on nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the lock compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is meta-locked; and

b) thereafter perform a lock operation on the object.

36. A computer data signal as defined in claim 35 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

37. A computer data signal as defined in claim 35 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

38. A computer data signal as defined in claim 35 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

39. A computer data signal as defined in claim 38 wherein:

A) in response to electrical signals representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

40. A computer data signal as defined in claim 35 wherein:

A) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a preliminary-read operation in which it reads the contents of the lock-word field;

B) the lock compare-and-swap operation is performed only if the synchronization-state-field contents of the lock-record field read in the preliminary-read operation indicate that the object is neither synchronized on nor meta-locked; and

C) the lock compare-and-swap operation is successful if the lock-word field'"'"'s pre-replacement contents are the same as the contents of the lock-record field read in the preliminary-read operation.

41. A computer data signal as defined in claim 40 wherein:

A) the lock operation results in a linked lock record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

42. A computer data signal as defined in claim 40 wherein:

A) the lock operation results in a linked jock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

43. A computer data signal as defined in claim 40 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

44. A computer data signal as defined in claim 43 wherein:

A) in response to electrical signals representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

45. A computer data signal as defined in claim 40 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

46. A computer data signal as defined in claim 35 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases the synchronizing execution thread'"'"'s lock on the object by replacing the pre-replacement contents of the object'"'"'s synchroni zation-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

47. A computer data signal as defined in claim 46 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

48. A computer data signal as defined in claim 47 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has more than one thread synchronized on it, and, in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

49. A computer data signal embodied in a carrier wave and representing a sequence of instructions that, when executed by a computer system, configures the computer system to operate as a compiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, produces electrical signals representing object code that directs the processor to;

i) perform an atomic release compare-and-swap operation that;

a) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the release compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

b) thereafter release the lock on the object.

50. A computer data signal as defined in claim 49wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

51. A computer data signal as defined in claim 50 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has no more than one thread synchronized on it, and in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

52. A storage medium containing instructions readable by a computer system to configure the computer system as a compiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, produces electrical signals representing object code that directs the processor in some circumstances to;

i) perform on the object'"'"'s lock-word field an atomic lock compareand-swap operation that;

a) is successful, performing a lock operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is locked and not meta-locked without first placing a meta-lock-indicating synchronization code in the synchronization-state field, only if the synchronization-state field in the pre-replacement lock-word-field contents indicate that the object is neither synchronized on nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the lock compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing pre-replacement contents of the object'"'"'s lock-word field with a lock word in which the synchronization-state field contains a synchronization-state code indicating that the object is meta-locked; and

b) thereafter perform a lock operation on the object.

53. A storage medium as defined in claim 52 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

54. A storage medium as defined in claim 52 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

55. A storage medium as defined in claim 52 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

56. A storage medium as defined in claim 55 wherein:

A) in response to electrical signals representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

57. A storage medium as defined in claim 52 wherein:

A) in response to electrical signals representing source code that calls for a synchronizing execution thread to lock the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a preliminary-read operation in which it reads the contents of the lock-word field;

B) the lock compare-and-swap operation is performed only if the synchronization-state-field contents of the lock-record field read in the preliminary-read operation indicate that the object is neither synchronized on nor meta-locked; and

C) the lock compare-and-swap operation is successful if the lock-word field'"'"'s pre-replacement contents are the same as the contents of the lock-record field read in the preliminary-read operation.

58. A storage medium as defined in claim 57 wherein:

A) the lock operation results in ed lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) the lock word with which the lock compare-and-swap operation replaces the pre-replacement contents of the object'"'"'s lock-word field has the release value.

59. A storage medium as defined in claim 57 wherein:

A) the lock operation results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) the lock operation includes producing a release value that includes;

i) a synchronization-state field that indicates that the object is locked; and

ii) an identifier field that identifies the linked lock-record list; and

C) if the lock compare-and-swap operation is unsuccessful, the lock operation is followed by a meta-lock-release operation in which the contents of the object'"'"'s lock-word field are replaced with a lock word whose value is the release value if the lock-word-field contents before the meta-lock-release operation are the same as the lock word with which the meta-lock-acquisition operation replaced the contents of the object'"'"'s lock-word field.

60. A storage medium as defined in claim 57 wherein the lock word with which the meta-lock-acquisition operation replaces pre-replacement contents of the object'"'"'s lock-word field includes an identifier of the synchronizing thread.

61. A storage medium as defined in claim 60 wherein:

A) in response to electrical signals representing source code that calls for execution of multiple execution threads, the compiler/interpreter produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment; and

B) the identifier of the synchronizing thread identifies the synchronizing thread'"'"'s execution environment.

62. A storage medium as defined in claim 57 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

63. A storage medium as defined in claim 52 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to:

A) perform an atomic release compare-and-swap operation that;

i) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases the synchronizing execution thread'"'"'s lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

ii) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

B) if the release compare-and-swap operation is unsuccessful;

i) replace the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

ii) thereafter release the lock on the object.

64. A storage medium as defined in claim 63 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

65. A storage medium as defined in claim 64 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has more than one thread synchronized on it, and, in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.

66. A storage medium containing instructions readable by a computer system to configure the computer system as a compiler/interpreter that:

A) in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, produces electrical signals representing object code that directs a processor to allocate to the object an object structure that includes a lock-word field of which a synchronization-state field is a part; and

B) in response to electrical signals representing source code that calls for a synchronizing execution thread to release its lock on the object, produces electrical signals representing object code that directs the processor to;

i) perform an atomic release compare-and-swap operation that;

a) if the object has no more than one thread synchronized on it and pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object is not meta-locked, is successful and releases its lock on the object by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is neither locked nor meta-locked; and

b) is otherwise unsuccessful and does not replace the pre-replacement contents of the object'"'"'s synchronization-state field; and

ii) if the release compare-and-swap operation is unsuccessful;

a) perform a meta-lock-acquisition operation by replacing the pre-replacement contents of the object'"'"'s synchronization-state field with a synchronization-state code indicating that the object is meta-locked; and

b) thereafter release the lock on the object.

67. A storage medium as defined in claim 66 wherein the release compare-and-swap operation is successful only if the pre-replacement contents of the object'"'"'s synchronization-state field indicate that the object has no more than one thread synchronized on it.

68. A storage medium as defined in claim 67 wherein, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform a monitor-access operation on the object, the compiler/interpreter produces electrical signals representing object code that directs the processor to perform a monitor-access operation that:

A) results in a linked lock-record list, associated with the object, that comprises a lock record associated with each thread synchronized on the object;

B) produces a release value that includes a synchronization-state field that;

i) indicates whether the object is locked; and

ii) if the linked lock-record list has more than one lock record in it, indicates that the object has no more than one thread synchronized on it, and in at least some circumstances, indicates otherwise if the linked lock-record list has no more than one lock record in it; and

C) replaces pre-replacement contents of the object'"'"'s lock-word field with the release value if no successor thread has placed in the object'"'"'s lock-word field a synchronization-state code indicating that the object is meta-locked.