Lottery Scheduling
Reading Notes
Overview
- resource management on CPU
- lottery scheduling: a novel randomized mechanism that provides responsive control over the relative execution rates of computations.
Q: At a high level, as a mechanism how does lottery scheduling provide modular resource management? Why can't the Unix scheduler provide a similar kind of management?
- Lottery schaeduling enables concurrent modules to insulate their resource allocation policies from one another.
2. Lottery Scheduling
- Resource rights are represented by lottery tickets.
- Scheduling by lottery is probabilistically fair.
- The number of lotteries won by a client has a binomial distribution.
3. Modular Resource Management
- Example Lottery
- A unique currency is used to denominate tickets within each trust boundary
4. Implementation
- currency’s value: summing the value of its backing tickets.
- ticket's value: multiplying the value of the currency in which it is denominated by its share of the active amount issued in that currency.
Class notes
Lottery scheduling
Overview of Lottery scheduling
- Each process has certain number of lottery tickets; each representing one PCU quanta
- OS holds regular lotteries to schedule each quanta
- Holder of winning ticket gets CPU
- More tickets -> more likely to get CPU quickly and more likely to get more CPU over time if a user has tickets out of a total of T, the probability of winning in a given round p=t/T