Scheduling of computer jobs employing dynamically determined top job party

• US 7,926,057 B2
• Filed: 12/15/2005
• Issued: 04/12/2011
• Est. Priority Date: 12/15/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Skovira, Joseph F., Chan, Waiman
• Primary Examiner(s): Ho; Andy
• Assistant Examiner(s): Mudrick; Timothy A
• Application Number:
  US11/304,876
• Publication Number:
  US 20070143760A1
• Time in Patent Office: 1,944 Days
• Field of Search: 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A facility is presented for scheduling computer jobs of a computing environment having a plurality of computing nodes. The facility includes scheduling N sequential computer jobs of a job queue until achieving a top job party, wherein N≧2, and the number of jobs in the top job party is dynamically determined by monitoring backfill window coverage of the computing nodes by the N scheduled jobs and automatically closing membership in the top job party once (i) all computing nodes are covered by at least one backfill window, or (ii) a backfill end time of at least one computing node is greater than or equal to a maximum wallclock limit of a set of job classes having the N scheduled jobs. Responsive to determining the top job party, the facility then backfill schedules jobs of the job queue around the top job party for execution.

Claims

1. A method of scheduling computer jobs of a computing environment comprising a plurality of computing nodes, the method comprising:

scheduling, by a processor, N sequential computer jobs of a job queue until achieving a top job party, wherein N≧

2, and the number N of computer jobs in the top job party is dynamically determined by monitoring backfill window coverage of the plurality of computing nodes by the N sequentially scheduled computer jobs and automatically closing membership in the top job party once (i) all computing nodes of the plurality of computing nodes are covered by at least one backfill window of at least one computer job of the N computer jobs in the top job party, or (ii) a backfill end time of at least one computing node of the plurality of computing nodes is greater than or equal to a maximum wallclock limit of a job class in a set of job classes comprising the N sequentially scheduled computer jobs; and

responsive to determination of the top job party, backfill scheduling at least one computer job of the job queue around the N computer jobs of the top job party for execution by the plurality of computing nodes.

2. The method of claim 1, wherein the number N of computer jobs in the top job party is less than a number of computer jobs in the job queue awaiting execution by the plurality of computing nodes, and wherein the N sequential computer jobs comprise N sequential top computer jobs in the job queue.

3. The method of claim 2, wherein each computer job of the job queue has an associated computing node requirement and wallclock time indicative of an amount of time required to run the computer job, and wherein the scheduling comprises employing the computing node requirements and wallclock times of the N computer jobs in determining when to close membership in the top job party.

4. The method of claim 1, wherein the scheduling comprises assigning a start time to each of the computer jobs of the N computer jobs in the top job party.

5. The method of claim 1, wherein the dynamically determining further comprises sorting computing nodes of the plurality of computing nodes by earliest free time initially, and for each computer job considered for inclusion in the top job party, determining whether free time of at least one computing node is greater than or equal to a wallclock time for the computer job considered for inclusion, and if so, saving the at least one computer node on a potential node list for execution of the computer job, and for each node of the potential node list, setting a backfill end time equal to a projected end time of the computer job once running on the computer node, and setting a return code equal to a job ID for the computer job.

6. The method of claim 5, wherein the closing membership comprises determining that all computing nodes of the plurality of computing nodes have a backfill start time greater than zero, thereby indicating closure of membership in the top job party.

7. The method of claim 5, wherein when there are insufficient computer nodes in the potential nodes list to execute the computer job, the method further comprises sorting the plurality of computer nodes by earliest backfill end time and pushing computer nodes onto a potential node stack by earliest backfill end time until a sufficient number of computer nodes are accumulated to execute the computer job, and determining whether at least one additional computer node of the plurality of computer nodes has a same backfill end time as the backfill end time for a last computer node on the potential node stack, and if so, adding the at least one additional computer node with the same backfill end time to the potential node stack, and removing computer nodes from the potential node stack in reverse order to placement on the stack, the removed nodes being designated to execute the computer job.

8. The method of claim 7, further comprising adjusting node free time for at least one computer node of the potential node stack to reduce the node free time based upon inclusion of the computer job in the top job party.

9. A computer system for scheduling computer jobs of a computing environment comprising a plurality of computing nodes, the computer system comprising:

a memory; and

a processor in communications with the memory, wherein the computer system is configured to perform a method, said method comprising;

scheduling N sequential computer jobs of a job queue until achieving a top job party, wherein N≧

2, and the number N of computer jobs in the top job party is dynamically determined by monitoring backfill window coverage of the plurality of computing nodes by the N sequentially scheduled computer jobs and automatically closing membership in the top job party once (i) all computing nodes of the plurality of computing nodes are covered by at least one backfill window of at least one computer job of the N computer jobs in the top job party, or (ii) a backfill end time of at least one computing node of the plurality of computing nodes is greater than or equal to a maximum wallclock limit of a job class in a set of job classes comprising the N sequentially scheduled computer jobs; and

