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 scheduling the execution of threads of a plurality of computer programs, the method comprising:
- accessing a schedule for at least one of the processors that specifies, for each of a series of recurring intervals, the identity of a computer program that is to be executed during the recurring interval in satisfaction of a reservation submitted on behalf of the specified computer program, and that further specifies, for at least a portion of the recurring intervals, the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread; and
iterating through the series of recurring intervals, for each recurring interval visited;
if the recurring interval specifies the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread, selecting for execution the thread whose identity is specified by the visited recurring interval, and if the recurring interval does not specify the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread, selecting for execution a thread of the computer program whose identity is specified by the visited recurring interval, such that selecting a thread for execution are performed in a bounded amount of time that is independent of the number of threads and computer programs being scheduled.
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.
72 Citations
62 Claims
-
1. A method in a computer system having a plurality of processors for scheduling the execution of threads of a plurality of computer programs, the method comprising:
-
accessing a schedule for at least one of the processors that specifies, for each of a series of recurring intervals, the identity of a computer program that is to be executed during the recurring interval in satisfaction of a reservation submitted on behalf of the specified computer program, and that further specifies, for at least a portion of the recurring intervals, the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread; and
iterating through the series of recurring intervals, for each recurring interval visited;
if the recurring interval specifies the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread, selecting for execution the thread whose identity is specified by the visited recurring interval, and if the recurring interval does not specify the identity of a thread of the specified computer program that is to be executed during the recurring interval in satisfaction of a time constraint submitted on behalf of the specified thread, selecting for execution a thread of the computer program whose identity is specified by the visited recurring interval, such that selecting a thread for execution are performed in a bounded amount of time that is independent of the number of threads and computer programs being scheduled. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 57)
-
-
24. A method in a computer system having a plurality of processors for ensuring the timely execution of a time constraint 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, using the accessed execution schedule, whether the sum of the undedicated future time intervals occurring before the deadline specified by the received constraint is at least as large as the execution time estimate specified by the received constraint;
if the sum of the undedicated future time intervals occurring before the deadline is at least as large as the execution time estimate, accepting the received time constraint; and
if the sum of the undedicated future time intervals occurring before the deadline is not at least as large as the execution time estimate, declining the received time constraint. - View Dependent Claims (25, 28, 29)
-
-
26. 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 (27)
-
-
30. 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 (31, 32, 33)
-
-
34. A method in a computer system having a plurality of processors for scheduling the execution of activities at different frequencies, each activity being comprised of at least one thread, the method comprising:
-
receiving, for each of a plurality of activities, a reservation specifying an amount of execution time and an execution window, the execution window identifying a length of time such that, during every period of time having that length, the threads of the activity are executed for at least the specified amount of execution time; and
in response to the receiving, constructing a graph for at least one of the plurality of processors for scheduling the execution of the activities that is comprised of nodes each representing a recurring execution interval, the graph having one root, at least one leaf, and at least one path from the root to each leaf, each node being on at least one path from the root to a leaf, the number of times the execution interval represented by each node occurs during a single complete traversal of the graph being equal to the number of paths from the root to a leaf that the node is on, each node having associated with it an execution interval length, the total execution interval lengths of the nodes on each path from the root to a leaf not exceeding a maximum total interval, and, for each reservation, nodes being dedicated to the execution of the threads of the activity specified by the reservation that have a total execution interval at least as large as the amount specified by the reservation and that are on at least as many of the paths from the root to a leaf as the product of the total number of paths and the quotient of the maximum total interval divided by the execution window specified by the reservation, the constructed graph being usable to schedule the execution of activities in satisfaction of the received reservations by traversing the graph and, for each node visited in the traversal, executing at least one thread of the activity to which the node is dedicated for a period of time substantially equal to the execution interval length of the node. - View Dependent Claims (35, 36, 37)
-
-
38. A method for a 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 (39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
-
52. A method for a 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 (53, 54)
-
-
55. A method for a discrete-clock system having a discrete period comprising:
-
receiving an activity having a desired period;
adjusting the desired period to be a multiple of the discrete period; and
,scheduling the activity as the desired period thereof has been adjusted, including inserting the activity on a schedule for at least one processor of the system.
-
-
56. A method for a system having an adjustable time-keeping periodic comprising:
-
receiving an activity having a desired period;
adjusting the adjustable time-keeping interval of the system based on the desired period; and
,scheduling the activity for execution on a processor of the system, including inserting the activity on a schedule for at least one processor of the system.
-
-
58. A method for a computer system having a plurality of processors and on which a particular processor already has scheduled thereon a reservation for a thread in the activity, the reservation specifying a recurring desired number of time units within a desired period, the method comprising:
-
receiving a constraint for the thread in the activity specifying a desired earliest start time, amount of requested execution time, and a deadline;
determining whether the constraint can be scheduled on the particular processor;
upon determining that the constraint can be scheduled on the particular processor, scheduling the constraint on the particular processor;
otherwise, determining whether one of a second reservation and a constraint for a second thread is also scheduled on the particular processor, such that absence of the one of the second reservation and the constraint would permit scheduling the constraint on the particular processor; and
,upon determining that there is one of a second reservation and a constraint for a second thread scheduled on the particular processor such that the absence thereof would permit scheduling the constraint on the particular processor, moving the one of the second reservation and the constraint to another processor and scheduling the constraint on the particular processor.
-
-
59. A method for a computer system having a plurality of processors comprising:
-
a) receiving a constraint for a thread in an activity specifying a desired earliest start time, amount of requested execution time, and a deadline;
b) determining the thread has previously been run on a particular processor;
c) upon determining that the thread has previously been run on a particular processor, i) determining whether the constraint can be scheduled on the particular processor;
ii) upon determining that the constraint can be scheduled on the particular processor, scheduling the constraint on the particular processor;
iii) otherwise, scheduling the constraint on a different processor; and
,d) otherwise, scheduling the constraint on a different processor.
-
-
60. A method for a computer system having a plurality of processors comprising:
-
a) receiving a reservation for an activity that previously had no reservations, the reservation specifying a recurring desired number of time units within a desired period;
b) determining whether a thread within the activity has previously been run on a particular processor;
c) upon determining that the thread has previously been on a particular processor, i) determining whether the reservation can be scheduled on the particular processor;
ii) upon determining that the reservation can be scheduled on the particular processor, scheduling the reservation on the particular processor;
iii) otherwise, scheduling the reservation on a different processor; and
,d) otherwise, scheduling the reservation on a different processor.
-
-
61. A method for a computer system having a plurality of processors comprising:
-
receiving a new reservation for an activity that is replacing an old reservation for the activity already scheduled on a particular processor, the new reservation specifying a recurring desired number of time units within a desired period;
determining whether the new reservation can be scheduled on the particular processor;
upon determining that the new reservation can be scheduled on the particular processor, scheduling the new reservation on the particular processor; and
,otherwise, scheduling the new reservation on a different processor.
-
-
62. A method for a computer system having a plurality of processors comprising:
-
receiving a new reservation for a gang of cooperating threads, where the number of threads within the gang is not greater than the number of processors; and
,coscheduling execution of the gang of cooperating threads, using a plan encompassing a number of processors equal to the number of threads within the gang, such that each processor within the plan is responsible for a corresponding thread.
-
Specification