US5361362A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive job scheduling for multiprocessing systems with master and slave processors executing tasks with opposite anticipated execution times respectively
Assignee: Nokia Bell Labs
•
Filing: 1992-11-04
•
Granted: 1994-11-01
•
Expires: 2012-11-04
Abstract
Abstract In a master/slave multiprocessor system, process execution tasks are allocated on the basis of anticipated execution time. Work which can be performed by either the master or the slave is entered on a double ended queue in a non-descending order of anticipated execution times. Processes having high anticipated execution times are selected for execution by the slave processor and processes having low anticipated execution times are selected for execution by the master processor. Anticipated holding times are computed on the basis of the time spent by the slave computer in the execution of a segment of a process without requiring interaction with the master processor. The slave processor records the time spent in execution each time a segment of the process is completed and the process has to be returned to the master. The master uses the recorded time as a measure of the anticipated execution time for a next segment of the same process.
Inventors
- 👤 Donald E. Benkeser
- 👤 Joseph B. Cyr
- 👤 Albert G. Greenberg
- 👤 Paul E. Wright
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 05:42
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881; G06F9/50; G06F9/5005; G06F9/5027; G06F2209/00; G06F2209/50; G06F2209/5021
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
119 words
In a multiprocessor arrangement having a master processor and a slave processor, a method of allocating work to said slave processor and said master processor comprising the steps of: assigning an anticipated holding time value of a next segment to program processes to be executed, said program processes executable by either of said master processor or said slave processor; ordering said program processes in a double ended queue in a monotonically increasing order of anticipated holding time values; selecting processes for execution by said slave processor from the end of said queue having higher anticipated holding time values; and selecting processes for execution by said master processor from the end of said queue having lower anticipated holding time values.
Claim 2
Dependent Claim
119 words
In a multiprocessor arrangement having a master processor and a slave processor, a method of allocating work to said slave processor and said master processor comprising the steps of: assigning an anticipated holding time value of a next segment to program processes to be executed, said program processes executable by either of said master processor or said slave processor; ordering said program processes in a double ended queue in a monotonically increasing order of anticipated holding time values; selecting processes for execution by said slave processor from the end of said queue having higher anticipated holding time values; and selecting processes for execution by said master processor from the end of said queue having lower anticipated holding time values.
Claim 3
Dependent Claim
131 words
In a multiprocessor system comprising a master and a slave processor, a method of scheduling execution of program processes each comprising at least one segment, by said master processor and said slave processor comprising the steps of: recording in a queue indicia identifying a plurality of processes to be executed each of which can be executed by either of said master or said slave processor; recording in association with each identified process an indication of anticipated execution time of a next segment; selecting for execution by said slave processor a process having recorded therewith an indication of a longer anticipated execution time than for other processes; and selecting for execution by said master processor a process having recorded therewith an indication of a shorter anticipated execution time than for other processes.
Claim 4
Dependent Claim
131 words
In a multiprocessor system comprising a master and a slave processor, a method of scheduling execution of program processes each comprising at least one segment, by said master processor and said slave processor comprising the steps of: recording in a queue indicia identifying a plurality of processes to be executed each of which can be executed by either of said master or said slave processor; recording in association with each identified process an indication of anticipated execution time of a next segment; selecting for execution by said slave processor a process having recorded therewith an indication of a longer anticipated execution time than for other processes; and selecting for execution by said master processor a process having recorded therewith an indication of a shorter anticipated execution time than for other processes.
Claim 5
Dependent Claim
70 words
A method of scheduling execution of program processes in accordance with claim 2, wherein said step of recording an anticipated execution time comprises computing an execution holding time value for an associated process each time a segment of the associated process is executed and defining the computed value for executing a previous segment of the associated process as the anticipated execution time for a next segment of the associated process.
Claim 6
Dependent Claim
71 words
A method of scheduling execution of program processes in accordance with claim 2, wherein said step of recording an anticipated execution time comprises computing an execution holding time value for an associated process each time a segment of the associated process is executed and deriving an anticipated process execution time for a next segment of the associated process from a plurality of computed execution holding time values for the associated process.
References Cited (Backward Citations)
US3648253A
Cited
US4318173A
Cited
US4333144A
Cited
US4403286A
Cited
US4394727A
Cited
US4633387A
Cited
US4839798A
Cited
US4989133A
Cited
US4736318A
Cited
US4908750A
Cited
US4953082A
Cited
US4954945A
Cited
US4852001A
Cited
US5109329A
Cited
US5050070A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-31 | 1998-05-02 | 1998-11-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-31 | 2002-05-02 | 2002-11-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-31 | 2006-05-02 | 2006-11-01 | $7700.00 | Window Closed / Lapsed |