US3648253A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Program scheduler for processing systems
Assignee: Unisys Corp
•
Filing: 1969-12-10
•
Granted: 1972-03-07
•
Expires: 1989-12-10
Abstract
Abstract A program scheduler is provided for use with a multiprocessor system or its equivalent, such as a multiprogrammed processor unit, and the program scheduler receives tasks to be executed, schedules them for assignment, allots a task to each processor and interrupts the processors to assign new tasks. The program scheduler includes a plurality of buckets or tables where task words are stored, and associated with each task word is a Te field which specifies the estimated processor time required to complete the task and a Td field which indicates the time remaining before the task must be completed. The ratio Te/Td provides an indication of the need of each task word for processor service since the need for such service becomes more urgent as the ratio approaches 1. A scheduling algorithm periodically recalculates the service ratio and shifts tasks, if need be, from one table to another whereby tasks with a similar service ratio are stored in a common table. Task words within a given table are divided into classes according to the length of time a task has not received service. An allocation algorithm allots tasks to processors from the older classes first and proceeds in sequence through the various classes to the latest classes. Both the scheduling algorithm and the allocation algorithm service all tables in the program scheduler, but the tables with higher service ratios are serviced more often by each algorithm than tables with lower service ratios. When many task words are awaiting processor service, a given task word receives processor service at a rather low frequency when it has a small service ratio, but it receives processor service at a relatively high frequency as its service ratio approaches 1.
Inventors
- 👤 Alvin P Mullery
- 👤 Frank W Zurcher Jr
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-22 20:55
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4812; G06F9/4825; G06F9/4843; G06F9/4881; G06F9/4887
Claims Analysis
Total Claims: 76
Claim 1
Independent Claim
154 words
A program scheduling device for allocating task words which identify tasks to be performed by data processing means, said program scheduling device including: a plurality of storage tables, first means for determining a service ratio for each task word where the service ratio represents the processing time required to complete a task divided by the time remaining before such task must be completed. second means coupled to the storage tables for storing the task words in the storage tables according to their service ratios whereby task words with service ratios having a magnitude within a given range are stored in a common storage table, and third means coupled to the storage tables for allocating task words to the data processing means, said third means being weighted or biased to allocate task words from the storage tables with higher service ratios more often than it allocates task words from storage tables with lower service ratios.
Claim 2
Dependent Claim
154 words
A program scheduling device for allocating task words which identify tasks to be performed by data processing means, said program scheduling device including: a plurality of storage tables, first means for determining a service ratio for each task word where the service ratio represents the processing time required to complete a task divided by the time remaining before such task must be completed. second means coupled to the storage tables for storing the task words in the storage tables according to their service ratios whereby task words with service ratios having a magnitude within a given range are stored in a common storage table, and third means coupled to the storage tables for allocating task words to the data processing means, said third means being weighted or biased to allocate task words from the storage tables with higher service ratios more often than it allocates task words from storage tables with lower service ratios.
Claim 3
Dependent Claim
9 words
storing the task words in the program-scheduling device, and
Claim 4
Dependent Claim
9 words
storing the task words in the program-scheduling device, and
Claim 5
Dependent Claim
32 words
The apparatus of claim 1 wherein the third means includes fourth means which first allocates from each storage table those task words which have been waiting the longest time for processor service.
Claim 6
Dependent Claim
18 words
storing the task words in the program-scheduling device in specified storage areas according to their service ratios, and
Claim 7
Dependent Claim
18 words
storing the task words in the program-scheduling device in specified storage areas according to their service ratios, and
Claim 8
Dependent Claim
21 words
storing the task words in the program-scheduling device in storage areas reserved for service ratios of a given range in magnitude,
Claim 9
Dependent Claim
21 words
storing the task words in the program-scheduling device in storage areas reserved for service ratios of a given range in magnitude,
Claim 10
Dependent Claim
42 words
The apparatus of claim 1 wherein control means operates the first means and the second means to recalculate the service ratios of task words in the storage tables and place them in the appropriate storage table according to the updated service ratios.
Claim 11
Dependent Claim
30 words
allocating the task words to the data processing device in an order derived as a function of their service ratios and the length of time they have waited for allocation.
Claim 12
Dependent Claim
30 words
allocating the task words to the data processing device in an order derived as a function of their service ratios and the length of time they have waited for allocation.
Claim 13
Dependent Claim
18 words
allocating the task words to the data processing device from a selected order of the storage areas, and
Claim 14
Dependent Claim
18 words
allocating the task words to the data processing device from a selected order of the storage areas, and
Claim 15
Dependent Claim
21 words
transferring the task words to the data processing device from the program-scheduling device in an order determined by their service ratios.
Claim 16
Dependent Claim
21 words
transferring the task words to the data processing device from the program-scheduling device in an order determined by their service ratios.
Claim 17
Dependent Claim
27 words
recalculating the service ratio of each task word based on the time then remaining before such task must be completed thereby to update the service ratio, and
Claim 18
Dependent Claim
27 words
recalculating the service ratio of each task word based on the time then remaining before such task must be completed thereby to update the service ratio, and
Claim 19
Dependent Claim
26 words
allocating task words from each storage area, when it is selected, according to the length of time they have waited in such storage area for allocation.
Claim 20
Dependent Claim
26 words
allocating task words from each storage area, when it is selected, according to the length of time they have waited in such storage area for allocation.
Claim 21
Dependent Claim
153 words
A program scheduling device for allocating task words to data processing means, the task words specifying tasks, said program scheduling device including: first means for determining a service ratio for each task word where the service ratio represents the processing time required to complete a task divided by the time remaining before such task must be completed, a plurality of storage areas, second means coupled to the storage areas for storing the task words in the storage areas according to their service ratios whereby task words with service ratios having a magnitude within a given range are stored in a common storage area, and third means coupled to the storage areas for allocating task words to the data processing means, said third means being weighted or biased to allocate task words from the storage areas with higher service ratios more often than it allocates task words from storage areas with lower service ratios.
Claim 22
Dependent Claim
153 words
A program scheduling device for allocating task words to data processing means, the task words specifying tasks, said program scheduling device including: first means for determining a service ratio for each task word where the service ratio represents the processing time required to complete a task divided by the time remaining before such task must be completed, a plurality of storage areas, second means coupled to the storage areas for storing the task words in the storage areas according to their service ratios whereby task words with service ratios having a magnitude within a given range are stored in a common storage area, and third means coupled to the storage areas for allocating task words to the data processing means, said third means being weighted or biased to allocate task words from the storage areas with higher service ratios more often than it allocates task words from storage areas with lower service ratios.
Claim 23
Dependent Claim
27 words
recalculating the service ratio of each task word thereby to update the service ratio according to the current time remaining before such task must be completed, and
Claim 24
Dependent Claim
27 words
recalculating the service ratio of each task word thereby to update the service ratio according to the current time remaining before such task must be completed, and
Claim 25
Dependent Claim
19 words
storing the task word with an updated service ratio in specified storage areas according to the updated service ratio.
Claim 26
Dependent Claim
19 words
storing the task word with an updated service ratio in specified storage areas according to the updated service ratio.
Claim 27
Dependent Claim
17 words
storing the task words with recalculated service ratios in storage areas according to the recalculated service ratios.
Claim 28
Dependent Claim
17 words
storing the task words with recalculated service ratios in storage areas according to the recalculated service ratios.
Claim 29
Dependent Claim
32 words
The apparatus of claim 4 wherein the third means includes fourth means which first allocates from each storage table those task words which have been waiting the longest time for processing service.
Claim 30
Dependent Claim
42 words
The apparatus of claim 4 wherein control means operates the first means and the second means to recalculate the service ratios of task words in the storage tables and place them in the appropriate storage table according to the updated service ratios.
Claim 31
Independent Claim
122 words
A system including data processIng means and a program scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a given task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, and third means coupled to the first means for changing the sequence of allocating task words to the data processing means based on the data processing time required to complete each task divided by the time remaining before each task must be completed.
Claim 32
Independent Claim
122 words
A system including data processIng means and a program scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a given task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, and third means coupled to the first means for changing the sequence of allocating task words to the data processing means based on the data processing time required to complete each task divided by the time remaining before each task must be completed.
Claim 33
Independent Claim
215 words
A system including data processing means and a program-scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a given task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, third means coupled to the first means for changing the sequence of allocating task words to the data processing means based on the ratio of the data processing time required to complete each task divided by the time remaining before each task must be completed, and fourth means coupled to the first and second means which allocates a plurality of task words determined by said second means to the data processing means for a period of time during which processing of the specified tasks takes place and after which unfinished tasks are interrupted and their task words are returned to the first means of the program scheduling device, said fourth means executing this procedure as necessary to allow all tasks to meet their deadlines, whereby tasks with a greater urgency are advanced over tasks with less urgency.
Claim 34
Independent Claim
215 words
A system including data processing means and a program-scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a given task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, third means coupled to the first means for changing the sequence of allocating task words to the data processing means based on the ratio of the data processing time required to complete each task divided by the time remaining before each task must be completed, and fourth means coupled to the first and second means which allocates a plurality of task words determined by said second means to the data processing means for a period of time during which processing of the specified tasks takes place and after which unfinished tasks are interrupted and their task words are returned to the first means of the program scheduling device, said fourth means executing this procedure as necessary to allow all tasks to meet their deadlines, whereby tasks with a greater urgency are advanced over tasks with less urgency.
Claim 35
Dependent Claim
34 words
The apparatus of claim 8 wherein the second means includes fifth means which first allocates from task words having a common ratio those task words which have been waiting the longest time for service.
Claim 36
Independent Claim
180 words
A system including data processing means and a program scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, and third means coupled to the first means which allocates a first group of task words determined by the second means to said data processing means for a given period of time during which processing of the specified tasks takes place and after which each unfinished task identified by the first group of task words is interrupted and a second group of task words determined by said second means is allocated to said processing means for a given period of processing time, said third means executing this allocation procedure as necessary to allow all tasks sufficient execution time to meet their deadlines.
Claim 37
Independent Claim
180 words
A system including data processing means and a program scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to data processing means, each task word identifying a task, said program scheduling device including: first means for storing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, and third means coupled to the first means which allocates a first group of task words determined by the second means to said data processing means for a given period of time during which processing of the specified tasks takes place and after which each unfinished task identified by the first group of task words is interrupted and a second group of task words determined by said second means is allocated to said processing means for a given period of processing time, said third means executing this allocation procedure as necessary to allow all tasks sufficient execution time to meet their deadlines.
Claim 38
Dependent Claim
45 words
The apparatus of claim 10 further including fourth means coupled to said first means for controlling the sequence of allocating task words as a function of the processing time required to complete each task divided by the time remaining before each task must be executed.
Claim 39
Independent Claim
211 words
A system including data processing means and a program-scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to the data processing means, each task word identifying a task, said program-scheduling device including: first means for stoRing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, third means coupled to the first means for changing the sequence of allocating task words to the data processing means, said third means changing the sequence of allocating task words as a function of the processing time required to complete a task divided by the time remaining before a task must be completed, fourth means coupled to the first means which allocates a first group of task words determined by the second means to said data processing means for a period of processing time after which unfinished tasks are interrupted and a second group of task words determined by said second means is allocated to said processing means for a period of processing time, said fourth means executing this allocation routine as necessary to allow all tasks sufficient execution time to meet their deadlines.
Claim 40
Independent Claim
211 words
A system including data processing means and a program-scheduling device coupled to the data processing means for receiving task words from the data processing means and for allocating task words to the data processing means, each task word identifying a task, said program-scheduling device including: first means for stoRing task words received from the data processing means, second means coupled to the first means for determining the sequence of allocating task words to the data processing means, third means coupled to the first means for changing the sequence of allocating task words to the data processing means, said third means changing the sequence of allocating task words as a function of the processing time required to complete a task divided by the time remaining before a task must be completed, fourth means coupled to the first means which allocates a first group of task words determined by the second means to said data processing means for a period of processing time after which unfinished tasks are interrupted and a second group of task words determined by said second means is allocated to said processing means for a period of processing time, said fourth means executing this allocation routine as necessary to allow all tasks sufficient execution time to meet their deadlines.
Claim 41
Dependent Claim
119 words
A task selection system for assigning task words from a task storage means to a data processing means which executes tasks, each task word specifying a particular task, said system comprising: first means for supplying first signals with each task word indicative of the time remaining before each task must be completed, second means for supplying second signals with each task word indicative of the processor time required to complete each task, third means for producing third signals for each task word by dividing the value indicated by the second signals by the value indicated by the first signals, and fourth means for selecting task words from the task storage means based on the value of the third signals.
Claim 42
Dependent Claim
119 words
A task selection system for assigning task words from a task storage means to a data processing means which executes tasks, each task word specifying a particular task, said system comprising: first means for supplying first signals with each task word indicative of the time remaining before each task must be completed, second means for supplying second signals with each task word indicative of the processor time required to complete each task, third means for producing third signals for each task word by dividing the value indicated by the second signals by the value indicated by the first signals, and fourth means for selecting task words from the task storage means based on the value of the third signals.
Claim 43
Dependent Claim
52 words
The apparatus of claim 13 wherein the fourth means includes additional means which changes the operation of the fourth means to select task words from the task storage means based on the value indicated by the third signals and the length of time the task word has been waiting for processing service.
Claim 44
Dependent Claim
49 words
A task selection arrangement as set forth in claim 13 including means for selectively updating all task words by recalculating the third signals for each task word based on the current time then remaining before each task must be completed and the processor time required to complete each task.
Claim 45
Independent Claim
221 words
A system including data processing means for carrying out tasks simultaneously, a program scheduler coupled to the data processing means, said program scheduler receiving task words from the data processing means and supplying task words to the data processing means, each task word identifying a task, said program scheduler including: storage means for storing task words, first means for supplying first signals with each task word indicative of the time remaining until each task must be completed, second means for supplying second signals with each task word indicative of the processing time required to complete each task, third means for producing third signals for each task word by dividing the value of the second signals by the value of the first signals, fourth means responsive to said third signals for storing the task words in designated areas of said storage means according to the value of said third signals whereby task words having third signals with a value in a given range are grouped together in a common area, fifth means coupled to said storage means for interrupting periodically the task or tasks being executed by the data processing means and substituting therefor task words from said storage means, and said fifth means including sixth means for selecting the task words transferred from said storage means to said data processing means.
Claim 46
Independent Claim
221 words
A system including data processing means for carrying out tasks simultaneously, a program scheduler coupled to the data processing means, said program scheduler receiving task words from the data processing means and supplying task words to the data processing means, each task word identifying a task, said program scheduler including: storage means for storing task words, first means for supplying first signals with each task word indicative of the time remaining until each task must be completed, second means for supplying second signals with each task word indicative of the processing time required to complete each task, third means for producing third signals for each task word by dividing the value of the second signals by the value of the first signals, fourth means responsive to said third signals for storing the task words in designated areas of said storage means according to the value of said third signals whereby task words having third signals with a value in a given range are grouped together in a common area, fifth means coupled to said storage means for interrupting periodically the task or tasks being executed by the data processing means and substituting therefor task words from said storage means, and said fifth means including sixth means for selecting the task words transferred from said storage means to said data processing means.
Claim 47
Dependent Claim
56 words
The apparatus of claim 16 wherein the data processing means includes means which updates the value of the first signals and the value of the second signals for each task word transferred from the data processing means to the program scheduler, and said program sCheduler includes means for updating said first signals of each task word.
Claim 48
Dependent Claim
52 words
The apparatus of claim 17 wherein control means is connected to said third and fourth means which periodically operates the third means to update the third signals for each task word and operates the fourth means to place each task word in the appropriate storage area according to the updated third signals.
Claim 49
Dependent Claim
52 words
The apparatus of claim 18 wherein the sixth means selects task words from the various common storage areas in turn, and the common areas with task words having higher values of said third signals are selected more often than common storage areas with task words having lower values of said third signals.
Claim 50
Independent Claim
101 words
A system for timely executing a plurality of tasks each of which is identified by a task word, said system including: data processing means which executes a plurality of task words, a program scheduler coupled to the data processing means which supplies task words to the data processing means and receives task words from the data processing means, and said program scheduler including a control arrangement which allocates task words from said program scheduler to said data processing means as a function of the processing time required to complete each task and the time remaining before each task must be completed.
Claim 51
Independent Claim
101 words
A system for timely executing a plurality of tasks each of which is identified by a task word, said system including: data processing means which executes a plurality of task words, a program scheduler coupled to the data processing means which supplies task words to the data processing means and receives task words from the data processing means, and said program scheduler including a control arrangement which allocates task words from said program scheduler to said data processing means as a function of the processing time required to complete each task and the time remaining before each task must be completed.
Claim 52
Dependent Claim
62 words
The apparatus of claim 20 wherein the control arrangement includes: first means to calculate a service ratio for each task word by dividing the processing time required to complete each task word by the time remaining before each task word must be completed, and second means which allocates task words to the data processing means or a function of the service ratio.
Claim 53
Dependent Claim
46 words
The apparatus of claim 21 wherein the second means includes selection means which selects task words, and said selection means includes weighting means which cause selection of task words with higher service ratios to occur more often than selection of task words with lower service ratios.
Claim 54
Dependent Claim
68 words
The apparatus of claim 21 wherein the second means includes third means which signifies the time task words have been waiting for allocation to the data processing means, and said second means and said third means cooperate to allocate task words to the processing means as a function of the service ratio and the time each task word has been waiting for allocation to the data processing means.
Claim 55
Dependent Claim
36 words
The apparatus of claim 23 wherein the third means defines time boundaries, and task words are divided into time groups by said third means according to the length of time they have been waiting for service.
Claim 56
Dependent Claim
50 words
The apparatus of claim 23 wherein the control arrangement includes fourth means which operates the first means to update or recalculate the service ratio of the task words based on the current processing time required to complete each task and the current time remaining before each task must be completed.
Claim 57
Independent Claim
423 words
A system including data processor means, a program scheduler coupled to the data processor means for receiving tasks from the data processor means to be executed and for assigning tasks to the data processor means for execution, each task being represented by a plurality of signals constituting a word designated a task word, each task word having an address portion which defines the memory address of the first instruction in the task, a Te portion which signifies the amount of processor time required to complete the task, and a Td portion which indicates a later point in time when the task must be completed, first means in the program scheduler which periodically decrements the Td portion of each task word thereby to update and maintain current said Td portion of each task word, second means in the program scheduler which determines a service ratio q for each task word, where q is defined as Te/Td, the program scheduler including a plurality of Q storage tables, designateD by service ratios Q 1/2, Q 1/4, and Q 1/8, ... Q 1/n third means coupled to said Q storage tables which responds to the service ratio q of each task word for storing (1) in the storage table Q 1/2 all task words having service ratios equal to or greater than 1/2 , (2) in the storage table Q 1/4 all task words having service ratios equal to or greater than 1/4 but less than 1/2 , and (3) in the storage table Q 1/8 all task words having service ratios less than 1/4 , etc. fourth means in the program scheduler which recalculates the service ratios of task words in the storage tables Q 1/2, Q 1/4, Q 1/8...Q1/n with storage table Q 1/2 receiving such recalculation service more often than storage table Q 1/4 and with storage table Q 1/4 receiving such recalculation service more often than storage table Q 1/8, etc., and fifth means in the program scheduler for allocating task words from the storage tables Q 1/2, Q 1/4, or Q 1/8...Q1/n to the data processor means, said fifth means allocating more tasks in a given time period from the storage table Q 1/2 than from the storage table Q 1/4, and said fifth means allocating more task words in said given time period from the storage table Q 1/4 than from the storage table Q 1/8, etc. whereby the sequence of tasks supplied to said data processor means provides for the timely completion of all tasks by the data processor means.
Claim 58
Independent Claim
423 words
A system including data processor means, a program scheduler coupled to the data processor means for receiving tasks from the data processor means to be executed and for assigning tasks to the data processor means for execution, each task being represented by a plurality of signals constituting a word designated a task word, each task word having an address portion which defines the memory address of the first instruction in the task, a Te portion which signifies the amount of processor time required to complete the task, and a Td portion which indicates a later point in time when the task must be completed, first means in the program scheduler which periodically decrements the Td portion of each task word thereby to update and maintain current said Td portion of each task word, second means in the program scheduler which determines a service ratio q for each task word, where q is defined as Te/Td, the program scheduler including a plurality of Q storage tables, designateD by service ratios Q 1/2, Q 1/4, and Q 1/8, ... Q 1/n third means coupled to said Q storage tables which responds to the service ratio q of each task word for storing (1) in the storage table Q 1/2 all task words having service ratios equal to or greater than 1/2 , (2) in the storage table Q 1/4 all task words having service ratios equal to or greater than 1/4 but less than 1/2 , and (3) in the storage table Q 1/8 all task words having service ratios less than 1/4 , etc. fourth means in the program scheduler which recalculates the service ratios of task words in the storage tables Q 1/2, Q 1/4, Q 1/8...Q1/n with storage table Q 1/2 receiving such recalculation service more often than storage table Q 1/4 and with storage table Q 1/4 receiving such recalculation service more often than storage table Q 1/8, etc., and fifth means in the program scheduler for allocating task words from the storage tables Q 1/2, Q 1/4, or Q 1/8...Q1/n to the data processor means, said fifth means allocating more tasks in a given time period from the storage table Q 1/2 than from the storage table Q 1/4, and said fifth means allocating more task words in said given time period from the storage table Q 1/4 than from the storage table Q 1/8, etc. whereby the sequence of tasks supplied to said data processor means provides for the timely completion of all tasks by the data processor means.
Claim 59
Dependent Claim
15 words
The apparatus of claim 26 wherein said data processing means includes a plurality of processors.
Claim 60
Dependent Claim
19 words
The apparatus of claim 26 wherein said data processing means includes a data processor which executes multiple instructions simultaneously.
Claim 61
Dependent Claim
63 words
The arrangement of claim 26 wherein the program scheduler includes sixth means which can periodically interrupt processors in turn, commencing with the processor working on a task having the lowest q value and proceeding sequentially through to the processor working on a task having the highest q value, and allocates task words supplied by said fifth means as necessary to successively interrupted processors.
Claim 62
Dependent Claim
30 words
The apparatus of claim 29 wherein said sixth means includes seventh means which detects an idle processor and allocates to such processor the next task from the said fifth means.
Claim 63
Dependent Claim
37 words
The apparatus of claim 26 wherein the fifth means includes eighth means which defines time boundaries and divides the task words into time groups according to the length of time they have been waiting for processing service.
Claim 64
Dependent Claim
38 words
The apparatus of claim 31 wherein the eighth means includes a set of boundary counter for each of said Q storage tables, the number of boundary counters in each set being equal to the number of time boundaries.
Claim 65
Dependent Claim
44 words
The apparatus of claim 32 wherein task words in the oldest time group of each of the storage tables Q 1/2, Q 1/4 and Q 1/8...Q1/n are allocated by said fifth means before allocating tasks from more recent time groups of these storage tables.
Claim 66
Independent Claim
30 words
A method of transferring task words which identify tasks from a program-scheduling device to a data processing device for execution of the specified tasks, said method comprising the steps of:
Claim 67
Independent Claim
30 words
A method of transferring task words which identify tasks from a program-scheduling device to a data processing device for execution of the specified tasks, said method comprising the steps of:
Claim 68
Independent Claim
29 words
A method of transferring task words from a program-scheduling device to a data processing device which performs tasks specified by the task words, said method comprising the steps of:
Claim 69
Independent Claim
29 words
A method of transferring task words from a program-scheduling device to a data processing device which performs tasks specified by the task words, said method comprising the steps of:
Claim 70
Dependent Claim
10 words
The method of claim 35 further including the steps of:
Claim 71
Independent Claim
29 words
A method of transferring task words from a program-scheduling device to a data processing device which performs tasks specified by the task words, said method comprising the steps of:
Claim 72
Independent Claim
29 words
A method of transferring task words from a program-scheduling device to a data processing device which performs tasks specified by the task words, said method comprising the steps of:
Claim 73
Dependent Claim
10 words
The method of claim 37 further including the steps of:
Claim 74
Independent Claim
459 words
A system including data processor means, a program scheduler coupled to the data processor means for receiving tasks from the data processor means to be executed and for assigning tasks to the data processor means for execution, each task being represented by a plurality of signals constituting a word designated a task word, each task word having an address portion which defines the memory address of the first instruction in the task, a Te portion which signifies the amount of processor time required to complete the task, and a Td portion which indicates a later point in time when the task must be completed, first means in the program scheduler which periodically decrements the Td portion of each task word thereby to update and maintain current said Td portion of each task word, second means in the program scheduler which determines a service ratio q for each task word, where q is defined as Te/Td, the program scheduler including a plurality of Q storage tables, designated by service ratios Q 1/2, Q 1/4, Q 1/18,...Q 1/n third means coupled to said Q storage tables which responds to the service ratio q of each task word for storing (1) in the storage table Q 1/2 all task words having service ratios equal to or greater than 1/2 , (1) in the storage table Q 1/4 all task words having service ratios equal to or greater than 1/4 but less than 1/2 , and (3) in the storage table Q 1/8 all task words having service ratios less than 1/4 , etc. fourth means in the program scheduler which recalculates the service ratios of task words in the storage tables Q 1/2, Q 1/4, Q 1/8...Q 1/n with storage table Q 1/2 receiving such recalculation service more often than storage table Q Q 1/4 with storage table Q 1/4 receiving such recalculation service more often than storage table Q 1/8, etc., fifth means in the program scheduler for allocating tAsk words from the storage tables Q 1/2, Q 1/4, Q 1/8...Q 1/n to the data processor means, said fifth means allocating more tasks in a given time period from the storage table Q 1/2 than from the storage table Q 1/4, and said fifth means allocating more task words in said given time period from the storage table Q 1/4 than from the storage table Q 1/8, etc. said fifth means including sixth means which, upon allocation of each task word, interrupts the task being processed which has the lowest service ratio thereby to give tasks with higher service ratios additional processor time during the allocation process. whereby the sequence of tasks supplied to said data processor means provides for the timely completion of all tasks by the data processor means.
Claim 75
Independent Claim
459 words
A system including data processor means, a program scheduler coupled to the data processor means for receiving tasks from the data processor means to be executed and for assigning tasks to the data processor means for execution, each task being represented by a plurality of signals constituting a word designated a task word, each task word having an address portion which defines the memory address of the first instruction in the task, a Te portion which signifies the amount of processor time required to complete the task, and a Td portion which indicates a later point in time when the task must be completed, first means in the program scheduler which periodically decrements the Td portion of each task word thereby to update and maintain current said Td portion of each task word, second means in the program scheduler which determines a service ratio q for each task word, where q is defined as Te/Td, the program scheduler including a plurality of Q storage tables, designated by service ratios Q 1/2, Q 1/4, Q 1/18,...Q 1/n third means coupled to said Q storage tables which responds to the service ratio q of each task word for storing (1) in the storage table Q 1/2 all task words having service ratios equal to or greater than 1/2 , (1) in the storage table Q 1/4 all task words having service ratios equal to or greater than 1/4 but less than 1/2 , and (3) in the storage table Q 1/8 all task words having service ratios less than 1/4 , etc. fourth means in the program scheduler which recalculates the service ratios of task words in the storage tables Q 1/2, Q 1/4, Q 1/8...Q 1/n with storage table Q 1/2 receiving such recalculation service more often than storage table Q Q 1/4 with storage table Q 1/4 receiving such recalculation service more often than storage table Q 1/8, etc., fifth means in the program scheduler for allocating tAsk words from the storage tables Q 1/2, Q 1/4, Q 1/8...Q 1/n to the data processor means, said fifth means allocating more tasks in a given time period from the storage table Q 1/2 than from the storage table Q 1/4, and said fifth means allocating more task words in said given time period from the storage table Q 1/4 than from the storage table Q 1/8, etc. said fifth means including sixth means which, upon allocation of each task word, interrupts the task being processed which has the lowest service ratio thereby to give tasks with higher service ratios additional processor time during the allocation process. whereby the sequence of tasks supplied to said data processor means provides for the timely completion of all tasks by the data processor means.
Claim 76
Dependent Claim
96 words
The apparatus of claim 39 wherein said data processor means includes a plurality of data processors; and said fifth means includes: a storage device, first control means coupled to the storage device which operates the storage device to store the identity of the data processor and the service ratio of the task word whenever each task word is allocated, and second control means coupled to the storage device which searches through the storage device and identifies the data processor which is working on the task with the lowest service ratio prior to allocating each task word.
References Cited (Backward Citations)
US3363234A
Cited
US3286239A
Cited
US3312951A
Cited
US3491339A
Cited
US3333252A
Cited
US3359544A
Cited
US3399384A
Cited
US3530438A
Cited
US3449722A
Cited
US3421150A
Cited
US3496551A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-03-07 | 1975-09-06 | 1976-03-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-03-07 | 1979-09-06 | 1980-03-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-03-07 | 1983-09-06 | 1984-03-07 | $7700.00 | Window Closed / Lapsed |