Providing predictable scheduling of programs using a repeating precomputed schedule

• US 6,792,445 B1
• Filed: 05/04/2000
• Issued: 09/14/2004
• Est. Priority Date: 01/09/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Michael B., Rosu, Marcel-Catalin, Rosu, Daniela, Draves, Richard P. Jr.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US09/564,822
• Time in Patent Office: 1,594 Days
• Field of Search: 709/300-305, 709/103, 709/104, 709/107, 709/226, 710/244, 701/129, 370/232, 370/319, 717/146, 717/151
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred 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. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.

Claims

1. A method in a computer system for ensuring the timely execution of a time constraint submitted by one of a plurality of active threads, the method comprising the steps of:

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 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 specific threads or groups of threads, and identifying undedicated future time intervals that have not been dedicated to executing specific threads or 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.

2. The method of claim 1, wherein the received time constraint further specifies a starting time at which the time constraint is to begin, and wherein the determining step determines, using the accessed execution schedule, whether the sum of the undedicated future time intervals occurring both before the deadline specified by the received time constraint and after the starting time specified by the received time constraint is at least as large as the execution time estimate specified by the received time constraint.

5. The method of claim 1, further comprising the step of, if the received time constraint is accepted:

modifying the execution schedule to dedicate to the submitting thread one or more undedicated future time intervals occurring before the deadline whose total durations are at least as large as the execution time estimate.

6. The method of claim 5, further comprising the step of, if the received time constraint is accepted:

executing the submitting thread in accordance with the modified execution schedule.

3. A method in a computer system 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 the steps of:

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 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 specific threads or 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 either critical or 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.

4. The method of claim 3, further including the step of executing plurality of active threads in accordance with the modified execution schedule, such that the submitting thread is executed during the future time intervals rededicated from a thread of the same activity having a non-critical reservation.

7. A method in a computer system for ensuring the timely execution of accepted time constraints submitted by one of a plurality of active threads, the method comprising the steps of:

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 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 specific threads or groups of threads, and identifying undedicated future time intervals that have not been dedicated to executing specific threads or 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 step, declining the received time constraint.

8. The method of claim 7 wherein the received time constraint further specifies a starting time at which the time constraint is to begin, and wherein the determining step determines, using the accessed execution schedule, whether the sum of the undedicated future time intervals occurring both before the deadline specified by the received time constraint and after the starting time specified by the received time constraint is at least as large as the execution time estimates specified by the received time constraint.

9. The method of claim 7 wherein at least a portion of the dedicated future time intervals identified by the execution schedule are dedicated in furtherance of an earlier-received reservation requiring that an identified group of threads receive at least the amount of execution time specified in the estimate during every time period having a specified window length,

and wherein the determining step includes the step of determining that successfully completing the time constraint received in the receiving step would require modifying the schedule to rededicate the future time intervals dedicated in furtherance of the earlier-received reservation to the time constraint received in the receiving step, such that, if the threads of the identified group are executed in accordance with the modified schedule, the identified group of threads would be executed for less than the amount of time specified by the reservation during at least one time period having the window length specified by the reservation.

10. The method of claim 7 wherein at least a portion of the dedicated future time intervals identified by the execution schedule are dedicated in furtherance of an earlier-received time constraint,

and wherein the determining step includes the step of determining that successfully completing the time constraint received in the receiving step would require modifying the schedule to rededicate the future time intervals dedicated in furtherance of the earlier-received time constraint to the time constraint received in the receiving step, such that, if the thread submitting the earlier-received time constraint is executed in accordance with the modified schedule, the earlier-received time constraint would not be successfully completed by its deadline.