Scheduling computing jobs over forecasted demands for computing resources

Patent metadata

Field	Value
Publication number	US-10089144-B1
Application number	US-201615186235-A
Country	US
Kind code	B1
Filing date	Jun 17, 2016
Priority date	Jun 17, 2016
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

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.

First claim

What is claimed is:

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 jo

Assignees

• Nutanix Inc

Inventors

• Nagpal Abhinay
• Beedu Bharat Kumar
• Shukla Himanshu

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06F9/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 title

• G06F17/30424

  Physics · mapped topic

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title