Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-12-02
2004-06-22
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C709S241000, C709S241000
Reexamination Certificate
active
06754898
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to methods and apparatus for converting a lightweight monitor to a heavyweight monitor in an object-based computing system. More particularly, the invention relates to methods and apparatus for atomically converting a lightweight monitor associated with a contended object to a corresponding heavyweight monitor in an object-based computing system.
2. Description of Relevant Art
Within an object-based environment, threads are often used to satisfy requests for services. A thread 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. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is “pushed” on the execution stack of the thread. When the method returns, or is deactivated, the activation is “popped” from the execution stack. Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
During the execution of an object-based program, a thread may attempt to execute operations that involve multiple objects. On the other hand, multiple threads may attempt to execute operations that 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.
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 respect to
FIG. 1
, a process of acquiring an object lock will be described. The process of acquiring an object lock begins at step
104
where a thread obtains the object on which the thread wishes to operate. In general, the object on which the thread intends to operate has an associated object lock. Then, in step
106
, a determination is made regarding whether the object is locked. That is, a determination is made regarding whether the object lock associated with the object is held by another thread, e.g., a thread that is currently operating on the object.
If the determination in step
106
is that the object is not locked, then the thread acquires the object lock in step
108
. Alternatively, if the object is locked, then the thread waits for the object to be unlocked in step
110
. Once the object is unlocked, process flow moves from step
110
to step
108
where the object is locked by the thread.
As previously mentioned, a thread is permitted to execute a synchronized operation on an object if it successfully acquires the lock on the object. While one thread holds the lock on an object, other threads may be allowed to attempt to execute additional synchronization operations on the object, and may execute non-synchronized operations on the object. Thread synchronization is a process by which threads may interact to check the status of objects, whether the objects are locked or unlocked, while allowing only the thread which holds an object lock to execute synchronized operations on the locked object. Thread synchronization also enables threads to obtain and remove object locks.
When threads are synchronized, in order to make certain that only the thread that possesses an object lock is allowed to operate on a locked object, synchronization constructs are generally provided. One such synchronization construct is known in the art as the monitor. Monitors are simple yet fundamental thread synchronization constructs used in, for example, the JAVA™ platform of the Sun Microsystems Corporation of Palo Alto, Calif. Typically, monitors are implemented using low-level synchronization primitives such as mutexes and the like. Even though programs may perform monitor operations on any object, it is generally too space inefficient to include a monitor implementation for every object. One alternative to having every object have its own monitor is to maintain a hash table that maps objects to monitors. Unfortunately, the use of hash tables introduces additional overhead in monitor lookup as well as causing multiple threads to contend for the access to the global hash table. However, even the use of hash tables can result in substantial overhead in those situations where only a small number of monitor operations are invoked.
Since experience has shown that the majority of monitor operations do not contend with monitor operations performed by other threads, one attempt at improving monitor utilization utilizes a small number of bits in the object header to handle the non-contended monitor operations. One such implementation, referred to as a “thin lock”, or lightweight monitor, is described in “Thin Locks: Featherweight Synchronization for Java” by David F. Bacon et al. (1998), 258-268 which is incorporated by reference in its entirety. As described, the lightweight monitor is formed of bits reserved in the object header that identifies which thread, in the form of a thread ID, owns the lightweight monitor and therefore has locked the associated object. In the case when monitor contention does occur, the virtual machine allocates a heavyweight monitor for the contended object.
FIG. 2
a
is a diagrammatic representation of the interface between a thread, an object, and a monitor in an object based system. A thread
202
attempts to execute the synchronization operation on an object
204
having a header
206
. In order to execute synchronization operation, the thread
202
must first determine if the object
204
is owned by another thread and therefore unavailable, or locked. The thread
202
determines whether or not the object
204
is locked by entering a monitor
208
included in the object header
206
. The monitor
208
represents either a lightweight monitor (otherwise referred to as a thin lock) or a pointer to a heavyweight monitor (also referred to as a fat lock). Generally, one bit in the monitor
208
(referred to as HEAVY_FLAG) indicates whether the monitor
208
is a lightweight monitor or a heavyweight monitor pointer. When the monitor is a lightweight monitor, the HEAVY_FLAG is set to “0” and, conversely, is the HEAVY_FLAG is set to “1” if it contains a heavyweight monitor pointer.
Typically, lightweight monitors are used for objects that are not subject to contention, i.e.; do not have wait, notify, or notifyALL operations performed upon them. The structure of a typical lightweight monitor
210
included in the object header
206
is shown in
FIG. 2
b
. The lightweight monitor
210
includes a thread identifier
212
, a nested lock count (recursion counter)
214
, and a HEAVY_FLAG bit. In the situation where the thread identifier
212
(corresponding to the object
204
) is zero, the associated object
204
is unowned and unlocked. If, however, the thread identifier
212
in not zero (i.e.; is a thread ID), it represents an index into a ta
Liang Sheng
Zhang Hong
Avellino Joseph E
Beyer Weaver & Thomas LLP
Sun Microsystems Inc.
Wiley David
LandOfFree
Method and apparatus for converting a lightweight monitor to... 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 converting a lightweight monitor to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for converting a lightweight monitor to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293155