From: ahemavathy (ahemavathy_at_hotmail.com)
Date: Tue Jan 27 2004 - 22:01:09 PST
The authors have developed a Lottery Scheduler on a Mach 3.0 microkernel. They feel current scheduling mechanisms such as priority scheduling, decay-usage scheduling do not provide flexible and responsive control over service rates. As per Lottery scheduling everybody gets a proportional share of the resources. These resources could be anything.
Lottery scheduling works as follows : Every thread/process owns tickets. More the tickets higher is the probability of it getting control. Everytime when the CPU has to choose a thread, it holds a lottery and picks a ticket. The owner of the ticket receives control. It has additional features like 1) compensation tickets where if the owner could use the CPU for 2 microsecs but it only uses half then compensation tickets are assigned to it and 2) transfer tickets : where if the owner of the ticket if blocked can pass the tickets to the server on which it is waiting so that it is helping to get its job done faster. That is the beauty of the scheduler. Inverse lottery i.e the owner of the ticket chosen becomes the loser could be used to relinquish valuable resources like memory.
I didn't enjoy this paper much. I feel there is a overhead in conducting the lottery each time. Also I feel the lesser ticket holders are at a very high risk of starvation in this scheduling mechanism. One more thing I didn't like about the paper is the graphs are not complete. They do not have an index explaining each curve and so the reader has to figure that out on his own.
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 22:01:42 PST