Method and apparatus for multi-dimensional priority determination for job scheduling

• US 7,743,378 B1
• Filed: 05/13/2005
• Issued: 06/22/2010
• Est. Priority Date: 05/13/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Markov, Lev
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Huaracha; Willy W
• Application Number:
  US11/128,629
• Time in Patent Office: 1,866 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104, 718/107, 718/108, 718/101
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine

Abstract

A method for scheduling computing jobs in a scheduling event includes calculating a static priority of each computing job ready for scheduling, and then selecting a first computing job having the highest static priority as compared to at least one other computing jobs ready for scheduling, the first computing job being associated with at least one required resource. Further, a subset of computing nodes able to satisfy the at least one required resource are identified, and predictions are made for each node of an earliest predicted completion time that the first computing job can be completed on each of those nodes, taking into account already scheduled jobs. Finally, execution of the first computing job is scheduled on the node having the earliest predicted completion time.

Claims

1. A method for scheduling a plurality of computing jobs during a scheduling event on a computing system comprising a plurality of heterogeneous computing nodes, wherein the plurality of computing jobs comprise a plurality of resource requirements, the method comprising:

receiving, by a scheduler of the computing system, the plurality of computing jobs comprising an active job and a pending job, wherein the active job is executing prior to the scheduling event on a first node of the plurality of heterogeneous computing nodes in accordance with an existing schedule, and wherein the pending job has not yet begun execution;

obtaining a plurality of initial priority values for the plurality of computing jobs;

identifying a maximum initial priority value and a minimum initial priority value from the plurality of initial priority values;

calculating a priority component for a first computing job by dividing an initial priority value for the first computing job by a difference between the maximum initial priority value and the minimum initial priority value;

calculating, based on the plurality of resource requirements, a plurality of urgency values for the plurality of computing jobs;

identifying a maximum urgency value and a minimum urgency value of the plurality of urgency values;

calculating an urgency component for the first computing job by dividing an urgency value for the first computing job by a difference between the maximum urgency value and the minimum urgency value;

calculating a static priority for the first computing job by adding the priority component and the urgency component;

selecting, after calculating the static priority for the first computing job, the active job from the plurality of computing jobs and scheduling the active job on the first node according to the existing schedule;

selecting, after placing the active job on the first node according to the existing schedule, the first computing job from the plurality of computing jobs, wherein the static priority of the first computing job exceeds a static priority of a second computing job in the plurality of computing jobs;

identifying a subset of the plurality of resource requirements corresponding to the first computing job;

identifying a second node of the plurality of heterogeneous computing nodes having a plurality of resources to satisfy the subset of the plurality of resource requirements corresponding to the first computing job;

predicting, for the second node, an earliest completion time for the first computing job, taking into account already scheduled jobs on the second node; and

scheduling execution of the first computing job on the second node based on the earliest completion time.

2. The method of claim 1, wherein the plurality of resources comprises at least one resource selected from a group consisting of a processor type, a supporting software, and a specified memory size.

3. The method of claim 1, wherein at least one of the plurality of resources is a floating resource.

4. The method of claim 1, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according to a scarcity of the resource.

5. The method of claim 1, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according a cost of the resource.

6. The method of claim 1, wherein the first computing job is characterized by at least one selected from the group consisting of dependence on other computing jobs, whether the first computing job is partitionable, preemptability, restartability, and completion deadline.

7. A computing system for scheduling a plurality of computing jobs having a plurality of resource requirements during a scheduling event, comprising:

a plurality of heterogeneous computing nodes for executing the plurality of computing jobs; and

a scheduler configured to schedule the plurality of computing jobs by;

receiving the plurality of computing jobs comprising an active job and a pending job, wherein the active job is executing prior to the scheduling event on a first node of the plurality of heterogeneous computing nodes in accordance with an existing schedule, and wherein the pending job has not yet begun execution;

obtaining a plurality of initial priority values for the plurality of computing jobs;

identifying a maximum initial priority value and a minimum initial priority value from the plurality of initial priority values;

calculating a priority component for a first computing job by dividing an initial priority value for the first computing job by a difference between the maximum initial priority value and the minimum initial priority value;

