Busy-wait-free synchronization

• US 6,173,442 B1
• Filed: 02/05/1999
• Issued: 01/09/2001
• Est. Priority Date: 02/05/1999
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alex, Ramakrishna, Y. Srinivas, White, Derek, Agesen, Ole, Detlefs, David L., Knippel, Ross C.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US09/245,778
• Time in Patent Office: 704 Days
• Field of Search: 717/9, 717/4, 717/5, 707/100, 707/103, 707/8, 709/103, 709/106, 711/118
• US Class Current: 717/141
• 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 execution of multiple execution threads, produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment that includes a successor-identifier field, a release-value-reception field, and a release-value-transmission field;

B) 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 an identifier field and a synchronization-state field; and

C) in response to electrical signals representing source code that calls for a synchronizing execution thread to perform any one of a set of at least one monitor-access operation with respect to the object, produces electrical signals representing object code that directs a processor to perform a monitor-access operation that;

i) begins with a meta-lock-acquisition operation in which the synchronizing execution thread;

a) performs an atomic swap operation in which the synchronizing execution thread swaps pre-acquisition identifier-field and synchronization-state-field contents for an identifier of the synchronizing execution thread and a predetermined busy code; and

b) if the pre-acquisition synchronization-state-field contents are the busy code, performs a slow-meta-lock operation in which the synchronizing execution thread copies a release value from the release-value-reception field of the synchronizing execution thread'"'"'s execution environment or from the release-value-transmission field of a predecessor thread'"'"'s execution environment;

ii) produces a release value by executing in accordance with the pre-acquisition synchronization-state-field contents if the pre-acquisition synchronization-state-field contents are not the busy code and by otherwise executing in accordance with the copied release value; and

iii) ends with a meta-lock-release operation, in which the synchronizing execution thread;

a) performs an atomic compare-and-swap operation that;

(1) is successful, replacing pre-release contents of the object'"'"'s identifier field and replacing pre-release contents of the object'"'"'s synchronization-state field with a synchronization-state code other than the busy code, if the pre-release contents of the object'"'"'s identifier field identify the synchronizing execution thread and the pre-release contents of the object'"'"'s synchronization-state field are the busy code; and

(2) is otherwise unsuccessful and does not replace the pre-release contents of the object'"'"'s identifier and synchronization-state fields; and

b) if the atomic compare-and-swap operation is unsuccessful, performs a slow-meta-lock-release operation, in which the synchronizing execution thread makes a determination of whether the contents of a successor-identifier field in its execution environment identify a successor thread and;

(1) if so, places a release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

(2) if not, places the release value in the release-value-transmission field of its own execution environment.

2. A computer system as defined in claim 1 wherein the release-value-reception and -transmission fields are the same field.

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

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

4. A computer system as defined in claim 1 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

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

A) the slow-meta-lock-acquisition operation includes making a determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment;

B) if so, the field from which the synchronizing execution thread copies the release value is the release-value-transmission field of the predecessor thread'"'"'s execution environment; and

C) if not, the field from which the synchronizing execution thread copies the release value is the release-value-reception field of the synchronizing execution thread'"'"'s execution environment.

6. A computer system as defined in claim 5 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

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

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

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

A. each execution environment allocated to a thread includes a release-value-received field;

B. the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C. the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

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

A. each execution environment allocated to a thread includes a release-value-ready field;

B. the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C. the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

10. A computer system as defined in claim 1 wherein, when any thread is synchronized on a given object at the end of any said monitor-access operation performed on that object, that monitor-access operation results in a linked lock-record list, associated with that object, that comprises a lock record associated with each such thread.

11. A computer system as defined in claim 10 wherein each lock record associated with a thread includes an owner field, which contains an identifier of the thread with which the lock record is associated.

12. A computer system as defined in claim 11 wherein the identifier contained in the owner field of a lock record is a pointer to the execution environment of the thread with which that lock record is identified.

13. A computer system as defined in claim 10 wherein one said monitor-access operation is a locking operation, which results in the linked list'"'"'s beginning with a lock record associated with the synchronizing execution thread.

14. A computer system as defined in claim 10 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

15. A computer system as defined in claim 10 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon in which the atomic compare-and-swap operation is unsuccessful, the release value placed into an execution environment during the resultant slow-meta-lock-release operation includes a linked-list identifier that identifies the linked lock-record list associated with that object.

