lottery scheduling (idea)

Lottery Scheduling is a relatively new method of CPU scheduling for operating systems. It was first introduced in 1994 by Carl Waldspurger and William Weihl of MIT. AFAIK, the only implementation of it in a real OS is in the Mach 3.0 Unix microkernel, although I just wrote a crappy one for NachOS, a simplified OS for teaching. Lottery scheduling selects processes to run in a probabalistically fair distribution, based on a simple priority model.

How it works:

Every process owns a number of lottery tickets. The more tickets your process has, the more likely it is to get scheduled the next quantum. Every quantum, the scheduler holds a quick lottery with all the tickets. If your process's ticket gets picked, then the next quantum is all yours.

Here's an example:

That's a total of 100 tickets, so process c has a 42% chance of being picked each time the OS performs a process switch and so on.

Some cool things that happen in this system:

Say process b with 30 tickets wants to break off into 3 separate threads. Well, if we limit the way new tickets are given out, it's got to give each thread 10 tickets. That means that a process can't hog all the scheduling time just by forking a bunch of times. Great for multi-user systems. It's even plausable (although I doubt it's been done) to make the system give each user a set number of tickets. There's a whole concept of "ticket currencies" in more advanced implementations that allow for all sorts of crazy "trust-boundary" partitioning.

Processes that are waiting in line for a resource can transfer their tickets to the process currently using that resource and get them back once it is done. This has the affect of making busy resources more efficient, since the more processes are blocking on a resource, the more processing time is devoted to keeping the line going. It's almost like voting.

Processing time given to concurrently running programs is very evenly-distributed and responsive. This makes it ideal for systems that run multiple important jobs, like servers. A high-traffic webserver won't hose the important, but less high-traffic mail server if you give the mail server enough tickets. Furthermore, if the mail server is multithreaded well, it won't stand in the way of the webserver when it's not doing anything.

One downside to lottery scheduling is the relatively high overhead involved in holding a lottery every quantum. There are presumably efficient ways of doing it, it's probably still less efficient than the hackjobs that pass for schedulers in most OSes.