Operating System #22 Completely Fair Scheduling (CFS)

Operating System #22 Completely Fair Scheduling (CFS)
Complete Operating Systems Lecture/ Tutorials from IIT @ https://goo.gl/GMr3if
MATLAB Tutorials @ https://goo.gl/EiPgCF
00:30 Completely Fair Scheduling (CFS)
• The Linux scheduler since 2.6.23
• By Ingo Molnar
– based on the Rotating Staircase Deadline Scheduler (RSDL) by Con Kolivas.
– Incorporated in the Linux kernel since 2007
• No heuristics.
• Elegant handling of I/O and CPU bound processes.

01:37 Ideal Fair Scheduling: Divide processor time equally among processes. Ideal Fairness if there are N processes in the system, each process should have got (100/N)% of the CPU time.
Ideal fairness not realizable
• A single processor can’t be shared simultaneously and equally among several processes
• Time slices that are infinitely small are not feasible
• The overheads due to context switching and scheduling will become significant
• CFS uses an approximation of ideal fairness

05:51 CFS Idea:
• When timer interrupt occurs
– Choose the task with the lowest vruntime (min_vruntime)
– Compute its dynamic timeslice (tl/n)
– Program the high resolution timer with this timeslice
• The process begins to execute in the CPU
• When interrupt occurs again
– Context switch if there is another task with a smaller runtime

Picking the Next Task to Run
• CFS uses a red-black tree.
– Each node in the tree represents a runnable task
– Nodes ordered according to their vruntime
• At a context switch,
– Pick the left most node of the tree
• This has the lowest runtime.
• It is cached in min_vruntime. Therefore accessed in O(1)
– If the previous process is runnable, it is inserted into
the tree depending on its new vruntime. Done in O(log(n))
• Tasks move from left to right of tree after its execution completes… starvation avoided

10:55 Priorities and CFS:
• Priority (due to nice values) used to weigh the vruntime
• if process has run for t ms, then
vruntime += t * (weight based on nice of process)

12:00 I/O and CPU bound processes:
• What we need,
– I/O bound should get higher priority and get a longer time to execute compared to CPU bound
– CFS achieves this efficiently
• I/O bound processes have small CPU bursts therefore will have a low vruntime. They would appear towards the left of the tree…. Thus are given higher priorities
• I/O bound processes will typically have larger time slices, because they have smaller vruntime

13:49 New Process:
• Gets added to the RB-tree
• Starts with an initial value of min_vruntime..
• This ensures that it gets to execute quickly

Видео Operating System #22 Completely Fair Scheduling (CFS) канала Xoviabcs