Commit | Line | Data |
---|---|---|
d6a3b247 MCC |
1 | ============= |
2 | CFS Scheduler | |
3 | ============= | |
5e7eaade | 4 | |
5cb350ba | 5 | |
f58e2c33 | 6 | 1. OVERVIEW |
d6a3b247 | 7 | ============ |
f58e2c33 CS |
8 | |
9 | CFS stands for "Completely Fair Scheduler," and is the new "desktop" process | |
10 | scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the | |
11 | replacement for the previous vanilla scheduler's SCHED_OTHER interactivity | |
12 | code. | |
13 | ||
14 | 80% of CFS's design can be summed up in a single sentence: CFS basically models | |
15 | an "ideal, precise multi-tasking CPU" on real hardware. | |
16 | ||
17 | "Ideal multi-tasking CPU" is a (non-existent :-)) CPU that has 100% physical | |
18 | power and which can run each task at precise equal speed, in parallel, each at | |
19 | 1/nr_running speed. For example: if there are 2 tasks running, then it runs | |
20 | each at 50% physical power --- i.e., actually in parallel. | |
21 | ||
22 | On real hardware, we can run only a single task at once, so we have to | |
23 | introduce the concept of "virtual runtime." The virtual runtime of a task | |
24 | specifies when its next timeslice would start execution on the ideal | |
25 | multi-tasking CPU described above. In practice, the virtual runtime of a task | |
26 | is its actual runtime normalized to the total number of running tasks. | |
27 | ||
28 | ||
29 | ||
30 | 2. FEW IMPLEMENTATION DETAILS | |
d6a3b247 | 31 | ============================== |
f58e2c33 CS |
32 | |
33 | In CFS the virtual runtime is expressed and tracked via the per-task | |
34 | p->se.vruntime (nanosec-unit) value. This way, it's possible to accurately | |
35 | timestamp and measure the "expected CPU time" a task should have gotten. | |
36 | ||
f1779d13 KK |
37 | Small detail: on "ideal" hardware, at any time all tasks would have the same |
38 | p->se.vruntime value --- i.e., tasks would execute simultaneously and no task | |
39 | would ever get "out of balance" from the "ideal" share of CPU time. | |
f58e2c33 CS |
40 | |
41 | CFS's task picking logic is based on this p->se.vruntime value and it is thus | |
42 | very simple: it always tries to run the task with the smallest p->se.vruntime | |
43 | value (i.e., the task which executed least so far). CFS always tries to split | |
44 | up CPU time between runnable tasks as close to "ideal multitasking hardware" as | |
45 | possible. | |
46 | ||
47 | Most of the rest of CFS's design just falls out of this really simple concept, | |
48 | with a few add-on embellishments like nice levels, multiprocessing and various | |
49 | algorithm variants to recognize sleepers. | |
50 | ||
51 | ||
52 | ||
53 | 3. THE RBTREE | |
d6a3b247 | 54 | ============== |
f58e2c33 CS |
55 | |
56 | CFS's design is quite radical: it does not use the old data structures for the | |
57 | runqueues, but it uses a time-ordered rbtree to build a "timeline" of future | |
58 | task execution, and thus has no "array switch" artifacts (by which both the | |
59 | previous vanilla scheduler and RSDL/SD are affected). | |
60 | ||
61 | CFS also maintains the rq->cfs.min_vruntime value, which is a monotonic | |
62 | increasing value tracking the smallest vruntime among all tasks in the | |
63 | runqueue. The total amount of work done by the system is tracked using | |
64 | min_vruntime; that value is used to place newly activated entities on the left | |
65 | side of the tree as much as possible. | |
66 | ||
67 | The total number of running tasks in the runqueue is accounted through the | |
68 | rq->cfs.load value, which is the sum of the weights of the tasks queued on the | |
69 | runqueue. | |
70 | ||
71 | CFS maintains a time-ordered rbtree, where all runnable tasks are sorted by the | |
3b524d60 | 72 | p->se.vruntime key. CFS picks the "leftmost" task from this tree and sticks to it. |
f58e2c33 CS |
73 | As the system progresses forwards, the executed tasks are put into the tree |
74 | more and more to the right --- slowly but surely giving a chance for every task | |
75 | to become the "leftmost task" and thus get on the CPU within a deterministic | |
76 | amount of time. | |
77 | ||
78 | Summing up, CFS works like this: it runs a task a bit, and when the task | |
79 | schedules (or a scheduler tick happens) the task's CPU usage is "accounted | |
80 | for": the (small) time it just spent using the physical CPU is added to | |
81 | p->se.vruntime. Once p->se.vruntime gets high enough so that another task | |
82 | becomes the "leftmost task" of the time-ordered rbtree it maintains (plus a | |
83 | small amount of "granularity" distance relative to the leftmost task so that we | |
84 | do not over-schedule tasks and trash the cache), then the new leftmost task is | |
85 | picked and the current task is preempted. | |
86 | ||
87 | ||
88 | ||
89 | 4. SOME FEATURES OF CFS | |
d6a3b247 | 90 | ======================== |
f58e2c33 CS |
91 | |
92 | CFS uses nanosecond granularity accounting and does not rely on any jiffies or | |
93 | other HZ detail. Thus the CFS scheduler has no notion of "timeslices" in the | |
94 | way the previous scheduler had, and has no heuristics whatsoever. There is | |
95 | only one central tunable (you have to switch on CONFIG_SCHED_DEBUG): | |
96 | ||
4078e359 | 97 | /proc/sys/kernel/sched_min_granularity_ns |
f58e2c33 CS |
98 | |
99 | which can be used to tune the scheduler from "desktop" (i.e., low latencies) to | |
100 | "server" (i.e., good batching) workloads. It defaults to a setting suitable | |
101 | for desktop workloads. SCHED_BATCH is handled by the CFS scheduler module too. | |
102 | ||
103 | Due to its design, the CFS scheduler is not prone to any of the "attacks" that | |
104 | exist today against the heuristics of the stock scheduler: fiftyp.c, thud.c, | |
105 | chew.c, ring-test.c, massive_intr.c all work fine and do not impact | |
106 | interactivity and produce the expected behavior. | |
107 | ||
108 | The CFS scheduler has a much stronger handling of nice levels and SCHED_BATCH | |
109 | than the previous vanilla scheduler: both types of workloads are isolated much | |
110 | more aggressively. | |
111 | ||
112 | SMP load-balancing has been reworked/sanitized: the runqueue-walking | |
113 | assumptions are gone from the load-balancing code now, and iterators of the | |
114 | scheduling modules are used. The balancing code got quite a bit simpler as a | |
115 | result. | |
116 | ||
117 | ||
118 | ||
1a73ef6a | 119 | 5. Scheduling policies |
d6a3b247 | 120 | ====================== |
1a73ef6a MS |
121 | |
122 | CFS implements three scheduling policies: | |
123 | ||
124 | - SCHED_NORMAL (traditionally called SCHED_OTHER): The scheduling | |
125 | policy that is used for regular tasks. | |
126 | ||
127 | - SCHED_BATCH: Does not preempt nearly as often as regular tasks | |
128 | would, thereby allowing tasks to run longer and make better use of | |
129 | caches but at the cost of interactivity. This is well suited for | |
130 | batch jobs. | |
131 | ||
132 | - SCHED_IDLE: This is even weaker than nice 19, but its not a true | |
133 | idle timer scheduler in order to avoid to get into priority | |
134 | inversion problems which would deadlock the machine. | |
135 | ||
489a71b0 | 136 | SCHED_FIFO/_RR are implemented in sched/rt.c and are as specified by |
1a73ef6a MS |
137 | POSIX. |
138 | ||
139 | The command chrt from util-linux-ng 2.13.1.1 can set all of these except | |
140 | SCHED_IDLE. | |
141 | ||
142 | ||
143 | ||
144 | 6. SCHEDULING CLASSES | |
d6a3b247 | 145 | ====================== |
f58e2c33 CS |
146 | |
147 | The new CFS scheduler has been designed in such a way to introduce "Scheduling | |
148 | Classes," an extensible hierarchy of scheduler modules. These modules | |
149 | encapsulate scheduling policy details and are handled by the scheduler core | |
150 | without the core code assuming too much about them. | |
151 | ||
489a71b0 | 152 | sched/fair.c implements the CFS scheduler described above. |
5cb350ba | 153 | |
489a71b0 | 154 | sched/rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler way than |
f58e2c33 CS |
155 | the previous vanilla scheduler did. It uses 100 runqueues (for all 100 RT |
156 | priority levels, instead of 140 in the previous scheduler) and it needs no | |
157 | expired array. | |
5cb350ba | 158 | |
f58e2c33 CS |
159 | Scheduling classes are implemented through the sched_class structure, which |
160 | contains hooks to functions that must be called whenever an interesting event | |
161 | occurs. | |
162 | ||
163 | This is the (partial) list of the hooks: | |
164 | ||
165 | - enqueue_task(...) | |
166 | ||
167 | Called when a task enters a runnable state. | |
168 | It puts the scheduling entity (task) into the red-black tree and | |
169 | increments the nr_running variable. | |
170 | ||
1232d613 | 171 | - dequeue_task(...) |
f58e2c33 CS |
172 | |
173 | When a task is no longer runnable, this function is called to keep the | |
174 | corresponding scheduling entity out of the red-black tree. It decrements | |
175 | the nr_running variable. | |
176 | ||
177 | - yield_task(...) | |
178 | ||
179 | This function is basically just a dequeue followed by an enqueue, unless the | |
180 | compat_yield sysctl is turned on; in that case, it places the scheduling | |
181 | entity at the right-most end of the red-black tree. | |
182 | ||
183 | - check_preempt_curr(...) | |
184 | ||
185 | This function checks if a task that entered the runnable state should | |
186 | preempt the currently running task. | |
187 | ||
188 | - pick_next_task(...) | |
189 | ||
190 | This function chooses the most appropriate task eligible to run next. | |
191 | ||
192 | - set_curr_task(...) | |
193 | ||
194 | This function is called when a task changes its scheduling class or changes | |
195 | its task group. | |
196 | ||
197 | - task_tick(...) | |
198 | ||
199 | This function is mostly called from time tick functions; it might lead to | |
200 | process switch. This drives the running preemption. | |
201 | ||
f58e2c33 CS |
202 | |
203 | ||
204 | ||
1a73ef6a | 205 | 7. GROUP SCHEDULER EXTENSIONS TO CFS |
d6a3b247 | 206 | ===================================== |
f58e2c33 CS |
207 | |
208 | Normally, the scheduler operates on individual tasks and strives to provide | |
209 | fair CPU time to each task. Sometimes, it may be desirable to group tasks and | |
210 | provide fair CPU time to each such task group. For example, it may be | |
211 | desirable to first provide fair CPU time to each user on the system and then to | |
212 | each task belonging to a user. | |
213 | ||
25c2d55c | 214 | CONFIG_CGROUP_SCHED strives to achieve exactly that. It lets tasks to be |
f58e2c33 CS |
215 | grouped and divides CPU time fairly among such groups. |
216 | ||
217 | CONFIG_RT_GROUP_SCHED permits to group real-time (i.e., SCHED_FIFO and | |
218 | SCHED_RR) tasks. | |
219 | ||
220 | CONFIG_FAIR_GROUP_SCHED permits to group CFS (i.e., SCHED_NORMAL and | |
221 | SCHED_BATCH) tasks. | |
222 | ||
25c2d55c | 223 | These options need CONFIG_CGROUPS to be defined, and let the administrator |
f58e2c33 | 224 | create arbitrary groups of tasks, using the "cgroup" pseudo filesystem. See |
da82c92f | 225 | Documentation/admin-guide/cgroup-v1/cgroups.rst for more information about this filesystem. |
f58e2c33 | 226 | |
25c2d55c | 227 | When CONFIG_FAIR_GROUP_SCHED is defined, a "cpu.shares" file is created for each |
f58e2c33 | 228 | group created using the pseudo filesystem. See example steps below to create |
d6a3b247 | 229 | task groups and modify their CPU share using the "cgroups" pseudo filesystem:: |
5cb350ba | 230 | |
f6e07d38 JS |
231 | # mount -t tmpfs cgroup_root /sys/fs/cgroup |
232 | # mkdir /sys/fs/cgroup/cpu | |
233 | # mount -t cgroup -ocpu none /sys/fs/cgroup/cpu | |
234 | # cd /sys/fs/cgroup/cpu | |
5cb350ba DG |
235 | |
236 | # mkdir multimedia # create "multimedia" group of tasks | |
237 | # mkdir browser # create "browser" group of tasks | |
238 | ||
239 | # #Configure the multimedia group to receive twice the CPU bandwidth | |
240 | # #that of browser group | |
241 | ||
242 | # echo 2048 > multimedia/cpu.shares | |
243 | # echo 1024 > browser/cpu.shares | |
244 | ||
245 | # firefox & # Launch firefox and move it to "browser" group | |
246 | # echo <firefox_pid> > browser/tasks | |
247 | ||
248 | # #Launch gmplayer (or your favourite movie player) | |
249 | # echo <movie_player_pid> > multimedia/tasks |