CS262A Reading Summary 18

Lottery Scheduling: Flexible Proportional-Share Resource Management

C. A. Waldspurger and W. E. Weihl
Summary by Feng Zhou
10/17/2002

1. Lottery scheduling is a very simple and attractive scheduling policy. With a simple protocol and very little computation, it is potentially able to solve problems like in-fairness and starvation easily. This is due to the random nature of the policy, which converges to the exact desire behavior in the long run.
2. A few tricks make lottery scheduling more interesting. Ticket transfer conveniently solves the priority inversion problem. Ticket inflation let trusted parties adjust their resource allocation without explicit communication. By using compensation tickets, fairness between resource-greedy parties and less greedy parties can be achieved. DAG shaped currency graph gives the scheduler load insulation between tasks in different parts of the graph, which is very important if different groups of tasks are run on the same system.
3. Lottery scheduling can be extended to other scenarios. It can be used to implement mutual exclusion and in the same time solves the priority inversion problem. Its variant can also be used to manage space-shared resources like main memory. Thus lottery scheduling can be taken as a large category of resource-allocation policies.

1 flaws:

There maybe one disadvantage of lottery scheduling: It focuses on fairness, not responsiveness. Thus it may not be well suited for a interative or GUI environment. In this situation, the UI task should be scheduled whenever possible when user input like mouse/keyboard action comes. This seems to be done better with an absolute prioritirized schedular, in which the UI task has a higher priority.