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

• US 7,162,720 B2
• Filed: 05/10/2004
• Issued: 01/09/2007
• 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/842,213
• Publication Number:
  US 20040210901A1
• Time in Patent Office: 974 Days
• Field of Search: 718/104, 718/105, 718/107, 718/103, 709/226
• 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 for a computer system having a plurality of processors comprising:

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

determining the thread has previously been run on a particular processor;

upon determining that the thread has previously been run on a particular processor,

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 using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule;

otherwise, scheduling the constraint on a different processor; and

,

otherwise, scheduling the constraint on a different processor.

2. A method for a computer system having a plurality of processors comprising:

receiving a reservation for an activity that previously had no reservations, the reservation specifying a recurring desired number of time units within a desired period;

determining whether a thread within the activity has previously been run on a particular processor;

upon determining that the thread has previously been on a particular processor,

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

upon determining that the reservation can be scheduled on the particular processor, scheduling the reservation on the particular processor using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule;

otherwise, scheduling the reservation on a different processor; and

,

otherwise, scheduling the reservation on a different processor.

3. One or more computer readable media comprising computer executable instructions that, when executed by a computer having a plurality of processors, direct the computer to:

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

determine the thread has previously been run on a particular processor;

when it is determined that the thread was previously run on a particular processor,

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 using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule;

otherwise, scheduling the constraint on a different processor; and

,

when it is determined that the thread was not previously run on a particular processor, scheduling the constraint on a different processor.