Pizza scheduler

Patent metadata

Field	Value
Publication number	US-9547528-B1
Application number	US-79803610-A
Country	US
Kind code	B1
Filing date	Mar 29, 2010
Priority date	Mar 29, 2010
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

Abstract

Causing a processor to execute a plurality of tasks includes determining a count for each task to be executed, determining a total count representing a sum of all counts for all tasks to be included in a run list, and constructing the run list by distributing corresponding entries for each task within the run list a number of times in accordance with each task's weighting factor. The weighting factor corresponds to a ratio of the each task's count with respect to a total count. Causing a processor to execute a plurality of tasks may also include executing the tasks in the run list in a round-robin manner where a particular entry in the run list is skipped in response to a corresponding task having previously relinquished a slot prior to expiration of time allotted for the task to run in the slot.

First claim

What is claimed is:

1. A method for causing a processor to execute a plurality of tasks, comprising:
determining a count for each task to be executed;
determining a total count representing a sum of all counts for all tasks to be included in a run list;
constructing the run list by distributing corresponding entries for each task within the run list a number of times in accordance with each task's weighting factor, the weighting factor corresponding to a ratio of the each task's count with respect to a total count, wherein at least one of the tasks has more than one corresponding entry in the run list; and
executing the tasks in the run list in a round-robin manner, wherein a particular entry in the run list is skipped in response to a corresponding task having relinquished a slot prior to expiration of time allotted for the task to run in the slot the last time the corresponding task was executed and the particular entry not being the entry from which the corresponding task had last been run.

2. The method of claim 1 , further comprising:
executing a task in the run list in response to the particular entry being the entry from which the task had been executed when the task previously relinquished the slot prior to expiration of time allotted for the task to run in the slot.

3. The method of claim 1 , further comprising:
determining a first position and a second successive position of a first task in the run list such that a minimum number of other tasks intervene between the first position and the second successive position.

4. The method of claim 3 , further comprising:
computing an updated total count value replacing the total count upon detection of at least one of: a task start, a task completion and a reset of a task's count.

5. The method of claim 4 , further comprising:
distributing, in response to the computing, each task throughout the run list in accordance with the each task's weighting factor using the updated total count value and the each task's weighting factor.

6. The method of claim 5 , wherein the run list is used by a task scheduler included in a data storage system of the computer system.

7. The method of claim 5 , wherein computing and distributing are performed by invoking a routine.

8. The method of claim 1 , wherein the run list is one of: a single and a doubly linked list.

9. The method of claim 1 , further comprising:
constructing additional run lists by distributing corresponding entries for each task within the run list a number of times in accordance with each task's weighting factor.

10. The method of claim 9 , wherein the run lists are used according to a relative amount of CPU usage set for each run list.

11. Computer software, provided in a non-transitory computer-readable medium, that causes a processor to execute a plurality of tasks, the software comprising:
executable code that determines a count for each task to be executed;
executable code that determines a total count representing a sum of all counts for all tasks to be included in a run list;
executable code that constructs the run list by distributing corresponding entries for each task within the run list a number of times in accordance with each task's weighting factor, the weighting factor corresponding to a ratio of the each task's count with respect to a total count, wherein at least one of the tasks has more than one corresponding entry in the run list; and
executable code that causes the tasks in the run list to be executed in a round-robin manner, wherein a particular entry in the run list is skipped in response to a corresponding task having relinquished a slot prior to expiration of time allotted for the task to run in the slot the last time the corresponding task was executed and the particular entry not being the entry from which the corresponding task had last been run.

12. The computer software of claim 11 , further comprising:
executable code that causes a task in the run list to be executed in response to the particular entry being the entry from which the task had been executed when the task previously relinquished the slot prior to expiration of time allotted for the task to run in the slot.

13. The computer software of claim 11 , further comprising:
executable code that determines a first position and a second successive position of a first task in the run list such that a minimum number of other tasks intervene between the first position and the second successive position.

14. The computer software of claim 13 , further comprising:
executable code that computes an updated total count value replacing the total count upon detection of at least one of: a task start, a task completion and a reset of a task's count.

15. The computer software of claim 14 , further comprising:
executable code that distributes, in response to the computing, each task throughout the run list in accordance with the each task's weighting factor using the updated total count value and the each task's weighting factor.

16. The computer software of claim 15 , wherein the run list is used by a task scheduler included in a data storage system of the computer system.

17. The computer software of claim 11 , wherein the run list is one of: a single and a doubly linked list.

18. The computer software of claim 11 , further comprising:
executable code that constructs additional run lists by distributing corresponding entries for each task within the run list a number of times in accordance with each task's weighting factor.

19. The computer software of claim 18 , wherein the run lists are used according to a relative amount of CPU usage set for each run list.

Assignees

• Mcclure Steven
• Emc Ip Holding Co Llc

Inventors

• Mcclure Steven

Classifications

• G06F9/4881 Primary

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