Monitor conversion in a multi-threaded computer system

Details Monitor conversion in a multi-threaded computer system Monitor conversion in a multi-threaded computer system

2000-02-22

2004-02-10

Chavis, John (Department: 2124)

Data processing: software development, installation, and managem

Software program development tool

Testing or debugging

C709S241000

Reexamination Certificate

active

06691304

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the 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. Related 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.
Typically, 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. 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 such synchronization construct is referred to as a monitor. Generally, a monitor is arranged such that only the thread that owns the monitor associated with an object is permitted to execute a synchronized operation on that object. Monitors may be either lightweight or heavyweight. Typically, lightweight monitors are preferable for objects that are not subject to contention, whereas heavyweight monitors are preferably used to handle contended monitor operations.
One particular implementation of a 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. 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.
FIG. 1A
illustrates an object header
100
and an associated lightweight monitor
102
. The lightweight monitor
102
includes a thread identifier field (also referred to as an owner field)
104
containing the thread ID of the thread that owns the lightweight monitor
102
. The lightweight monitor
102
also includes a recursion counter
106
indicating the number of times that the current thread has re-entered the lightweight monitor. The lightweight monitor
102
also includes a heavyweight monitor flag
108
used to identify the lightweight monitor
102
as a lightweight monitor when the heavyweight monitor flag is set to “0”.
In the situation where the owner field
104
is zero, the lightweight monitor
102
is unowned and therefor unlocked. If, however, the owner field
104
contains a thread ID representative of the current thread that owns the lightweight monitor
102
.
In order to enter a lightweight monitor, a thread
110
typically performs a compare and swap operation on the object header
100
that contains the lightweight monitor
102
. In a compare and swap operation, the new value of the compare and swap operator is the thread ID associated with the thread
110
and the comperand of the compare and swap operator is zero. With this arrangement, if the compare and swap operation is successful, then the thread ID, recursion counter, and all flags (such as the heavyweight monitor flag
108
) in the lightweight monitor
102
had been all been initially zero indicating that the lightweight monitor
102
was un-owned and, therefor, un-locked. After the successful completion of the compare and swap operation, the owner field
104
now contains the thread ID associated with the thread
110
indicating that the thread
110
owns the lightweight monitor
102
and has therefor locked the lightweight monitor
102
.
In those cases where a thread is re-entering a monitor that it already owns (i.e.; the thread is re-entrant), the re-entering thread must first increment the recursion counter
106
without causing an overflow condition. In those situations where a re-entering thread does cause an overflow condition, the re-entering thread must convert the lightweight monitor
102
into a heavyweight monitor
114
that is built upon a system monitor
116
. It should be noted that, by design, only the current owner of the system monitor
116
is capable of converting the lightweight monitor
102
to the heavyweight monitor
114
. Typically, this conversion is accomplished by performing a compare and swap operation on the object header
100
with the new value of the compare and swap operator being a heavyweight monitor pointer corresponding to the newly created heavyweight monitor
114
. In this way, after the successful compare and swap operation, the object header
100
contains the heavyweight monitor pointer.
The heavyweight monitor
114
includes a recursion counter field
118
that is updated every time a particular thread re-enters the system monitor
116
. The heavyweight monitor
114
also includes a heavyweigh

Affiliated with

Also associated with

Rating

Monitor conversion in a multi-threaded computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Monitor conversion in a multi-threaded computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monitor conversion in a multi-threaded computer system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3345889