Long-term resource provisioning with cascading allocations

Patent metadata

Field	Value
Publication number	US-9092265-B2
Application number	US-201213692912-A
Country	US
Kind code	B2
Filing date	Dec 3, 2012
Priority date	Feb 26, 2012
Publication date	Jul 28, 2015
Grant date	Jul 28, 2015

Abstract

One embodiment of the present invention provides a system for provisioning physical resources shared by a plurality of jobs. During operation, the system establishes resource-usage models for the jobs, ranks the jobs based on quality of service (QoS) requirements associated with the jobs, and provisions the jobs for a predetermined time interval in such a way that any unused reservations associated with a first subset of jobs having higher QoS rankings are distributed to other remaining jobs with preference given to a second subset of jobs having a highest QoS ranking among the other remaining jobs. Provisioning the jobs involves making reservations for the jobs based on the resource-usage model and corresponding QoS requirements associated with the jobs.

First claim

What is claimed is:

1. A computer-executable method for provisioning physical resources shared by a plurality of jobs, comprising:
establishing resource-usage models for the jobs;
ranking the jobs based on quality of service (QoS) requirements associated with the jobs; and
provisioning the jobs for a predetermined time interval in such a way that any unused reservations associated with a first subset of jobs having higher QoS rankings than other remaining jobs are distributed to the other remaining jobs with preference given to a second subset of jobs having a highest QoS ranking among the other remaining jobs, wherein provisioning the jobs involves making reservations for the jobs based on the resource-usage model and corresponding QoS requirements associated with the jobs.

2. The method of claim 1 , wherein provisioning the jobs further involves:
assigning different numbers of shares to the jobs based on corresponding QoS rankings associated with the jobs, wherein the number of shares assigned to a respective job is inversely correlated to the respective job's QoS ranking; and
assigning reservations based on an assumption that unused reservations associated with the first subset of jobs will be proportionally distributed to the other remaining jobs according to the number of shares assigned to the other remaining jobs.

3. The method of claim 1 , wherein provisioning the jobs further involves:
sorting the jobs in descending order based on QoS rankings; and
iteratively, starting from a job having a highest QoS ranking,
forming a subgroup by adding a next-in-line job to a previously formed subgroup;
establishing a resource-usage model for the subgroup; and
determining a required amount of resources needed by the subgroup based on the resource-usage model for the subgroup and QoS requirement associated with the next-in-line job.

4. The method of claim 3 , further comprising:
making a reservation for the next-in-line job based on a difference between the required amount of resources and reservations made for the previously formed subgroup.

5. The method of claim 3 , further comprising:
in response to at least two jobs having a same QoS ranking, forming a tiered subgroup by adding the at least two jobs as a tier to the previously formed subgroup;
determining a scale factor for each of the at least two jobs based on resources required by each of the least two jobs; and
making reservations for each of the at least two jobs based on the scale factor.

6. The method of claim 1 , further comprising provisioning the jobs for multiple predetermined time intervals, which involves determining a maximum amount of resources required by a group of one or more jobs over the multiple predetermined time intervals.

7. The method of claim 1 , further comprising receiving an isolation parameter which defines a degree of isolation among jobs, wherein provisioning the jobs involves applying the isolation parameter while making reservations for the jobs, and wherein a complete isolation results in making individual reservations for the jobs.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for provisioning physical resources shared by a plurality of jobs, the method comprising:
establishing resource-usage models for the jobs;
ranking the jobs based on quality of service (QoS) requirements associated with the jobs; and
provisioning the jobs for a predetermined time interval in a such way that any unused reservations associated with a first subset of jobs having higher QoS rankings than other remaining jobs are distributed to the other remaining jobs with preference given to a second subset of jobs having a highest QoS ranking among the other remaining jobs, wherein provisioning the jobs involves making reservations for the jobs based on the resource-usage model and corresponding QoS requirements associated with the jobs.

9. The computer-readable storage medium of claim 8 , wherein provisioning the jobs further involves:
assigning different numbers of shares to the jobs based on corresponding QoS rankings associated with the jobs, wherein the number of shares assigned to a respective job is inversely correlated to the respective job's QoS ranking; and
assigning reservations based on an assumption that unused reservations associated with the first subset of jobs will be proportionally distributed to the other remaining jobs according to the number of shares assigned to the other remaining jobs.

10. The computer-readable storage medium of claim 8 , wherein provisioning the jobs further involves:
sorting the jobs in descending order based on QoS rankings; and
iteratively, starting from a job having a highest QoS ranking,
forming a subgroup by adding a next-in-line job to a previously formed subgroup;
establishing a resource-usage model for the subgroup; and
determining a required amount of resources needed by the subgroup based on the resource-usage model for the subgroup and QoS requirement associated with the next-in-line job.

11. The computer-readable storage medium of claim 10 , wherein the method further comprises making a reservation for the next-in-line job based on a difference between the required amount of resources and reservations made for the previously formed subgroup.

12. The computer-readable storage medium of claim 10 , wherein the method further comprises:
in response to at least two jobs having a same QoS ranking, forming a tiered subgroup by adding the at least two jobs as a tier to the previously formed subgroup;
determining a scale factor for each of the at least two jobs based on resources required by each of the at least two jobs; and
making reservations for each of the at least two jobs based on the scale factor.

13. The computer-readable storage medium of claim 8 , wherein the method further comprises provisioning the jobs for multiple predetermined time intervals, which involves determining a maximum amount of resources required by a group of one or more jobs over the multiple predetermined time intervals.

14. The computer-readable storage medium of claim 8 , wherein the method further comprises receiving an isolation parameter which defines a degree of isolation among jobs, wherein provisioning the jobs involves applying the isolation parameter while making reservations for the jobs, and wherein a complete isolation results in making individual reservations for the jobs.

15. A computing system for provisioning physical resources shared by a plurality of jobs, comprising:
a processor;
a memory;
a resource-usage model constructor configured to construct resource-usage models for the jobs;
a ranking mechanism configured to rank the jobs based on quality of service (QoS) requirements associated with the jobs; and
a provisioning mechanism configured to provision the jobs for a predetermined time interval in such a way that any unused reservations associated with a first subset of jobs having higher QoS rankings than other remaining jobs are distributed to the other remaining jobs with preference given to a second subset of jobs having a highest QoS ranking among the other remaining jobs, wherein provisioning the jobs involves making reservations for the jobs based on the resource-usage model and corresponding QoS requirements associated with the jobs.

16. The system of claim 15 , wherein while provisioning the jobs the provisioning mechanism is configured to:
assign different numbers of shares to the jobs based on corresponding QoS rankings associated with the jobs

Assignees

• Palo Alto Res Ct Inc

Inventors

• Greene Daniel H
• Crawford Lara S
• Chu Maurice K
• Hanley John

Classifications

• G06F9/505 Primary

  considering the load · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• Y02B60/142

  Cross-Sectional Technologies · mapped topic

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · 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