From: Honghai Liu (liu789_at_hotmail.com)
Date: Wed Jan 28 2004 - 14:54:13 PST
Reviewer: Honghai Liu
The paper presents a unique algorithm, lottery scheduling, to manage scheduling in the operating systems. The idea is simple but extremely powerful- every resource holds lottery tickets and the probability of scheduling a task is dependant or proportional on the number of tickets it holds compared to the total tickets.
Some unique properties of the lottery scheduling:
First, it is fair. Though it sounds simple, most of the operating system don't have this properties. They are priority based, basically, the one with high priority wins the time to run. But there is a problem with it, because it is sometimes arbitrary. For example, initially task A and B has equal priorities but at same point task A consumes less CPU time than B so its priority increases by one, let's say. All it means is that it will get chance to run before B next time. But it's not fair for two reasons: One, how can we quantify the priority level, i.e. what one level higher really means. It can mean quite differently in different system. Second, task A's priority has been increased without any consideration of tasks in the system other than B. Lottery scheduling can easily solve these two problems.
Second, it's dynamic. With simple mechanisms like ticket transfer, inflation, compensation and currency management, the lottery scheduling can dynamically adjust the ticket distribution based on different scenarios. It is amazing to see it still work even with the addition of other task.
Third, it is lightweight and responsive. The data shows that latency and throughput are comparable with most of the scheduling system. It's an important because it means it can be run on any operating systems without compromising its performance.
One thing I am not clear in the paper:
In Sec. 6.1 why the mutex has to transfer its inheritance ticket to the thread holding the mutex
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 14:55:46 PST