9. Scheduling. Proprotional share

Question 1

What is concept that proportional share is based on?

Answer 1

Instead of optimizing for turnaround or respones time, it aims at making sure each process gets certain CPU percentage of time

Question 2

What is an example of proprotional share scheduling?

Answer 2

Lottery scheduling

Question 3

What resource is used in lottery scheduling?

Answer 3

Tickets

Question 4

Is lottery scheduling probablistic or deterministic?

Answer 4

Probablistic

Question 5

How does lottery scheduling makes a decision?

Answer 5

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

Question 6

What is the benefit of using randomness?

Answer 6

Absence of edge cases and no or almost no state management

Question 7

What mechanism are available in ticket system?

Answer 7

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

Question 8

In ticket lottery, is it true that scheduling decision depends exactly on the number of tickets the process holds?

Answer 8

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

Question 9

What metric can be used to determine how good fair scheduler is? How does this metric behave in relation to job’s length?

Answer 9

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.

Question 10

What kind of deterministic fair scheduler exists? How does it work?

Answer 10

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

Question 11

What is open question we have with stride scheduling?

Answer 11

What pass value should be for a new process? If set to 0, it will monopolize the CPU

Question 12

What is current Linux scheduler?

Answer 12

The Linux Completely Fair Scheduler (CFS)

Question 13

How does CFS work?

Answer 13

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”

Question 14

How does CFS know when to perform a context switch to let other process run?

Answer 14

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

Question 15

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?

Answer 15

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

Question 16

Since CFS is a fair scheduler, how does it utilize niceness to give some process more time to run?

Answer 16

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.

Question 17

How does CFS achieves the goal of efficiency when it needs to find next job to run?

Answer 17

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.

Question 18

How does CFS handle I/O?

Answer 18

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.