Providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems
First Claim
1. A method in a computer system having a plurality of processors for ensuring the timely execution of a critical time constraint submitted by one of a plurality of active threads, each active thread belonging to one of a plurality of activities, the method comprising:
- receiving a critical time constraint from a submitting thread specifying a deadline and an estimate of the amount of execution time required by the time constraint;
accessing a prospective execution schedule for at least one of the processors of future time intervals each having a duration and occurring at a specified time in the future, the execution schedule identifying dedicated future time intervals that have been dedicated to executing one of specific threads and groups of threads, and identifying undedicated future time intervals that have not been dedicated to executing a specific thread, at least a portion of the dedicated future time intervals being dedicated in furtherance of an earlier-received time constraint, each earlier-received time constraint being one of critical and non-critical; and
modifying the accessed execution schedule to rededicate to the submitting thread at least one future time interval dedicated in furtherance of a non-critical constraint to a thread belonging to the same activity as the submitting thread.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems. In one embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. There may be one scheduling graph for each processor, or a scheduling graph may traverse multiple processors. Start and end times for reservations and constraints are adjusted to compensate for the granularity of the clock of the system. Furthermore, the scheduler may use an existing priority-based scheduler in order to cause scheduling decisions it has made to be acted upon.
30 Citations
8 Claims
-
1. A method in a computer system having a plurality of processors for ensuring the timely execution of a critical time constraint submitted by one of a plurality of active threads, each active thread belonging to one of a plurality of activities, the method comprising:
-
receiving a critical time constraint from a submitting thread specifying a deadline and an estimate of the amount of execution time required by the time constraint; accessing a prospective execution schedule for at least one of the processors of future time intervals each having a duration and occurring at a specified time in the future, the execution schedule identifying dedicated future time intervals that have been dedicated to executing one of specific threads and groups of threads, and identifying undedicated future time intervals that have not been dedicated to executing a specific thread, at least a portion of the dedicated future time intervals being dedicated in furtherance of an earlier-received time constraint, each earlier-received time constraint being one of critical and non-critical; and modifying the accessed execution schedule to rededicate to the submitting thread at least one future time interval dedicated in furtherance of a non-critical constraint to a thread belonging to the same activity as the submitting thread. - View Dependent Claims (2, 3, 4)
-
-
5. A method in a computer system having a plurality of processors for ensuring the timely execution of accepted time constraints submitted by one of a plurality of active threads, the method comprising:
-
receiving a time constraint from a submitting thread specifying a deadline and an estimate of the amount of execution time required by the time constraint; accessing a prospective execution schedule for at least one of the processors of future time intervals each having a duration and occurring at a specified time in the future, the execution schedule identifying dedicated future time intervals that have been dedicated to executing one of specific threads and groups of threads, and identifying undedicated future time intervals that have not been dedicated to executing one of specific threads and groups of threads; determining that the received time constraint cannot be successfully complete while also executing threads and groups of threads in accordance with the accessed execution schedule; and in response to the determining, declining the received time constraint. - View Dependent Claims (6, 7, 8)
-
Specification