Method and apparatus for a user-driven priority based job scheduling in a data processing platform

Patent metadata

Field	Value
Publication number	US-2015150016-A1
Application number	US-201314089253-A
Country	US
Kind code	A1
Filing date	Nov 25, 2013
Priority date	Nov 25, 2013
Publication date	May 28, 2015
Grant date	—

Abstract

A method, non-transitory computer readable medium, and apparatus for configuring a scheduling a job request in a data processing platform are disclosed. The method receives a new job request having a priority selected by a user, submits the new job request to an online job queue comprising a plurality of jobs, wherein each one of the plurality of jobs comprises a respective priority selected by a respective user and schedules the new job request and the plurality of jobs in the online job queue to one or more available worker nodes in a unit time slot based upon a comparison of the priority of the new job and the respective priority of the plurality of jobs in the online job queue, wherein the scheduling algorithm is based on one of: blocks having a variable size and a static processing time or blocks having a static size and a variable processing time.

First claim

What is claimed is:

1 . A method for scheduling a job request in a data processing platform, comprising:
receiving, by a processor of the data processing platform, a new job request having a priority selected by a user; submitting, by the processor, the new job request to an online job queue comprising a plurality of jobs, wherein each one of the plurality of jobs comprises a respective priority selected by a respective user; and scheduling, by the processor, the new job request and the plurality of jobs in the online job queue to one or more available worker nodes in a unit time slot based upon a comparison of the priority of the new job and the respective priority of the plurality of jobs in the online job queue, wherein the scheduling algorithm is based on at least one of: blocks having a variable size and a static processing time or blocks having a static size and a variable processing time.

2 . The method of claim 1 , wherein the data processing platform comprises a distributed processing platform comprising a cluster of computers.

3 . The method of claim 1 , wherein a cost of the new job request is a function of the priority selected by the user.

4 . The method of claim 1 , further comprising:
repeating, by the processor, the scheduling for each successive unit time slot of a plurality of unit time slots for each one of the one or more available worker nodes.

5 . The method of claim 1 , wherein the algorithm based on the blocks having the variable size and the static processing time comprises a function of a capacity of a job represented as a ratio of the job over a sum of all priorities, a function of a total number of worker nodes represented as a minimum of the capacity, a remaining number of required unit time slots for the job and a remaining number of worker nodes available in a current unit time slot and a function of a forfeit represented as a difference of the total number of work nodes and the capacity.

6 . The method of claim 1 , wherein the algorithm based on the blocks having a static size and a variable processing time comprises a function of a capacity of a job represented as a ratio of the job over a sum of all priorities, a function of a total number of worker nodes represented as a minimum of the capacity, a remaining number of required unit time slots for the job and a remaining number of worker nodes available in a current unit time slot, a function of a forfeit represented as a difference of the total number of work nodes and the capacity, an actual allocation of the one or more available worker nodes in one or more future unit time slots and an additional forfeit for using consecutive unit time slots.

7 . The method of claim 1 , further comprising:
providing, by the processor, an option to the user to make a reservation in a reservation queue for the new job request to be processed at a future time instead of submitting the new job request to the online job queue.

8 . The method of claim 7 , wherein a predefined number of all worker nodes is reserved for the reservation queue and a remainder of the all worker nodes is used for the online job queue.

9 . The method of claim 7 , further comprising:
estimating, by the processor, an expected completion time and an expected cost for the new job request to allow the user to decide between the reservation queue or the online job queue.

10 . The method of claim 9 , wherein the estimating the expected completion time is based upon an execution time of a single block of the new job request, a size of the unit time slot and a number of blocks in the new job request.

11 . A non-transitory computer-readable medium storing a plurality of instructions, which when executed by a processor, cause the processor to perform operations for scheduling a job request in a data processing platform, the operations comprising:
receiving a new job request having a priority selected by a user; submitting the new job request to an online job queue comprising a plurality of jobs, wherein each one of the plurality of jobs comprises a respective priority selected by a respective user; and scheduling the new job request and the plurality of jobs in the online job queue to one or more available worker nodes in a unit time slot based upon a comparison of the priority of the new job and the respective priority of the plurality of jobs in the online job queue, wherein the scheduling algorithm is based on at least one of: blocks having a variable size and a static processing time or blocks having a static size and a variable processing time.

12 . The non-transitory computer-readable medium of claim 11 , wherein a cost of the new job request is a function of the priority selected by the user.

13 . The non-transitory computer-readable medium of claim 11 , further comprising:
repeating the scheduling for each successive unit time slot of a plurality of unit time slots for each one of the one or more available worker nodes.

14 . The non-transitory computer-readable medium of claim 11 , wherein the algorithm based on the blocks having the variable size and the static processing time comprises a function of a capacity of a job represented as a ratio of the job over a sum of all priorities, a function of a total number of worker nodes represented as a minimum of the capacity, a remaining number of required unit time slots for the job and a remaining number of worker nodes available in a current unit time slot and a function of a forfeit represented as a difference of the total number of work nodes and the capacity.

15 . The non-transitory computer-readable medium of claim 11 , wherein the algorithm based on the blocks having a static size and a variable processing time comprises a function of a capacity of a job represented as a ratio of the job over a sum of all priorities, a function of a total number of worker nodes represented as a minimum of the capacity, a remaining number of required unit time slots for the job and a remaining number of worker nodes available in a current unit time slot, a function of a forfeit represented as a difference of the total number of work nodes and the capacity, an actual allocation of the one or more available worker nodes in one or more future unit time slots and an additional forfeit for using consecutive unit time slots.

16 . The non-transitory computer-readable medium of claim 11 , further comprising:
providing an option to the user to make a reservation in a reservation queue for the new job request to be processed at a future time instead of submitting the new job request to the online job queue.

17 . The non-transitory computer-readable medium of claim 16 , wherein a predefined number of all worker nodes is reserved for the reservation queue and a remainder of the all worker nodes is used for the online job queue.

18 . The non-transitory computer-readable medium of claim 16 , further comprising:
estimating, by the processor, an expected completion time and an expected cost for the new job request to allow the user to decide between the reservation queue or the online job queue.

19 . The non-transitory computer-readable medium of claim 18 , wherein the estimating the expected completion time is based upon an execution time of a single block of the new job request, a size of the unit time slot and a number of blocks in the new job request.

20 . A method for scheduling a job request in a data processing platform, comprising:
providing, by a processor of the data processing platform, an estimated priority

Assignees

• Xerox Corp

Inventors

• Kim Hyun Joo

Classifications

• G06F2209/5021

  Priority · 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

• G06F2209/483

  Multiproc · CPC title

• G06F2209/5014

  Reservation · CPC title

• G06F9/4881 Primary

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