16. A computer system as defined in claim 15 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

17. A computer system as defined in claim 16 wherein the linked-list identifier is an identifier of the first lock record in the linked list.

18. A computer system as defined in claim 17 wherein the identifier of the first lock record in the linked list is a pointer to the first lock record in the linked list.

19. A computer system as defined in claim 18 wherein the linked-list identifier is a truncated pointer to the first lock record in the linked list.

20. A method of generating object code comprising the steps of:

A) in response to source code that calls for execution of multiple execution threads, producing object code that for each thread directs a processor to allocate an execution environment that includes a successor-identifier field, a release-value-reception field, and a release-value-transmission field;

B) 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 an identifier field and a synchronization-state field; and

C) in response to source code that calls for a synchronizing execution thread to perform any one of a set of at least one monitor-access operation with respect to the object, producing object code that directs a processor to perform a monitor-access operation that;

i) begins with a meta-lock-acquisition operation in which the synchronizing execution thread;

a) performs an atomic swap operation in which the synchronizing execution thread swaps pre-acquisition identifier-field and synchronization-state-field contents for an identifier of the synchronizing execution thread and a predetermined busy code; and

b) if the pre-acquisition synchronization-state-field contents are the busy code, performs a slow-meta-lock operation in which the synchronizing execution thread copies a release value from the release-value-reception field of the synchronizing execution thread'"'"'s execution environment or from the release-value-transmission field of a predecessor thread'"'"'s execution environment;

ii) produces a release value by executing in accordance with the pre-acquisition synchronization-state-field contents if the pre-acquisition synchronization-state-field contents are not the busy code and by otherwise executing in accordance with the copied release value; and

iii) ends with a meta-lock-release operation, in which the synchronizing execution thread;

a) performs an atomic compare-and-swap operation that;

(1) is successful, replacing pre-release contents of the object'"'"'s identifier field and replacing pre-release contents of the object'"'"'s synchronization-state field with a synchronization-state code other than the busy code, if the pre-release contents of the object'"'"'s identifier field identify the synchronizing execution thread and the pre-release contents of the object'"'"'s synchronization-state field are the busy code; and

(2) is otherwise unsuccessful and does not replace the pre-release contents of the object'"'"'s identifier and synchronization-state fields; and

b) if the atomic compare-and-swap operation is unsuccessful, performs a slow-meta-lock-release operation, in which the synchronizing execution thread makes a determination of whether the contents of a successor-identifier field in its execution environment identifies a successor thread and;

(3) if so, places a release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

(4) if not, places the release value in the release-value-transmission field of its own execution environment.

21. A method as defined in claim 20 wherein the release-value-reception and -transmission fields are the same field.

22. A method as defined in claim 20 wherein:

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

23. A method as defined in claim 20 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

24. A method as defined in claim 20 wherein:

A) the slow-meta-lock-acquisition operation includes making a determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment;

B) if so, the field from which the synchronizing execution thread copies the release value is the release-value-transmission field of the predecessor thread'"'"'s execution environment; and

C) if not, the field from which the synchronizing execution thread copies the release value is the release-value-reception field of the synchronization execution thread'"'"'s execution environment.

25. A method as defined in claim 24 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

26. A method as defined in claim 24 wherein:

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

27. A method as defined in claim 24 wherein:

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

28. A method as defined in claim 27 wherein:

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

29. A method as defined in claim 20 wherein, when any thread is synchronized on a given object at the end of any said monitor-access operation performed on that object, that monitor-access operation results in a linked lock-record list, associated with that object, that comprises a lock record associated with each such thread.

30. A method as defined in claim 29 wherein each lock record associated with a thread includes an owner field, which contains an identifier of the thread with which the lock record is associated.

31. A method as defined in claim 30 wherein the identifier contained in the owner field of a lock record is a pointer to the execution environment of the thread with which that lock record is identified.

32. A method as defined in claim 29 wherein one said monitor-access operation is a locking operation, which results in the linked list'"'"'s beginning with a lock record associated with the synchronizing execution thread.

33. A method as defined in claim 29 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

34. A method as defined in claim 29 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon in which the atomic compare-and-swap operation is unsuccessful, the release value placed into an execution environment during the resultant slow-meta-lock-release operation includes a linked-list identifier that identifies the linked lock-record list associated with that object.

