Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-05-04
2004-04-06
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S226000
Reexamination Certificate
active
06718360
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to the field of processor scheduling, and, more specifically, to the field of scheduling the execution of real-time programs and non-real-time programs.
BACKGROUND OF THE INVENTION
Multitasking operating systems allow a number of different programs to execute “simultaneously” on a single processor. Such multitasking operating systems do so by rapidly switching the processor between the execution of multiple programs.
A single program, also known as a “process,” may have one or more threads. The word “thread” as used herein means the finest scheduleable unit of execution. A thread is typically represented by a data structure called an execution context, which contains state information about the execution of the thread, such as register and stack contents. When the operating system suspends a thread in favor of the execution of another thread, it copies the information from the registers and stack to the thread's execution context. When the operating system subsequently reselects the thread for execution after suspending another thread, it copies the information in the thread's execution context back to the actual registers and stack. In this way, the thread continues executing with the same register and stack contents as when it was suspended. One or more threads often belong to a process, which corresponds to a body of code and which may own certain single-process resources, such as blocks of memory. While processes and programs can be viewed as roughly equivalent, in some cases, multiple processes may be said to constitute a program, and in other cases, a process may include several programs.
The process of determining which threads to execute at which times is generally termed “scheduling” a computer system's CPU. The way in which scheduling is performed can significantly impact a user's perception of whether individual threads are performing adequately. Modern multimedia applications, for example, often require substantial processor time, and appear to proceed slowly or in a jerky fashion if they do not receive the required processor time.
Real-time programs are programs that have an understanding of their execution performance needs and timeliness requirements, and can interact with a real-time interface of the operating system to make those execution performance needs and timeliness requirements known to the operating system, such as multimedia applications and industrial applications. Real-time programs can each have a number of threads of execution, grouped under one or more “activities,” or aspects of the real-time program whose overall execution performance needs differ. Each activity may submit a processor reservation specifying the amount of processor time that its threads collectively need on an ongoing basis. Each thread may itself submit time constraints specifying that it needs a certain amount of processor time by a certain deadline. Reservations and time constraints are known collectively as “execution timing requests.”
Certain conventional schedulers handle reservations and time constraints by maintaining the information relating to the reservations and time constraints for use in identifying the next thread to execute on an ad hoc basis each time the processor becomes available for reassignment to a new thread. This conventional “ad hoc” approach to scheduling has several disadvantages. First, completely reevaluating the relative urgencies of all of the existing threads each time the processor becomes available for reassignment often consumes substantial execution time, which makes this execution time unavailable to the real-time programs. Additionally, the approach cannot guarantee at the time a reservation or time constraint is submitted that the reservation or time constraint will be honored. The ad hoc approach can also cause unnecessarily frequent thread switches, thereby reducing. the efficiency gains resulting from caching information relating to the executing thread. Further, reservations, while honored for specific periods of time under the ad hoc approach, are not executed with the regularity necessary to honor the reservations over every window of time.
SUMMARY OF THE INVENTION
The present invention provides predictable scheduling of real-time programs and non-real-time programs using a repeating precomputed schedule. In accordance with the invention, a thread scheduling software facility (“the scheduler”) overcomes the shortcomings of the conventional ad hoc approach to scheduling by utilizing a precomputed schedule that specifies the future execution of activities and threads having outstanding time constraints, which significantly reduces the processing required to (A) identify the next thread to execute when the processor becomes available and (B) determine the amount of time for which to execute the identified thread. As a result, the process of identifying the next thread to execute and determining the amount of time for which to execute the identified thread can be performed in a bounded amount of time that is independent of the number of threads and activities being scheduled. The precomputed schedule allows the scheduler to assess the feasibility of reservations and time constraints when they are submitted, and immediately refuse any nonfeasible reservations and time constraints. The precomputed schedule also allows the scheduler to guarantee that reservations will be honored with regularity. The precomputed schedule further allows the scheduler to maximize the length of individual intervals assigned to each thread, thereby allowing each thread to make more efficient use of caches. The scheduler further enables blocked activities to receive extra processing time when they are unblocked. The scheduler further effectively schedules the simultaneous execution of real-time and non-real-time programs on the same processor. The scheduler further is able to effectively schedule non-real-time programs in the complete absence of real-time programs, reservations, and constraints.
The precomputed schedule is preferably represented as a directed acyclic graph of nodes, each node corresponding to an execution interval of a specified length, that is incrementally traversed to determine which activity to execute next. (As discussed herein, “executing an activity” means executing one or more threads belonging to the activity.) Each node may either be dedicated to an activity, such that its interval is used to execute that activity, or designated as a “free node,” whose interval may be used to execute any activity. A complete traversal of the graph is made by traversing, in turn, each path from a root node to one of a group of leaf nodes. The sum of the lengths of the intervals of the nodes in each such path is equal. The number of paths that pass through each node determine the frequency with which its interval recurs while traversing the graph.
The scheduler incorporates reservations in the scheduling graph by dedicating one or more nodes of the graph to the activity submitting the reservation. Nodes are selected that are on enough paths to be executed frequently enough to satisfy the reservation, and whose intervals are long enough to satisfy the reservation. When the scheduler traverses to a node dedicated to the activity, the scheduler executes one or more threads of that activity. The scheduler incorporates time constraints in the scheduling graph by allocating to the time constraints specific traversals through nodes of the graph that are either dedicated to the activity of the thread submitting the time constraint or that are free nodes. When the scheduler performs the allocated traversals through these nodes, the thread submitting the time constraint is executed.
REFERENCES:
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5210872 (1993-05-01), Ferguson et al.
patent: 5247675 (1993-09-01), Farrell et al.
patent: 5301333 (1994-04-01), Lee
patent: 5317734 (1994-05-01), Gupta
patent: 5392430 (1995-02-01), Chen et al.
patent: 5467268 (1995-11-01), Sisley et al.
patent: 552851
Draves, Jr. Richard P.
Jones Michael B.
Rosu Daniela
Rosu Marcel-Catalin
Donaghue Larry D.
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
LandOfFree
Providing predictable scheduling of programs using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Providing predictable scheduling of programs using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Providing predictable scheduling of programs using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3261756