Providing predictable scheduling of programs using a repeating precomputed schedule

• US 6,718,360 B1
• Filed: 05/04/2000
• Issued: 04/06/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: Rosu, Marcel-Catalin, Rosu, Daniela, Draves, Richard P. Jr., Jones, Michael B.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US09/564,881
• Time in Patent Office: 1,433 Days
• Field of Search: 709/300-305, 709/103, 709/104, 709/107, 709/226, 710/244, 701/129, 370/232, 370/319, 370/327
• 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 scheduling the execution of threads of two or more computer programs, the method comprising the steps of:

accessing a schedule 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 the steps of selecting a thread for execution are performed in a bounded amount of thread that is independent of the number of threads and computer programs being scheduled.

2. The method of claim 1, further including the step of executing each thread selected for execution in response to the selection of the thread for execution.

3. The method of claim 1 wherein the accessing step is preceded by the steps of:

dividing the repeating schedule into the series of recurring intervals each having a specified duration; and

for each of the computer programs on whose behalf a reservation was submitted, assigning at least one of the recurring intervals exclusively to the computer program such that the sum of the durations of the recurring intervals assigned to the computer program is at least as large as the amount specified by the reservation of the computer program.

4. The method of claim 3 wherein, for one or more of the computer programs, no reservation is submitted on behalf of the computer program, and wherein the assigning step omits to assign at least one of the recurring intervals, and further including the step of, for each recurring interval visited, if the recurring interval is not assigned to any computer program, selecting for execution a thread from among all of the threads of all of the programs, such that, in some cases, threads of computer programs on whose behalf no reservations are submitted are selected for execution.

5. The method of claim 1 wherein the schedule is represented by a graph comprised of connected nodes each corresponding to a recurring interval,

and wherein the step of iterating through the series of recurring intervals includes the step of performing a complete traversal of the graph.

6. The method of claim 1 wherein, for each time constraint, the executing step executes the thread that is the subject of the time constraint in the iterations of the recurring intervals that are dedicated to the time constraint.

7. The method of claim 1 wherein, for each iteration of a recurring interval that is dedicated to any time constraint, the executing step executes the thread that is the subject of the time constraint having the earliest deadline.

8. The method of claim 1, further including the steps of:

receiving a nested time constraint submitted on behalf of an identified thread on whose behalf an existing active time constraint was submitted, the nested time constraint specifying a start time, a deadline, and an execution time estimate; and

in response to the receiving step, modifying the schedule to specify that the identified thread is to be executed during one or more intervals in satisfaction of the nested time constraint, such that the occurrences between the specified start time and the specified ending time of the recurring intervals specifying either that the identified thread is to be executed during the interval in satisfaction of the existing time constraint or that the identified thread is to be executed during the interval in satisfaction of the nested time constraint total at least the specified execution time estimate.

9. The method of claim 1, further including the steps of:

determining that a thread on whose behalf a time constraint was submitted has blocked on a synchronization mechanism;

identifying the thread owning the synchronization mechanism; and

transferring the time constraint of the blocked thread to the owning thread, such that, for visited recurring intervals that specify the identity of the blocked thread that is to be executing during the recurring interval in satisfaction of the time constraint, the step of selecting for execution the thread whose identity is specified by the visited recurring interval selects for execution the owning thread instead of the blocked thread.

10. The method of claim 9, further including the step of, when the blocked thread is unblocked, transferring the time constraint back to the blocked thread, such that, for visited recurring intervals that specify the identity of the blocked thread that is to be executing during the recurring interval in satisfaction of the time constraint, the step of selecting for execution the thread whose identity is specified by the visited recurring interval selects for execution the blocked thread.

11. The method of claim 3 wherein the assigning step includes the step of withholding from assignment to any computer program a plurality of the recurring intervals of the series.

12. The method of claim 11 wherein the withheld recurring intervals are distributed substantially evenly across each iteration of the series of recurring intervals.

13. The method of claim 11, further including the steps of:

receiving a new time constraint on behalf of one of the threads; and

