Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-26
2003-01-21
Robinson, Greta L. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S241000, C709S241000
Reexamination Certificate
active
06510437
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
The present invention is a continuation-in-part of co-pending U.S. patent application Ser. No. 08/743,484 now U.S. Pat. No. 6,134,627, filed Nov. 4, 1996, and claims priority of copending provisional U.S. patent application Ser. No. 60/057,050, filed Aug. 27, 1997, which are incorporated herein by reference in their entirety.
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to methods and apparatus for locking and unlocking objects in an object-based system. More particularly, the invention relates to methods and apparatus for enabling multiple concurrent threads to operate synchronously, and efficiently, in an object-based system.
2. Description of Relevant Art
An object generally 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. For example, a value returned by an operation associated with an object is dependent upon the state of the object as well as the arguments to the operation. As such, each invocation of an object may have a different result. In contrast, a value returned by a function is typically dependent only on the arguments to the function. Accordingly, for a given set of arguments, each invocation of a function will have the same result.
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.
Threads may generally be either “cooperative” or “concurrent.” Threads are considered to be cooperative when a single thread maintains complete control, e.g., control of a computational resource such as a processor or a process, until the thread voluntarily relinquishes control. Concurrent threads, on the other hand, are arranged such that although a thread may also voluntarily relinquish control, other threads may essentially cause the thread to involuntarily relinquish control.
In a concurrent threading model, multiple threads are allowed to execute independently of one another. Rather than being cooperatively scheduled like cooperative threads, concurrent threads are preemptively scheduled. That is, a computation by a given concurrent thread may be preempted at any point in time by an outside entity such as another concurrent thread, e.g., a scheduler, or the operating system. Thread preemption may occur because of meaningful events in the execution of a program. By way of example, a meaningful event may be when a thread's priority is programmatically raised to be higher than that of a currently running thread. Alternatively, thread preemption may occur because of artificially induced events such as the elapsing of a particular interval of time.
During the execution of an object-based program, a thread may attempt to execute operations which involve multiple objects. On the other hand, 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.
In addition to the synchronized operations defined on a given object, there may be some number of non-synchronized operations defined on that object. Non-synchronized operations are not prevented from being simultaneously executed on a given object by more than one thread. Several non-synchronized operations may be executed at once on a given object, and one or more non-synchronized operations may be executed at the same time as a synchronized operation.
Since a concurrent thread 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 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.
FIG. 2
is a diagrammatic representation of the interface between a thread, an object, and a synchronization construct in an object-based system. A thread
202
attempts to execute a synchronized operation on an object
204
. In order for thread
202
to execute the synchronized operation on object
204
, thread
202
must first obtain the object lock for object
204
.
When thread
202
attempts to execute a synchronized operation on object
204
, a synchronization construct
206
which is associated with object
204
is obtained. In general, object
204
is dynamically associated with a synchronization construct, as for example synchronization construct
206
a
, which is arranged to provide synchronized access to object
204
. If synchronization cons
Bak Lars
Lindholm Timothy G.
Beyer Weaver & Thomas LLP
Robinson Greta L.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for concurrent thread synchronization 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 concurrent thread synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for concurrent thread synchronization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3012886