From: Reid Wilkes (reidwilkes_at_hotmail.com)
Date: Sun Feb 01 2004 - 23:24:51 PST
The Lottery Scheduling paper proposes a new scheme for resource allocation by the OS to processes (tasks). The paper itself carries no date to indicate how old it is - but one can infer the year 1993 - 1994 from the dates of the references made in the paper. The idea of lottery scheduling is one which struck me as being particularly profound. I have never really before considered the merits of the standard priority-based schemes used for processor allocation, essentially taking it for granted as "the way things are". But upon closer inspection there do seem to be quite a few problems with priorities: primarily that the assignment of priorities essentially disintegrates into an ad-hoc exercise; and phenomena such as priority inversion can occur when processor usage priority models are disjoint from the access arbitration to other resources. It seems clear that there is room for improvement in this area. At the same time, however, it also seems clear that there is a small threshold of performance in which any new scheme must fit: a complex or otherwise lengthy scheduling algorithm would have serious detrimental effects to overall machine performance. The lottery scheduling proposal is based on a scheme in which each task (thread, process, etc..) which is competing for a resource (in this case, processor time) holds a certain number of tickets. As in a real lottery, a ticket is a probability of winning a random selection. The more tickets one holds, the higher the probability of winning the selection. When a processor becomes free due to a task ending, blocking, or expiring its quantum, a lottery is held. The lottery in the prototype implementation is actually a very fast pseudo-random number generation algorithm. This is coupled with a relatively simple search algorithm to identify the task holding the winning ticket. The winning task is then scheduled onto the processor. This simple idea is coupled with a seemingly very flexible mechanism to allow cooperating groups of tasks to adjust their relative priorities. This mechanism is called "currencies" and basically allows the cooperating groups of tasks to allocate and distribute tickets amongst the constituent tasks without increasing the cumulative number of tickets the group holds on the system by revaluing tickets. Another intriguing related idea is that of transferring tickets to other tasks; for instance a client can transfer its tickets to a server on a synchronous call to that server. This prevents a high priority client being blocked on a low priority server. In a related idea, tickets can be transferred from all the threads waiting on a mutex to the mutex holder. Again, this presents an effective solution to the priority inversion issue. Overall, I found this paper to present a very exciting idea. It was fascinating to see how flexible this relatively simple idea was in addressing many of the known problems in resource scheduling and allocation. I wish the paper had discussed in a little more detail how the system worked from a programmer's point of view - how a process acquired and used tickets.
This archive was generated by hypermail 2.1.6 : Sun Feb 01 2004 - 23:25:06 PST