Method and apparatus for job assignment and scheduling using advance reservation, backfilling, and preemption

• US 8,214,836 B1
• Filed: 05/13/2005
• Issued: 07/03/2012
• 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): Puente, Emerson
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US11/128,725
• Time in Patent Office: 2,608 Days
• Field of Search: 718/102
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method for scheduling computing jobs in a scheduling event. A computing node is identified that is able to satisfy the required resource during a first time period. A second computing job is determined to have previously been scheduled to execute during a second time period, where the second time period overlaps a first time period. Execution of the second computing job is preempted if the first computing job'"'"'s priority is greater than the second computing job'"'"'s priority by at least a threshold amount, and if preempting the second job frees the required resource for use by the first computing job. Execution of the first computing job is scheduled to take place on a first computing node during the first time period, where a start time associated with the first time period is a time selected from the group consisting of a current time and a future time.

Claims

1. A method for scheduling computing jobs comprising:

calculating a priority component and an urgency component for scheduling a first computing job within a computer farm comprising a plurality of heterogeneous computing nodes, wherein the plurality of heterogeneous computing nodes comprise a plurality of resources, and wherein the urgency component is calculated based on a resource requirement of the first computing job and the plurality of resources;

adding the priority component to the urgency component of the first computing job to create a static priority of the first computing job;

selecting the first computing job that is ready for scheduling from a plurality of computing jobs, wherein the static priority of the first computing job is higher than a static priority of at least one other computing job of the plurality of computing jobs;

identifying a first computing node able to satisfy at least one resource of the resource requirement during a first time period;

determining that a second computing job has previously been scheduled to execute during a second time period, wherein the second time period overlaps the first time period;

preempting execution of the second computing job if the static priority of the first computing job is greater than a static priority of the second computing job by at least a threshold amount and if preempting the second computing job frees at least one resource of the resource requirement; and

scheduling execution of the first computing job to take place on the first computing node during the first time period, wherein the first time period is shorter than an anticipated execution time of a fourth computing job, and wherein the fourth computing job is partitioned into the first computing job and a fifth computing job so that the first computing job may be scheduled into the first time period.

2. The method of claim 1 wherein the second time period begins before the first time period begins.

3. The method of claim 1 wherein the second time period ends after the first time period begins.

4. The method of claim 1 wherein the second computing job was previously scheduled on the first computing node.

5. The method of claim 1 wherein the second computing job was previously scheduled on a second computing node.

6. The method of claim 1 wherein an end of the first time period is prior to a start time associated with a third time period, and wherein a third computing job is scheduled to execute during the third time period.

7. The method of claim 1 wherein a beginning of the first time period is later than an end of a third time period, and wherein a third computing job is scheduled to execute during the third time period.

8. A computing system comprising:

a computer farm comprising a plurality of heterogeneous computing nodes for executing a plurality of computing jobs, wherein the plurality of heterogeneous computing nodes are operatively connected using a network and comprise a plurality of resources; and

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

calculating a priority component and an urgency component for scheduling a first computing job of the plurality of computing jobs on the computer farm,

wherein the urgency component is calculated based on a resource requirement of the first computing job and the plurality of resources;

adding the priority component to the urgency component of the first computing job to create a static priority of the first computing job;

selecting the first computing job that is ready for scheduling from the plurality of computing jobs, wherein the static priority of the first computing job is higher than a static priority of at least one other computing job of the plurality of computing jobs;

identifying a first computing node able to satisfy at least one resource of the resource requirement during a first time period;

determining that a second computing job has previously been scheduled to execute during a second time period, wherein the second time period overlaps the first time period;

preempting execution of the second computing job if the static priority of the first computing job is greater than a static priority of the second computing job by at least a threshold amount and if preempting the second computing job frees at least one resource of the resource requirement; and

scheduling execution of the first computing job to take place on the first computing node during the first time period, wherein the first time period is shorter than an anticipated execution time of a fourth computing job, and wherein the fourth computing job is partitioned into the first computing job and a fifth computing job so that the first computing job may be scheduled into the first time period.

9. The system of claim 8 wherein calculating a static priority of each computing job comprises:

selecting a computing job for which to compute the static priority; and

computing at least one optimization parameter involving at least one resource selected from a list consisting of an average memory required to properly execute the selected computing job, an average number of CPUs used for the selected computing job, an amount of time the selected computing job has been waiting for execution, and an average execution time expected for the selected computing job over different nodes.

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

11. A non-transitory computer-readable storage medium having instructions disposed thereon to perform a method comprising:

calculating a priority component and an urgency component for scheduling a first computing job within a computer farm comprising a plurality of heterogeneous computing nodes,

wherein the plurality of heterogeneous computing nodes comprise a plurality of resources, and

wherein the urgency component is calculated based on a resource requirement of the first computing job and the plurality of resources;

adding the priority component to the urgency component of the first computing job to create a static priority of the first computing job;

selecting the first computing job that is ready for scheduling from a plurality of computing jobs, wherein the static priority of the first computing job is higher than a static priority of at least one other computing job of the plurality of computing jobs;

identifying a first computing node able to satisfy at least one resource of the resource requirement during a first time period;

determining that a second computing job has previously been scheduled to execute during a second time period, wherein the second time period overlaps the first time period;

preempting execution of the second computing job if the static priority of the first computing job is greater than a static priority of the second computing job by at least a threshold amount and if preempting the second computing job frees at least one resource of the resource requirement; and

scheduling execution of the first computing job to take place on the first computing node during the first time period, wherein the first time period is shorter than an anticipated execution time of a fourth computing job, and wherein the fourth computing job is partitioned into the first computing job and a fifth computing job so that the first computing job may be scheduled into the first time period.

12. The non-transitory computer-readable storage medium of claim 11 wherein calculating a static priority of each computing job comprises:

selecting a computing job for which to compute the static priority; and

computing at least one optimization parameter involving at least one resource selected from a list consisting of an average memory required to properly execute the selected computing job, an average number of CPUs used for the selected computing job, an amount of time the selected computing job has been waiting for execution, and an average execution time expected for the selected computing job over different nodes.

13. The non-transitory computer-readable storage medium of claim 11 wherein the second time period begins before the first time period begins.

14. The non-transitory computer-readable storage medium of claim 11 wherein the second time period ends after the first time period ends.

15. The non-transitory computer-readable storage medium of claim 11 wherein the second computing job was previously scheduled on the first computing node.

16. The non-transitory computer-readable storage medium of claim 11 wherein the second computing job was previously scheduled on a second computing node.

17. The non-transitory computer-readable storage medium of claim 11 wherein the end of the first time period is prior to a start time associated with a third time period, and wherein a third computing job is scheduled to execute during the third time period.

18. The non-transitory computer-readable storage medium of claim 11 wherein the beginning of the first time period is later than an end time associated with a third time period, and wherein a third computing job is scheduled to execute during the third time period.