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

• US 7,107,593 B2
• Filed: 05/13/2004
• Issued: 09/12/2006
• Est. Priority Date: 01/09/1997
• Status: Expired due to Fees

• 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:
  US10/845,404
• Publication Number:
  US 20040210904A1
• Time in Patent Office: 852 Days
• Field of Search: 718/104, 718/103, 718/107, 709/226
• US Class Current: 718/103
• 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 for a computer system having a plurality of processors and on which a particular processor already has scheduled thereon a reservation for a thread in the activity, the reservation specifying a recurring desired number of time units within a desired period, the method comprising:

receiving a constraint for the thread in the activity specifying a desired earliest start time, amount of requested execution time, and a deadline;

determining whether the constraint can be scheduled on the particular processor;

upon determining that the constraint can be scheduled on the particular processor, scheduling the constraint on the particular processor;

otherwise, determining whether one of a second reservation and a constraint for a second thread is also scheduled on the particular processor, such that absence of the one of the second reservation and the constraint would permit scheduling the constraint on the particular processor; and

,

upon determining that there is one of a second reservation and a constraint for a second thread scheduled on the particular processor such that the absence thereof would permit scheduling the constraint on the particular processor, moving the one of the second reservation and the constraint to another processor and scheduling the constraint on the particular processor.