Lottery Scheduling Policy
Lottery Scheduling is a completely different approach to managing the CPU. It is a proportional-share algorithm, which means its goal is to guarantee that each process receives a certain percentage of CPU time, rather than scheduling them in a strict, deterministic order.
Instead of assigning rigid priorities, the OS issues "lottery tickets" to processes. Every time a scheduling decision needs to be made, the OS randomly draws a winning ticket. The process holding that ticket gets the CPU for a time quantum!
Real-Life Example
Imagine a company raffle for a brand new TV. Alice buys 80 raffle tickets, and Bob buys 20 raffle tickets. Alice has an 80% chance of winning, and Bob has a 20% chance.
Alice is not mathematically *guaranteed* to win. If the announcer pulls a lucky ticket out of the bowl, Bob could still walk away with the TV! However, if they hold 100 raffles over the year, Alice will reliably win about 80 of those TVs. Lottery scheduling works exactly the same way for CPU time.
Example 1: The Expected Outcome
Because Lottery Scheduling is randomized, we cannot draw a static Gantt chart without simulating the random draws. Let's look at two simulations for the same set of processes to see how the randomness affects Turnaround and Waiting times.
Assume both processes arrive at time 0. The Time Quantum is 2 ms.
| Process | Tickets | Win Probability | Burst Time (ms) |
|---|---|---|---|
| P1 | 80 | 80% | 4 |
| P2 | 20 | 20% | 2 |
Simulation 1 (The Favorite Wins):
1. At time 0, the OS draws a ticket between 1 and 100. It draws 42. Since P1 holds tickets 1-80, P1 wins! P1 runs for 2 ms.
2. At time 2, the OS draws ticket 15. P1 wins again! P1 runs for 2 ms and finishes its total 4 ms burst.
3. At time 4, P1 is done. P2 is the only process left, so it wins by default and runs for 2 ms to completion.
Here is the Gantt chart:
+---------+---------+---------+
| P1(Win) | P1(Win) | P2(Def) |
+---------+---------+---------+
0 2 4 6Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 4 ms: 4 - 0 = 4 ms.
- P2 finishes at 6 ms: 6 - 0 = 6 ms.
Average Turnaround Time = (4 + 6) / 2 = 5 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 4 - 4 = 0 ms.
- P2: 6 - 2 = 4 ms.
Average Waiting Time = (0 + 4) / 2 = 2 ms.
Example 2: The Underdog Gets Lucky
Now, let's run the exact same processes again, but this time, the random number generator is going to favor the underdog.
| Process | Tickets | Win Probability | Burst Time (ms) |
|---|---|---|---|
| P1 | 80 | 80% | 4 |
| P2 | 20 | 20% | 2 |
Simulation 2 (The Upset):
1. At time 0, the OS draws ticket 95. P2 only holds tickets 81-100, but it hits the jackpot! P2 wins the CPU and runs for 2 ms, completely finishing its burst.
2. At time 2, P2 is done. P1 is the only process left, so it runs for its 4 ms total (from time 2 to 6).
Here is the Gantt chart:
+---------+---------+---------+
| P2(Win) | P1(Def) | P1(Def) |
+---------+---------+---------+
0 2 4 6Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 6 ms: 6 - 0 = 6 ms.
- P2 finishes at 2 ms: 2 - 0 = 2 ms.
Average Turnaround Time = (6 + 2) / 2 = 4 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 6 - 4 = 2 ms.
- P2: 2 - 2 = 0 ms.
Average Waiting Time = (2 + 0) / 2 = 1 ms.
Because of pure luck, P2 getting scheduled first drastically improved the overall average waiting time of the system!
Advantages of Lottery Scheduling
- Highly responsive and guarantees that no process will ever suffer from absolute starvation (as long as it holds at least 1 ticket).
- Extremely flexible. The OS can instantly give a process more CPU time simply by issuing it more tickets.
- Very simple to implement compared to complex priority aging algorithms.
Disadvantages of Lottery Scheduling
- It is non-deterministic. The OS cannot guarantee hard deadlines because scheduling relies on random chance.
- In the short term, a high-ticket process could get unlucky and experience unusually high waiting times.
- It can be difficult to figure out exactly how many tickets to assign to a process to achieve the desired system behavior.
Lottery Odds
Question 1 of 1Test your understanding of ticket probabilities.