Providing predictable scheduling of programs using a repeating precomputed schedule

• US 6,317,774 B1
• Filed: 01/09/1997
• Issued: 11/13/2001
• 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:
  US08/781,106
• Time in Patent Office: 1,769 Days
• Field of Search: 709/300-305, 709/100-107, 709/226, 395/706, 395/208, 370/232, 370/319, 370/327, 705/9, 710/244, 701/129
• 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 activities at different frequencies, each activity being comprised of one or more threads, the method comprising the steps of:

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 step, constructing a graph for scheduling the execution of the activities that is comprised of nodes each representing a recurring execution interval, the graph having one root, one or more leaves, 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 one or more of the threads of the activity to which the node is dedicated for a period of time substantially equal to the execution interval length of the node.

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

completely traversing the constructed graph by visiting the nodes of the graph along each path from the root of the graph to a leaf of the graph; and

for each node of the graph visited during the traversal, executing one or more of the threads of the activity to which the node is dedicated for the time interval specified for the node.

3. The method of claim 2 wherein the traversing and executing steps are repeated multiple times.

4. The method of claim 2 wherein each activity has exactly one thread that is executed in the executing step.

5. A method in a computer system having a processor for scheduling the execution of a plurality of activities each having one or more threads, the method comprising the steps of:

accessing an activity scheduling graph comprised of nodes each representing a recurring execution interval, the graph having one root, one or more leaves, 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 the 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 and being adapted to being dedicated to executing the threads of a single activity;

selecting a current node within the accessed graph;

when the processor becomes available, advancing from the current node to a new current node in accordance with a root-to-leaf traversal of the graph; and

executing the 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.

6. The method of claim 5, further including the step of repeating the advancing and executing steps multiple times to traverse a plurality of nodes and execute the threads of the activities to which the traversed nodes are dedicated.

7. A computer-readable medium whose contents cause a computer system having a processor to schedule the execution of a plurality of activities each having one or more threads by performing the steps of:

accessing an activity scheduling graph comprised of nodes each representing a recurring execution interval, the graph having one root, one or more leaves, 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 the 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 and being adapted to being dedicated to executing the threads of a single activity;

selecting a current node within the accessed graph;

when the processor becomes available, advancing from the current node to a new current node in accordance with a root-to-leaf traversal of the graph; and

executing the 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.

8. A method in a computer system for scheduling units of execution of one or more activities, the method comprising the steps of:

receiving a request from a plurality of activities to be scheduled, each request specifying a reservation window and an execution time for one of the plurality of activities to be scheduled;

constructing a scheduling graph based on the received requests, a node in the scheduling graph indicating an activity that will be executed at each of a plurality of future times for a specified time interval; and

executing the units of execution in the activity in accordance with the scheduling graph such that the execution timing requests are satisfied.

9. A computer-readable medium whose contents cause a computer system to schedule the execution of units of execution of one or more activities by performing the steps of:

receiving requests from a plurality of activities to be scheduled, each request specifying a reservation window and an execution time for one of the plurality of activities to be scheduled;

constructing a scheduling graph based on the received requests, a node in the scheduling graph indicating an activity that will be executed at each of a plurality of future times for a specified time interval; and

executing the units of execution in the activity in accordance with the scheduling graph such that the execution timing requests are satisfied.

10. A computer memory containing a scheduling graph data structure for scheduling the execution of activities at different frequencies, each activity being comprised of one or more threads, the scheduling graph having one root, one or more leaves, 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, nodes being dedicated to the execution of the threads of each activity having a total execution interval, the graph being usable to schedule the execution of activities at different frequencies by traversing the graph in a root-to-leaf manner and, for each node visited in the traversal, executing one or more of the threads of the activity to which the node is dedicated for a period of time substantially equal to the execution interval length of the node, such that activities whose nodes are on a greater number of paths are executed with greater frequency.