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