9. Scheduling. Proprotional share Flashcards
What is concept that proportional share is based on?
Instead of optimizing for turnaround or respones time, it aims at making sure each process gets certain CPU percentage of time
What is an example of proprotional share scheduling?
Lottery scheduling
What resource is used in lottery scheduling?
Tickets
Is lottery scheduling probablistic or deterministic?
Probablistic
How does lottery scheduling makes a decision?
Randomly choose a number and pick a process into which range this number falls. The bigger the process range (number of tickets), the bigger the chance
What is the benefit of using randomness?
Absence of edge cases and no or almost no state management
What mechanism are available in ticket system?
1) Ticket currency. Regardless of the amount of tickets user holds, the system can transform this amount into the global currency
2) Ticket transfer. A process can temporarily held off its tickets to another process
3) Ticket inflation. A process can temporarily raise or lower number of tickets it owns. Makes sense only in a trusted environment
In ticket lottery, is it true that scheduling decision depends exactly on the number of tickets the process holds?
Not exactly. While traversing a list of processes with their tickets, each process tickets are added to a counter until the counter exceeds the random number.
To optimize this mechanism, list of processes and their tickets can be sorted
What metric can be used to determine how good fair scheduler is? How does this metric behave in relation to job’s length?
Fairness metric. It’s a value obtained by dividing the time of first job finish by the time of second job. The closer this value to 1, the more fair the scheduler
With short jobs, this metric won’t do good, but the longer the jobs run, the more fair will be scheduler.
What kind of deterministic fair scheduler exists? How does it work?
Stride scheduler. Each job has a stride, which is inverse proportion to the number of tickets it has (for example, job A has 20 tickets, 10000/20, job’s stride is 500). Every time a process runs, a counter for it is incremented by its stride (called pass value). The process with lowest pass value is scheduled
What is open question we have with stride scheduling?
What pass value should be for a new process? If set to 0, it will monopolize the CPU
What is current Linux scheduler?
The Linux Completely Fair Scheduler (CFS)
How does CFS work?
As each process runs, it accumulates “vruntime”. In the most basic case, “vruntime” increases at the same rate, in proportion with real time. When a scheduling decision occurs, CFS will pick the process with lowest “vruntime”
How does CFS know when to perform a context switch to let other process run?
Through various control parameters:
- sched_latency: determines how long should process run before considering a switch. This value is divided by number of processes to determine a time slice for a process. Its default value is 48 milliseconds
How is problem of too many context switches solved when there are too many processes running and time slice obtained with sched_latency is too small?
Another parameter:
- min_granularity: a minimal value for a time slice. The process can’t run shorter than this value. Usually set to 6 milliseconds
Since CFS is a fair scheduler, how does it utilize niceness to give some process more time to run?
OS utilizes prio_to_weight structure that maps priority of process to the weight. The time slice for a process is obtained by diving the weight of process by sum of weights of all processes and multiplying by sched_latency
The “vrtuntime” also has to be adjusted for process. The value added to current value of runtime is default weight (1024) divided by weight of the process. This way, the processes with lower nice value accumulate “vruntime” slower.
How does CFS achieves the goal of efficiency when it needs to find next job to run?
By keeping processes in “red-black tree” which is more efficient than usual binary trees and achieves logarithmic time by smartly managing depth of a tree. It’s a type of balanced tree. Only running or runnable processes are kept in this structure. Processes are ordered by “vruntime” in this tree.
How does CFS handle I/O?
When jobs sleeps, it does not accumulate “vruntime” which might then make process monopolize CPU if not handled. Instead, when such process is waken up, it’s “vruntime” is set to a minimal number in the tree.
