Scheduling and execution of tasks based on resource availability

• US 9,501,318 B2
• Filed: 06/17/2015
• Issued: 11/22/2016
• Est. Priority Date: 01/10/2014
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cao, Zhao, Shi, Ju Wei, Wang, Chen, Wang, Lan Jun, Wang, Yu, Zou, Jia
• Primary Examiner(s): Lee, Adam
• Application Number:
  US14/741,776
• Publication Number:
  US 20150286504A1
• Time in Patent Office: 524 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

An apparatus for scheduling includes a receiving unit, configured to receive a task of a job; a configuration unit, configured to configure resource amounts for the task in at least two resource dimensions respectively, wherein each of the resource dimensions represents a resource available for configuring; and an interface unit, configured to distribute the task along with information about the resource amounts configured for the task in the resource dimensions.

Claims

1. A method of scheduling, comprising:

receiving a task of a job;

configuring resource amounts for the task in at least two resource dimensions respectively, wherein each of the resource dimensions represents a resource available for configuring;

distributing the task along with information about the resource amounts configured for the task in the resource dimensions to available resources;

executing the task using the available resources;

selecting tasks respectively from a plurality of jobs as candidate tasks to be distributed to the available resources;

receiving the candidate tasks;

configuring resource amounts for each of the candidate tasks in at least two resource dimensions respectively, wherein each of the resource dimensions represents a resource available for configuring;

estimating both a gain and a cost of waiting to generate a scheme for distributing one or more of the candidate tasks to the available resources until after one or more currently executing tasks have completed;

generating the scheme for distributing the one or more of the candidate tasks to the available resources after the one or more currently executing tasks have completed according to the resource amounts configured for each of the one or more of the candidate tasks in the resource dimensions when the estimated gain exceeds the estimated cost;

generating the scheme for distributing the one or more of the candidate tasks to the available resources while the one or more currently executing tasks are executing according to the resource amounts configured for each of the one or more of the candidate tasks in the resource dimensions when the estimated gain is less than or equal to the estimated cost;

distributing the one or more of the candidate tasks along with information about the resource amounts configured for the one or more of the candidate tasks to the available resources according to the generated scheme; and

executing the one or more of the candidate tasks using the available resources.

2. The method according to claim 1, further comprising:

estimating the resource amounts to be consumed by the task in the at least two resource dimensions;

wherein configuring resource amounts for the task in at least two resource dimensions respectively comprises configuring the resource amounts for the task in at least two resource dimensions respectively according to result of the estimating.

3. The method according to claim 2, wherein estimating the resource amounts to be consumed by the task in the at least two resource dimensions comprises:

estimating the resource amounts to be consumed by the task in the at least two resource dimensions according to historical information.

4. The method according to claim 2, wherein estimating the resource amounts to be consumed by the task in the at least two resource dimensions comprises:

estimating the resources amounts to be consumed by the task in the at least two resource dimensions according to sampled information.

5. The method according to claim 1, wherein the method of scheduling is included in a Map process of a MapReduce process.

6. The method according to claim 1, wherein the method of scheduling is included in a Reduce process of a MapReduce process.