Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-05-22
2001-07-17
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06263359
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to scheduling resources in a computer system.
2. Description of the Related Art
The general goal of resource scheduling is to order the use of or access to the resource by tasks to meet a set of system-level and/or user-level objectives. For example, these objectives may include resource utilization objectives among different types (i.e. classes) of tasks, satisfying wait/response time objectives among different task classes, providing predictable (i.e. low variance) performance within and across task classes, allocating resources in a fair manner, and favoring tasks with short resource usage/holding time over tasks with long usage/holding time.
Many of these scheduling goals are often in conflict, thus making resource scheduling a complex design problem. Given this complexity, many scheduling algorithms have been designed to meet only a subset of the above objectives. While these policies are typically effective within their intended domains, they often have limited success, or they do not perform well at all in system environments with different requirements. Indeed, it is not unusual to find systems in which the scheduling and dispatching parameters must be manually adjusted in response to large changes in customer workload. This requirement gives rise to undesirable complexity and overhead. Thus, in addition to supporting multiple diverse scheduling objectives, a principal design challenge is to provide effective control over resource allocation to achieve the desired performance requirements for these simultaneous objectives.
The present invention addresses these problems.
SUMMARY OF THE INVENTION
It is a primary object of the invention to achieve proportional usage and response time performance objectives for the use of or the access to a resource within a unified and integrated scheduling mechanism of a computer system.
It is a further object of the invention to provide both “usage” and “response” mode scheduling of a computer resource, for example, a processor, wherein one mode is effected within the confines of a job class that has been constrained by the other mode.
It is still another object to allow for a system to dynamically adjust to changes in workload requirements for a resource without manual intervention.
It is another object of this invention to provide general, flexible and adaptive control over resource allocation to achieve diverse scheduling objectives and performance requirements.
It is another object of the invention to schedule a resource in a computer using a hierarchical scheme that supports the combination of “usage” and “response” mode objectives in a general and flexible manner, and to as many levels as desired.
Another object of the invention is to schedule a resource using general time-based functions that are driven by resource utilization and response time objectives, an adaptive feedback mechanism, and a notion of resource requester classes.
It is yet another object of the invention to schedule a computer resource for “classes” of requests, wherein a class consists of a group of requesters that have the same performance objective in relation to other classes of requesters in the system.
Still another object of the invention is to provide a job class scheduler that includes a migration mechanism associated with each class such that a given job that “taxes” the resource is migrated to a lower priority job class upon meeting a set of usage criteria.
A still further object is to use the unified and integrated methodology of the invention to address and solve known scheduling problems that have not been adequately solved by the prior art.
According to the invention, resource scheduling is performed for jobs in job classes within a unified framework according to “time-functions.” Each job class has a “time-function” associated with it, the value of which dynamically controls when the job class is selected for scheduling as the resource becomes available. A time-function can be any function of “time” in the most general sense, such as a formula that determines the certain values returned by the function given values of a set of variables (or input parameters). The “time” parameter can be any measure of time with respect to the resource and other resources that are used to evaluate the per-class time-function value. In the preferred operation, the time-functions can be based on a general “usage” mode, in which the time parameter is any measure of the use of the resource or set of resources by the class, a general “response” mode, in which the time parameter is any measure of the waiting for the resource or set of resources by the class, or any combination of such modes. Any general order relation, or choice function, can then be used to determine which class should be selected based on the per-class time-function values. Example choice functions include the maximum and minimum operator, but in the preferred operation, the choice function is typically the operator that chooses the minimum value among the time-function values being considered. Once a job class is selected for scheduling, a job within that class is provided to the resource for execution.
According to another feature of the inventive scheduling framework, the job classes vying for a resource's attention are arranged in a general “hierarchy.” The time-functions associated with the classes of each level of the hierarchy have the same “mode.” However, each mode is preferably of equal and consistent viability. Moreover, the system administrator and/or user can arrange the job classes and the time-function modes at each level in any manner desired, and for as many levels as desired. For example, the top level of the hierarchy may consist of several job classes among which the resource is allocated to maintain a set of proportional utilization goals. Each of these classes has a usage-mode time-function associated with it that dynamically controls which class is selected for scheduling when the resource becomes available. At the next level of the hierarchy, each of the top-level classes may comprise several subclasses among which the resource is allocated to maintain a set of response time objectives. Each of these subclasses has a response-mode time-function associated with it that dynamically controls which subclass is selected for scheduling when its parent class is selected at the top level of the hierarchy. This hierarchical scheduling framework is completely general and can be recursively defined to as many levels as necessary/desired.
According to another feature of the invention, the collection of job classes at each level of the scheduling hierarchy can be partitioned into “groups” of job classes with the first group having absolute priority over all other groups, in the sense that job classes in other groups are not considered for access to the resource unless all classes in the first group are empty. The second job class group has absolute priority over all other groups except the first job class group, and a similar absolute priority ordering is defined for the remaining job class groups. The time-functions for the classes in each group have similar forms in the sense that they are either constant (i.e they do not vary with “time”), or they vary dynamically according to either “usage” or “response” mode. For example, a first job class group may comprise high-priority short system tasks, interactive work (wherein only a small amount of resource usage occurs between substantial idle periods), and jobs with real-time contraints that have absolute priority over other classes of work.
In one preferred embodiment, it is preferably intended to exploit the job class grouping primarily at the top level of the hierarchy at any level or combination of levels of the heirarchy. However, the present invention includes general use of job class groups together with the scheduling hierarchy,
Several adaptive feedback mechanisms are preferably a feature of the inventive scheduling framework. One such techni
Fong Liana Liyow
Hough Roger Eldred
Squillante Mark Steven
Banankhah Majid A.
International Business Machines - Corporation
LaBaw Jeffrey S.
LandOfFree
Computer resource proportional utilization and response time... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer resource proportional utilization and response time..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer resource proportional utilization and response time... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457550