Pizza scheduler

Abstract

Described are techniques used in task scheduling to form a run list used by a task scheduler. A non-priority based technique is disclosed in which each task to be executed is allotted a “pie” count representing the number of times out of the total run list each task is considered for scheduling. The total run list is the sum of all the “pie” counts for all tasks. Each time a task starts, exits, or has its pie count reset, the total number of “pie” counts is computed and tasks are distributed throughout the run list. Each task is distributed in the run list in accordance with its number of “pie” counts such that a minimum number of intervening tasks appears between each successive appearance of the same task. The computed run list is then used by the scheduler. The task scheduling techniques disclosed may be used in a data storage system or elsewhere in a computer system.

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 said run list; 
 constructing the run list by distributing corresponding entries for each task within said run list a number of times in accordance with each task's weighting factor, said weighting factor being represented as a ratio of said each task's count with respect to the total count, wherein at least one of said tasks has more than one corresponding entry in said run list; and 
 executing said tasks in said run list in a round-robin manner. 
 
   
   
     2. The method of  claim 1 , further comprising:
 determining a first position and a second successive position of a first task in said run list such that a minimum number of other tasks intervene between said first position and said second successive position. 
 
   
   
     3. The method of  claim 2 , further comprising:
 computing an updated total count value replacing said total count upon detection of at least one of: a task start, a task completion and a reset of a task's pie count. 
 
   
   
     4. The method of  claim 3 , further comprising:
 distributing, in response to said computing, each task throughout said run list in accordance with said each task's weighting factor using said updated total count value and said each task's pie count. 
 
   
   
     5. The method of  claim 4 , wherein said computing and said distributing in response to said computing are performed by invoking a routine. 
   
   
     6. The method of  claim 5 , wherein said run list is one of a single and a doubly linked list. 
   
   
     7. The method of  claim 4 , wherein said run list is used by a task scheduler included in a data storage system of said computer system. 
   
   
     8. The method of  claim 1 , wherein said count associated with each task in said run list is 1. 
   
   
     9. The method of  claim 1 , wherein said count associated with a first task in said run list is 2 and all other tasks in said run list have an associated count of 1, said first task appearing at a first position at the start of the run list and at a second position approximately half way through said run list. 
   
   
     10. A computer program product, provided in a computer-readable storage medium, for causing a processor to execute a plurality of tasks, comprising:
 machine executable code that determines a count for each task to be executed; 
 machine executable code that determines a total count representing a sum of all counts for all tasks to be included in said run list; and 
 machine executable code that constructs a run list by distributing corresponding entries for each task within said run list a number of times in accordance with each task's weighting factor, said weighting factor being represented as a ratio of said each task's count with respect to the total count, wherein at least one of said tasks has more than one corresponding entry in said run list; and 
 executable code that causes each of said tasks in said run list to run in a round-robin manner. 
 
   
   
     11. The computer program product of  claim 10 , further comprising:
 machine executable code that determines a first position and a second successive position of a first task in said run list such that a minimum number of other tasks intervene between said first position and said second successive position. 
 
   
   
     12. The computer program product of  claim 11 , further comprising:
 machine executable code that computes an updated total count value replacing said total count upon detection of at least one of: a task start, a task completion and a reset of a task's pie count. 
 
   
   
     13. The computer program product of  claim 12 , further comprising:
 machine executable code that distributes, in response to said computing, each task throughout said run list in accordance with said each task's weighting factor using said updated total count value and said each task's pie count. 
 
   
   
     14. The computer program product of  claim 13 , wherein said machine executable code that computes and said machine executable code that, in response to said computing, distributes, are executed by invoking a routine. 
   
   
     15. The computer program product of  claim 14 , wherein said run list is one of a single and a doubly linked list. 
   
   
     16. The computer program product of  claim 13 , wherein said run list is used by a task scheduler included in a data storage system of said computer system. 
   
   
     17. The computer program product of  claim 10 , wherein said count associated with each task in said run list is 1. 
   
   
     18. The computer program product of  claim 10 , wherein said count associated with a first task in said run list is 2 and all other tasks in said run list have an associated count of 1, said first task appearing at a first position at the start of the run list and at a second position approximately half way through said run list.