Documentation/scheduler/sched-design-CFS.rst

15 an "ideal, precise multi-tasking CPU" on real hardware.
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
20 each at 50% physical power --- i.e., actually in parallel.
22 On real hardware, we can run only a single task at once, so we have to
25 multi-tasking CPU described above.  In practice, the virtual runtime of a task
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.
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.  ]
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
44 up CPU time between runnable tasks as close to "ideal multitasking hardware" as
48 with a few add-on embellishments like nice levels, multiprocessing and various
57 runqueues, but it uses a time-ordered rbtree to build a "timeline" of future
61 CFS also maintains the rq->cfs.min_vruntime value, which is a monotonic
68 rq->cfs.load value, which is the sum of the weights of the tasks queued on the
71 CFS maintains a time-ordered rbtree, where all runnable tasks are sorted by the
72 p->se.vruntime key. CFS picks the "leftmost" task from this tree and sticks to it.
74 more and more to the right --- slowly but surely giving a chance for every task
76 amount of time.
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
84 do not over-schedule tasks and trash the cache), then the new leftmost task is
105 chew.c, ring-test.c, massive_intr.c all work fine and do not impact
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
124   - SCHED_NORMAL (traditionally called SCHED_OTHER): The scheduling
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
132   - SCHED_IDLE: This is even weaker than nice 19, but its not a true
139 The command chrt from util-linux-ng 2.13.1.1 can set all of these except
165  - enqueue_task(...)
168    It puts the scheduling entity (task) into the red-black tree and
171  - dequeue_task(...)
174    corresponding scheduling entity out of the red-black tree.  It decrements
177  - yield_task(...)
181    entity at the right-most end of the red-black tree.
183  - check_preempt_curr(...)
188  - pick_next_task(...)
190    This function chooses the most appropriate task eligible to run next.
192  - set_curr_task(...)
197  - task_tick(...)
199    This function is mostly called from time tick functions; it might lead to
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
215 grouped and divides CPU time fairly among such groups.
217 CONFIG_RT_GROUP_SCHED permits to group real-time (i.e., SCHED_FIFO and
225    Documentation/admin-guide/cgroup-v1/cgroups.rst for more information about this filesystem.
231 	# mount -t tmpfs cgroup_root /sys/fs/cgroup
233 	# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu