Electrical computers and digital data processing systems: input/ – Interrupt processing
Reexamination Certificate
1999-02-23
2004-05-18
Lefkowitz, Sumati (Department: 2112)
Electrical computers and digital data processing systems: input/
Interrupt processing
C710S269000, C709S241000, C709S241000, C709S241000, C711S147000, C712S244000
Reexamination Certificate
active
06738846
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to methods and apparatus for cooperative processing of a task using multiple threads in a multi-threaded computing system.
2. Description of Relevant Art
In general, a thread 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 primitive before invoking the method.
Since multiple threads must work together on a shared data resource, there must be a mechanism for preventing these threads from destroying data integrity by, for example, writing at the same time to a particular data area. This particular problem has been solved by using synchronization primitives such as locks, mutexes, semaphores, and monitors 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.
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.
In recent years significant efforts have been made to facilitate the creation of platform independent software. That is, software that can execute on multiple different platforms (e.g., different types of computer systems), without requiring the software program to be rewritten or customized to operate on specific platforms. By way of example, the Java programming language is designed to facilitate the creation of Java software objects that are platform independent. Platforms that support Java and a number of other programming languages, require native threads to cooperate with platform independent threads.
Since platform independent threads, such as Java, are subject to potentially long delays they are generally not designed to run time critical code. That task is left to native threads since they typically are capable of quickly reacting to and processing tasks where timely completion is important. By way of example, native code is used to process an interrupt asserted by, for example, a serial device whose buffer may overrun if not handled fast enough. If, for example, the serial device interrupt was handled by a Java thread, too much latency would accrue in those situations when the Java thread is held off from running. If the Java thread was held off long enough, the delay in processing the serial device interrupt could potentially cause an device error.
One situation where a Java thread is held off from running is referred to as garbage collection. Typical of a Java Virtual Machine (JVM), garbage collection is a process whereby inactive, or otherwise unneccessary objects and/or threads, are identified, collected, and deactivated. In a typical object based computing system, all platform independent threads are kept from running for at least the duration of the garbage collection process.
An additional problem related to those situations where platform independent and native threads do not cooperate occurs in those situations where a Java thread holds ownership of a synchronization primitive (such as a mutex, lock, semaphore, etc.) just prior to being suspended during, for example, the initiation of garbage collection. In this situation, the Java thread cannot relinquish ownership of the synchronization primitive for at least the duration of garbage collection. Consequently, the native thread cannot obtain ownership of the particular synchronization primitive owned by the Java thread and is thereby prevented accessing a locked resource thereby preventing the native thread from running time critical execution of code during garbage collection.
In view of the foregoing, it should be apparent that improved mechanisms and frameworks for cooperative execution of a task using multiple threads in a multi-threaded computer system would be desirable.
SUMMARY OF THE INVENTION
To achieve the foregoing and other objectives, improved mechanisms for cooperatively processing a task in a multi-threaded computer system are described. In one aspect of the invention, a first thread is arranged to receive a task and only partially process the task. During its processing, the first thread stores processing information that is relevant to future processing in a packet that is associated with the task. Upon completing its processing, the first thread designates a second thread as the owner of the packet. After the second thread obtains ownership of the packet it then further processes the task based at least in part upon the processing information stored in the packet by the first thread. With the described arrangement no synchronization primitives are required for the threads to cooperate in processing the task.
In some embodiments, additional threads also participate in the cooperative processing of the task. By way of example, in an embodiment having three threads that cooperatively process the task, the second thread stores additional processing information in the packet and designates a third thread as the owner of the packet upon completion of its processing. The third thread then further processes the task after it obtains ownership of the packet, based at least in part upon the processing information stored in the packet by the second thread.
In some preferred embodiments, designating ownership of the packet is accomplished by updating an ownership field included in the packet. In this arrangement, each thread that participates in the processing of the task sets the ownership of the packet to the next thread to process the task and the final thread to process the task sets the ownership of the packet to no owner.
In a described embodiment, the task is interrupt handling, the threads execute different order interrupt handlers and the packet is an interrupt packet.
In another aspect of the invention an improved interrupt handling system is described. The interrupt handling system includes an interrupt packet and an in
Saulpaugh Thomas E.
Slaughter Gregory L.
Traversat Bernard A.
Beyer Weaver & Thomas LLP
Lefkowitz Sumati
Sun Microsystems Inc.
Vu Trisha
LandOfFree
Cooperative processing of tasks in a multi-threaded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cooperative processing of tasks in a multi-threaded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cooperative processing of tasks in a multi-threaded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3186038