Demand-Driven Workload Scheduling Optimization on Shared Computing Resources

• US 20110154353A1
• Filed: 04/30/2010
• Published: 06/23/2011
• Est. Priority Date: 12/22/2009
• Status: Abandoned Application

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: Piazza, Jeff, Theroux, Michael, Solin, David
• Application Number:
  US12/772,047
• Publication Number:
  US 20110154353A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/506 Constraint
• 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

Abstract

Systems and methods implementing a demand-driven workload scheduling optimization of shared resources used to execute tasks submitted to a computer system are disclosed. Some embodiments include a method for demand-driven computer system resource optimization that includes receiving a request to execute a task (said request including the task'"'"'s required execution time and resource requirements), selecting a prospective execution schedule meeting the required execution time and a computer system resource meeting the resource requirement, determining (in response to the request) a task execution price for using the computer system resource according to the prospective execution schedule, and scheduling the task to execute using the computer system resource according to the prospective execution schedule if the price is accepted. The price varies as a function of availability of the computer system resource at times corresponding to the prospective execution schedule, said availability being measured at the time the price is determined.

Claims

1. A method for demand-driven computer system resource optimization, the method comprising:

receiving, by a processor within a computer system, a request to execute a task, said request comprising a required execution time and a resource requirement for said task;

selecting, by the processor, a prospective execution schedule that meets the required execution time and a computer system resource that meets the resource requirement;

determining, in response to the request, a price for executing the task using the computer system resource according to the prospective execution schedule; and

scheduling, by the processor, the task to execute using the computer system resource according to the prospective execution schedule if an indication of acceptance of the price is received;

wherein said price varies as a function of availability of the computer system resource at one or more times corresponding to the prospective execution schedule, said availability being measured at the time the price is determined.

2. The method of claim 1, wherein selecting the prospective execution schedule comprises:

identifying a plurality of prospective execution schedules if the request allows for variations in the required execution time; and

selecting the prospective execution schedule from the plurality of prospective execution schedules;

wherein each of the plurality of prospective execution schedules reflects a different variation of the required execution time.

3. The method of claim 2, wherein the act of selecting the prospective execution schedule results in a lowest mean value of allocated resources over a specified time period when compared to selecting at least one other prospective execution schedule of the plurality of prospective execution schedules.

4. The method of claim 2, wherein the act of selecting the prospective execution schedule is based at least in part on an analysis of the plurality of prospective execution schedules, the analysis comprising a method selected from the group consisting of a deterministic method, a stochastic method and a metaheuristic method.

5. The method of claim 1, wherein the act of selecting the computer system resource comprises:

identifying a plurality of computer system resources if the request allows for variations in the resource requirement; and

selecting the computer system resource from the plurality of computer system resources;

wherein each of the plurality of computer resources reflects a different variation of the resource requirement.

6. The method of claim 5, wherein the act of selecting the computer system resource results in a lowest mean value of allocated resources over a specified time period when compared to selecting at least one other computer resource of the plurality of computer resources.

7. The method of claim 5, wherein the act of selecting the computer resource is based at least in part on an analysis of the plurality of computer resources, the analysis comprising a method selected from the group consisting of a deterministic method, a stochastic method and a metaheuristic method.

8. The method of claim 1, wherein if an indication of rejection of the price is received instead of an indication of acceptance, the method further comprises:

receiving, by the processor, a second request to execute a task, said request comprising a second required execution time for said task; and

repeating the selecting, determining and scheduling steps of claim 1 using the second required execution time.

9. The method of claim 1, wherein if an indication of rejection of the price is received instead of an indication of acceptance, the method further comprises:

receiving, by the processor, a second request to execute a task, said request comprising a second resource requirement for said task; and

repeating the selecting, determining and scheduling steps of claim 1 using the second resource requirement.

10. A computer-readable storage medium comprising software that can be executed on a processor to cause the processor to perform the method of claim 1.

11. A networked computer system, comprising:

a communication network; and

a plurality of computer systems each coupled to the communication network, at least one computer system of the plurality of computer systems comprising;

a processing unit that;

selects a prospective execution schedule that meets the required execution time and a computer system resource that meets the resource requirement;

determines a price, in response to the request, for executing the task using the computer system resource according to the prospective execution schedule; and

schedules the task to execute using the computer system resource according to the prospective execution schedule if the processing unit receives an indication of acceptance of the price; and

a network interface communicatively coupled to the communication network and the processing unit;

wherein said price increases as a function of decreasing availability of the computer system resource at one or more times corresponding to the prospective execution schedule, said availability being measured at the time the price is determined.

12. The networked computer system of claim 11, the at least one computer system further comprising:

a non-volatile storage device comprising utilization data reflecting current and past utilization of resources of the networked computer system and further comprising resource allocations and task metadata of tasks previously scheduled for execution;

wherein the processing unit selects the prospective execution schedule and the computer system resource that meet the requirements of said request based at least in part on the utilization data, resource allocations and task metadata stored on the non-volatile storage device.

13. The networked computer system of claim 11, wherein the processing unit further:

identifies a plurality of prospective execution schedules if the request allows for variations in the required execution time; and

selects the prospective execution schedule from the plurality of prospective execution schedules;

wherein each of the plurality of prospective execution schedules reflects a different variation of the required execution time.

14. The networked computer system of claim 13, wherein the processing unit selects the prospective execution schedule that results in a lowest mean value of allocated resources over a specified time period when compared to a selection of at least one other prospective execution schedule of the plurality of prospective execution schedules.

15. The networked computer system of claim 13, wherein the processing unit selects the prospective execution schedule based at least in part on an analysis of the plurality of prospective execution schedules, the analysis comprising a method selected from the group consisting of a deterministic method, a stochastic method and a metaheuristic method.

16. The networked computer system of claim 11, wherein the processing unit further:

identifies a plurality of computer system resources if the request allows for variations in the resource requirement; and

selects the computer system resource from the plurality of computer system resources;

wherein each of the plurality of computer resources reflects a different variation of the resource requirement.

17. The networked computer system of claim 16, wherein the processing unit selects the computer system resource that results in a lowest mean value of allocated resources over a specified time period when compared to a selection of at least one other computer resource of the plurality of computer resources.

18. The networked computer system of claim 16, wherein the processing unit selects the computer resource based at least in part on an analysis of the plurality of computer resources, the analysis comprising a method selected from the group consisting of a deterministic method, a stochastic method and a metaheuristic method.

19. The networked computer system of claim 11, wherein if the processor receives an indication of a rejection of the price, the processor further:

receives a second request to execute a task, said request comprising a second required execution time for said task; and

repeats the selection, determination and scheduling performed in claim 11 using the second required execution time.

20. The networked computer system of claim 11, wherein if the processor receives an indication of a rejection of the price, the processor further:

receives a second request to execute a task, said request comprising a second resource requirement for said task; and

repeats the selection, determination and scheduling performed in claim 11 using the second resource requirement.