chapter 9 - Scheduling: Proportional Share Flashcards
tickets
represents a process’s share of a resource - like CPU
how does lottery scheduling choose who runs
pick a random ticket each time slice - owner of ticket wins
If Process A has 75 tickets and B has 25, how is CPU time divided?
A gets 75% of the CPU, B gets 25%
What is ticket currency?
A user can divide their global ticket share into local tickets for their own jobs
What is ticket transfer?
A process gives its tickets temporarily to another (e.g., client to server)
What is ticket inflation?
A process temporarily increases its own ticket count to gain more CPU — only safe in trusted environments
What is the risk of ticket inflation in untrusted environments?
A greedy process could dominate the CPU unfairly
how does scheduler select a process in lottery scheduling
pick random number from 0 to total-1- walk the list and sum ticket values - first process where cumulative exceeds the random number wins
unfairness metric U represent
U = time job 1 completes/ time job 2 completes – U = 1 is fair
Why doesn’t lottery scheduling guarantee fairness in the short term?
Because of its random nature - fairness only emerges over time
What is stride scheduling?
A deterministic alternative to lottery scheduling that uses strides and pass values to control CPU access
how is stride and pass calculated
- stride = large number / tickets
- pass += stride
how does a scheduler pick a job in stride scheduling
pick the job with lowest pass value
downside of stride scheduling
- requires global state
- hard to set fair initial pass for new job
how does lottery scheduling avoid strides downside
It uses a single global ticket pool, making it easier to add/remove jobs dynamically
