US6263359B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer resource proportional utilization and response time scheduling
Assignee: International Business Machines Corp
•
Filing: 1997-05-22
•
Granted: 2001-07-17
•
Expires: 2017-05-22
Abstract
Abstract A method of scheduling jobs to be executed by a resource in a computer system wherein the jobs are grouped in “classes.” The job classes vying for the resource's attention are arranged in a hierarchy. Each job class has a time-function value that controls when the job class is selected by the resource if processing time becomes available. Within a particular level of the hierarchy, scheduling priorities are defined by one or more time-based functions, each of which may be constant or dynamically varying. When constant time-based functions are used, each job class has a schedule value that remains fixed with time. When dynamic time-based functions are used, job class “time-function values” are modified to alter the timing by which the job class(es) acquire the resource.
Inventors
- 👤 Liana Liyow Fong
- 👤 Mark Steven Squillante
- 👤 Roger Eldred Hough
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 08:14
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
110 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: organizing the jobs into a hierarchy comprising groups of job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; proportionally allocating the resource to the hierarchy according to a usage objective; proportionally allocating the resource to the hierarchy according to a response objective; and scheduling job classes for execution to satisfy an objective selected from the group of objectives consisting of the usage objective, the response time objective and a combination of the usage and response time objectives.
Claim 2
Independent Claim
110 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: organizing the jobs into a hierarchy comprising groups of job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; proportionally allocating the resource to the hierarchy according to a usage objective; proportionally allocating the resource to the hierarchy according to a response objective; and scheduling job classes for execution to satisfy an objective selected from the group of objectives consisting of the usage objective, the response time objective and a combination of the usage and response time objectives.
Claim 3
Dependent Claim
22 words
The method as described in claim 1 wherein the usage objective proportionally allocates the resource to job classes within a given group.
Claim 4
Dependent Claim
30 words
The method as described in claim 2 wherein the response objective proportionally allocates the resource to subclasses within a particular job class of the job classes with the given group.
Claim 5
Dependent Claim
22 words
The method as described in claim 1 wherein the response objective proportionally allocates the resource to job classes within a given group.
Claim 6
Dependent Claim
30 words
The method as described in claim 4 wherein the usage objective proportionally allocates the resource to subclasses within a particular job class of the job classes with the given group.
Claim 7
Dependent Claim
27 words
The method as described in claim 1 wherein at least a first group of job classes has a higher priority than a second group of job classes.
Claim 8
Dependent Claim
28 words
The method as described in claim 6 wherein the first group of job classes comprises job classes comprising short system tasks, interactive tasks and jobs with real-time constraints.
Claim 9
Dependent Claim
23 words
The method as described in claim 7 wherein each of the job classes in the first group is associated with a constant time-function.
Claim 10
Dependent Claim
26 words
The method as described in claim 7 wherein each of the job classes in the second group of job classes is associated with a dynamic time-function.
Claim 11
Dependent Claim
17 words
The method as described in claim 1 further including the step of modifying the response time objective.
Claim 12
Dependent Claim
26 words
The method as described in claim 10 wherein the response time objective is modified by adaptively adjusting time-function values associated with one or more job classes.
Claim 13
Dependent Claim
17 words
The method as described in claim 1 further including the step of modifying the usage time objective.
Claim 14
Dependent Claim
26 words
The method as described in claim 12 wherein the usage time objective is modified by adaptively adjusting time-function values associated with one or more job classes.
Claim 15
Dependent Claim
21 words
The method as described in claim 1 further including the step of migrating a job between job classes of a group.
Claim 16
Dependent Claim
32 words
The method as described in claim 14 further including the step of returning the job to an originating job class if the job does not access the resource within a given time.
Claim 17
Independent Claim
100 words
A method of scheduling jobs to be executed by a processor in a computer system, comprising the steps of: organizing the jobs into a hierarchy comprising job classes, wherein at least one job class has a set of subclasses associated therewith; proportionally allocating the processor to the hierarchy according to a usage objective; proportionally allocating the processor to the hierarchy according to a response objective; and scheduling job classes for execution to satisfy an objective selected from the group of objectives consisting of the usage objective, the response time objective and a combination of the usage and response time objectives.
Claim 18
Independent Claim
100 words
A method of scheduling jobs to be executed by a processor in a computer system, comprising the steps of: organizing the jobs into a hierarchy comprising job classes, wherein at least one job class has a set of subclasses associated therewith; proportionally allocating the processor to the hierarchy according to a usage objective; proportionally allocating the processor to the hierarchy according to a response objective; and scheduling job classes for execution to satisfy an objective selected from the group of objectives consisting of the usage objective, the response time objective and a combination of the usage and response time objectives.
Claim 19
Dependent Claim
19 words
The method as described in claim 16 wherein the usage objective proportionally allocates the processor to the job classes.
Claim 20
Dependent Claim
22 words
The method as described in claim 17 wherein the response objective proportionally allocates the processor to subclasses within a particular job class.
Claim 21
Dependent Claim
19 words
The method as described in claim 16 wherein the response objective proportionally allocates the processor to the job classes.
Claim 22
Dependent Claim
22 words
The method as described in claim 19 wherein the usage objective proportionally allocates the processor to subclasses within a particular job class.
Claim 23
Dependent Claim
17 words
The method as described in claim 16 further including the step of dynamically adjusting the response objective.
Claim 24
Dependent Claim
17 words
The method as described in claim 16 further including the step of dynamically adjusting the usage objective.
Claim 25
Dependent Claim
19 words
The method as described in claim 16 further including the step of selectively migrating a job between job classes.
Claim 26
Dependent Claim
34 words
The method as described in claim 23 further including the step of selectively returning the job back to an originating job class if the job does not access the resource within a given time.
Claim 27
Dependent Claim
102 words
A computer, comprising: processor, an operating system, and a scheduler run by the operating system for scheduling jobs to be executed by the processor, the scheduler comprising: means for organizing the jobs into a hierarchy comprising job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; means for proportionally allocating the processor to the hierarchy according to a usage objective; means for proportionally allocating the processor to the hierarchy according to a response objective; and means for scheduling jobs for execution to satisfy the usage and response time objectives.
Claim 28
Dependent Claim
102 words
A computer, comprising: processor, an operating system, and a scheduler run by the operating system for scheduling jobs to be executed by the processor, the scheduler comprising: means for organizing the jobs into a hierarchy comprising job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; means for proportionally allocating the processor to the hierarchy according to a usage objective; means for proportionally allocating the processor to the hierarchy according to a response objective; and means for scheduling jobs for execution to satisfy the usage and response time objectives.
Claim 29
Dependent Claim
84 words
A computer program product in a computer-readable medium, comprising: means for organizing the jobs into a hierarchy comprising job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; means for proportionally allocating the processor to the hierarchy according to a usage objective; means for proportionally allocating the processor to the hierarchy according to a response objective; and means for scheduling jobs for execution to satisfy the usage and response time objectives.
Claim 30
Dependent Claim
84 words
A computer program product in a computer-readable medium, comprising: means for organizing the jobs into a hierarchy comprising job classes, wherein at least one group of job classes includes at least one job class having a set of subclasses associated therewith; means for proportionally allocating the processor to the hierarchy according to a usage objective; means for proportionally allocating the processor to the hierarchy according to a response objective; and means for scheduling jobs for execution to satisfy the usage and response time objectives.
Claim 31
Independent Claim
61 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a response mode objective, wherein each of the job classes has associated therewith a monotonically non-increasing time-function value; and scheduling job classes for execution to satisfy the response mode objective.
Claim 32
Independent Claim
61 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a response mode objective, wherein each of the job classes has associated therewith a monotonically non-increasing time-function value; and scheduling job classes for execution to satisfy the response mode objective.
Claim 33
Dependent Claim
50 words
The method as described in claim 27 wherein the time-function value for each job class is determined by a waiting time of an oldest job in the job class and the job classes are scheduled at each scheduling epoch by selecting a given job class having a minimum time-function value.
Claim 34
Independent Claim
61 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a usage mode objective, wherein each of the job classes has associated therewith a monotonically non-decreasing time-function value; and scheduling job classes for execution to satisfy the usage mode objective.
Claim 35
Independent Claim
61 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a usage mode objective, wherein each of the job classes has associated therewith a monotonically non-decreasing time-function value; and scheduling job classes for execution to satisfy the usage mode objective.
Claim 36
Dependent Claim
50 words
The method as described in claim 29 wherein the time-function value for each job class is determined by an accumulated usage by all the jobs in the job class and the job classes are scheduled at each scheduling epoch by selected a given job class having a minimum time-function value.
Claim 37
Independent Claim
106 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a response mode objective, wherein each of the job classes has associated therewith a monotonically non-increasing time-function value; proportionally allocating the resource to a set of job classes according to a usage mode objective, wherein each of the job classes has associated therewith a monotonically non-decreasing time-function value; and scheduling job classes for execution to satisfy the response mode objective, the usage mode objection, or a combination of the response mode and usage mode objectives.
Claim 38
Independent Claim
106 words
A method of scheduling jobs to be executed by a resource in a computer system, comprising the steps of: proportionally allocating the resource to a set of job classes according to a response mode objective, wherein each of the job classes has associated therewith a monotonically non-increasing time-function value; proportionally allocating the resource to a set of job classes according to a usage mode objective, wherein each of the job classes has associated therewith a monotonically non-decreasing time-function value; and scheduling job classes for execution to satisfy the response mode objective, the usage mode objection, or a combination of the response mode and usage mode objectives.
Claim 39
Dependent Claim
56 words
The method as described in claim 31 wherein the time-function value for each job class associated with the response mode objective is determined by a waiting time of an oldest job in the job class and the job classes are scheduled at each scheduling epoch by selected a given job class having a minimum time-function value.
Claim 40
Dependent Claim
56 words
The method as described in claim 31 wherein the time-function value for each job class associated with the usage mode objective is determined by an accumulated usage by all the jobs in the job class and the job classes are scheduled at each scheduling epoch by selected a given job class having a minimum time-function value.
References Cited (Backward Citations)
US4007444A
Cited
US5325525A
Cited
US5504894A
Cited
EP0647903A1
Cited
US5537542A
Cited
JPH0830471A
Cited
EP0725339A2
Cited
US5838968A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-16 | 2005-01-15 | 2005-07-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-16 | 2009-01-15 | 2009-07-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-16 | 2013-01-15 | 2013-07-17 | $7700.00 | Window Closed / Lapsed |