Facilitating biased synchronization in an object-based system

• US 7,519,967 B1
• Filed: 06/17/2005
• Issued: 04/14/2009
• Est. Priority Date: 06/17/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Russell, Kenneth B.
• Primary Examiner(s): Ho; Andy
• Application Number:
  US11/156,308
• Time in Patent Office: 1,397 Days
• Field of Search: 718/102, 718/104, 719/316
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

One embodiment of the present invention provides a system that facilitates biased locking of objects within an object-based computing system. The system encounters a lock-acquisition operation while executing a current thread, wherein the lock-acquisition operation attempts to acquire a lock for an object. In response to the lock-acquisition operation, the system examines synchronization information associated with the object, wherein the process of examining the synchronization information does not involve atomic operations. If the synchronization information indicates that the lock is biasable and that the lock is biased toward the current thread, the system allows the current thread to acquire the lock without updating the synchronization information.

Claims

1. A method for facilitating biased locking of objects within an object-based computing system, comprising:

encountering a lock-acquisition operation while executing a current thread, wherein the lock-acquisition operation attempts to acquire a lock for an object;

in response to the lock-acquisition operation, examining synchronization information associated with the object, wherein the process of examining the synchronization information does not involve atomic operations;

if the synchronization information indicates that the lock is biasable and that the lock is biased toward the current thread, allowing the current thread to acquire the lock without updating the synchronization information; and

if the synchronization information indicates that the lock is biasable and that the lock is biased toward another thread revoking the bias toward the other thread by;

stopping all threads in the object-based computing system at a safe point;

determining whether the lock is held by the other thread;

if not, resetting the synchronization information to indicate that the lock is biasable but unbiased whereby the lock can be subsequently rebiased; and

if the lock is held, resetting the synchronization information to indicate that the lock is not biasable, and falling back to an underlying synchronization technique to acquire the lock, and also updating the synchronization information to reflect the locking state of the object in the underlying synchronization technique;

wherein acquiring the lock for the object without atomic operations reduces the number of hardware operations the current thread needs to execute on the object-based computing system to acquire the lock.

2. The method of claim 1, wherein if the synchronization information indicates that the lock is biasable and the lock is presently unbiased, the method further comprises:

using an atomic operation to attempt to update the synchronization information to indicate that the lock is biased toward the current thread; and

if the atomic operation succeeds and the lock is biased toward the current thread, allowing the current thread to acquire the lock.

3. The method of claim 1, wherein if the synchronization information indicates that the lock is not biasable, the method further comprises using an underlying synchronization technique to acquire the lock.

4. The method of claim 1, wherein determining if the lock is held by the other thread involves:

walking a stack for the other thread to enumerate stack records associated with the object that have not been filled in yet;

filling in the enumerated stack records with values that are consistent with the locking state of the object; and

if any stack records were found, indicating that the lock is held by the other thread, updating the synchronization information associated with the object to reference the bottommost stack record associated with the object.

5. The method of claim 1, wherein the method further comprises:

estimating a rate of bias revocation on a per-data-type basis; and

if the estimated rate of bias revocation for a given data type exceeds a threshold value, performing a bulk revocation for all instances of the given data type.

6. The method of claim 5, wherein if revocations for objects of the given data type persist, the method further comprises:

ensuring that all subsequently created instances of the given data type are not biasable; and

performing a bulk revocation which ensures that all existing instances of the given data type are not biasable.

7. The method of claim 1, wherein the method further comprises:

encountering a lock-release operation while executing the current thread, wherein the lock-release operation attempts to release the lock for the object; and

in response to the lock-release operation, allowing the current thread to release the lock without updating the synchronization information if the object was biased toward the current thread.

8. The method of claim 1, wherein the synchronization information associated with the object is contained within a synchronization word within the object.

9. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating biased locking of objects within an object-based computing system, the method comprising:

encountering a lock-acquisition operation while executing a current thread, wherein the lock-acquisition operation attempts to acquire a lock for an object;

in response to the lock-acquisition operation, examining synchronization information associated with the object, wherein the process of examining the synchronization information does not involve atomic operations;

if the synchronization information indicates that the lock is biasable and that the lock is biased toward the current thread, allowing the current thread to acquire the lock without updating the synchronization information; and