35. A method as defined in claim 34 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

36. A method as defined in claim 35 wherein the linked-list identifier is an identifier of the first lock record in the linked list.

37. A method as defined in claim 36 wherein the identifier of the first lock record in the linked list is a pointer to the first lock record in the linked list.

38. A method as defined in claim 37 wherein the linked-list identifier is a truncated pointer to the first lock record in the linked list.

39. 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 execution of multiple execution threads, produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment that includes a successor-identifier field, a release-value-reception field, and a release-value-transmission field;

B) 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 an identifier field and a synchronization-state field; and

C) in response to electrical signals representing source code that calls for a synchronizing execution thread to perform any one of a set of at least one monitor-access operation with respect to the object, produces electrical signals representing object code that directs a processor to perform a monitor-access operation that;

i) begins with a meta-lock-acquisition operation in which the synchronizing execution thread;

a) performs an atomic swap operation in which the synchronizing execution thread swaps pre-acquisition identifier-field and synchronization-state-field contents for an identifier of the synchronizing execution thread and a predetermined busy code; and

b) if the pre-acquisition synchronization-state-field contents are the busy code, performs a slow-meta-lock operation in which the synchronizing execution thread copies a release value from the release-value-reception field of the synchronizing execution thread'"'"'s execution environment or from the release-value-transmission field of a predecessor thread'"'"'s execution environment;

ii) produces a release value by executing in accordance with the pre-acquisition synchronization-state-field contents if the pre-acquisition synchronization-state-field contents are not the busy code and by otherwise executing in accordance with the copied release value; and

iii) ends with a meta-lock-release operation, in which the synchronizing execution thread;

a) performs an atomic compare-and-swap operation that;

(1) is successful, replacing pre-release contents of the object'"'"'s identifier field and replacing pre-release contents of the object'"'"'s synchronization-state field with a synchronization-state code other than the busy code, if the pre-release contents of the object'"'"'s identifier field identify the synchronizing execution thread and the pre-release contents of the object'"'"'s synchronization-state field are the busy code; and

(2) is otherwise unsuccessful and does not replace the pre-release contents of the object'"'"'s identifier and synchronization-state fields; and

b) if the atomic compare-and-swap operation is unsuccessful, performs a slow-meta-lock-release operation, in which the synchronizing execution thread makes a determination of whether the contents of a successor-identifier field in its execution environment identifies a successor thread and;

(1) if so, places a release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

(2) if not, places the release value in the release-value-transmission field of its own execution environment.

40. A computer data signal as defined in claim 39 wherein the release-value-reception and -transmission fields are the same field.

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

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

42. A computer data signal as defined in claim 39 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

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

A) the slow-meta-lock-acquisition operation includes making a determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment;

B) if so, the field from which the synchronizing execution thread copies the release value is the release-value-transmission field of the predecessor thread'"'"'s execution environment; and

C) if not, the field from which the synchronizing execution thread copies the release value is the release-value-reception field of the synchronizing execution thread'"'"'s execution environment.

44. A computer data signal as defined in claim 43 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

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

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

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

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution threads places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

47. A computer data signal as defined in claim 46 wherein:

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

48. A computer data signal as defined in claim 39 wherein, when any thread is synchronized on a given object at the end of any said monitor-access operation performed on with that object, that comprises a lock record associated with each such thread.

49. A computer data signal as defined in claim 48 wherein each lock record associated with a thread includes an owner field, which contains an identifier of the thread with which the lock record is associated.

50. A computer data signal as defined in claim 49 wherein the identifier contained in the owner field of a lock record is a pointer to the execution environment of the thread with which that lock record is identified.

51. A computer data signal as defined in claim 48 wherein one said monitor-access operation is a locking operation, which results in the linked list'"'"'s beginning with a lock record associated with the synchronizing execution thread.

52. A computer data signal as defined in claim 48 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

53. A computer data signal as defined in claim 48 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon in which the atomic compare-and-swap operation is unsuccessful, the release value placed into an execution environment during the resultant slow-meta-lock-release operation includes a linked-list identifier that identifies the linked lock-record list associated with that object.

54. A computer data signal as defined in claim 53 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

55. A computer data signal as defined in claim 54 wherein the linked-list identifier is an identifier of the first lock record in the linked list.

