EP0491342A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for fast communication between user program and operating system
Assignee: Cray Research LLC
•
Filing: 1991-12-17
•
Granted: —
•
Expires: 2011-12-17
Abstract
Abstract Three new, efficient protocols for providing communications between a user's application program, a Multiprocessing Library, and the host Operating System is described. These new protocols are termed WAKEUP, GIVEUP, and CONTEXT-TO-USER-SPACE. They utilize the concept of a conduit through which the Operating System and the user application program can communicate without the need for expensive system calls. A primary use for the new protocols is the scheduling of multiple Central Processing Units (CPUs) into a single user program in a multi-CPU, multiprogramming, multi-tasking environment. WAKEUP allows a master process to quickly request the asynchronous scheduling of slave processes to help execute parallel tasks. GIVEUP allows a slave process time to finish a task before Operating System interruption. Once completed with its task, there is no need to save the context of the slave process. CONTEXT-TO-USE-SPACE allows other slave processes the opportunity to execute interrupted tasks that were not allowed to finish under GIVEUP.
Inventors
- 👤 Mark Furtney
- 👤 Frank R. Barriuso
- 👤 Clayton D. Andreasen
- 👤 Timothy W. Hoel
- 👤 Suzanne L. Lacroix
- 👤 Steven P. Reinhardt
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-06 14:24
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/45; G06F9/00; G06F9/06; G06F9/46; G06F9/52
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
82 words
In a multiprocessor system, a method for allowing a master process to asynchronously activate sleeping processes and assign parallel tasks when encountering a multiple CPU region of code, comprising the steps of: (a) the master process setting WAKEUP flags in a data buffer area associated with the additional processes; (b) asynchronous polling of the flags by an Operating System; (c) the Operating System, upon detecting a WAKEUP flag, activating a sleeping process; and (d) scheduling a parallel task to the activated process.
Claim 2
Dependent Claim
106 words
In a multiprocessor system, a method for delaying Operating System interruptions of a process until its task is complete or the expiration of a time slice, comprising the steps of: (a) the Operating System setting a GIVEUP flag in a data buffer area associated with the process; (b) the process reading the GIVEUP flag and returning the CPU to the Operating System if the GIVEUP flag is set; and (c) the Operating System interrupting the process at the end of a time slice, if the process has not yet finished its work and returned the CPU back to the Operating System in accordance with step (b).
Claim 3
Dependent Claim
100 words
In a multiprocessor system, a method for assigning parallel tasks from interrupted processes to available processes, comprising the steps of: (a) setting a save-in-user-space flag to inform the Operating System that a given slave process is currently performing a parallel task; (b) if interrupted, saving the context of the given slave process in user-space; (c) setting a flag to inform a Multiprocessing Library that the given task was interrupted while performing a parallel task; (d) asynchronous polling of the flag by the Multiprocessing Library to detect the interrupted task; and (e) assigning the interrupted task to the first available process.
Claim 4
Dependent Claim
21 words
The method according to claim 1 further wherein scheduling a task to an activated process is accomplished by a Multiprocessing Library.
Claim 5
Dependent Claim
27 words
The method according to claim 1 further comprising scheduling, upon completion of a task, a further task to an activated process if a further task is available.
Claim 6
Dependent Claim
26 words
The method according to claim 5 further wherein the further task is a task that has been disconnected with its context stored in the data buffer.
Claim 7
Dependent Claim
21 words
The method according to claim 2 further wherein a process checks its associated GIVEUP flag after it completes its assigned task.
Claim 8
Dependent Claim
53 words
The method according to claim 3 further wherein the step of assigning a given process a task includes setting a save-in-system-space flag to inform the Operating System to save the context of the given process in system space if the process is interrupted because the process is not currently performing a parallel task.
Claim 9
Dependent Claim
63 words
The method according to claim 2 further wherein each slave process has a thread structure associated with it and further comprising the step of the Operating System checking to see if a process it wants to interrupt has a thread structure associated with it and, if it does, setting the GIVEUP flag for the process, and, if it does not, interrupting the process.
Claim 10
Dependent Claim
33 words
The method according to claim 1 further including the step of a process upon completion of the task, spin waiting for a time slice and thereafter releasing its CPU to the Operating System.
Claim 11
Dependent Claim
71 words
The method according to claim 2 flag wherein said method further comprises the steps of: (d) setting a context save flag to "save-in-user-space" if the process is performing parallel work; and (e) the Operating System checking the context save flag if it interrupts the process and saving the context of the interrupted process in user space if the flag is set so that the context may be retrieved by another process.
Claim 12
Dependent Claim
49 words
The method according to claim 11 further comprising the steps of: (f) setting the context save flag to "don't-save-at-all" if the process has no context worth saving; and (g) the Operating System not saving the context of the interrupted process if the context save flag is set to don't-save-at-all.
Claim 13
Dependent Claim
31 words
The method according to claim 10 wherein said time slice is of a duration long enough to allow a slave process to conclude a task requiring a reasonable length of time.
Claim 14
Dependent Claim
17 words
The method according to claim 2 further wherein an interrupted process is rescheduled on a priority basis.
Claim 15
Dependent Claim
35 words
The method according to claim 3 further comprising the step of the first available process retrieving the context of the interrupted given task from user space and using the context to continue executing the task.
Claim 16
Dependent Claim
190 words
In a multiprocessor system, a method for parallel processing of parallel regions of code, comprising the steps of: (a) establishing a master process and one or more slave processes; (b) establishing a data buffer conduit including a thread structure and a context structure for each said slave process, each said thread structure including a WAKEUP flag and a GIVEUP flag; (c) the master process setting the WAKEUP flag for a slave process when a parallel region of code is encountered; (d) the Operating System asynchronously polling said WAKEUP flags and, upon detection of a WAKEUP flag for a slave process, activating the slave process to run; (e) the Operating System setting the GIVEUP flag for the running slave process if the Operating System desires to interrupt the process; (f) the running slave process polling the GIVEUP flag at the completion of its task and returning control to the Operating System if the GIVEUP flag is set; and (g) the Operating System interrupting the slave process for which it has set the GIVEUP flag if the slave process does not return control to the Operating System within a predetermined time slice.
Claim 17
Dependent Claim
88 words
The method according to claim 16 further wherein the thread structure includes a context save flag, and wherein said method further comprises the steps of: (h) setting the context save flag to "save-in-user-space" if the slave process is currently performing parallel work; and (i) the Operating System checking the context save flag if it interrupts a slave process and saving the context of the interrupted process in user space in the context structure if the flag is set so that the context may be retrieved by another process.
Claim 18
Dependent Claim
53 words
The method according to claim 17 further comprising the steps of: (j) setting the context save flag to "save-in-system-space" if the process is not currently performing parallel work; and (k) the Operating System saving the context of the interrupted slave process in system space if the context save flag is set to save-in-system-space.
Claim 19
Dependent Claim
50 words
The method according to claim 17 further comprising the steps of: (1) setting the context save flag to "don't-save-at-all" if the process has no context worth saving; and (m) the Operating System not saving the context of the interrupted slave process if the context save flag is set to don't-save-at-all.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.