Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-11-22
2004-02-03
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C719S315000, C719S316000
Reexamination Certificate
active
06687904
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 obtaining a lock on 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, may be thought of as a “sketch pad” of storage resources, and 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. In other words, more than one thread may attempt to operate on 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. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method 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.
FIG. 1
is a diagrammatic representation of an object which is provided with a lock and two threads that both require access to the object. An object
102
includes a header field
106
and a word
110
which is arranged to indicate if object
102
is locked, or owned by a thread
114
. As shown, object
102
is locked by thread
114
a
. Accordingly, word
110
identifies thread
114
a
as owning object
102
. Another word
118
is stored in a stack frame
122
, e.g., stack frame
122
a
, of a stack
126
a
that is associated with thread
114
a
. Word
118
is arranged to indicate that thread
114
a
has possession of the lock on object
102
and is, therefore, allowed to operate on object
102
.
When thread
114
b
, which has an associated stack
126
b
, requires access to object
102
, thread
114
b
reads word
110
and determines whether object
102
is available. When object
102
is locked by thread
114
a
, thread
114
b
may not obtain the lock on object
102
until thread
114
a
has relinquished the lock. In other words, until word
110
indicates that no thread owns object
102
, thread
114
b
may not obtain the lock on object
102
.
In general, thread
114
b
may either repeatedly attempt to lock object
102
, or thread
114
b
may effectively “sleep” until it is notified that object
102
is available. With reference to
FIG. 2
, the steps associated with the acquisition of an object lock by a thread will be described. A process
202
of acquiring an object lock begins at step
204
in which a thread, e.g., thread
114
b
of
FIG. 1
, attempts to lock an object, e.g., object
102
of FIG.
1
. In attempting to lock an object or, more generally, in attempting to acquire the ownership of an object, the thread may study the object to determine if the object is locked. By way of example, as discussed above with respect to
FIG. 1
, the thread may read a specific word stored in the object to determine if the object is available to the thread. When the object is available, the thread may update the specific word to indicate that it has locked, or acquired ownership of, the object.
A determination is made in step
208
as to whether the attempt by the thread to lock the object was successful. If the determination is that the attempt was successful, then the thread has the object lock, and the process of locking the object is completed. Alternatively, when it is determined that the attempt to lock the object was not successful, the indication is that the object is locked by another thread. As such, the thread typically must wait for the other thread to relinquish the object lock before the thread may lock the object.
When the attempt to lock the object was not successful, then process flow proceeds to step
212
where it is determined if the thread is coded to spin or to block when awaiting the availability of the object. When a thread is coded to spin, the thread will periodically check the object to determine if the lock on the object is available. Spinning, or busy-waiting for a resource such as an object to be freed, avoids thread context switches, as will be appreciated by those skilled in the art. Alternatively, when a thread is coded to block, the thread effectively puts itself into a sleep state during which the thread does not attempt to access the object.
If the determination in step
212
is that the thread is coded to spin, then the thread spins for a given period of time in step
216
. The given period of time is typically specified by the overall computing system, and is considered to be one “spin cycle.” After the thread spins for one spin cycle, process flow returns to step
204
where the thread once again attempts to lock the object.
Alternatively, when it is determined in step
212
that the thread is coded to block, the thread blocks itself in step
220
. As will be appreciated by those skilled in the art, computing systems generally specify a maximum number of spin cycles. In some systems, when a thread has spun for the maximum number of spin cycles without successfully locking an object, the thread may then block itself. That is, in some systems, a thread may be coded to first spin, then eventually block if the object lock has not been successfully obtained through spinning.
While the thread is blocked, the thread awaits notification, typically from an operating system, that the object is available for locking. In step
224
, the thread receives notification that the object is available for locking. Accordingly, the thread unblocks itself and process flow returns to step
204
in which the thread once again attempts to lock the object.
Blocking a thread, or putting a thread to sleep such that the thread is effectively not executing, while waiting for an object to be freed is computationally less expensive than allowing a thread to spin if it is expected to take a significant amount of time for the object to become free. However, since blocking a thread typically requires context switches, if an object is expected to be freed in a relatively short amount of time, then allowing the thread to spin may be more efficient from a performance point of view. As will be understood by those skilled in the art, a context switch entails allowing another thread to execute on a particular central processing unit (CPU) if another thread is available. In general, the choice of whether to block a thread or to allow the thread to spin is made on a system-wide basis. That is, either all threads in a system block, or all threads in th
Gomes Benedict A.
Weissman Boris
Banankhah Majid A.
Beyer Weaver & Thomas LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for selecting a locking policy based on... 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 selecting a locking policy based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for selecting a locking policy based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3332423