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 | |
69 | p->se.vruntime key (there is a subtraction using rq->cfs.min_vruntime to | |
70 | account for possible wraparounds). CFS picks the "leftmost" task from this | |
71 | tree and sticks to it. | |
72 | As the system progresses forwards, the executed tasks are put into the tree | |
73 | more and more to the right --- slowly but surely giving a chance for every task | |
74 | to become the "leftmost task" and thus get on the CPU within a deterministic | |
75 | amount of time. | |
76 | ||
77 | Summing up, CFS works like this: it runs a task a bit, and when the task | |
78 | schedules (or a scheduler tick happens) the task's CPU usage is "accounted | |
79 | for": the (small) time it just spent using the physical CPU is added to | |
80 | p->se.vruntime. Once p->se.vruntime gets high enough so that another task | |
81 | becomes the "leftmost task" of the time-ordered rbtree it maintains (plus a | |
82 | small amount of "granularity" distance relative to the leftmost task so that we | |
83 | do not over-schedule tasks and trash the cache), then the new leftmost task is | |
84 | picked and the current task is preempted. | |
85 | ||
86 | ||
87 | ||
88 | 4. SOME FEATURES OF CFS | |
89 | ||
90 | CFS uses nanosecond granularity accounting and does not rely on any jiffies or | |
91 | other HZ detail. Thus the CFS scheduler has no notion of "timeslices" in the | |
92 | way the previous scheduler had, and has no heuristics whatsoever. There is | |
93 | only one central tunable (you have to switch on CONFIG_SCHED_DEBUG): | |
94 | ||
4078e359 | 95 | /proc/sys/kernel/sched_min_granularity_ns |
f58e2c33 CS |
96 | |
97 | which can be used to tune the scheduler from "desktop" (i.e., low latencies) to | |
98 | "server" (i.e., good batching) workloads. It defaults to a setting suitable | |
99 | for desktop workloads. SCHED_BATCH is handled by the CFS scheduler module too. | |
100 | ||
101 | Due to its design, the CFS scheduler is not prone to any of the "attacks" that | |
102 | exist today against the heuristics of the stock scheduler: fiftyp.c, thud.c, | |
103 | chew.c, ring-test.c, massive_intr.c all work fine and do not impact | |
104 | interactivity and produce the expected behavior. | |
105 | ||
106 | The CFS scheduler has a much stronger handling of nice levels and SCHED_BATCH | |
107 | than the previous vanilla scheduler: both types of workloads are isolated much | |
108 | more aggressively. | |
109 | ||
110 | SMP load-balancing has been reworked/sanitized: the runqueue-walking | |
111 | assumptions are gone from the load-balancing code now, and iterators of the | |
112 | scheduling modules are used. The balancing code got quite a bit simpler as a | |
113 | result. | |
114 | ||
115 | ||
116 | ||
1a73ef6a MS |
117 | 5. Scheduling policies |
118 | ||
119 | CFS implements three scheduling policies: | |
120 | ||
121 | - SCHED_NORMAL (traditionally called SCHED_OTHER): The scheduling | |
122 | policy that is used for regular tasks. | |
123 | ||
124 | - SCHED_BATCH: Does not preempt nearly as often as regular tasks | |
125 | would, thereby allowing tasks to run longer and make better use of | |
126 | caches but at the cost of interactivity. This is well suited for | |
127 | batch jobs. | |
128 | ||
129 | - SCHED_IDLE: This is even weaker than nice 19, but its not a true | |
130 | idle timer scheduler in order to avoid to get into priority | |
131 | inversion problems which would deadlock the machine. | |
132 | ||
489a71b0 | 133 | SCHED_FIFO/_RR are implemented in sched/rt.c and are as specified by |
1a73ef6a MS |
134 | POSIX. |
135 | ||
136 | The command chrt from util-linux-ng 2.13.1.1 can set all of these except | |
137 | SCHED_IDLE. | |
138 | ||
139 | ||
140 | ||
141 | 6. SCHEDULING CLASSES | |
f58e2c33 CS |
142 | |
143 | The new CFS scheduler has been designed in such a way to introduce "Scheduling | |
144 | Classes," an extensible hierarchy of scheduler modules. These modules | |
145 | encapsulate scheduling policy details and are handled by the scheduler core | |
146 | without the core code assuming too much about them. | |
147 | ||
489a71b0 | 148 | sched/fair.c implements the CFS scheduler described above. |
5cb350ba | 149 | |
489a71b0 | 150 | sched/rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler way than |
f58e2c33 CS |
151 | the previous vanilla scheduler did. It uses 100 runqueues (for all 100 RT |
152 | priority levels, instead of 140 in the previous scheduler) and it needs no | |
153 | expired array. | |
5cb350ba | 154 | |
f58e2c33 CS |
155 | Scheduling classes are implemented through the sched_class structure, which |
156 | contains hooks to functions that must be called whenever an interesting event | |
157 | occurs. | |
158 | ||
159 | This is the (partial) list of the hooks: | |
160 | ||
161 | - enqueue_task(...) | |
162 | ||
163 | Called when a task enters a runnable state. | |
164 | It puts the scheduling entity (task) into the red-black tree and | |
165 | increments the nr_running variable. | |
166 | ||
1232d613 | 167 | - dequeue_task(...) |
f58e2c33 CS |
168 | |
169 | When a task is no longer runnable, this function is called to keep the | |
170 | corresponding scheduling entity out of the red-black tree. It decrements | |
171 | the nr_running variable. | |
172 | ||
173 | - yield_task(...) | |
174 | ||
175 | This function is basically just a dequeue followed by an enqueue, unless the | |
176 | compat_yield sysctl is turned on; in that case, it places the scheduling | |
177 | entity at the right-most end of the red-black tree. | |
178 | ||
179 | - check_preempt_curr(...) | |
180 | ||
181 | This function checks if a task that entered the runnable state should | |
182 | preempt the currently running task. | |
183 | ||
184 | - pick_next_task(...) | |
185 | ||
186 | This function chooses the most appropriate task eligible to run next. | |
187 | ||
188 | - set_curr_task(...) | |
189 | ||
190 | This function is called when a task changes its scheduling class or changes | |
191 | its task group. | |
192 | ||
193 | - task_tick(...) | |
194 | ||
195 | This function is mostly called from time tick functions; it might lead to | |
196 | process switch. This drives the running preemption. | |
197 | ||
f58e2c33 CS |
198 | |
199 | ||
200 | ||
1a73ef6a | 201 | 7. GROUP SCHEDULER EXTENSIONS TO CFS |
f58e2c33 CS |
202 | |
203 | Normally, the scheduler operates on individual tasks and strives to provide | |
204 | fair CPU time to each task. Sometimes, it may be desirable to group tasks and | |
205 | provide fair CPU time to each such task group. For example, it may be | |
206 | desirable to first provide fair CPU time to each user on the system and then to | |
207 | each task belonging to a user. | |
208 | ||
25c2d55c | 209 | CONFIG_CGROUP_SCHED strives to achieve exactly that. It lets tasks to be |
f58e2c33 CS |
210 | grouped and divides CPU time fairly among such groups. |
211 | ||
212 | CONFIG_RT_GROUP_SCHED permits to group real-time (i.e., SCHED_FIFO and | |
213 | SCHED_RR) tasks. | |
214 | ||
215 | CONFIG_FAIR_GROUP_SCHED permits to group CFS (i.e., SCHED_NORMAL and | |
216 | SCHED_BATCH) tasks. | |
217 | ||
25c2d55c | 218 | These options need CONFIG_CGROUPS to be defined, and let the administrator |
f58e2c33 | 219 | create arbitrary groups of tasks, using the "cgroup" pseudo filesystem. See |
45ce80fb | 220 | Documentation/cgroups/cgroups.txt for more information about this filesystem. |
f58e2c33 | 221 | |
25c2d55c | 222 | When CONFIG_FAIR_GROUP_SCHED is defined, a "cpu.shares" file is created for each |
f58e2c33 CS |
223 | group created using the pseudo filesystem. See example steps below to create |
224 | task groups and modify their CPU share using the "cgroups" pseudo filesystem. | |
5cb350ba | 225 | |
f6e07d38 JS |
226 | # mount -t tmpfs cgroup_root /sys/fs/cgroup |
227 | # mkdir /sys/fs/cgroup/cpu | |
228 | # mount -t cgroup -ocpu none /sys/fs/cgroup/cpu | |
229 | # cd /sys/fs/cgroup/cpu | |
5cb350ba DG |
230 | |
231 | # mkdir multimedia # create "multimedia" group of tasks | |
232 | # mkdir browser # create "browser" group of tasks | |
233 | ||
234 | # #Configure the multimedia group to receive twice the CPU bandwidth | |
235 | # #that of browser group | |
236 | ||
237 | # echo 2048 > multimedia/cpu.shares | |
238 | # echo 1024 > browser/cpu.shares | |
239 | ||
240 | # firefox & # Launch firefox and move it to "browser" group | |
241 | # echo <firefox_pid> > browser/tasks | |
242 | ||
243 | # #Launch gmplayer (or your favourite movie player) | |
244 | # echo <movie_player_pid> > multimedia/tasks |