Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-04-02
2003-05-06
Lao, Sue (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06560626
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to multi-threaded computer processing, and more particularly to interruption handling for such processing.
BACKGROUND OF THE INVENTION
A computer's central processing unit (CPU) can only execute one instruction at a time. However, fast CPUs are capable of executing many instructions each second so that by switching between instructions in one program and those in another, the computer appears to the user to be running multiple programs simultaneously. Furthermore, a single program can have multiple concurrent processes, or threads, which are dynamically created and terminated by a main thread.
The operating system determines which thread should be run and which should be suspended. Many mechanisms are well-known for scheduling threads in a multi-threaded computer environment but all rely, to some extent, on the fact that most threads must periodically wait for something to happen and do not require CPU time while they are waiting. Typically threads wait for user input, for data to be retrieved from a storage device, or similar external events. A thread can also put itself to sleep for a specified period of time. For example, a thread may perform a certain operation at specific intervals and sleep between those operations.
In either case, the thread generally enters a non-interruptible, blocked (non-running) state until the conditions of the wait or sleep function are satisfied. A sleeping thread typically resumes execution when the specified period of time has elapsed. A waiting thread resumes execution when a specified synchronization object goes through a state transition. Among standard synchronization objects are counting semaphores and “mutex” (“mutual exclusion”) objects. Most implementations of the wait function also provide an optional timeout period so that the waiting thread unconditionally resumes execution after the timeout period expires even though the specified synchronization object has not yet undergone a state change.
Because the thread functions are unavailable during its blocked state, an additional feature of some wait and/or sleep functions permits another thread to prematurely terminate, or interrupt, the wait or sleep so that the waiting/sleeping thread resumes execution. Such interruptible wait/sleep functions can be based on the non-interruptible version of the wait function by including a synchronization object in the set of conditions that control the wait function. When another thread requests that the waiting thread be interrupted, the operating system signals the synchronization object to change its state. An interruptible sleep function is frequently implemented using the above-described interruptible wait function by setting the optional timeout period equal to the sleep period.
The processor cost for such interruptible wait/sleep functions which use synchronization objects are high. Since each blocked thread must be individually addressable to be awoken, a particular synchronization object must be associated with each blocked thread. Thus, the resource utilization of the function increases in linear fashion with the number of threads in the multi-threaded environment. Theoretically, a percentage of this resource cost can be mitigated by taking advantage of the fact that the synchronization objects are only required when a thread is actually waiting or sleeping. However, in practice, such savings are small, as most threads in a multi-threaded environment spend the bulk of their elapsed time waiting for pre-determined conditions to be satisfied.
Therefore, there is a need in a multi-threaded processing environment for thread interruption which does not exhibit the linear increase in resource utilization exhibited by synchronization objects as the number of threads increases.
SUMMARY OF THE INVENTION
A thread interruption function in multi-threaded runtime environment allows a thread to enter an alertable blocked state so that it can be awakened upon request by another thread. The wake up request causes the runtime environment to queue an asynchronous procedure call (APC) against the blocked thread. A callback routine associated with the APC is processed in a context of the blocked thread when the blocked thread is in the alertable state. An indicator associated with the APC is stored in the context of the blocked thread so that exception handling in the runtime environment captures the indicator and the blocked thread is activated as a result of the capture to complete the wake up process. The indicator can be created and stored by the callback routine. Alternatively, the indicator can be created and stored at the time the APC is queued against the blocked thread or after the callback routine has been processed. In one aspect of the invention, the indicator is implemented as a standard Java exception class.
Because an APC does not require the use of a synchronization object to wake up a blocked thread, the impact of the invention on the resource overhead of the runtime environment is minimal. Additionally, the use of standard APCs requires little additional programming to implement the thread interruption function.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.
REFERENCES:
patent: 5327558 (1994-07-01), Burke et al.
patent: 5623676 (1997-04-01), Horiguchi et al.
patent: 5675796 (1997-10-01), Hodges et al.
patent: 5968157 (1999-10-01), Joy et al.
patent: 6006247 (1999-12-01), Browning et al.
patent: 6128640 (2000-10-01), Kleinman
patent: 6182108 (2001-01-01), Williams et al.
Author unknown, IBM Technical Disclosure Bulletin, Apr. 1, 1997, T.DB ACC NO NN9704151, vol. 40, Issue No. 4, pp. 151-152.
Hogle Francis M.
Sharpe Tracy C.
Fourson Gary Scott
Klarquist & Sparkman, LLP
Lao Sue
Microsoft Corporation
LandOfFree
Thread interruption with minimal resource usage using an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Thread interruption with minimal resource usage using an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thread interruption with minimal resource usage using an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068955