EP0553588A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Multi-media computer operating system and method
Assignee: International Business Machines Corp
•
Filing: 1992-12-22
•
Granted: —
•
Expires: 2012-12-22
Abstract
Abstract An operating system for scheduling execution of a random set of periodically recurring hard, real-time tasks encountered in multi-media computer system applications and which is useful in a multi-tasking computer operating environment. Periodically recurring computer tasks having relatively short execution periods for which execution results are absolutely required in hard, real-time environments such as multi-media systems, create a significant task scheduling overhead reducing the available processor resource. Overhead processing at task invocation is eliminated in the invention by placing all active recurrent tasks in an execution queue, regardless of the task's current state of activity and by reprioritizing the order of execution of the tasks in the queue whenever a given task execution is completed. Measured by reduction in task scheduling overhead consumed by the processor in scheduling the tasks, this achieves a 50-100% improvement over conventional scheduling and operating systems.
Inventors
- 👤 Donald Edward Carmon
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-08 06:50
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881; G06F9/4887
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
126 words
A method of controlling execution in a computer of a randomly varying set of one or more recurring hard, real-time completion deadline critical computer tasks in a multi tasking computer system, comprising steps of: receiving at said computer system requests for initiation of one or more of said tasks; generating an ordered task execution priority queue in accordance with the required completion deadlines of said tasks, said queue having an entry therein corresponding to all of said tasks, said entries being ranked in priority corresponding to the completion deadlines of said tasks with said task having the earliest said completion deadline having the highest priority; and executing said tasks beginning with the highest priority said entry in said queue which is found ready to begin execution.
Claim 2
Dependent Claim
26 words
A method as claimed in Claim 1, further comprising a step of: reordering the entries in said queue whenever execution of an entry therein is completed.
Claim 3
Independent Claim
53 words
A method as claimed in any one of Claims 1 to 2, further comprising steps of: removing an entry from said queue upon completion of execution thereof; and reinserting said entry at a position in said queue corresponding to a new completion deadline equal to the completion deadline period of said recurring task.
Claim 4
Independent Claim
55 words
A method as claimed in any one of Claims 1 to 2, further comprising a step of: ordering said entries having equal completion deadlines in accordance with the starting times of said tasks corresponding to said entries with the earliest said starting time being the highest priority entry among said entries having equal completion deadlines.
Claim 5
Dependent Claim
50 words
A method as claimed in Claim 3, further comprising a step of: ordering said entries having equal completion deadlines in accordance with the starting times of said tasks corresponding to said entries with the earliest said starting time being the highest priority entry among said entries having equal completion deadlines.
Claim 6
Independent Claim
34 words
A method as claimed in any one of Claims 1 to 4, further comprising a step of: inserting a lowest priority entry in said queue corresponding to at least one asynchronous, non-realtime recurring task.
Claim 7
Independent Claim
38 words
A method as claimed in any one of Claims 1 to 6, wherein: each of said entries in said queue includes all of said tasks having execution completion deadlines equal to said deadline to which said entry corresponds.
Claim 8
Independent Claim
60 words
A method as claimed in any one of Claims 1 to 7, further comprising a step of: generating another said ordered queue of entries, said entries corresponding to completed said execution tasks, which tasks are awaiting their next recurring execution start times, and which queue is ordered in priority with the highest priority assigned to the earliest said start time.
Claim 9
Dependent Claim
114 words
An operating system for controlling execution in a computer of a randomly varying set of periodically recurring, hard real-time competition deadline tasks in a multi tasking computer system, characterized in that it comprises : means for generating an ordered task execution priority queue in accordance with the required task execution completion deadlines of all of said tasks, with the highest priority said entry in said queue corresponding to the earliest said task execution completion deadline; means for searching said queue to find the highest priority said entry having a task which is found ready to begin execution; and means for causing the commencement of execution of any said tasks found ready to begin execution.
Claim 10
Dependent Claim
25 words
A system as claimed in Claim 9, further comprising: means for re-ordering the entires in said queue whenever execution of an entry therein is completed.
Claim 11
Independent Claim
55 words
A system as described in any one of claims 9 to 10, further comprising: means for removing an entry from said queue upon completion of execution thereof; and means for reinserting said entry at a position in said queue corresponding to a new completion deadline equal to the completion deadline period of said recurring tasks.
Claim 12
Independent Claim
54 words
A system as claimed in any one of Claims 9 to 10, further comprising: means for ordering said entries having equal completion deadlines in accordance with the starting times of said tasks corresponding to said entries with the earliest said starting time being the highest priority entry among said entries having equal completion deadlines.
Claim 13
Dependent Claim
49 words
A system as claimed in Claim 11, further comprising: means for ordering said entries having equal completion deadlines in accordance with the starting times of said tasks corresponding to said entries with the earliest said starting time being the highest priority entry among said entries having equal completion deadlines.
Claim 14
Dependent Claim
33 words
A system as claimed in any one of Claim 9 to 12, further comprising: means for inserting a lowest priority entry in said queue corresponding to at least one asynchronous, non-realtime recurring task.
Claim 15
Independent Claim
38 words
A system as claimed in any one of Claims 9 to 14, wherein: each of said entries in said queue includes all of said tasks having execution completion deadlines equal to said deadlines to which said entry corresponds.
Claim 16
Independent Claim
63 words
A system for controlling execution in a computer as claimed in any one of Claims 9 to 15, further comprising: means for generating another of said ordered queue of entries, said entries corresponding to completed said execution tasks which said tasks are awaiting their next recurring execution start times, said queue being ordered with the earliest occurring said start time having highest priority.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.