Lottery Scheduling

There are a number of problems with standard priority-based Unix scheduling algorithms. First, there is no way to insulate users from each other. It is possible for a single user to monopolize the CPU simply by starting many processes. Second, there is no way to directly control relative execution rates. I.e. a user or administrator cannot specify that one task should get half as much CPU as another.

Lottery scheduling CITE was proposed to address the problems mentioned above. In lottery scheduling each task is given some number of tickets. When it is time choose a new task, a lottery is held, and the task holding the winning ticket is allowed to run. This addresses the problem of specifying relative execution rates; a task is expected to run in proportion to the number of tickets it holds.

The problem of user insulation can be addressed by a slight extension of the basic lottery scheduling algorithm: Each user is assigned a number of base tickets. A currency can then be defined that allows the user to distibute as many tickets as he likes to his own tasks, backing those tickets with his base tickets. Lotteries are then performed after task's tickets are scaled by the number of base tickets that they represent. The idea of currencies can be extended indefinately to implement hierarchical resource management.

As it stands, this lottery scheduling algorithm suffers from at least one major drawback. Tasks that consistently use less than their share of the quantum will not recieve their full share of the processor. Waldsprger and Weihl suggest the use of compensation tickets to address this issue. This involves boosting a task's tickets by a factor of $\frac{1}{f}$, where f is the fraction of the quantum that was used. With this modification, tasks can expect to recieve the appropriate share of the CPU even if they do not use their entire quantum.

Compensation tickets also have the effect of increasing interactivity in lottery scheduling. In general, interactive processes spend most of their time waiting for user input, and do not usually use all of their quantum. With compensation tickets, these tasks will tend to be scheduled more frequently.