56. A computer data signal as defined in claim 55 wherein the identifier of the first lock record in the linked list is a pointer to the first lock record in the linked list.

57. A computer data signal as defined in claim 56 wherein the linked-list identifier is a truncated pointer to the first lock record in the linked list.

58. 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 execution of multiple execution threads, produces electrical signals representing object code that for each thread directs a processor to allocate an execution environment that includes a successor-identifier field, a release-value-reception field, and a release-value-transmission field;

B) 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 an identifier field and a synchronization-state field; and

C) in response to electrical signals representing source code that calls for a synchronizing execution thread to perform any one of a set of at least one monitor-access operation with respect to the object, produces electrical signals representing object code that directs a processor to perform a monitor-access operation that;

i) begins with a meta-lock-acquisition operation in which the synchronizing execution thread;

a) performs an atomic swap operation in which the synchronizing execution thread swaps pre-acquisition identifier-field and synchronization-state-field contents for an identifier of the synchronizing execution thread and a predetermined busy code; and

b) if the pre-acquisition synchronization-state-field contents are the busy code, performs a slow-meta-lock operation in which the synchronizing execution thread copies a release value from the release-value-reception field of the synchronizing execution thread'"'"'s execution environment or from the release-value-transmission field of a predecessor thread'"'"'s execution environment;

ii) produces a release value by executing in accordance with the pre-acquisition synchronization-state-field contents if the pre-acquisition synchronization-state-field contents are not the busy code and by otherwise executing in accordance with the copied release value; and

iii) ends with a meta-lock-release operation, in which the synchronizing execution thread;

a) performs an atomic compare-and-swap operation that;

(1) is successful, replacing pre-release contents of the object'"'"'s identifier field and replacing pre-release contents of the object'"'"'s synchronization-state field with a synchronization-state code other than the busy code, if the pre-release contents of the object'"'"'s identifier field identify the synchronizing execution thread and the pre-release contents of the object'"'"'s synchronization-state field are the busy code; and

(2) is otherwise unsuccessful and does not replace the pre-release contents of the object'"'"'s identifier and synchronization-state fields; and

b) if the atomic compare-and-swap operation is unsuccessful, performs a slow-meta-lock-release operation, in which the synchronizing execution thread makes a determination of whether the contents of a successor-identifier field in its execution environment identifies a successor thread and;

(1) if so, places a release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

(2) if not, places the release value in the release-value-transmission field of its own execution environment.

59. A storage medium as defined in claim 58 wherein the release-value-reception and -transmission fields are the same field.

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

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

61. A storage medium as defined in claim 58 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

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

A) the slow-meta-lock-acquisition operation includes making a determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment;

B) if so, the field from which the synchronizing execution thread copies the release value is the release-value-transmission field of the predecessor thread'"'"'s execution environment; and

C) if not, the field from which the synchronizing execution thread copies the release value is the release-value-reception field of the synchronizing execution thread'"'"'s execution environment.

63. A storage medium as defined in claim 62 wherein the synchronizing execution thread makes the determination of whether the contents of the successor-identifier field in its execution environment identifies a successor thread by concluding that its execution environment does contain a successor identifier if a successor-identifier field therein does not contain a predetermined no-identifier-indicating value.

64. A storage medium as defined in claim 62 wherein:

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

65. A storage medium as defined in claim 62 wherein:

A) each execution environment allocated to a thread includes a release-value-received field;

B) the slow-meta-lock-release operation includes placing a predetermined reception-indicating value in the release-value-received field of the execution environment of the synchronizing execution thread'"'"'s successor when the synchronizing execution thread places the release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

C) the slow-meta-lock-acquisition operation includes preceding the synchronizing execution thread'"'"'s copying of the release value from the release-value-reception field with the synchronizing execution thread'"'"'s reading of the predetermined reception-indicating value from the release-value-received field.

66. A storage medium as defined in claim 65 wherein:

A) each execution environment allocated to a thread includes a release-value-ready field;

B) the slow-meta-lock-release operation includes placing a predetermined ready-indicating value in the release-value-ready field of the synchronizing execution thread'"'"'s execution environment when the synchronizing execution thread places the release value in the release-value-transmission field of the synchronizing execution thread'"'"'s execution environment; and

