Task scheduling using improved weighted round robin techniques

Patent metadata

Field	Value
Publication number	US-10324755-B2
Application number	US-201615286680-A
Country	US
Kind code	B2
Filing date	Oct 6, 2016
Priority date	Oct 6, 2016
Publication date	Jun 18, 2019
Grant date	Jun 18, 2019

Abstract

Mechanisms are provided for distributing work requests to worker devices. The mechanisms generate a cycle table data structure which segments a set of work request allocations into a plurality of cycles in which, for each cycle, a subset of worker devices, from a set of worker devices, are eligible to receive allocations of work requests. The mechanisms receive a work request from a computing device and select a worker device to receive the work request, from a first subset of worker devices that are eligible to receive allocations of work requests for a current cycle in the cycle table data structure, based on both of entries in the cycle table data structure corresponding to a current cycle, and execution of weighted round robin scheduling logic. The mechanisms distribute the work request to the selected worker device which performs an operation on the work request.

First claim

What is claimed is:

1. A method, in a data processing system specifically configured with logic for implementing the method, the method being for distributing work requests to worker devices and comprising:
generating, by the data processing system, a cycle table data structure wherein the cycle table data structure segments a set of work request allocations into a plurality of cycles in which, for each cycle, a subset of worker devices, from a set of worker devices, are eligible to receive allocations of work requests;
receiving, by the data processing system, a work request from a computing device;
selecting, by the data processing system, a worker device to receive the work request, from a first subset of worker devices that are eligible to receive allocations of work requests for a current cycle in the cycle table data structure, based on both of entries in the cycle table data structure corresponding to a current cycle, and execution of weighted round robin scheduling logic; and
distributing, by the data processing system, the work request to the selected worker device, wherein the worker device performs an operation on the work request.

2. The method of claim 1 , further comprising:
maintaining, by the data processing system, a current cycle index value indicating a current cycle for allocating work requests to worker devices; and
maintaining, by the data processing system, a last worker index value indicating the identity of a last worker device, in the set of worker devices, to which a work request was allocated, wherein selecting a worker device to receive the work request comprises selecting the worker device based on the last worker index value and values in entries of the cycle table data structure corresponding to the current cycle index value.

3. The method of claim 2 , wherein selecting the worker device based on the last worker index value and values of the current cycle index value comprises:
identifying a row of the cycle table data structure corresponding to the current cycle index value;
identifying the subset of worker devices as worker devices associated with weight values for which corresponding entries in the identified row of the cycle table data structure are set to an allocation value indicating eligibility to receive allocations of work requests; and
selecting a next worker device, in the subset of worker devices, that is after a worker device indicated by the last worker index value, in a sequential order, as the selected worker device.

4. The method of claim 1 , wherein each cycle, in the plurality of cycles, has a different associated subset of worker devices that are eligible to receive work requests, during that cycle, than is associated with other cycles in the plurality of cycles of the cycle table data structure.

5. The method of claim 1 , wherein the cycle table data structure comprises columns corresponding to weight values associated with zero or more worker devices in the set of worker devices, and rows corresponding to individual cycles in the plurality of cycles, and wherein worker devices, in the subset of worker devices, for a cycle in the plurality of cycles, are indicated in the cycle table data structure as being eligible for receiving allocations of work requests by a specified value in columns corresponding to weight values assigned to worker devices in the subset of worker devices.

6. The method of claim 5 , wherein the cycle table data structure comprises a number of columns equal to or exceeding a maximum weight value assigned to the set of worker devices.

7. The method of claim 6 , wherein the cycle table data structure comprises a number of rows equal to or exceeding the maximum weight value assigned to the set of work devices.

8. The method of claim 5 , wherein, for each column in the cycle table data structure, a number of entries in the column having allocation values that indicate eligibility to be allocated work requests is equal to a corresponding column number in the cycle table data structure for the column.

9. The method of claim 8 , wherein, for each column in the cycle table data structure, the entries having allocation values that indicate eligibility to allocate work requests are distributed amongst the entries for the column as evenly as possible given the number of entries.

10. The method of claim 1 , wherein the worker devices are one of a data processing system that executes an operation on work requests allocated to the worker device, or a computing device associated with a human being that performs an operation based on the work request.

11. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:
generate a cycle table data structure wherein the cycle table data structure segments a set of work request allocations into a plurality of cycles in which, for each cycle, a subset of worker devices, from a set of worker devices, are eligible to receive allocations of work requests;
receive a work request from a computing device;
select a worker device to receive the work request, from a first subset of worker devices that are eligible to receive allocations of work requests for a current cycle in the cycle table data structure, based on both of entries in the cycle table data structure corresponding to a current cycle, and execution of weighted round robin scheduling logic; and
distribute the work request to the selected worker device, wherein the worker device performs an operation on the work request.

12. The computer program product of claim 11 , wherein the computer readable program further causes the computing device to:
maintain a current cycle index value indicating a current cycle for allocating work requests to worker devices; and
maintain a last worker index value indicating the identity of a last worker device, in the set of worker devices, to which a work request was allocated, wherein selecting a worker device to receive the work request comprises selecting the worker device based on the last worker index value and values in entries of the cycle table data structure corresponding to the current cycle index value.

13. The computer program product of claim 12 , wherein the computer readable program further causes the computing device to select the worker device based on the last worker index value and values of the current cycle index value at least by:
identifying a row of the cycle table data structure corresponding to the current cycle index value;
identifying the subset of worker devices as worker devices associated with weight values for which corresponding entries in the identified row of the cycle table data structure are set to an allocation value indicating eligibility to receive allocations of work requests; and
selecting a next worker device, in the subset of worker devices, that is after a worker device indicated by the last worker index value, in a sequential order, as the selected worker device.

14. The computer program product of claim 11 , wherein each cycle, in the plurality of cycles, has a different associated subset of worker devices that are eligible to receive work requests, during that cycle, than is associated with other cycles in the plurality of cycles of the cycle table data structure.

15. The computer program product of claim 11 , wherein the cycle table data structure comprises columns corresponding to weight values associated with zero or more worker devices in the set of worker devices, and rows corresponding to individual cyc

Assignees

• IBM

Inventors

• Hirsch Philip D

Classifications

• G06F9/4881 Primary

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