Expedited object locking and unlocking6314563
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
What is claimed is:
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.
Description
BACKGROUND OF THE INVENTION
The present invention is directed to compiling and interpreting computer programs. It particularly concerns synchronization between execution threads.
FIG. 1 depicts a typical computer system 10. A microprocessor 11 receives data, and instructions for operating on them, from on-board cache memory or further cache memory 12, possibly through the mediation of a cache controller 13, which can in turn receive such data from system read/write memory ("RAM") 14 through a RAM controller 15, or from various peripheral devices through a system bus 16.
The RAM 14's data and instruction contents will ordinarily have been loaded from peripheral devices such as a system disk 17. Other sources include communications interface 18, which can receive instructions and data from other computer systems.
The instructions that the microprocessor executes are machine instructions. Those instructions are ultimately determined by a programmer, but it is a rare programmer who is familiar with the specific machine instructions in which his efforts eventually result. More typically, the programmer writes higher-level-language "source code" from which a computer software-configured to do so generates those machine instructions, or "object code."
FIG. 2 represents this sequence. FIG. 2's block 20 represents a compiler process that a computer performs under the direction of compiler object code. That object code is typically stored on the system disk 17 or some other machine-readable medium and by transmission of electrical signals is loaded into RAM 15 to configure the computer system to act as a compiler. But the compiler object code's persistent storage may instead be in a server system remote from the machine that performs the compiling. The electrical signals that carry the digital data by which the computer systems exchange the code are exemplary forms of carrier waves transporting the information.
The compiler converts source code into further object code, which it places in machine-readable storage such as RAM 15 or disk 17. A computer will follow that object code's instructions in performing an application 21 that typically generates output from input. The compiler 20 is itself an application, one in which the input is source code and the output is object code, but the computer that executes the application 21 is not necessarily the same as the one that performs the compiler process.
The source code need not have been written by a human programmer directly. Integrated development environments often automate the source-code-writing process to the extent that for many applications very little of the source code is produced "manually." As will be explained below, moreover, the "source" code being compiled may sometimes be low-level code, such as the byte-code input to the Java.TM. virtual machine, that programmers almost never write directly. (Sun, the Sun Logo, Sun Microsystems, and Java are trademarks or registered trademarks of Sun Microsystems, Inc., in the United States and other countries.) Moreover, although FIG. 2 may appear to suggest a batch process, in which all of an application's object code is produced before any of it is executed, the same processor may both compile and execute the code, in which case the processor may execute its compiler application concurrently with--and, indeed, in a way that can be dependent upon--its execution of the compiler's output object code.
So the sequence of operations by which source code results in machine-language instructions may be considerably more complicated than one may infer from FIG. 2. To give a sense of the complexity that can be involved, we discuss by reference to FIG. 3 an example of one way in which various levels of source code can result in the machine instructions that the processor executes. The human application programmer produces source code 22 written in a high-level language such as the Java programming language. In the case of the Java programming language, a compiler 23 converts that code into "class files." These predominantly include routines written in instructions, called "byte codes" 24, for a "virtual machine" that various processors can emulate under appropriate instructions. This conversion into byte codes is almost always separated in time from those codes' execution, so that aspect of the sequence is depicted as occurring in a "compile-time environment" 25 separate from a "run-time environment" 26, in which execution occurs.
Most typically, the class files are run by a processor under control of a computer program known as a virtual machine 27, whose purpose is to emulate a machine from whose instruction set the byte codes are drawn. Much of the virtual machine's action in executing these codes is most like what those skilled in the art refer to as "interpreting," and FIG. 3 shows that the virtual machine includes an "interpreter" 28 for that purpose. The resultant instructions typically involve calls to a run-time system 29, which handles matters such as loading new class files as they are needed and performing "garbage collection," i.e., returning allocated memory to the system when it is no longer needed.
Many virtual-machine implementations also actually compile the byte codes concurrently with the resultant object code's execution, so FIG. 3 depicts the virtual machine as additionally including a "just-in-time" compiler 30. It may be that the resultant object code will make low-level calls to the run-time system, as the drawing indicates. In any event, the code's execution will include calls to the local operating system 31.
It is not uncommon for a virtual-machine implementation both to compile and to interpret different parts of the same byte-code program. And, although the illustrated approach of first compiling the high-level code into byte codes is typical, the Java programming language is sometimes compiled directly into native machine code. So there is a wide range of mechanisms by which source code--whether high-level code or byte code--can result in the actual native machine instructions that the hardware processor executes. The teachings to be set forth below can be used in all of them, many of which, as was just explained, do not fit neatly into either the compiler or interpreter category. So we will adopt the term compiler interpreter to refer to all such mechanisms, whether they be compilers, interpreters, hybrids thereof, or combinations of any or all of these.
In actual operation, the typical computer program does not have exclusive control over the machine whose operation it directs; a typical user concurrently runs a number of application programs. Of course, a computer that is not a multiprocessor machine can at any given instant be performing the instructions of only one program, but a typical multitasking approach employed by single-processor machines is for each concurrently running program to be interrupted from time to time to allow other programs to run, with the rate of such interruption being high enough that the programs' executions appear simultaneous to the human user.
The task of scheduling different applications programs' executions typically falls to the computer's operating system. In this context, the different concurrently running programs are commonly referred to as different "processes." In addition to scheduling, the operating system so operates the computer that the various processes' physical code, data, and stack spaces do not overlap. So one process cannot ordinarily interfere with another. The only exceptions to this rule occur when a process specifically calls an operating-system routine ("makes a system call") intended for inter-process communication.
The operating system's scheduling function can be used to divide processor time not only among independent processes but also among a single process's different "threads of execution." Different execution threads are like different processes in that the operating system divides time among them so that they can take turns executing. They therefore have different call stacks, and the operating system has to swap out register contents when it switches between threads. But a given process's different execution threads share the same data space, so they can have access to the same data without operating-system assistance. Indeed, they also share the same code space and can therefore execute the same instructions, although different threads are not in general at the same point in those instructions' execution at the same time. By using threads to take advantage of the operating system's scheduling function, the programmer can simplify the task of programming a plurality of concurrent operations; he does not have to write the code that explicitly schedules the threads' concurrent executions.
FIG. 4 is a Java programming language listing of a way in which a programmer may code concurrent threads. The steps in that drawing's fourth and fifth lines create new instances of the classes Transferer and Totaler and assign these objects to variables transferer and totaler, respectively. The Transferor and Totaler classes can be used to create new threads of control, because they extend the class Thread, as the nineteenth and twenty-ninth lines indicate. When a Thread object's start( ) method is called, its run( ) method is executed in a new thread of control. So the sixth line's transferor.start( ) statement results in execution of the method, defined in the twenty-second through twenty-seventh lines, that transfers an amount back and forth between two member variables, account_1 and account_2, of an object of the class Bank. And the seventh line's totaler.start( ) statement results in execution of a method, defined in the thirty-second through thirty-fourth lines, that prints out the total of those member variables' values. Note that neither method refers to the other; by taking advantage of the programming language's thread facility, the programmer is relieved of the burden of scheduling.
There is not in general any defined timing between two concurrently running threads, and this is often the intended result: the various threads are intended to execute essentially independently of each other. But there are also many instances in which total independence would yield unintended results. For example, the b.transfer( ) method is intended to simulate internal transfers back and forth between two of a bank's accounts, while the b.total( ) method is intended to print out the total of the bank's account balances. Clearly, completely internal transfers should not change the bank's account total. But consider what would happen if the transferer thread's execution is interrupted between the fourteenth and fifteenth lines, i.e., between the time the amount is subtracted from one account and the time it is added to the other account. Intervening execution of the totaler thread could print the bank's total out as a value different from the one that the simulation is intended to represent: the state of the simulated bank would be inconsistent.
To prevent such inconsistent results, mechanisms for inter-thread communication have been developed. In the example, the thirteenth and seventeenth lines include the "synchronized" modifier. This directs the compiler/interpreter to synchronize its implementation of the transfer( ) and total( ) methods: before a thread begins execution of either method, it must obtain an exclusive "lock" on the object on which the instance method is called. So no other thread can execute a synchronized method on that object until the first thread releases its lock. If a transferer thread is in the midst of executing b.transfer( ), for instance, it must have a lock on object b, and this means that the totaler thread will be blocked from executing b.total( ) until the transferer thread's execution of transfer( ) has been completed.
Those familiar with the Java programming language will additionally recognize that a thread can lock an object even when it is not executing one of that object's synchronized methods. FIG. 5 is a listing of source code for a class Bar containing two methods. The "synchronized" statement in the onlyMe( ) method indicates that an execution must obtain a lock on the object f before it executes the subsequent code block. which calls the doSomething( ) method. FIG. 6 shows a possible result of compiling the onlyMe( ) method to Java virtual machine byte-code instructions. The fourth and eighth lines contain the mnemonics for the byte codes that direct the executing virtual machine respectively to acquire and release a lock on object f, which the topmost evaluation-stack entry references.
The particular way in which the compiler/interpreter obtains a lock on an object (also referred to as acquiring a "monitor" associated with the object) depends on the particular compiler/interpreter implementation. (It is important at this point to recall that we are using the term compiler/interpreter in a broad sense to include, for instance, the functions performed by a Java virtual machine in executing the so-called byte code into which the Java Programming language code is usually compiled; it is that process that implements monitor acquisition in response to the byte code whose mnemonic is monitorenter. Still, Java programming language code also is occasionally compiled directly into native machine code without the intervening step of byte-code generation. Indeed, monitor acquisition and release in the case of FIG. 4's program would be performed without any explicit byte-code instruction for it, such as monitorexit, even if, as is normally the case, most of that code is compiled into byte code.)
The most natural way to implement a monitor is to employ available operating-system facilities for inter-thread and -process communication. Different operating systems provide different facilities for this purpose, but most of their applications-programming interfaces ("APIs") provide routines for operating on system data structures called "mutexes" (for "mutual exclusion"). A thread or process makes a system call by which it attempts to acquire a particular mutex that it and other threads and/or processes associate with a particular resource. The nature of mutex operations is such that an attempt to acquire a mutex is delayed (or "blocked") if some other process or thread currently owns that particular mutex; when a mutex acquisition attempt completes, the process or thread that performed the acquisition may safely assume that no other process or thread will complete an acquisition operation until the current process or thread releases ownership of the mutex. If all processes or threads that access a shared resource follow a convention of considering a particular shared mutex to "protect" the resource--i.e., if every process or thread accesses the resource only when it owns the mutex--then they will avoid accessing the resource concurrently.
The system-mutex approach has been employed for some time and has proven effective in a wide variety of applications. But it must be used judiciously if significant performance penalties or programming difficulties are to be avoided. Since the number of objects extant at a given time during a program's execution can be impressively large, for instance, allocating a mutex to each object to keep track of its lock state would result in a significant run-time memory cost.
So workers in the field have attempted to minimize any such disincentives by adopting various monitor-implementation approaches that avoid storage penalties to as great an extent as possible. One approach is to avoid allocating any monitor space to an object until such time as a method or block synchronized on it is actually executed. When a thread needs to acquire a lock on an object under this approach, it employs a hash value for that object to look it up in a table containing pointers to monitor structures. If the object is already locked or currently has some other need for a monitor structure, the thread will find that monitor structure by consulting the table and performing the locking operation in accordance with that monitor structure's contents. Otherwise, the thread allocates a monitor structure and lists it in the table. When synchronization activity on the object ends, the monitor structure's space is returned to the system or a pool of monitor structures that can be used for other objects.
Since this approach allocates monitor structures only to objects that currently are the subject of synchronization operations, the storage penalty is minimal; although the number of extant objects at any given time can be impressively large, the number of objects that a given thread holds locked at one time is ordinarily minuscule in comparison, as is the number of concurrent threads. Unfortunately, although this approach essentially eliminates the excessive storage cost that making objects lockable could otherwise exact, it imposes a significant performance cost. Specifically, the time cost of the table lookup can be significant. It also presents scalability problems, since there can be contention for access to the table itself; the table itself must therefore be locked and thus can cause a bottleneck if the number of threads becomes large.
And the nature of object-oriented programming tends to result in extension of this performance cost beyond single-thread programming. There are classes of programming objects that are needed time and again in a wide variety of programming projects, and legions of programmers have duplicated effort in providing the same or only minimally different routines. One of the great attractions of object-oriented programming is that it lends itself to the development of class libraries. Rather than duplicate effort, a programmer can employ classes selected from a library of classes that are widely applicable and thoroughly tested.
But truly versatile class libraries need to be so written that each class is "thread safe." That is, any of that class's methods that could otherwise yield inconsistent results when methods of an object of that class are run in different threads will have to be synchronized. And unless the library provides separate classes for single-thread use, the performance penalty that synchronized methods exact will be visited not only upon multiple thread programs but upon single-thread programs as well.
An approach that to a great extent avoids these problems is proposed by Bacon et al., "Thin Locks: Feather Weight Synchronization for Java," Proc. ACM SIGPLAN '98, Conference on Programming Language Design and Implementation (PLDI), pp. 258-68, Montreal, June 1998. That approach is based on the recognition that most synchronization operations are locking or unlocking operations, and most such operations are uncontended, i.e., involve locks on objects that are not currently locked or are locked only by the same thread. (In the Java virtual machine, a given thread may obtain multiple simultaneous locks on the same object, and a count of those locks is ordinarily kept in order to determine when the thread no longer needs exclusive access to the object.) Given that these are the majority of the situations of which the monitor structure will be required to keep track, the Bacon et al. approach is to include in the object's header a monitor structure that is only large enough (twenty-four bits) to support uncontended locking. That monitor includes a thread identifier, a lock count, and a "monitor shape bit," which indicates whether that field does indeed contain all of the monitor information currently required.
When a thread attempts to obtain a lock, it first inspects the object's header to determine whether the monitor-shape bit, lock count, and thread identifier are all zero and thereby indicate that the object is unlocked and subject to no other synchronization operation. If they are, as is usually the case, the thread places an index identifying itself in the thread-identifier field, and any other thread similarly inspecting that header will see that the object is already locked. It happens that in most systems this header inspection and conditional storage can be performed by a single atomic "compare-and-swap" operation, so obtaining a lock on the object consists only of a single atomic operation if no lock already exists. If the monitor-shape bit is zero and the thread identifier is not zero but identifies the same thread as the one attempting to obtain the lock, then the thread simply retains the lock but performs the additional step of incrementing the lock count. Again, the lock-acquisition operation is quite simple. These two situations constitute the majority of locking operations.
But the small, twenty-four-bit header monitor structure does not have enough room for information concerning contended locking; there is no way to list the waiting threads so that they can be notified that the first thread has released the lock by writing zeroes into that header field. In the case of a contended lock, this forces the Bacon et al. arrangement to resort to "spin locking," also known as "busy-waits." Specifically, a thread that attempts to lock an object on which some other thread already has a lock repeatedly performs the compare-and-swap operation on the object-header monitor structure until it finds that the previous lock has been released. This is obviously a prodigal use of processor cycles, but it is necessary so long as the monitor structure does not have enough space to keep track of waiting threads.
When the previously "spinning" thread finally does obtain access to the object, the Bacon et al. arrangement deals with the busy-wait problem by having that thread allocate a larger monitor structure to the object, placing an index to the larger structure in the header, and setting the object's monitor-shape bit to indicate that it has done so, i.e., to indicate that the monitor information now resides outside the header. Although this does nothing to make up for the thread's previous spinning, it is based on the assumption that the object is one for which further lock contention is likely, so the storage penalty is justified by the future spinning avoidance that the larger structure can afford.
A review of the Bacon et al. approach reveals that its performance is beneficial for the majority of synchronization operations, i.e., for uncontested or nested locks. But it still presents certain difficulties. In the first place, although the object-header-resident monitor structure is indeed relatively small in comparison with a fuller-featured monitors, it still consumes twenty-four bits in each and every object. Since this is three bytes out of an average object size of, say, forty bytes, that space cost is non-negligible. Additionally, the relatively small monitor size forces a compromise between monitor size and contention performance. As was mentioned above, initial contention results in the significant performance penalty that busy-waits represent. The Bacon et al. arrangement avoids such busy-waits for a given object after the first contention, but only at the expense of using the larger monitor structure, which needs to remain allocated to that object unless the previously contended-for object is again to be made vulnerable to busy-waits. In other words, the Bacon et al. arrangement keeps the object's monitor structure "inflated" because the object's vulnerability to busy-waits would return if the monitor were "deflated."
Finally, the only types of synchronization operations with which the Bacon et al. approach can deal are the lock and unlock operations. It provides no facilities for managing other synchronization operations, such as those known as "wait," "notify," and "notifyAll"; it assumes the existence of heavy-weigh t monitor structu res for those purposes.
SUMMARY OF THE INVENTION
The above-identified parent application claims a method that can be used for a wide variety of synchronization operations but avoids busy-waits, imposes much less per-object storage-space cost, and exhibits better worst-case storage behavior. The present invention provides a way of affording that invention's advantages while in some situat ions avoiding the "meta-locking" delay that it sometimes involves.
Compiler/interpreters employing the parent application's approach allocate object structures in which the header includes a synchronization field, which can be as small as two bits, that can contain a code representing the object's synchronization state. The codes employed by the compiler/interpreter in the example to be described below, for instance, variously indicate that the object is locked, that threads are waiting to lock it or be "notified on" it, and that there are no locks or waiters.
Since this information is not alone enough to contain all of the information concerning the object's synchronization information when various threads are synchronized on the object, synchronization operations will involve access to monitor structures temporarily assigned to the object to support those operations. In accordance with the parent application's invention, a thread precedes access to such structures with what we call "meta-lock" acquisition. In that operation, a given thread attempting to begin a monitor-access operation performs a swap operation in which it replaces the synchronizationstate-field contents with a "busy"-valued synchronization-state code whose meaning is that the object is what we call "meta-locked," i.e., that a thread has acquired exclusive access to the resources needed to support synchronization on the object. In the same operation it replaces the contents of an identifier field in the object's header with an identifier of the thread performing the operation, i.e., of the thread attempting to acquire a meta-lock. In performing that swap the thread learns whether the object is already meta-locked and, if so, the identity of the immediate-predecessor contender for the meta-lock.
Preferably, the header field in which the thread identifier is thus written contains other information when the object is not meta-locked; header information swapped out (i.e., atomically read and displaced) by the first meta-lock-acquiring thread in writing its thread identifier into the object header preferably includes any information that the acquiring thread's monitor-access operation will modify and/or need as input. So the only part of the header required to be dedicated solely to supporting synchronization is a minimal (typically two- or three-bit) synchronization-state field.
If the synchronization-state code swapped out of the object's header in the meta-lock-acquisition operation is not the predetermined busy code--i.e., if there was not already a meta-lock in place--then the given thread concludes that it possesses the object's meta-lock, i.e., that it has exclusive access to the monitor data for that object. In that case, the monitor-access operation proceeds in accordance with the swapped-out synchronization-state field's contents and, preferably, with the header information displaced by that meta-lock-acquisition operation's swapping a thread identifier for prior header contents.
If the code swapped out of the header is the busy code, on the other hand, the given thread concludes that some other thread already owns the meta-lock on the object. So it must delay performance of the monitor access operation until it receives ownership from its predecessor, which may be the current owner or some intervening contender for the meta-lock. The given thread additionally concludes that it will not be able to consult the object header to read the synchronization state in which its predecessor leaves the object; if the predecessor were to record in the object header the synchronization state in which that predecessor's monitor-access operation leaves the object, it would thereby erase the busy code that the given thread has placed there, so any successor--i.e., any thread that attempts to acquire the meta-lock before the given thread releases it--would not be apprised of the meta-lock to which the given thread will succeed when its predecessor releases the meta-lock. So that thread arranges with its predecessor to receive that information by inter-thread communication through those threads' respective "execution environments," i.e., through the data structures that represent those threads' states.
Specifically, the given thread waits, if necessary, for its predecessor thread to write into the given or predecessor thread's execution environment the value that the synchronization-state word should have after the predecessor's monitor-access operation has been completed. When a thread (such as the given thread's predecessor) completes a monitor-access operation, it performs a meta-lock-release operation in which it uses a compare-and-swap operation. In that operation it places the synchronization-state-code results of its just-completed monitor-access operation in the object header's synchronization-state field if the comparison part of the compare-and-swap operation reveals there has been n o contender for the meta-lock. If there has been such a contender, though, the meta-lock-releasing thread places that code-and preferably other information as well--in its own execution environment if its immediate successor has not identified itself to the meta-lock-releasing thread by writing that successor's thread identifier into the releasing thread's execution environment.
So the given thread preferably first inspects the predecessor thread's execution environment for an indication that the predecessor's execution environment contains that code. If a thread performing the meta-lock-acquisition operation finds that the predecessor thread has not yet placed that information into that predecessor's execution environment, it places its thread identifier in the predecessor's execution environment and suspends itself. Eventually, its predecessor completes its monitor-access operation and finds in its meta-lock-release operation's compare-and-swap step that it has a contending successor, namely, the now-suspended given thread. The predecessor responds by determining whether the given thread has identified itself, in the manner just described. Since it has, the predecessor places the synchronization-state-code results of its now-finished monitor-access operation in the given thread's execution environment and arranges for that thread to be reactivated so that it can read the information thereby transferred. When the given thread is thereby reactivated, it performs its monitor-access operation, using the information thereby obtained.
Note that if several threads all attempt to acquire an unlocked meta-lock at approximately the same instant, the atomicity guarantee of the atomic swap instruction will impose an order on these threads. The thread that is first will read the original (unlocked) lock-word contents. The second thread will read the lock word written by the first thread and therefore know that the object is meta-locked, and, further, that the first thread is its predecessor. The third thread finds the second thread as its predecessor, and so on. Each thread in this order (other than the last) will discover that it is not the last thread, and it will "hand off" the meta-lock to its successor, passing through their execution environments the data that it would otherwise have written into the object header's lock word. That is, the successor will own the meta-lock, and it will proceed as if it had read from the object header's lock word the information that the predecessor has instead passed to it through one or the other of their execution environments.
As the description below will show, this approach is largely independent of the particular type of monitor structure that it guards and can beneficially be used with monitor structures that can be implemented on little more than a per-thread basis. By using a thread-identifier swap to contend for a meta-lock, the meta-lock-acquisition operation automatically sequences the meta-lock contenders on a first-come, first-served basis. Also, this approach takes advantage of the fact that each thread can be performing only one locking operation at a time; it uses the thread's execution environment to pass header information from one meta-lock-contending thread to the next. This enables it to avoid the need to reserve exclusive header space for any monitor data other than the minimal synchronization-state code. So this approach minimizes the storage cost of implementing a monitor and does so in a way that is applicable to a variety of synchronization operations with little performance penalty.
According to the present invention, we further minimize any performance penalty by omitting the meta-lock-acquisition and -release operations from some lock operations. This is accomplished by performing an atomic compare-and-swap operation on an objectheader field that includes the synchronization-state field. If successful, that operation replaces that field, which we call the "lock-word field," with a lock word in which the synchronization-state code indicates that the object is locked and not meta-locked, and this is all the header access needed for the locking operation: no meta-lock acquisition or release is necessary. The compare-and-swap operation is successful only if the synchronization-state field in the pre-replacement lock-word-field contents indicate, as they usually do, that the object is neither synchronized on nor meta-locked. In less-common cases, in which the object is already synchronized on or meta-locked, the locking operation proceeds as described above for monitor-access operations generally: it is guarded by meta-lock-acquisition and -release operations.
In accordance with another aspect of the invention, we are able to dispense with meta-lock acquisition and release in some lock-release operations. This, too, is achieved by performing an atomic compare-and-swap operation. If successful, that operation relaces the lock-word field with a lock word in which the synchronization-state code indicates that the object is neither locked nor meta-locked, this is all the header access needed for the unlocking operation: no meta-lock acquisition or release is necessary. As will be described in more detail below, the lock release's compare-and-swap operation is successful if, as is usually the case, 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. Otherwise, the lock-release operation proceeds as described above for monitor-access operations generally: it is guarded by meta-lock-acquisition and -release operations.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention description below refers to the accompanying drawings, of which:
FIG. 1, described above, is a block diagram of a computer system in which the present invention's teachings can be employed;
FIG. 2, described above, is a block diagram illustrating the relationship between a compiler, source code, and object code;
FIG. 3, described above, is a block diagram illustrating a more-complex mechanism for converting source code into object code and executing the object code;
FIG. 4, described above, is a listing of a Java programming language program that uses a synchronized method;
FIG. 5, described above, is a listing of a simple Java programming language program;
FIG. 6, described above, is a listing of the byte code into which FIG. 5's code would typically be compiled;
FIGS. 7A-K are diagrams of monitor resources as they change during a sequence of synchronization operations in which there is no contention for those resources;
FIG. 8 is a simplified C-language listing of the procedure employed for acquiring a meta-lock on the monitor resources;
FIGS. 9A-J are diagrams of an object structure and various threads' execution environments showing the results of meta-lock-acquisition and -release operations;
FIG. 10 is a simplified C-language listing of a routine for releasing a meta-lock; and
FIGS. 11A-F are diagrams of monitor resources as they change during a sequence of synchronization operations implemented in accordance with the present invention.
DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT
Before we discuss the meta-locking operations that the present invention can be used to minimize, we will consider some monitor-access operations that those operations can be used to guard. But those operations are only exemplary; the meta-locking operations neither depend greatly on nor dictate the nature of the monitor-access operations with which the meta-locking is used or on the monitor structures that support those operations.
In FIG. 7A, an object structure 40 includes memory locations in which the information related specifically to a particular object is principally stored. The "other object fields" portion contains the object's data members. In addition to these data members, which the programmer will have explicitly specified in defining the instance data members of the object's class, the object structure will typically include further, housekeeping information in a part of the data structure typically referred to as a "header."
The contents and format of the header structure depend on the particular virtual-machine implementation. For the sake of example, we assume that the header consists of two thirty-two-bit words. The first word is a pointer to an object representing the class to which the object belongs. The second word includes a hash field and an age field. If the object's hash-value-assigning method is called, the hash field contains the resultant value. That value thereafter remains unchanged, being used for purposes such as finding the object's entries in various hash tables. The age field indicates how many times the memory allocated to the object has been considered for garbage collection, i.e., how many times the virtual machine's run-time system has decided that the operating system should not reclaim the memory space allocated to the object structure. The header also includes a synchronization-state field 42, which in the illustrated embodiment is also part of the second word and is only two bits wide. For reasons that will become apparent, we refer to the second word as the "lock word" and to its hash and age fields together as the "identifier" field.
In the illustrated environment, the 00.sub.2 synchronization-state-field value that FIG. 7A depicts indicates that no thread is yet synchronized on the object: no lock has been acquired on the object, and there are no threads waiting for a lock or for what will presently be described as "notification" on it. We do assume, though, that three threads T1, T2, and T3 are currently running and will become synchronized on it. FIG. 7A therefore includes representations of data structures 44, 46, and 48, known as thread "execution environments," where the operating system stores data concerning those threads' states. (The drawings refer to execution environments 44, 46, and 48 as "EE.sub.T1," "EE.sub.T2," and "EE.sub.T3," respectively.) Whereas the number of objects for which memory is allocated at any given time can be extremely large, the number of threads existing at a given time is typically quite small. Execution-environment size is therefore relatively unimportant in comparison with object-structure size, and in most implementations an execution environment contains many fields (and is many times the size of, for instance, the typical object structure). But FIG. 7A specifically depicts only the fields germane to the subject of FIGS. 7A-K.
A given execution environment's free-lock-record field contains a pointer to a linked list of what we call "lock records" allocated to that execution environment. In the illustrated embodiment, a thread's initialization includes allocation of a pool of lock-record structures, such as lock record 50, that can be used for synchronization in a manner to be described below. Each lock record contains an owner field that identifies the thread to which it is allocated. Specifically, the owner field contains a pointer to that thread's execution environment. Execution environment 44's free-lock-records field contains a pointer to lock record 50, which is the first lock record in a linked list of lock records available for use by thread T1, and lock record 50's next-free field contains a pointer to the next lock record in that linked list. Lock records 52 and 54 are the lock records in the linked lists of available lock records allocated to threads T2 and T3, respectively.
When a thread obtains a lock on an object, it identifies itself as the holder of the lock by selecting a lock record from its pool and placing a pointer to that lock record in the object's header. Since this places that lock record in use, the thread removes that lock record from its linked list of available lock records: the thread replaces the contents of its execution environment's free-lock-records field with the contents of that lock record's next-free field. As will also be described below, though, subsequent synchronization operations by other threads may place those threads' lock records in a different linked list, one whose members belong to threads waiting in one way or another for access to the object, and the lock record additionally includes a next-LR field to support that linked list. When the lock record is initially allocated, this field contains a NULL value.
FIG. 7A represents the situation in which no synchronization activity is occurring. If in that situation thread T1 encounters code that calls a synchronized method on the object, thread T1 will need to acquire a lock on that object. FIG. 7B shows the result of thread T1's acquisition of that lock. As FIG. 7B shows, the illustrated embodiment's locking operation removes the hash- and age-field contents from the object structure 40's header. So as not to lose these values, the thread reads them before that removal. In the illustrated embodiment, it does so as part of what we call "meta-lock" acquisition, which precedes at least some types of monitor-access operations, such as object locking. As will be described below in connection with FIGS. 8 and 9A-J, the central purpose of meta-lock acquisition is to accord the thread exclusive access to resources, such as lock records, that support the monitor-access operation.
After reading the hash and age values as part of meta-lock acquisition, the thread stores them in a field provided for that purpose in the next available lock record. With the hash and age values thus stored, the thread can use the header's identifier field, which previously held them, to hold the pointer to the lock record 50. Actually, the identifier field consists of only thirty bits in total, so it can hold only the most-significant thirty bits of the (in this embodiment, thirty-two-bit) lock-record pointer. But this is adequate, because the illustrated embodiment's lock-record locations are known to be four-byte aligned; the last two bits of any are known always to have the value 00.sub.2, so the complete address of a lock record can be inferred from a truncated pointer containing only its most-significant thirty bits. Thread T1 employs a meta-lock-release operation, to be described below in connection with FIGS. 9A-J and 10, to place this truncated pointer in the header's identifier field and place the value 01.sub.2 in the object's synchronization-state field 42, as FIG. 7B also indicates. That value signifies that the object is locked.
Although different threads cannot have locks on the same object simultaneously, the Java virtual machine allows a single thread to have more than one lock on an object. To keep track of the number of locks, the lock record includes a lock-count field. To save steps, the value that a typical implementation places in that field when the lock record as initially allocated is one, even though no lock has yet been acquired, since the lock-count field should have that value when the lock record is initially brought into use.
The meta-lock-acquisition operation actually results in an additional header state between those that FIGS. 7A and B depict. Such a state also occurs between the states that each other pair of consecutive FIG. 7 drawings represents, but we postpone a description of that state until we discuss meta-locking below in connection with FIGS. 9A-J. Also, the header state that results from the meta-lock-release operation would differ from that shown in FIG. 7B if another thread had attempted to begin a monitor-access operation while thread T1's was still in progress. Throughout the discussion of FIGS. 6A-K, though, we will assume that each thread completes its monitor-access operation before the next thread's monitor-access operation begins. The way in which the meta-lock-acquisition and -release operations are performed when this assumption is violated will thereafter be described by reference to FIGS. 8, 9A-K, and 10.
The usual reason for a thread to lock an object is to read or write one or more of that object's fields. Let us suppose that a result of thread T1's reading one of the object fields is its synchronized method's discovery that the object is not yet in a state required for subsequent method steps. In such a situation, a method may call for its current thread to "go to sleep," i.e., to have the operating system suspend the thread and not re-activate it until some condition changes. To do so, the thread calls the object's waito method, which begins with a monitor-access operation.
FIG. 7C depicts the result of that monitor-access operation. Specifically, thread T1 changes the code in the synchronization field 42 to 10.sub.2. This code indicates that the object is not locked but that there is a thread that is waiting for a lock or, as is the case here, is waiting to be "notified" about something related to the object. The thread sets its isWaitingForNotify field to its TRUE value to indicate that it is waiting for notification as opposed to a lock. As in the previous monitor-access operation and the other monitor-access operations that FIGS. 7A-K illustrate, access to the monitor resources is guarded by the meta-locking to be described in connection with FIGS. 8, 9A-J, and 10.
Any thread that obtains a lock places a lock record from its pool at the head of the locked object's linked lock-record list. FIG. 7D illustrates this by showing the result of thread T2's obtaining a lock on the object while thread T1 is waiting for notification. Note that thread T2's locking at this point does not violate the FIG. 7 assumption that each monitor-access operation is completed before the next one starts. Thread T1's wait operation includes more than one monitor-access operation. The first of these, which was to place the thread in the queue of threads waiting for notification, is completed when thread T2 begins to obtain the lock, even though thread T1's wait for notification is not.
As FIG. 7D shows, one result of thread T2's locking operation is that thread T2 has taken a lock record 52 from its linked list of available lock records. It has also placed that lock record at the head of the object's linked list by pointing the object header's lock-record pointer to lock record 52 and placing a pointer to lock record 50 in lock record 52's next-LR field. Another result of the locking operation is that the hash and age values that lock record 50 previously contained have been copied into corresponding fields of thread T2's lock record 52. Additionally, thread T2 has changed the synchronization-state field 42's contents to the lock-indicating value, 01.sub.2.
Note that FIG. 7D's representation of thread T1's lock record 50 contains question marks in the location that previously contained the hash and age fields. In practice, the hash and age values typically still would be in that location. But the hash and age values are updated as necessary only in the object header or the first lock record, not in any other lock record, so the question marks represent the resultant, possibly stale values.
Although FIG. 7D depicts lock record 52 as having a lock count of one, it is possible that the synchronized method responsible for the lock is of the recursive variety: it may call itself. In such a situation, each nested call of that routine could obtain a further lock, and the result would be to increment the lock count. When the nested subroutines subsequently start returning, each would release a lock by, among other things, decrementing the lock count. Actually, such multiple locking can result not only from recursive synchronized methods but also from any synchronized method that calls another synchronized method on the same object.
FIG. 7E illustrates the result of an attempt by a further thread, T3, to obtain a lock on the object. As FIG. 7D shows, thread T2 already has a lock on the object, so thread T3 takes a lock record 54 from its free-lock-record list and places it at the end of the object's linked list, not at the beginning. That is, since synchronization-state field 42's value is 01.sub.2, meaning that the object is already locked, thread T3 follows that object's lock-record list to lock record 50, whose NULL next-LR value distinguishes it as the last lock record in the list. It makes that next-LR field point to a lock record chosen from thread T3's pool of available lock records. Since there can be at most one lock-owning thread for a given object, and since that thread's lock record is at the head of the object's linked lock-record list, both of the other lock records represent threads that are waiting for the object. Since the isWaitingForNotify field of the execution environment to which lock record 50 points has a TRUE value, whereas that of the execution environment to which lock record 54 points has a FALSE value, FIG. 7E depicts a state in which lock record 50 represents a thread waiting for notification, while lock record 54 represents a thread waiting to obtain a lock.
When thread T2 completes the synchronized method or other synchronized code block, it releases the lock by placing the most-significant thirty bits of its next-LR field's value in the object's identifier field, setting that field's synchronization-state field to 10.sub.2, resetting its next-LR field to the NULL value, and copying its lock record 52's hash and age fields into the corresponding fields of the next lock record, lock record 50. It also returns its lock record 52 to the start of its free-lock-record list. FIG. 7F depicts the result.
Note that all of the lock records in FIG. 7F contain lock counts of one, even though none represents a lock on the object. The lock count does not matter for any of those records; that count's value has meaning only in a lock record that represents an existing lock, i.e., only in the first lock record in a linked list pointed to by an object whose synchronization-state field has the value 01.sub.2. Leaving a value of one in that field saves a step if the lock record is subsequently used to represent a lock.
Part of thread T2's lock-release operation not mentioned above is a system call that results in the operating-system thread scheduler's reactivating at least one thread, such as thread T3, that is waiting to obtain a lock on the object. (Thread T1 is waiting for notification rather than a lock.) When thread T3 is reactivated, the object is no longer locked, so thread T3 thread can obtain a lock on it. To that end, thread T3 places its lock record 54 at the head of the list, as FIG. 7G illustrates. That is, it replaces the contents of the object's lock-record pointer with the first thirty bits of a pointer to its lock record 54, places in that lock record's next-LR field a pointer to the erstwhile first lock record 50, and resets that lock-record's next-LR field to a NULL value. It also changes the contents of the object's synchronization-state field 42 from 10.sub.2 (meaning not locked but having a queue of least one waiter) to 01.sub.2 (meaning locked).
At this point in the example, we assume that, having obtained a lock on the object, thread T3 performs a further monitor-access operation, namely, "notifying on" the object. In the Java programming language, three native methods of the class Object are wait( ), notify( ), and notifyAll( ), which the Java virtual machine usually implements by mapping them to the underlying operating system's thread-suspension and -resumption operations. The wait( ) method, which thread T1 performed a monitor-access operation to begin in FIG. 7C, directed the operating system to take that thread out of the queue of activated threads until such time as another thread, in performing the object's notify( ) method, chooses to deliver the notification to thread T1.
FIG. 7H shows what happens when thread T3 then performs the notify( ) method on the object. Specifically, it follows the linked lock-record list to find the first lock record whose owner is a thread waiting for notification. In this case, that lock record is thread T1's lock record 50. Guided by that lock record's owner pointer, it sets thread T1's isWaitingForNotify value to FALSE, thereby converting thread T1 to a waiter for a lock rather than for a notification.
The notifyAll( ) operation is the same as the notify( ) operation, with the exception that the notifying thread notifies each thread awaiting notification, not just the first one.
Thread T3 then releases its lock on the object, as FIG. 7I illustrates. Specifically, it changes the object's synchronization-state field 42 to 10.sub.2 to indicate that the record is not locked but does have a queue of at least one waiter associated with it. It then removes its lock record from the linked lock-record list by changing the contents of that lock record's next-LR field to NULL and redirecting the object's lock-record pointer to thread T1's lock record 50, i.e., placing in that pointer field the first thirty bits of the value from the next-LR field of thread T3's lock record 54 so that it points to the new head of the linked lock-record list. This leaves lock record 54 free for reuse, so thread T3 returns that record to thread T3's queue of free lock records by placing the pointer from its execution environment's free-lock-records field in that of lock record 54 and replacing it with a pointer to lock record 54. It completes the operation by copying the hash and age fields from lock record 54 into the new first lock record 50.
As was mentioned above, the lock-release operation makes system calls to reactivate one or more waiting threads not waiting for notification. Since thread T1's isWaitingForNotify value is no longer TRUE, this may include thread T1, in which case the operating system gives it a turn to execute. When it does, it obtains a lock on the object, placing the lock-indicating code 01.sub.2 into the object's synchronization-state field 42, as FIG. 7J illustrates.
When thread T1 has completed the operations for which it required the lock, it releases the lock, as FIG. 7K illustrates, by returning the hash and age values to the object header's appropriate fields and setting the object's synchronization-state code to 00.sub.2, which indicates that there are no locks or waiters. In FIG. 7K, lock records 50, 52, and 54 are shown in the states that prevail when they have been returned to their respective threads' pools of available lock records. Note that the only per-object resource required to support thread safety is the two-bit synchronization-state field 42. Although multiple lock records were additionally needed to support the object's synchronization operations, these are not per-object resources: they belong to associated threads, and they are bound only to objects on which their threads are currently synchronized. So the number of required lock records is ordinarily negligible in comparison with the number of structures required for per-object resources.
Having reviewed the way in which exemplary monitor-access operations may be performed in the absence of contention for monitor resources, we turn to a discussion of how they acquire and release meta-locks to deal with such contention. FIG. 8 is a simplified C-language listing of a routine, getMetaLock( ), for performing meta-lock acquisition. It was mentioned in connection with the examples of FIGS. 7A-K that the monitor-access operations depicted in those drawings begin by using the meta-lock-acquisition operation to read the object header's lock word. In the cases that those drawings illustrate, in which there has been no contention for monitor resources--i.e., in which the previous monitor-access operation was completed before the current one started--that lock word is the bit field shown by FIG. 8's first line to be getMetaLock( )'s return value. The discussion that follows will additionally explain that, when there is contention, get-MetaLock( ) instead returns the value that the lock word would have had if the previous monitor-access operation had been completed before the current one started.
We assume for the sake of illustration that getMetaLock( ) is called in the state that FIG. 7B represents, i.e., in a state in which the lock word's first thirty bits are the first thirty bits of the lock-record pointer. As FIG. 8's first line shows, the arguments that the calling monitor-access operation passes to getMetaLock( )are pointers to the executing thread's execution environment and to the object on which the thread is attempting to obtain a lock. The heart of the getMetaLock( ) routine in the illustrated embodiment is its third-line step of the placing the value 11.sub.2 (referred to in the listing as "IsBusy") in the object header's synchronization-state field, whose contents in the absence of meta-locking are 00.sub.2 (no locks or waiters), 01.sub.2, (locked), or 10.sub.2 (waiters only). That value's meaning is that a thread has a meta-lock on the object, i.e., has a lock on its monitor resources. The same step replaces the identifier field's contents with the first thirty bits of a pointer to the thread's execution environment. (Execution environments, too, are four-byte aligned in the illustrated embodiment, so an execution-environment pointer's value can be inferred from its thirty most-significant bits.)
This third-line replacement is part of a swap operation performed by making a call that takes advantage of the fact that reading the lock-word field's contents and replacing them can be performed atomically, i.e., can be guaranteed to occur without any intervening operation. In some cases this atomicity is inherent because the instruction set of the processor involved includes an atomic "swap" operation. In others, it results from the swap's being implemented as a call to a system-API routine that the operating system does not permit its thread-scheduling operation to interrupt. The resultant atomicity avoids the need for any lower-level lock on the object header.
If that operation is begun in the state that FIG. 7B represents, it results in the transition between the states that FIGS. 9A and B depict. In all FIG. 9 drawings, the object's structure is on the left, while various fields of thread T1's, T2's, and T3's execution environments are on the right. (Although the drawings depict each execution environment as a single group of contiguous memory locations, and although such an arrangement is beneficial, those skilled in the art will recognize that there is nothing critical about such an organization, and execution-environment fields can in fact be disbursed to suit the particular application.)
As FIG. 8's fourth line indicates, getMetaLock( )returns the value of the thus-read lock word so long as the value of its synchronization-state field is not lsBusy (=11.sub.2), i.e., so long as the calling monitor-access operation does not begin until all previous monitor-access operations have released the meta-lock. This is the situation assumed above in connection with FIGS. 7B and C.
But now suppose that, instead of waiting for thread T1 to complete the wait-operation commencement that produced the FIG. 7C state, thread T2 attempts to begin the subsequent lock operation before the FIG. 7C state is reached, i.e., while the object's header is still in the meta-locked state that FIG. 9B depicts. Thread T2's attempt to perform a monitor-access operation still begins with the atomic swap operation of FIG. 8's third line, so it replaces the first thirty bits of thread T1's execution-environment pointer with the corresponding bits of its own execution-environment pointer. But this time the condition in FIG. 8's fourth row is false: as FIG. 9B indicates, the value in the object's synchronization-state field 42 is 11.sub.2. So, instead of returning the contents of the object's lock word, getMetaLock( )returns the return value of another routine. This routine, called getMetaLockSlow( ), returns the value that the object header's lock word would have had if the previous monitor-access operation had first gone to completion, as it did in FIG. 7C.
Basically, getMetaLockSlow( ) determines that value by waiting until the previous monitor-access operation has completed. But the predecessor thread does not then write that value back into the object's lock word, as it would in the absence of contention for the synchronization resources; to do so would erase the object structure's meta-lock indication, which tells other threads that the necessary synchronization resources are still reserved, as, upon thread T1's release, they are by thread T2. Instead, the meta-lock-releasing thread passes that value to its successor through fields in their respective execution environments.
For communication to occur in that fashion, thread T1 will ordinarily need to know which thread is its successor, and FIG. 9C illustrates the result of thread T2's giving thread T1 this information by writing thread T2's execution-environment pointer into an appropriate field of thread T1 's execution environment. FIG. 8's twentieth line represents that step. To do this without risking the inconsistencies in which concurrent access to thread T1's execution environment could otherwise result, thread T2 executes the tenth-line system call to obtain a lock on a mutex that the threads associate with T1's execution environment. If some other thread currently has a lock on that mutex, mutexLock( ) suspends the calling thread until the lock is released.
As FIG. 8's eleventh and eighteenth lines indicate, the successor-thread-identification operation represented by its twentieth line occurs only if the contents of a bitsForGrab field in the predecessor's execution environment has a FALSE value. The reason for this condition will be explained presently, but it usually prevails, so that identification operation usually occurs. Having thus identified itself to its predecessor thread T1, thread T2 then waits for thread T1 to complete its monitor-access operation and communicate the resultant release bits--i.e., the lock-word value that thread T1 would place in the header if there were no synchronization-resource contention--to thread T2.
To this end, thread T2 makes the system call of FIG. 8's twenty-third line. This system call (1) directs the operating system to suspend the calling thread until some other thread "signals" a condition variable to which the predecessor's execution environment points in a field not shown, (2) releases the lock on the mutex associated with access to the predecessor's execution environment, and (3) attempts to reacquire the lock on that mutex when it is awakened. The reason for placing this step in a do-while loop will be set forth presently.
We now assume that yet another thread, thread T3, attempts to begin a monitor-access operation before the previous meta-lock on the monitor resources has been released. Thread T3 begins just as thread T2 did. But we will assume for the sake of illustration that the operating system's thread scheduler ends thread T3 's time slice during execution of the instructions that result from, say, FIG. 8's tenth line. Accordingly, FIG. 9D shows the object's lock word as containing the first thirty bits of a pointer to thread T3's execution environment as a result of this step in FIG. 8's line 3, but thread T3 has temporarily been interrupted before it can identify itself to its predecessor by placing a pointer to its execution environment in the succEE field of thread T2's execution environment.
When thread T1 completes the monitor-access operation for which it acquired a meta-lock in FIG. 9B, it must release its meta-lock. To this end, it performs a releaseMetaLock( ) routine, which FIG. 10 represents by simplified C code. As FIG. 10's first line indicates, a monitor-access operation that is releasing a meta-lock passes the releaseMetaLock( ) routine not only pointers to its thread's execution environment and the object but also releaseBits, which is the data word that will be written into the object's lock word if no other thread is contending for the synchronization resources.
In the absence of such contention, that writing occurs in the third and fourth lines' step. That step involves a processor- or operating-system-provided atomic operation known as "compare-and-swap." This operation is similar to the swap operation described above in that it reads the lock word's contents, but it differs from that operation in that replacement of those contents is conditional upon their having a predetermined value. Specifically, the thread performing FIG. 10's releaseMetaLocko operation replaces the object's lock word with the releaseBits value passed to it by the calling monitor-access operation only if that lock word still contains the data word that the thread wrote there when it obtained the meta-lock, i.e., only if no successor has attempted to begin a monitor-access operation in the interim. If none has, then the meta-lock-release operation is completed.
In the present example, though, threads T2 and T3 have both attempted to begin monitor-access operations and thus modified the object's lock word since thread T1 obtained the meta-lock. In particular, the header's lock word is now in use to identify the last meta-lock contender. To avoid erasing this information, the compare-and-swap operation fails, so the releaseBits value is not thereby communicated to thread T2 through the object's header. Instead, releaseMetaLocko calls releaseMetaLockSlow( ), as FIG. 10's fifth line indicates, to perform that communication through the execution environments.
In executing releaseMetaLockSlow( ), thread T1 acquires the mutex that locks its execution environment, as FIG. 10's eighth line indicates. It then determines whether its execution environment's succEE has a non-NULL value, i.e., whether thread T1's successor has already identified itself. As was explained by reference to FIG. 9C, its successor thread T2 has in fact done so by placing in that field a pointer to thread T2's execution environment. The releaseMetaLockSlow( ) routine therefore executes its branch that includes the fourteenth-line step of communicating the releaseBits value to thread T2 by placing that value in the metaLockBits field of thread T2's execution environment, as FIG. 9E indicates. As that drawing also indicates, thread T1 additionally performs the sixteenth-line step of setting to the TRUE value a gotMetaLockSlow flag, which indicates whether the metaLockBits field of thread T2's execution environment has received the releaseBits result of the monitor-access operation that thread T2's predecessor performed.
Having already used the successor-identity information in its succEE field, thread T1 then performs the seventeenth-line step of setting that field to a NULL value, as FIG. 9E also indicates. It then performs the eighteenth-line step of unlocking the mutex that guards access to its execution environment, after which it "signals" the condition variable that tells the operating system to awaken at least one other thread waiting to acquire that mutex. In other words, it may signal the operating system to cause thread T2's execution to resume.
This completes T1's release of its meta-lock. Note that the resultant object-header state depicted in FIG. 9E differs from the result, depicted in FIG. 7C, that the same monitor-access operation produced when there was no contention for the synchronization resources. S |
