Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-12-02
2002-10-29
Thai, Xuan M. (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S200000, C709S241000
Reexamination Certificate
active
06473820
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to methods and apparatus implementing a monitor wait operation in an object-based computing system. More particularly, the invention relates to methods and apparatus for a thread to atomically release a monitor lock and enter a corresponding wait queue 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.
In some situations, a thread owning a target object's monitor may wish to release the target object's monitor and suspend execution by issuing what is referred to as a wait operation. When a thread calls a monitor wait operation, all synchronization locks on the target object associated with the thread are released allowing other threads to enter the monitor (i.e.; get the mutex) associated with the target object. After release of the synchronization locks, the thread is placed (enqueued) in the wait queue associated with the target object until such time as (1) another thread calls a notify method or a notifyALL method, or (2) a timeout period has elapsed. As known in the art, the notify method removes an arbitrary thread from the wait queue which then competes for the mutex on the target object, whereas a notifyALL method removes all threads from the wait queue.
The conventional method of implementing a monitor wait operation presents a number of problems. One such problem occurs when a notification is lost. For example, if a first thread is attempting to issue a monitor wait it must first release the monitor lock and prepare to sleep (i.e.; suspend execution). If, however, a second thread grabs the target object's lock and issues a monitor notify before the first thread has entered the wait queue, the notification will be lost since wait queue is empty. In this case, the first thread will be sleeping until the timeout period has elapsed wasting valuable time in the process.
Another problem associated with the conventional approach to issuing a monitor wait is related to inappropriate queuing order in the wait queue. Inappropriate queuing order may arise if during the period of time between a first thread releasing a monitor lock and entering an associated wait queue, a second thread enters the monitor and issues its own monitor wait. In this case, the second thread may enter the wait queue before the first thread thereby compromising the queuing order.
And still another problem associated with the conventional approach to issuing a monitor wait is related to those situations where a notifyALL is issued by the monitor owner. In this case, all waiting threads then compete for the object lock which causes a substantial waste of CPU time. It should also be noted that in some cases, a timeout, a thread interrupt, and a wait notification may occur substantially simultaneously which cannot be supported by most monitor implementations. Therefore, an improved method and apparatus for implementing a monitor wait operation is desirable.
SUMMARY OF THE INVENTION
Broadly speaking, the invention relates to an improved method, apparatus and computer system for implementing an atomic monitor wait operation. According to one aspect of the invention, a computer-implemented method for implementing an atomic monitor wait operation includes creating a semaphore specific to a first thread desiring to exit a monitor associated with a target object. The semaphore is then placed in a wait queue (enqueued) associated with the target object. After the enqueuing, the first thread releases the lock on the target object allowing a second thread to execute a synchronous operation on the target object
Beyer Weaver & Thomas LLP
Sun Microsystems Inc.
Thai Xuan M.
LandOfFree
Method and apparatus for user level monitor implementation 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 user level monitor implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for user level monitor implementation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944002