assigning to the thread on whose behalf the new time constraint was received specific iterations through their recurring intervals assigned to the computer program of the thread on whose behalf the new time constraint was submitted.

14. The method of claim 13 wherein the step of assigning interval iterations to the new time constraint also assigns to the new time constraint one or more iterations of one of the withheld intervals.

15. The method of claim 13 wherein the executing step includes the step of, for iterations of a withheld recurring interval assigned to the new time constraint, executing the thread on whose behalf the new time constraint was submitted.

16. The method of claim 11, further comprising the step of maintaining a circular list of the computer programs reflecting an order for distributing undedicated iterations of withheld recurring intervals and specifying a next computer program to receive undedicated iterations of withheld recurring intervals,

and wherein the executing step includes the step of, for iterations of withheld recurring intervals not dedicated to any time constraint, executing a thread of the next computer program specified by the circular list of activities.

17. The method of claim 16 wherein at least one of the computer programs is a non-real-time program on whose behalf no reservation has been submitted, and whose identity is not specified for execution during any recurring interval by the schedule, and wherein the step of executing a thread of the next computer program specified by the circular list of activities in some cases executes a thread of the non-real-time program, such that threads of the non-real-time computer program are executed despite the fact that no reservation was submitted on behalf of the non-real-time program.

18. The method of claim 16 wherein each of the computer programs is a non-real-time program on whose behalf no reservation is submitted, and wherein the withholding step withholds from assignment to any computer program all of the recurring intervals of the series, and wherein the step of executing a thread of the next computer program specified by the circular list of activities in each case executes a thread of a non-real-time program, such that threads of the non-real-time programs are executed despite the fact that no reservations have been submitted on their behalf.

19. The method of claim 16, further comprising the step of, for each computer program, maintaining a circular list of the threads of the computer program reflecting an order for distributing undedicated iterations of withheld recurring intervals and specifying a next thread to receive undedicated iterations of withheld intervals,

and wherein the executing step includes the step of, for iterations of withheld recurring intervals not dedicated to any time constraint, executing the next thread of the next computer program specified by the circular list of activities and the circular list of threads of the next computer program.

20. A method in a computer system for scheduling the execution of a plurality of Cads based in part on time constraints each submitted on behalf of one of the threads, each time constraint being either active or inactive, each thread belonging to one of one or more activities, the method including the steps of:

based in part on the active time constraints, selecting an activity for execution;

if any time constraint submitted on behalf of one of the threads of the selected activity is inactive, selecting for execution the thread upon whose behalf the time constraint was submitted; and

if no time constraint submitted on behalf of one of the threads of the selected activity is inactive, selecting a thread for execution from among all of the threads belonging to the selected activity.

21. A method in a computer system for scheduling the execution of a plurality of activities each having one or more threads, each thread capable of either being executable or being blocked, the method comprising the steps of:

(a) generating a schedule specifying, for a plurality of future times, which activity will be executing unless all of the threads of that activity are blocked;

(b) executing the threads of each activity in accordance with the schedule generated in step (a);

(c) during the performance of step (b), identifying an activity whose threads are all blocked;

(d) in response to step (c), when any of the threads of the identifier activity is unblocked, determining whether the threads of the identified activity were all blocked for at least a threshold amount of time; and

(e) if the threads of the identified activity were not all blocked for at least the threshold amount of time, executing one or more threads of the identified activity during times for which the schedule generated in step (a) does not specify that the identified activity will be executing, in order to compensate for the failure of the identified activity to execute while all of its threads were blocked.

22. The method of claim 21, further including the step of, while the threads of the identified activity are all blocked, executing threads of activities other than the identified activities during times for which the schedule specifies that the identified activity will be executing.

23. A computer-readable medium whose contents cause a computer system to schedule the execution of threads of two or more of the computer programs by performing the steps of:

accessing a schedule 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 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 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 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.

24. The computer-readable medium of claim 23, wherein the contents of the computer-readable medium further cause the computer system to perform the step of executing each thread selected for execution in a response to the selection of the thread for execution.