Providing predictable scheduling of programs using a repeating precomputed schedule

• US 6,490,612 B1
• Filed: 05/04/2000
• Issued: 12/03/2002
• 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,564
• Time in Patent Office: 943 Days
• Field of Search: 709/107, 709/103, 709/104, 709/226, 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 computer system for scheduling the execution of programs that may include both real-time and non-real-time programs, real-time programs each providing one or more execution timing requests specifying details about when the real-time program is to be executed, comprising:

a processor for executing programs; and

a scheduling subsystem, comprising;

a precomputed schedule identifying a series of recurring intervals, at least one of the intervals being committed to the execution of each real-time program in furtherance of the execution timing requests submitted by the real-time program, at least a portion of the intervals being uncommitted to the execution of any real-time program,

a list of all real-time and non-real-time programs, and

a program selector that traverses the recurring intervals of the precomputed schedule, and;

for each recurring interval committed to the execution of one of the real-time programs, executing with the processor the real-time program to whose execution the recurring interval is committed in furtherance of the execution timing requests submitted by the real-time program to whose execution the recurring interval is committed; and

for each recurring interval not committed to the execution of any real-time program, executing with the processor a program selected from the list of all real-time and non-real-time programs, such that any real-time programs are executed in accordance with their execution timing requests, and such that any non-real time programs are executed fairly.

2. The computer system according to claim 1, wherein the precomputed schedule is represented by a graph comprised of connected nodes each corresponding to a recurring interval, and wherein the program selector completely traverses the graph.

3. The computer system according to claim 2, wherein the graph 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 the leaf, the number of times the execution interval represented by each node occurs during the traveral 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 a program.

4. The computer system according to claim 2, wherein the graph is based on the requests from a plurality of programs, each request specifying a reservation window and an execution time for one of the plurality of programs to be scheduled.

5. The computer system according to claim 1 wherein the list of all real time and non-real time programs is a circular list reflecting an order for distributing undedicated iterations of withheld recurring intervals and specifying a next computer program to receive undedicated iterations of withheld recurring iterations.

6. The computer system according to claim 1 further comprising at least one-real-time program and at least one recurring interval not committed to the execution of any real-time program, wherein the processor executes the non-real-time program in at least one of the recurring intervals not committed to the execution of any real-time program.

7. The computer system according to claim 6 wherein the identity of the non-real-time program is not specified for execution during any recurring interval by the precomputed schedule and no reservation has been previously submitted for the non-real-time program.

8. The computer system according to claim 1 wherein upon notification of a non-real time program, the processor executes the non-real-time program in a recurring interval not committed to the execution of a real-time program.