Scheduling computing jobs over forecasted demands for computing resources

• US 10,089,144 B1
• Filed: 06/17/2016
• Issued: 10/02/2018
• Est. Priority Date: 06/17/2016
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Nagpal, Abhinay, Beedu, Bharat Kumar, Shukla, Himanshu
• Primary Examiner(s): Dascomb, Jacob D
• Application Number:
  US15/186,235
• Time in Patent Office: 837 Days
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• 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: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Measurements comprising time-series stimuli and time-series responses of a computing platform that has executed a first set of jobs are collected over a first time period. The measurements are used to form a query-able predictive model pertaining to resource usage demand predictions for the first set of jobs. A second set of job records describe a second set of jobs to be invoked in a second time period. The predictive model is queried to determine a likelihood to complete by the predicted finish time based on resource usage demand predictions for the first set of jobs. A weighting factor related to a likelihood to complete the second set of jobs by a particular time is calculated. A reward value based on the weighting factor is assigned to respective jobs in the second set of jobs. Some of the second set of jobs are rescheduled, based on a then-current reward value.

Claims

1. A method comprising:

collecting measurements over a first time period, the measurements comprising at least time-series stimuli and time-series responses of a computing platform that is executing a set of foreground jobs;

forming an initial predictive model from the time-series stimuli and the time-series responses, wherein the initial predictive model is used to derive a respective degree of confidence which correlates to a respective percentage corresponding to a respective likelihood for a respective set of jobs to complete by a respective predicted finish time;

querying the initial predictive model to retrieve a time series of resource usage demand predictions for the set of foreground jobs;

receiving a set of job records that describe a set of background jobs to be invoked in a second time period, the set of background jobs having a latest finish time specification;

querying, for the set of background jobs, the initial predictive model to retrieve a predicted finish time and a percentage corresponding to a likelihood to complete by the predicted finish time based at least in part on the time series of the resource usage demand predictions for the set of foreground jobs;

associating a static schedule weighting factor to the set of background jobs, wherein the static schedule weighting factor is related to the percentage corresponding to the respective likelihood to complete at least one of the set of background jobs by the predicted finish time;

assigning a reward value to at least some of the set of background jobs, wherein the reward value is based at least in part on the static schedule weighting factor;

scheduling the second set of background jobs, based at least in part on the reward value;

forming an updated predictive model based on the initial predictive model and new time-series stimuli; and

automatically re-scheduling, based on the updated predictive model, at least some of the set of background jobs, wherein the re-scheduling causes a readjustment to the resources allocated to the at least some of the set of background jobs.

2. The method of claim 1, further comprising, after invoking at least some of the second set of background jobs to execute on the computing platform, then querying the initial predictive model again to retrieve a time series of then-current resource usage demand predictions for a set of then-current user jobs.

3. The method of claim 1, wherein the likelihood to complete by the predicted finish time is determined by one or more queries to the initial predictive model.

4. The method of claim 1, wherein the static schedule weighting factor is based at least in part on a determination of a schedule using a threshold.

5. The method of claim 1, wherein the reward value is based on the likelihood to complete by an end time.

6. The method of claim 1, wherein the reward value is based at least in part on a likelihood of breaching a threshold.

7. The method of claim 1, wherein at least one of the job records describes a backup job that has a constraint from a service level agreement.

8. A computer readable medium, embodied in a non-transitory computer readable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when stored in memory and executed by one or more processors causes the one or more processors to perform a set of acts, the acts comprising:

collecting measurements over a first time period, the measurements comprising at least time-series stimuli and time-series responses of a computing platform that is executing a set of foreground jobs;

forming an initial predictive model from the time-series stimuli and the time-series responses, wherein the initial predictive model is used to derive a respective degree of confidence which correlates to a respective percentage corresponding to a respective likelihood for a respective set of jobs to complete by a respective predicted finish time;

querying the initial predictive model to retrieve a time series of resource usage demand predictions for the set of foreground jobs;

receiving a set of job records that describe a set of background jobs to be invoked in a second time period, the set of background jobs having a latest finish time specification;

querying, for the set of background jobs, the initial predictive model to retrieve a predicted finish time and a percentage corresponding to a likelihood to complete by the predicted finish time based at least in part on the time series of the resource usage demand predictions for the set of foreground jobs;

associating a static schedule weighting factor to the set of background jobs, wherein the static schedule weighting factor is related to the percentage corresponding to the respective likelihood to complete at least one of the set of background jobs by the predicted finish time;

assigning a reward value to at least some of the set of background jobs, wherein the reward value is based at least in part on the static schedule weighting factor;

scheduling the second set of background jobs, based at least in part on the reward value;

forming an updated predictive model based on the initial predictive model and new time-series stimuli; and

automatically re-scheduling, based on the updated predictive model, at least some of the set of background jobs, wherein the re-scheduling causes a readjustment to the resources allocated to the at least some of the set of background jobs.

9. The computer readable medium of claim 8, wherein the likelihood to complete by the predicted finish time is determined by one or more queries to the initial predictive model.

10. The computer readable medium of claim 8, wherein the static schedule weighting factor is based at least in part on a determination of a schedule using a threshold.

11. The computer readable medium of claim 8, wherein the reward value is based on the likelihood to complete by an end time.

12. The computer readable medium of claim 8, wherein the reward value is based at least in part on a likelihood of breaching a threshold.

13. The computer readable medium of claim 8, wherein at least one of the job records describes a backup job that has a constraint from a service level agreement.

14. A system comprising:

a storage medium having stored thereon a sequence of instructions; and

one or more processors that execute the instructions to cause the one or more processors to perform a set of acts, the acts comprising,

collecting measurements over a first time period, the measurements comprising at least time-series stimuli and time-series responses of a computing platform that is executing a set of foreground jobs;

forming an initial predictive model from the time-series stimuli and the time-series responses, wherein the initial predictive model is used to derive a respective degree of confidence which correlates to a respective percentage corresponding to a respective likelihood for a respective set of jobs to complete by a respective predicted finish time;

querying the initial predictive model to retrieve a time series of resource usage demand predictions for the set of foreground jobs;

receiving a set of job records that describe a set of background jobs to be invoked in a second time period, the set of background jobs having a latest finish time specification;

querying, for the second set of background jobs, the initial predictive model to retrieve a predicted finish time and a percentage corresponding to a likelihood to complete by the predicted finish time based at least in part on the time series of the resource usage demand predictions for the set of foreground jobs;

associating a static schedule weighting factor to the set of background jobs, wherein the static schedule weighting factor is related to the percentage corresponding to the respective likelihood to complete at least one of the set of background jobs by the predicted finish time;

assigning a reward value to at least some of the set of background jobs, wherein the reward value is based at least in part on the static schedule weighting factor;

scheduling the second set of background jobs, based at least in part on the reward value;

forming an updated predictive model based on the initial predictive model and new time-series stimuli; and

automatically re-scheduling, based on the updated predictive model, at least some of the set of background jobs, wherein the re-scheduling causes a readjustment to the resources allocated to the at least some of the set of background jobs.

15. The system of claim 14, wherein the likelihood to complete by the predicted finish time is determined by one or more queries to the initial predictive model.

16. The system of claim 14, wherein the static schedule weighting factor is based at least in part on a determination of a schedule using a threshold.

17. The system of claim 14, wherein the reward value is based on the likelihood to complete by an end time.

18. The system of claim 14, wherein the reward value is based at least in part on a likelihood of breaching a threshold.

19. The system of claim 14, wherein at least one of the job records describes a backup job.

20. The system of claim 14, wherein a backup job comprises a constraint from a service level agreement.