C) the determination of whether the predecessor thread has updated the release-value-transmission field of the predecessor thread'"'"'s execution environment is based on the contents of the release-value-ready field of the predecessor thread'"'"'s execution environment.

67. A storage medium as defined in claim 58 wherein, when any thread is synchronized on a given object at the end of any said monitor-access operation performed on that object, that monitor-access operation results in a linked lock-record list, associated with that object, that comprises a lock record associated with each such thread.

68. A storage medium as defined in claim 67 wherein each lock record associated with a thread includes an owner field, which contains an identifier of the thread with which the lock record is associated.

69. A storage medium as defined in claim 68 wherein the identifier contained in the owner field of a lock record is a pointer to the execution environment of the thread with which that lock record is identified.

70. A storage medium as defined in claim 67 wherein one said monitor-access operation is a locking operation, which results in the linked list'"'"'s beginning with a lock record associated with the synchronizing execution thread.

71. A storage medium as defined in claim 67 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

72. A storage medium as defined in claim 67 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon in which the atomic compare-and-swap operation is unsuccessful, the release value placed into an execution environment during the resultant slow-meta-lock-release operation includes a linked-list identifier that identifies the linked lock-record list associated with that object.

73. A storage medium as defined in claim 72 wherein, if any thread is synchronized on a given object at the end of any said monitor-access operation thereon and the atomic compare-and-swap operation of the meta-lock-release operation with which that monitor-access operation ends is successful, that meta-lock-release operation places in the object'"'"'s identifier field a linked-list identifier that identifies the linked lock-record list associated with that object.

74. A storage medium as defined in claim 73 wherein the linked-list identifier is an identifier of the first lock record in the linked list.

75. A storage medium as defined in claim 74 wherein the identifier of the first lock record in the linked list is a pointer to the first lock record in the linked list.

76. A storage medium as defined in claim 75 wherein the linked-list identifier is a truncated pointer to the first lock record in the linked list.

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

A) means for, in response to electrical signals representing source code that calls for execution of multiple execution threads, producing electrical signals representing object code that for each thread directs a processor to allocate an execution environment that includes a successor-identifier field, a release-value-reception field, and a release-value-transmission field;

B) means for, in response to electrical signals representing source code that calls for allocation of an object on which thread execution can be synchronized, producing electrical signals representing object code that directs a processor to allocate to the object an object structure that includes an identifier field and a synchronization-state field; and

C) means for, in response to electrical signals representing source code that calls for a synchronizing execution thread to perform any one of a set of at least one monitor-access operation with respect to the object, producing electrical signals representing object code that directs a processor to perform a monitor-access operation that;

i) begins with a meta-lock-acquisition operation in which the synchronizing execution thread;

a) performs an atomic swap operation in which the synchronizing execution thread swaps pre-acquisition identifier-field and synchronization-state-field contents for an identifier of the synchronizing execution thread and a predetermined busy code; and

b) if the pre-acquisition synchronization-state-field contents are the busy code, performs a slow-meta-lock operation in which the synchronizing execution thread copies a release value from the release-value-reception field of the synchronizing execution thread'"'"'s execution environment or from the release-value-transmission field of a predecessor thread'"'"'s execution environment;

ii) produces a release value by executing in accordance with the pre-acquisition synchronization-state-field contents if the pre-acquisition synchronization-state-field contents are not the busy code and by otherwise executing in accordance with the copied release value; and

iii) ends with a meta-lock-release operation, in which the synchronizing execution thread;

a) performs an atomic compare-and-swap operation that;

(1) is successful, replacing pre-release contents of the object'"'"'s identifier field and replacing pre-release contents of the object'"'"'s synchronization-state field with a synchronization-state code other than the busy code, if the pre-release contents of the object'"'"'s identifier field identify the synchronizing execution thread and the pre-release contents of the object'"'"'s synchronization-state field are the busy code; and

(2) is otherwise unsuccessful and does not replace the pre-release contents of the object'"'"'s identifier and synchronization-state fields; and

b) if the atomic compare-and-swap operation is unsuccessful, performs a slow-meta-lock-release operation, in which the synchronizing execution thread makes a determination of whether the contents of a successor-identifier field in its execution environment identifies a successor thread and;

(1) if so, places a release value in the release-value-reception field of the successor thread'"'"'s execution environment; and

(2) if not, places the release value in the release-value-transmission field of its own execution environment.