calculating, based on the plurality of resource requirements, a plurality of urgency values for the plurality of computing jobs;

identifying a maximum urgency value and a minimum urgency value of the plurality of urgency values;

calculating an urgency component for the first computing job by dividing an urgency value for the first computing job by a difference between the maximum urgency value and the minimum urgency value;

calculating a static priority for the first computing job by adding the priority component and the urgency component;

selecting, after calculating the static priority for the first computing job, the active job from the plurality of computing jobs and scheduling the active job on the first node according to the existing schedule;

selecting, after placing the active job on the first node according to the existing schedule, the first computing job from the plurality of computing jobs, wherein the static priority of the first computing job exceeds a static priority of a second computing job in the plurality of computing jobs;

identifying a subset of the plurality of resource requirements corresponding to the first computing job;

identifying a second node of the plurality of heterogeneous computing nodes having a plurality of resources to satisfy the subset of the plurality of resource requirements corresponding to the first computing job;

predicting, for the second node, an earliest completion time for the first computing job, taking into account already scheduled jobs on the second node; and

scheduling execution of the first computing job on the second node based on the earliest completion time.

8. The system of claim 7, wherein the plurality of resources comprises at least one resource selected from a group consisting of a processor type, a supporting software, and a specified memory size.

9. The system of claim 7, wherein at least one of the plurality of resources is a floating resource.

10. The system of claim 7, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according to a scarcity of the resource.

11. The system of claim 7, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according a cost of the resource.

12. The system of claim 7, wherein the first computing job is characterized by at least one selected from the group consisting of dependence on other computing jobs, whether the first computing job is partitionable, preemptability, restartability, and completion deadline.

13. A computing program product having instructions disposed thereon for scheduling a plurality of computing job during a scheduling event on a computing system comprising a plurality of heterogeneous computing nodes, wherein the plurality of computing jobs comprise a plurality of resource requirements, when executed by a processor the instructions perform a method comprising:

receiving, by a scheduler of the computing system, the plurality of computing jobs comprising an active job and a pending job, wherein the active job is executing prior to the scheduling event on a first node of the plurality of heterogeneous computing nodes in accordance with an existing schedule, and wherein the pending job has not yet begun execution;

obtaining a plurality of initial priority values for the plurality of computing jobs;

identifying a maximum initial priority value and a minimum initial priority value from the plurality of initial priority values;

calculating a priority component for a first computing job by dividing an initial priority value for the first computing job by a difference between the maximum initial priority value and the minimum initial priority value;

calculating, based on the plurality of resource requirements, a plurality of urgency values for the plurality of computing jobs;

identifying a maximum urgency value and a minimum urgency value of the plurality of urgency values;

calculating an urgency component for the first computing job by dividing an urgency value for the first computing job by a difference between the maximum urgency value and the minimum urgency value;

calculating a static priority for the first computing job by adding the priority component and the urgency component;

selecting, after calculating the static priority for the first computing job, the active job from the plurality of computing jobs and scheduling the active job on the first node according to the existing schedule;

selecting, after placing the active job on the first node according to the existing schedule, the first computing job from the plurality of computing jobs, wherein the static priority of the first computing job exceeds a static priority of a second computing job in the plurality of computing jobs;

identifying a subset of the plurality of resource requirements corresponding to the first computing job;

identifying a second node of the plurality of heterogeneous computing nodes having a plurality of resources to satisfy the subset of the plurality of resource requirements corresponding to the first computing job;

predicting, for the second node, an earliest completion time for the first computing job, taking into account already scheduled jobs on the second node; and

scheduling execution of the first computing job on the second node based on the earliest completion time.

14. The computing program product of claim 13, wherein the plurality of resources comprises at least one resource selected from a group consisting of a processor type, a supporting software, and a specified memory size.

15. The computer program product of claim 13, wherein at least one of the plurality of resources is a floating resource.

16. The computer program product of claim 13, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according to a scarcity of the resource.

17. The computer program product of claim 13, wherein predicting an earliest completion time comprises assigning a rank to a resource of the plurality of resources according a cost of the resource.