Providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems
First Claim
1. A computer implementable method for a continuous-clock computer system having a plurality of processors comprising:
- receiving an activity comprising at least one of;
a constraint for a thread in the activity specifying a desired earliest start time, amount of requested execution time, and a deadline; and
, a reservation for the activity specifying a recurring desired number of time units within a desired period;
determining one of the plurality of processors for which execution of the activity and threads within the activity that are to be scheduled, based on a heuristic; and
,scheduling the activity and the constraints for execution on the determined one of the plurality of processors, including inserting the activity and the constraints on a schedule for the determined one of the plurality of processors.
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.
-
Citations
20 Claims
-
1. A computer implementable method for a continuous-clock computer system having a plurality of processors comprising:
-
receiving an activity comprising at least one of;
a constraint for a thread in the activity specifying a desired earliest start time, amount of requested execution time, and a deadline; and
, a reservation for the activity specifying a recurring desired number of time units within a desired period;determining one of the plurality of processors for which execution of the activity and threads within the activity that are to be scheduled, based on a heuristic; and
,scheduling the activity and the constraints for execution on the determined one of the plurality of processors, including inserting the activity and the constraints on a schedule for the determined one of the plurality of processors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer-implementable method for a continuous-clock computer system having, a plurality of processors comprising:
- receiving an activity comprising at least one of;
a constraint for a thread in the activity specifying a desired earliest start time, an amount of requested execution time, and a deadline; and
, a reservation for the activity specifying a recurring desired number of time units within a desired period;determining at least one of the plurality of processors for which execution of the activity and threads within the activity that are to be scheduled, based on a heuristic; and
,scheduling the activity and the constraints for execution on the determined one of the plurality of processors, including inserting the activity and the constraints on a schedule for the determined at least one of the plurality of processors. - View Dependent Claims (15, 16, 17)
- receiving an activity comprising at least one of;
-
18. A system for scheduling a plurality of activities for each of a plurality of processors in a continuous-clock computer system, comprising:
-
a scheduling facility configured to; receive an activity to be performed by at least one of the processors; receive at least one constraint for processing the activity; identify at least one of the plurality of processors to process the activity based on a heuristic; and
,generate a schedule for at least one the identified processor, the schedule including the activity and the at least one constraint; and a scheduling status data structure operably coupled with the scheduling facility and the processors, and being configured to; receive the schedule from the scheduling facility; store the schedule; and provide access to the processors such that the identified processor is able to identify the activity and the at least one constraint. - View Dependent Claims (19, 20)
-
Specification