Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-07-08
2004-06-01
Donaghue, Larry (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S226000
Reexamination Certificate
active
06745222
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 one or more processors. Such multitasking operating systems do so by rapidly switching the processor between the execution of multiple programs.
A multitasking operating system may operate on an underlying platform having either one or multiple processors. A single-processor system is referred to as a uniprocessor system. A system having multiple processors is referred to as a multiprocessor system. Having more processors available generally means that more programs can be executed simultaneously on a single system.
An operating system can also have either discrete or continuous clock or timing facility. A continuous-clock system as used herein refers to the lowest granularity of timing at which an item can be scheduled relative thereto being many orders less than the units of work to be scheduled, such that to the system the timing is effectively continuous—that is, any desired start time, stop time, and/or duration of an activity can be specified with accuracy. Conversely, a discrete-clock system as used herein refers to the lowest granularity of timing at which an item can be scheduled relative thereto being on about the same order as the units of work to be scheduled, such that to the system the timing appears discrete—that is, any desired start time, stop time, and/or duration of an activity cannot be specified with as great as accuracy as in a continuous system. For example, a continuous-clock system may allow for timing to be specified in microsecond increments, while the items to be scheduled may have durations on the order of milliseconds, such that relative to the scheduled items, the clock appears continuous. As a further example, a discrete-clock system may allow for timing to be specified only in millisecond increments (which can be referred to as the discrete clock time-keeping interval)—the same order of timing for which the scheduled items may be specified in, such that relative to the scheduled items, the clock is discrete, which is a barrier for providing accurately scheduled items as desired.
Furthermore, a discrete-clock system may also be either periodic or aperiodic. A periodic-clock system has timing interrupts at regular intervals, for example, at times 0, 1, 2, 3, 4, etc. That is, a periodic clock provides scheduling interrupts on a periodic basis. Conversely, an aperiodic-clock system allows for the skipping of unwanted or undesired intervals. Several potential interrupt intervals may be skipped, such that intervals are instead provided at, for example, 0, 1, 7, 9, 10, 11, 17, 19, etc.
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. Modem 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.
In the copending and coassigned application entitled “Providing Predictable Scheduling of Programs Using A Repeating Precomputed Schedule,” filed on Jan. 9, 1997, and assigned Ser. No. 08/781,106, of which the current application is a continuation-in-part, a real-time scheduler is described. However, the real-time scheduler has three primary limitations: first, it operates only a uniprocessor system, not on multiprocessor systems; second, it uses a continuous aperiodic clock, not a discrete clock, and in particular not the more common periodic clock; and, third, it does not utilize the existing scheduler of an operating system such as Windows NT, but rather specifies its own scheduler. For these and other reasons, there is a need for the present invention.
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 identifyi
Jones Michael B.
Regehr John
Donaghue Larry
Leydig Voit & Mayer LTD
Microsoft Corporation
LandOfFree
Providing predictable scheduling of programs using repeating... 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 repeating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Providing predictable scheduling of programs using repeating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293119