Electrical computers and digital processing systems: processing – Processing architecture – Superscalar
Reexamination Certificate
1999-09-30
2002-11-26
Coleman, Eric (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Superscalar
C709S241000
Reexamination Certificate
active
06487652
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to methods and apparatus for improving the performance of software applications. More particularly, the present invention relates to methods and apparatus for reducing the overhead associated with allowing a thread to effectively own an object.
2. Description of the Related Art
In object-based computing systems, objects are generally operated on by threads. An object typically includes a set of operations and a state that remembers the effect of the operations. Since an object has some memory capability, an object differs from a function, which has substantially no memory capability. A thread, as will be understood by those skilled in the art, is essentially a single sequential flow of control within a computer program. In general, a thread, or a “thread of control,” is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside.
During the execution of an object-based program, multiple threads may attempt to execute operations which involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
Since a thread, e.g., a concurrent thread as will be appreciated by those skilled in the art, is not able to predict when it will be forced to relinquish control, synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object.
With reference to
FIG. 2
, the steps associated with locking an object will be described. A process
104
of locking an object begins at step
108
in which object information associated with the object is obtained by the thread that is attempting to lock the object, i.e., the current thread. While the object information that is obtained may vary, the object information generally includes bits or pointers which identify whether the object is already locked.
After the object information is obtained, a determination is made in step
112
as to whether the object is locked by another thread, or a thread which is not the current thread. If the determination is that the object is locked by another thread, then process control moves to step
1
16
in which the current thread blocks itself. By blocking itself, the current thread may effectively put itself to sleep, or otherwise cease execution, until notification is received that the object is no longer locked. When notification that the object is available is received in step
120
, then the current thread unblocks itself and obtains the object lock in step
124
. By obtaining the object lock, the current thread becomes the owner of the object, and is allowed to operate on the object. Hence, the process of locking the object is completed.
Alternatively, when it is determined in step
112
that the object is not locked by another thread, then a determination is made in step
128
regarding whether the current thread has already locked the object. In other words, the current thread determines whether it holds the lock on the object. If it is determined that the current thread has not already locked the object, then the indication is that the object is not locked. Accordingly, process flow moves to step
136
where a locking record in the object information is updated to indicate that the object is locked, or owned, by the current thread. When there is no existing locking record, then a new locking record is created, and set to indicate that the object is locked by the current thread. Once the locking record is either updated or set, the process of locking the object is completed.
Returning to step
128
, if the determination is that the object is already locked by the current thread, then in step
132
the locking record in the object information is updated to indicate the depth of the lock. Indicating the depth of the lock effectively identifies how many separate operations the current thread is either performing or attempting to perform on the object. The indication of the depth of the lock prevents the current thread from releasing the lock prematurely, e.g., before the current thread is finished operating on the object, as will be appreciated by those skilled in the art. After the depth of the lock is updated, the process of locking the object is completed.
In order to prevent a thread from acquiring ownership of an object while another thread is studying the object, e.g., attempting to lock the object, operations associated with locking an object are performed atomically. That is, the sequence of operations associated with locking an object is essentially performed all at once. The use of atomic operations is computationally expensive and, as a result, an object locking process is expensive.
Some objects or data structures, such as vectors and hash tables, are effectively implemented in a single-threaded manner. That is, ownership of such objects or data structures is rarely contested. However, despite the fact that some objects or data structures are substantially always used by the same thread, the objects or data structures still include locks. Therefore, whenever the thread wishes to operate on or use such objects or data structures, a locking procedure is performed. As previously mentioned, a locking procedure includes atomic operations which are computationally costly. The performance of an expensive locking procedure on an object whose ownership will generally not be contested may unnecessarily increase the overhead associated with the execution of an object-based program, since substantially only the owner thread will ever attempt to operate on the object.
Therefore, what is desired is a method for reducing the cost associated with locking an object whose ownership is not typically contested. That is, what is needed is an efficient method for allowing an object to be operated on by a thread when the thread has not actually locked the object.
SUMMARY OF THE INVENTION
The present invention relates to an object which may be speculatively locked such that a thread may operate on the object without acquiring the actual lock associated with the object. Enabling a thread to effectively possess an object without actually owning the object reduces the locking overhead associated with an overall computing system, thereby improving the performance of the computing system. According to one aspect of the present invention, a method for acquiring use of an object using a current thread includes a determination of whether a first bit associated with the object is set to indicate that the object is speculatively owned by a speculative owner thread. When the object is speculatively owned, the speculative owner thread is allowed to use the object without locking the object. The method also includes checking a stored identifier that is associated with the object and identifies the speculative owner thread, as well as determining whether the stored identifier identifies the current thread. When the stored identifie
Bak Lars
Gomes Benedict A.
Stoutamire David P.
Beyer Weaver & Thomas LLP
Coleman Eric
Sun Microsystems Inc.
LandOfFree
Method and apparatus for speculatively locking objects in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for speculatively locking objects in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for speculatively locking objects in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2921032