US5247677A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Stochastic priority-based task scheduler
Assignee: Apple Inc
•
Filing: 1992-05-22
•
Granted: 1993-09-21
•
Expires: 2012-05-22
Abstract
Abstract A stochastic priority based scheduler for selecting executable tasks in a computer system is disclosed. The stochastic priority based scheduler selects tasks on the basis of a random number weighted by task priority. Since every task has a nonzero finite probability of being selected, the probability being proportional to the task priority, all tasks, even low priority ones, have a chance of being selected, thus eliminating the lockout problem.
Inventors
- 👤 Robert V. Welland
- 👤 Walter R. Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:22
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
59 words
In a computer system wherein a plurality of executable tasks are available for execution, a task selection method comprising the steps of: maintaining a data structure containing the plurality of executable tasks; associating a priority with each of the executable tasks; and selecting a task at random weighted by a task priority from the data structure of executable tasks.
Claim 2
Dependent Claim
59 words
In a computer system wherein a plurality of executable tasks are available for execution, a task selection method comprising the steps of: maintaining a data structure containing the plurality of executable tasks; associating a priority with each of the executable tasks; and selecting a task at random weighted by a task priority from the data structure of executable tasks.
Claim 3
Dependent Claim
119 words
The task selection method of claim 1 wherein the step of selecting a task at random weighted by a task priority further comprises: calculating the sum of the priorities for all executable tasks; generating a random selection value between 1 and the sum of the priorities; initializing a temporary variable to zero; traversing the data structure of executable tasks by adding the task priority to the temporary variable, comparing the temporary variable to the random selection value, and moving to the next task in the data structure if the temporary variable is less than the selection value; and selecting the task that resulted in the temporary variable being equal or greater than the selection value as the executable task.
Claim 4
Dependent Claim
20 words
The task selection method of claim 2 wherein the data structure of executable tasks is kept as a linked list.
Claim 5
Dependent Claim
22 words
The task selection method of claim 2 wherein the data structure of executable tasks is kept as a set of indexed tables.
Claim 6
Dependent Claim
96 words
The task selection method of claim 1 wherein the step of selecting a task at random weighted by task priority further comprises: calculating the sum of the priorities for all executable tasks; generating a random selection value between 1 and the sum of the priorities; traversing the data structure of executable tasks by subtracting the task priority from the selection value, and moving to the next task in the data structure if the selection value is greater than zero; and selecting the task that resulted in the selection value being less than or equal to zero.
Claim 7
Dependent Claim
20 words
The task selection method of claim 5 wherein the data structure of executable tasks is kept as a linked list.
Claim 8
Dependent Claim
22 words
The task selection method of claim 5 wherein the data structure of executable tasks is kept as a set of indexed tables.
References Cited (Backward Citations)
US4642756A
Cited
US5129078A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-20 | 1997-03-22 | 1997-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-20 | 2001-03-22 | 2001-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-20 | 2005-03-22 | 2005-09-21 | $7700.00 | Window Closed / Lapsed |