Providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems

• US 6,745,222 B1
• Filed: 07/08/1999
• Issued: 06/01/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., Regehr, John
• Primary Examiner(s): DONAGHUE, LARRY D
• Application Number:
  US09/350,083
• Time in Patent Office: 1,790 Days
• Field of Search: 709/107, 709/103, 709/102, 709/104, 709/105, 709/229, 709/320
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

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.

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 is performed in a bounded amount of time that is independent of the number of threads and computer programs being scheduled.

2. The method of claim 1, wherein accessing a schedule for at least one of the processors comprises accessing a schedule for the plurality of processors.

3. The method of claim 1, wherein accessing a schedule for at least one of the processors comprises accessing a schedule for one of the processors.

4. The method of claim 1, wherein accessing a schedule for at least one of the processors comprises accessing a schedule for a subset of the processors.

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

6. The method of claim 1 wherein the computer system is a discrete-clock computer system having a discrete clock time-keeping interval and accessing is preceded by:

dividing the repeating schedule into the series of recurring intervals, each having a specified duration such that the recurring intervals are rounded to a multiple of the discrete clock time-keeping interval; 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.

7. The method of claim 6 wherein, for at least one of the computer programs, no reservation is submitted on behalf of the computer program, and wherein the assigning omits to assign at least one of the recurring intervals, and further including, 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.

8. The method of claim 6, further comprising modifying the minimum period of the discrete-clock computer system based on the series of recurring intervals.

9. The method of claim 1 wherein the schedule is represented by a graph comprising connected nodes each corresponding to a recurring interval, and wherein iterating through the series of recurring intervals includes performing a complete traversal of the graph.

10. The method of claim 1 wherein, for each time constraint, the executing 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.

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

12. The method of claim 1, further including:

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, modifying the schedule to specify that the identified thread is to be executed during at least one interval 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.

13. The method of claim 1, further including:

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, 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.

14. The method of claim 13, further including, 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, selecting for execution the thread whose identity is specified by the visited recurring interval selects for execution the blocked thread.

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

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

17. The method of claim 15, further including:

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.

18. The method of claim 17 wherein assigning interval iterations to the new time constraint also assigns to the new time constraint at least one iteration of one of the withheld intervals.

19. The method of claim 17 wherein the executing includes, 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.

20. The method of claim 15, further comprising 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 includes, 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.

21. The method of claim 20 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 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.

22. The method of claim 20 wherein each of the computer programs is a non-real-time program on whose behalf no reservation is submitted, and wherein the withholding withholds from assignment to any computer program all of the recurring intervals of the series, and wherein 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.

23. The method of claim 20, further comprising, 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 includes, 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.