9. Lottery Scheduling Flashcards
What is proportional-share?
It is when a scheduler tries to guarantee that each job obtain a certain percentage of CPU time
What is lottery scheduling?
Using a random lottery system to decide which process should run next
What are tickets?
The share of a resource that a process should receive
What are the three ticket mechanisms?
Ticket currency: Allows user to allocate tickets among their own jobs. The system will then convert it to a global value.
Ticket transfer: A process can temporarily hand off it tickets to another process
Ticket inflation: A process can temporarily raise or lower the number of tickets it owns
What is the fairness metric?
The time the first job completes divided by the time the second job completes
What is a stride?
A stride is inversely proportional to the number of tickets where a large number is divided by the number of tickets
How does a stride scheduling algorithm work?
At each iteration, it will take the process with the smallest pass value. Once it runs, the process pass value will be increased by its stride value
How does the Completely Fair Scheduler (CFS) work?
It is based on a counting technique known as virtual runtime. The scheduler will pick the one with the lowest vruntime.
The CFS has two metrics:
- scheu_latency: how long does a process run before considering a switch
- min_granularity: minimum amount of time a process should run before considering a switch
CFS also has a nice metric to prioritise jobs.
What data structure does CFS use?
Red black trees are used to store the vruntime of running processes.
How does CFS handle processes who are going through I/O or sleep?
CFS will assign the lowest vruntime to them when they are ready to be executed