backfill scheduling, responsive to determination of the top job party, at least one computer job of the job queue around the N computer jobs of the top job party for execution by the plurality of computing nodes.

10. The computer system of claim 9, wherein the number N of computer jobs in the top job party is less than a number of computer jobs in the job queue awaiting execution by the plurality of computing nodes, and wherein the N sequential computer jobs comprise N sequential top computer jobs in the job queue.

11. The computer system of claim 10, wherein each computer job of the job queue has an associated computing node requirement and wallclock time indicative of an amount of time required to run the computer job, and wherein the scheduling comprises employing the computing node requirements and wallclock times of the N computer jobs in determining when to close membership in the top job party.

12. The computer system of claim 9, wherein the scheduling comprises assigning a start time to each of the computer jobs of the N computer jobs in the top job party.

13. The computer system of claim 9, wherein the dynamically determining further comprises sorting computing nodes of the plurality of computing nodes by earliest free time initially, and for each computer job considered for inclusion in the top job party, determining whether free time of at least one computing node is greater than or equal to a wallclock time for the computer job considered for inclusion, and if so, saving the at least one computer node on a potential node list for execution of the computer job, and for each node of the potential node list, setting a backfill end time equal to a projected end time of the computer job once running on the computer node, and setting a return code equal to a job ID for the computer job.

14. The computer system of claim 13, wherein when there are insufficient computer nodes in the potential nodes list to execute the computer job, the method further comprises sorting the plurality of computer nodes by earliest backfill end time and pushing computer nodes onto a potential node stack by earliest backfill end time until a sufficient number of computer nodes are accumulated to execute the computer job, and determining whether at least one additional computer node of the plurality of computer nodes has a same backfill end time as the backfill end time for a last computer node on the potential node stack, and if so, adding the at least one additional computer node with the same backfill end time to the potential node stack, and removing computer nodes from the potential node stack in reverse order to placement on the stack, the removed nodes being designated to execute the computer job.

15. A computer program product for scheduling computer jobs of a computing environment comprising a plurality of computing nodes, the computer program product comprising;

a non-transitory storage medium readable by a processor and storing instructions for execution by the processor to perform a method comprising;

scheduling N sequential computer jobs of a job queue until achieving a top job party, wherein N≧

2, and the number N of computer jobs in the top job party is dynamically determined by monitoring backfill window coverage of the plurality of computing nodes by the N sequentially scheduled computer jobs and automatically closing membership in the top job party once (i) all computing nodes of the plurality of computing nodes are covered by at least one backfill window of at least one computer job of the N computer jobs in the top job party, or (ii) a backfill end time of at least one computing node of the plurality of computing nodes is greater than or equal to a maximum wallclock limit of a job class in a set of job classes comprising the N sequentially scheduled computer jobs; and

responsive to determination of the top job party, backfill scheduling at least one computer job of the job queue around the N computer jobs of the top job party for execution by the plurality of computing nodes.

16. The computer program product of claim 15, wherein the number N of computer jobs in the top job party is less than a number of computer jobs in the job queue awaiting execution by the plurality of computing nodes, and wherein the N sequential computer jobs comprise N sequential top computer jobs in the job queue.

17. The computer program product of claim 16, wherein each computer job of the job queue has an associated computing node requirement and wallclock time indicative of an amount of time required to run the computer job, and wherein the scheduling comprises employing the computing node requirements and wallclock times of the N computer jobs in determining when to close membership in the top job party.

18. The computer program product of claim 15, wherein the scheduling comprises assigning a start time to each of the computer jobs of the N computer jobs in the top job party.

19. The computer program product of claim 15, wherein the dynamically determining further comprises sorting computing nodes of the plurality of computing nodes by earliest free time initially, and for each computer job considered for inclusion in the top job party, determining whether free time of at least one computing node is greater than or equal to a wallclock time for the computer job considered for inclusion, and if so, saving the at least one computer node on a potential node list for execution of the computer job, and for each node of the potential node list, setting a backfill end time equal to a projected end time of the computer job once running on the computer node, and setting a return code equal to a job ID for the computer job.

20. The computer program product of claim 19, wherein when there are insufficient computer nodes in the potential nodes list to execute the computer job, the method further comprises sorting the plurality of computer nodes by earliest backfill end time and pushing computer nodes onto a potential node stack by earliest backfill end time until a sufficient number of computer nodes are accumulated to execute the computer job, and determining whether at least one additional computer node of the plurality of computer nodes has a same backfill end time as the backfill end time for a last computer node on the potential node stack, and if so, adding the at least one additional computer node with the same backfill end time to the potential node stack, and removing computer nodes from the potential node stack in reverse order to placement on the stack, the removed nodes being designated to execute the computer job.