What is Lottery Scheduling?
Learn how lottery scheduling works — tickets, random draws, ticket transfer — with a clear OS interview question answered.
Expected Interview Answer
Lottery scheduling is a probabilistic CPU scheduling algorithm that gives each process a number of lottery tickets proportional to its desired share of the CPU, and on each scheduling decision the OS draws a random ticket and runs whichever process holds it, so long-run CPU share converges to each process’s ticket proportion.
Instead of computing an explicit ordering like priority or round-robin schedulers do, the scheduler simply picks a random ticket number in the range of all outstanding tickets and runs the process owning that ticket for one quantum. A process with twice as many tickets as another gets, on average, roughly twice the CPU time over many scheduling rounds, giving proportional-share scheduling without complex bookkeeping. Ticket counts can be adjusted dynamically to change priority on the fly, and ticket transfer lets a process temporarily hand its tickets to another (useful when a client process is blocked waiting on a server process, avoiding priority inversion). Because the process is chosen randomly, lottery scheduling avoids the pathological starvation cases some deterministic algorithms suffer, though it introduces some variance in short-term fairness that averages out over time.
- Provides proportional-share CPU allocation via ticket counts
- Simple randomized selection avoids complex priority bookkeeping
- Ticket transfer helps avoid priority inversion between cooperating processes
- Randomness statistically avoids indefinite starvation
AI Mentor Explanation
Lottery scheduling is like a raffle for net-practice slots where each batter is handed a number of raffle tickets based on how much practice time they have earned: a batter with twice as many tickets as another has twice the chance of their number being drawn for the next slot. Over many draws across the season, ticket holders get roughly the share of slots their ticket count implies, even though any single draw is random. A batter can even lend tickets to a teammate waiting on them, so the teammate gets picked sooner without the coach manually reordering anyone.
Step-by-Step Explanation
Step 1
Ticket allocation
Each process is assigned a number of tickets proportional to its desired CPU share.
Step 2
Random draw
On each scheduling decision, the scheduler picks a random ticket number from the total pool of outstanding tickets.
Step 3
Owner runs
The process holding the drawn ticket is scheduled to run for the next quantum.
Step 4
Dynamic adjustment
Tickets can be granted, revoked, or transferred between processes to adjust priority or avoid priority inversion.
What Interviewer Expects
- Understanding that ticket count determines probabilistic, proportional CPU share
- Ability to explain why randomness statistically avoids starvation
- Knowledge of ticket transfer and its use for cooperating processes
- Awareness that lottery scheduling trades short-term determinism for simplicity
Common Mistakes
- Thinking lottery scheduling guarantees exact CPU proportions on every single round
- Confusing ticket transfer with permanent priority reassignment
- Assuming lottery scheduling is deterministic like round robin
- Not knowing it is a form of proportional-share scheduling
Best Answer (HR Friendly)
“Lottery scheduling gives each task a number of virtual raffle tickets based on how much CPU time it should get, then the operating system randomly draws a ticket to decide what runs next. Over time, tasks with more tickets get proportionally more CPU time, and because it is random, no task gets permanently locked out the way some strict priority systems can.”
Code Example
int total_tickets(struct process *procs[], int n) {
int total = 0;
for (int i = 0; i < n; i++) total += procs[i]->tickets;
return total;
}
struct process *pick_winner(struct process *procs[], int n) {
int winning_ticket = rand() % total_tickets(procs, n);
int counter = 0;
for (int i = 0; i < n; i++) {
counter += procs[i]->tickets;
if (winning_ticket < counter) {
return procs[i]; /* this process owns the winning ticket */
}
}
return procs[n - 1];
}Follow-up Questions
- How does ticket transfer help avoid priority inversion?
- How would you convert a desired CPU percentage into a ticket count?
- Why does lottery scheduling avoid starvation better than strict priority scheduling?
- How does stride scheduling improve on lottery scheduling’s short-term variance?
MCQ Practice
1. In lottery scheduling, a process with twice as many tickets as another process will, over the long run, receive?
Because scheduling is a weighted random draw, a process’s long-run CPU share converges to its proportion of the total outstanding tickets.
2. What is ticket transfer used for in lottery scheduling?
A blocked process can lend its tickets to the process it is waiting on so that dependency gets scheduled sooner, avoiding a priority-inversion-like delay.
3. What is the main mechanism lottery scheduling uses to pick the next process to run?
The scheduler draws a random ticket number from the pool of all tickets and runs whichever process owns it.
Flash Cards
What is lottery scheduling? — A probabilistic scheduler where each process holds tickets proportional to its desired CPU share, and a random ticket is drawn to pick the next process.
How is proportional CPU share achieved? — A process with more tickets has a proportionally higher chance of being drawn on each round, converging to its share over many rounds.
What is ticket transfer for? — Letting a blocked process lend its tickets to the process it depends on, avoiding priority-inversion-like delays.
Why does lottery scheduling avoid starvation? — Every process with at least one ticket has a nonzero chance of being drawn on any round, so indefinite exclusion is statistically avoided.