Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-03-11
2003-06-24
Banankhah, Majid (Department: 2156)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06584489
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to the field of resource scheduling, and, more specifically, to the field of scheduling the use of one or more microprocessors.
BACKGROUND OF THE INVENTION
Conventional resource management strategies for real-time application programs have been unsatisfactory. A “real-time application program” is an application program that must execute in a predictable and timely fashion in order to operate properly. Many current efforts to provide resource management for real-time application programs may only manage a static set of resources. In other words, the resource set may not change during the course of operation of the system. Another limitation of many conventional resource management strategies is that they only accommodate one type of resource (i.e., the resources must be homogeneous). An additional limitation of many conventional resource management strategies is that they rely upon the resource or the application program to determine which application program should be allocated a resource and what quantity of the resource should be allocated. Another conventional approach has been to rely upon human experts to correctly assign priorities to tasks within the system. Unfortunately, such human experts typically cannot accurately assign priorities for a dynamic mix of real-time application programs.
The process of determining which threads to execute at which times is generally termed “scheduling” a computer system's CPU. Conventional CPU scheduling is an example of an unsatisfactory conventional resource management strategy for real-time applications. A typical conventional scheduling strategy is to divide the processor time resource into “time slices” having a uniform length. At the expiration of a time slice, a conventional scheduler identifies a thread to execute during the next time slice. In a balanced allocation scheme, each ready thread receives one time slice in turn, so that the processor time is divided evenly among the ready threads. In a weighted allocation scheme, each thread specifies the percentage of total processor time it is to receive. The scheduler then uses an accounting process to keep track of the number of time slices each thread has received, and assigns the next time slice to the thread that is furthest from having received its specified percentage. Such time slice scheduling has two significant disadvantages. First, such time slice scheduling can be inefficient because it involves frequent reassignments of the processor. On the other hand, even the weighted allocation scheme does not take into account thread processing requirements finer than the overall percentage of processor time that must be used to successfully schedule multiple threads having significant processor time demands.
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 jerkily if they do not receive it. To ensure adequate performance, conventional multimedia applications and other real-time applications typically secure exclusive use of the processor, to the exclusion of any other existing threads.
A hardware device connected to a computer system typically interacts with the computer system by raising an assigned one of a set of device interrupts. The computer system typically responds to the interrupt by executing an interrupt handling routine corresponding to the raised interrupt. In conventional operating systems, this device interrupt handling is typically performed preemptively by, when a device interrupt occurs, suspending the normal scheduled processing of threads while executing the interrupt processing routine. As a result, time-critical threads can be suspended for significant periods of time when their execution coincides with device interrupts.
SUMMARY OF THE INVENTION
The preferred embodiment of the present invention provides a resource management mechanism for arbitrating resource requests and resource usage among independent real-time application programs that run simultaneously on a single machine or set of machines. The resource management mechanism is adaptable to installation on a distributed system having separate computer systems by installing the mechanism on each of the computer systems within the distributed system. The resource management mechanism utilizes dynamic feedback to adapt to changing resource availability and resource requirements. In addition, the resource management mechanism is extensible so that the resource management employed in the system accounts for new resources that are added to the system and for resources that are removed from the system. The resource management mechanism separates resource management policy from resource management mechanism such that the mechanism is independent of the policy. The mechanism for implementing policy is generalized so as to facilitate any one of a number of different policies. In the preferred embodiment of the present invention, real-time application programs are resource self-aware in that they are aware of what resources they require and what quantity of those resources they require. The applications negotiate with the resource management mechanism to reserve resources and ensure predictable performance. Programs may perform one or more “activities,” and reserve resources on behalf of a particular one of their activities. Reserved resources are provided to either that activity or to threads making up the activity as a whole by resource providers.
The present invention further provides a method and system for scheduling the execution of threads using optional time-specific scheduling constraints. In a preferred embodiment, a thread scheduling software facility (“the scheduler”) uses a unified urgency indicator to schedule the execution of each of a plurality of threads producing predictable performance in which the threads are scheduled to execute when needed. The scheduler maintains an urgency indicator for each thread based either on a time-specific scheduling constraint that specifies an absolute deadline for a specified quantity of work or on a time-general scheduling constraint that specifies a percentage of processor time to be dedicated to the thread, depending on which type of scheduling constraint is specified for the thread. Modem multimedia applications demand time-specific scheduling for acceptable performance, and their threads are examples of threads for which time-specific scheduling constraints are specified. Modem applications generally also specify time-general scheduling constraints for their threads, which specify the percentage of processor time to be dedicated to the execution of the thread in the long term. Many older legacy programs, on the other hand, specify only time-general scheduling constraints for their threads. If no scheduling constraints are specified for a thread, the facility, or another entity such as the operating system, preferably specifies a default time-general scheduling constraint so that the scheduler permits the thread to execute. The threads scheduled by the scheduler preferably include threads for performing device interrupt handling, so that device interrupt handling is scheduled against the tasks performed by other executing programs.
REFERENCES:
patent: 5303369 (1994-04-01), Borcherding et al.
patent: 5388097 (1995-02-01), Baugher et al.
patent: 5581703 (1996-12-01), Baugher et al.
patent: 5586264 (1996-12-01), Belknap et al.
patent: 5640595 (1997-06-01), Baugher et al.
patent: 6282561 (2001-08-01), Jones et al.
patent: 0 415 515 (1991-03-01), None
Anderson, David P., “Metascheduling for Continuous Media,”ACM Transactions on Computer Systems, vol. 11(3): 226-252, 1993.
Locke, Douglass C.,Best-Effort Decision Making for Real-Time Scheduling, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 1986, pp. 1-144.
Northcutt et al.,Decentralized Real-Time Scheduling, Rome Air
Barrera, III Joseph S.
Draves, Jr. Richard P.
Fitzgerald Robert P.
Jones Michael B.
Leach Paul J.
Banankhah Majid
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
LandOfFree
Method and system for scheduling the use of a computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for scheduling the use of a computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for scheduling the use of a computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118316