if the synchronization information indicates that the lock is biasable and that the lock is biased toward another thread revoking the bias toward the other thread by;

stopping all threads in the object-based computing system at a safe point;

determining whether the lock is held by the other thread;

if not, resetting the synchronization information to indicate that the lock is biasable but unbiased, whereby the lock can be subsequently rebiased; and

if the lock is held, resetting the synchronization information to indicate that the lock is not biasable, and falling back to an underlying synchronization technique to acquire the lock, and also updating the synchronization information to reflect the locking state of the object in the underlying synchronization technique;

wherein acquiring the lock for the object without atomic operations reduces the number of hardware operations the current thread needs to execute on the object-based computing system to acquire the lock.

10. The computer-readable storage medium of claim 9, wherein if the synchronization information indicates that the lock is biasable and the lock is presently unbiased, the method further comprises:

using an atomic operation to attempt to update the synchronization information to indicate that the lock is biased toward the current thread; and

if the atomic operation succeeds and the lock is biased toward the current thread, allowing the current thread to acquire the lock.

11. The computer-readable storage medium of claim 9, wherein if the synchronization information indicates that the lock is not biasable, the method further comprises using an underlying synchronization technique to acquire the lock.

12. The computer-readable storage medium of claim 9, wherein determining if the lock is held by the other thread involves:

walking a stack for the other thread to enumerate stack records associated with the object that have not been filled in yet;

filling in the enumerated stack records with values that are consistent with the locking state of the object; and

if any stack records were found, indicating that the lock is held by the other thread, updating the synchronization information associated with the object to reference the bottommost stack record associated with the object.

13. The computer-readable storage medium of claim 9, wherein the method further comprises:

estimating a rate of bias revocation on a per-data-type basis; and

if the estimated rate of bias revocation for a given data type exceeds a threshold value, performing a bulk revocation for all instances of the given data type.

14. The computer-readable storage medium of claim 13, wherein if revocations for objects of the given data type persist, the method further comprises:

ensuring that all subsequently created instances of the given data type are not biasable; and

performing a bulk revocation which ensures that all existing instances of the given data type are not biasable.

15. The computer-readable storage medium of claim 9, wherein the method further comprises:

encountering a lock-release operation while executing the current thread, wherein the lock-release operation attempts to release the lock for the object; and

in response to the lock-release operation, allowing the current thread to release the lock without updating the synchronization information if the object was biased toward the current thread.

16. The computer-readable storage medium of claim 9, wherein the synchronization information associated with the object is contained within a synchronization word within the object.

17. An apparatus for facilitating biased locking of objects within an object-based computing system, comprising:

a lock-acquisition mechanism;

wherein when a lock-acquisition operation is executed by a current thread, the lock-acquisition mechanism is configured to examine synchronization information associated with the object, wherein the process of examining the synchronization information does not involve atomic operations;

wherein if the synchronization information indicates that the lock is biasable and that the lock is biased toward the current thread, the lock-acquisition mechanism is configured to allow the current thread to acquire the lock without updating the synchronization information; and

wherein if the synchronization information indicates that the lock is biasable and that the lock is biased toward another thread, the lock-acquisition mechanism is configured to revoke the bias toward the other thread by;

stopping all threads in the object-based computing system at a safe point;

determining whether the lock is held by the other thread;

if not, resetting the synchronization information to indicate that the lock is biasable but unbiased, whereby the lock can be subsequently rebiased; and

if the lock is held, resetting the synchronization information to indicate that the lock is not biasable, and falling back to an underlying synchronization technique to acquire the lock, and also updating the synchronization information to reflect the locking state of the object in the underlying synchronization technique;

wherein acquiring the lock for the object without atomic operations reduces the number of hardware operations the current thread needs to execute on the object-based computing system to acquire the lock.

18. The apparatus of claim 17, wherein if the synchronization information indicates that the lock is biasable and the lock is presently unbiased, the lock-acquisition mechanism is configured to:

use an atomic operation to attempt to update the synchronization information to indicate that the lock is biased toward the current thread; and

if the atomic operation succeeds and the lock is biased toward the current thread, to allow the current thread to acquire the lock.