System and method for optimizing job scheduling within program builds

• US 10,061,577 B2
• Filed: 10/14/2014
• Issued: 08/28/2018
• Est. Priority Date: 10/14/2014
• Status: Active Grant

• Current Assignee: Cloudebees Incorporated
• Original Assignee: Electric Cloud, Inc.
• Inventors: Melski, John Eric
• Primary Examiner(s): ST LEGER, GEOFFREY R
• Application Number:
  US14/513,446
• Publication Number:
  US 20160103677A1
• Time in Patent Office: 1,414 Days
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 9/4806 Task transfer initiation or dispatching
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method for executing program builds comprising: analyzing file dependency information and job duration information associated with jobs of the program build; scheduling jobs for a current program build based on the analysis of the dependency information and the job duration data; executing the jobs according to the schedule; collecting file usage information and new job duration information from each of the jobs; supplementing the file dependency information with the file usage information; and storing the new job duration information to be used for scheduling jobs in subsequent program builds.

Claims

1. A method for executing program builds comprising:

analyzing file dependency information and job duration information associated with jobs of a past program build to determine a total duration for each of the jobs, wherein the total duration of a job is a sum of a duration of the job and the duration of one or more jobs that are dependent on the job;

scheduling jobs for a current program build based on analysis of both the file dependency information and the job duration information including analyzing the total duration for each of the jobs determined from the analysis of the file dependency information and the job duration information, wherein a first job that is otherwise equivalent to a second job is scheduled before the second job for the current program build based on relative total durations of the first job and the second job, wherein the scheduling further comprises;

building a job graph based on the file dependency information and/or file usage information, wherein the job graph comprises a plurality of nodes and edges, each node representing a job and each edge representing dependencies between the jobs of the current program build, the nodes including at least one source node having no inbound edges and at least one sink node having no outbound edges; and

analyzing the job graph in view of the job duration information to determine an optimized order in which to execute the jobs of the current program build, wherein analyzing the job graph in view of the job duration information to determine an optimized order in which to execute the jobs of the current program build further comprises;

iterating through the nodes of the job graph in reverse order, starting with the sink node;

for each node N, determining a waiter node with the greatest chain length, wherein a chain represents a sequence of jobs such that each job in the sequence directly waits for a previous job in the sequence before it will execute;

computing the chain length for node N as the sum of the length of the job represented by node N and the greatest chain length of that job'"'"'s waiter nodes; and

scheduling jobs of the current program build for execution in the optimized order based on calculated chain lengths of corresponding nodes;

executing the jobs of the current program build according to the optimized order;

collecting file usage information and new job duration information from each of the executed jobs of the current program build;

supplementing the file dependency information with the collected file usage information; and

storing the new job duration information to be used for scheduling jobs in subsequent program builds.

2. The method as in claim 1 wherein the optimized order comprises an order in which larger chain lengths are executed ahead of shorter chains, all other variables being equal.

3. The method as in claim 1 wherein executing the jobs of the current program build according to the schedule comprises:

scheduling the jobs of the current program build for parallel execution across a plurality of nodes.

4. The method as in claim 3 further comprising:

collecting the file usage information and the new job duration information at each of the nodes; and

transmitting the file usage information and the new job duration information from each of the nodes to a central build module, the central build module combining and storing the file usage information and the new job duration information received from each of the nodes.

5. The method as in claim 4 further comprising:

transmitting files required for each of the jobs of the current program build to each of the respective nodes prior to the execution of each of the jobs of the current program build on the nodes.

6. The method as in claim 1 wherein the job duration information is accumulated across multiple program builds and used to schedule jobs for the current program build.

7. The method as in claim 6 wherein accumulating the job duration information comprises maintaining a running average for each job of the current program build.

8. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:

analyzing file dependency information and job duration information associated with jobs of a past program build to determine a total duration for each of the jobs, wherein the total duration of a job is a sum of a duration of the job and the duration of one or more jobs that are dependent on the job;

scheduling jobs for a current program build based on analysis of both the file dependency information and the job duration information including analyzing the total duration for each of the jobs determined from the analysis of the file dependency information and the job duration information, wherein a first job that is otherwise equivalent to a second job is scheduled before the second job for the current program build based on relative total durations of the first job and the second job, wherein the scheduling further comprises;

building a job graph based on the file dependency information and/or file usage information, wherein the job graph comprises a plurality of nodes and edges, each node representing a job and each edge representing dependencies between the jobs of the current program build the nodes including at least one source node having no inbound edges and at least one sink node having no outbound edges; and

analyzing the job graph in view of the job duration information to determine an optimized order in which to execute the jobs of the current program build, wherein analyzing the job graph in view of the job duration information to determine an optimized order in which to execute the jobs of the current program build further comprises;

iterating through the nodes of the job graph in reverse order, starting with the sink node;

for each node N, determining a waiter node with the greatest chain length, wherein a chain represents a sequence of jobs such that each job in the sequence directly waits for a previous job in the sequence before it will execute;

computing, the chain length for node N as the sum of the length of the job represented by node N and the greatest chain length of that job'"'"'s waiter nodes; and

scheduling jobs of the current program build for execution in the optimized order based on calculated chain lengths of corresponding nodes;

executing the jobs of the current program build according to the optimized order;

collecting file usage information and new job duration information from each of the executed jobs of the current program build;

supplementing the file dependency information with the collected file usage information; and

storing the new job duration information to be used for scheduling jobs in subsequent program builds.

9. The non-transitory machine-readable medium as in claim 8 wherein the optimized order comprises an order in which larger chain lengths are executed ahead of shorter chains, all other variables being equal.

10. The non-transitory machine-readable medium as in claim 8 wherein executing the jobs of the current program build according to the schedule comprises:

scheduling the jobs of the current program build for parallel execution across a plurality of nodes.

11. The non-transitory machine-readable medium as in claim 10 further comprising program code to cause the machine to perform the operations of:

collecting the file usage information and the new job duration information at each of the nodes; and

transmitting the file usage information and the new job duration information from each of the nodes to a central build module, the central build module combining and storing the file usage information and the new job duration information received from each of the nodes.

12. The non-transitory machine-readable medium as in claim 11 further comprising program code to cause the machine to perform the operations of:

transmitting files required for each of the jobs of the current program build to each of the respective nodes prior to the execution of each of the jobs of the current program build on the nodes.

13. The non-transitory machine-readable medium as in claim 8 wherein the job duration information is accumulated across multiple program builds and used to schedule jobs for the current program build.

14. The non-transitory machine-readable medium as in claim 13 wherein accumulating the job duration information comprises maintaining a running average for each job of the current program build.