Computer resource proportional utilization and response time scheduling

• US 6,263,359 B1
• Filed: 05/22/1997
• Issued: 07/17/2001
• Est. Priority Date: 05/22/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fong, Liana Liyow, Hough, Roger Eldred, Squillante, Mark Steven
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/862,044
• Time in Patent Office: 1,517 Days
• Field of Search: 709/100, 709/102, 709/103, 709/104, 709/105, 709/106, 709/107, 709/108, 712/28
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

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.

Claims

1. 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.

2. The method as described in claim 1 wherein the usage objective proportionally allocates the resource to job classes within a given group.

3. 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.

4. The method as described in claim 1 wherein the response objective proportionally allocates the resource to job classes within a given group.

5. 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.

6. 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.

7. 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.

8. The method as described in claim 7 wherein each of the job classes in the first group is associated with a constant time-function.

9. 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.

10. The method as described in claim 1 further including the step of modifying the response time objective.

11. 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.

12. The method as described in claim 1 further including the step of modifying the usage time objective.

13. 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.

14. The method as described in claim 1 further including the step of migrating a job between job classes of a group.

15. 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.

16. 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.

17. The method as described in claim 16 wherein the usage objective proportionally allocates the processor to the job classes.

18. The method as described in claim 17 wherein the response objective proportionally allocates the processor to subclasses within a particular job class.

19. The method as described in claim 16 wherein the response objective proportionally allocates the processor to the job classes.

20. The method as described in claim 19 wherein the usage objective proportionally allocates the processor to subclasses within a particular job class.

21. The method as described in claim 16 further including the step of dynamically adjusting the response objective.

22. The method as described in claim 16 further including the step of dynamically adjusting the usage objective.

23. The method as described in claim 16 further including the step of selectively migrating a job between job classes.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.