Add scheduler overview documentation
Subsystems (3)
v6 cover Add scheduler overview documentation
This patch series updates the scheduler documentation to add more topics wrt to scheduler overview. New sections are added to provide a brief overview of the kernel structs used by the scheduler, scheduler invocation, context switch and Capacity Aware Scheduling. Previous version of the patch was reviewed at:
https://lore.kernel.org/lkml/[email protected]/
version 6:
-Fix typos.
version 5:
-Fix description error on CAS
version 4:
-Added section on Capacity-Aware Scheduling -Reworded CFS recently added features. -Removed vruntime description from scheduler structs -Added description of idle and stopper sched classses
version 3:
-Fix spelling, spacing and typo errors.
version 2:
- Remove :c:func: directive as it was redundant
- Limit document width (line symbol count) to 75
- Replace dot file with ASCII art
- Describe prepare_task_switch(), ASID use, kernel/user transtion, MIPS FPU affinity correctly
- Add missing references to files
- Removed internal APIs from scheduler API reference
- Described rq struct member as kernel-doc comments
- Replaced CFS history with CFS current status
- Added documentation for sched_class fields
- Refined explanation of context swtich functionality
- Replace CFS history with recent changes
- Added kernel-doc comments for struct rq
John Mathew (3):
docs: scheduler: Restructure scheduler documentation.
docs: scheduler: Add scheduler overview documentation
docs: scheduler: Add introduction to scheduler context-switch
Documentation/scheduler/arch-specific.rst | 14 + Documentation/scheduler/cfs-overview.rst | 102 ++++++ Documentation/scheduler/context-switching.rst | 125 ++++++++ Documentation/scheduler/index.rst | 33 +- .../scheduler/mips-context-switch.rst | 89 ++++++ Documentation/scheduler/overview.rst | 293 ++++++++++++++++++ Documentation/scheduler/sched-cas.rst | 92 ++++++ .../scheduler/sched-data-structs.rst | 182 +++++++++++ Documentation/scheduler/sched-debugging.rst | 14 + Documentation/scheduler/sched-features.rst | 21 ++ Documentation/scheduler/scheduler-api.rst | 31 ++ .../scheduler/x86-context-switch.rst | 65 ++++ kernel/sched/core.c | 28 +- kernel/sched/sched.h | 169 +++++++++- 14 files changed, 1238 insertions(+), 20 deletions(-) create mode 100644 Documentation/scheduler/arch-specific.rst create mode 100644 Documentation/scheduler/cfs-overview.rst create mode 100644 Documentation/scheduler/context-switching.rst create mode 100644 Documentation/scheduler/mips-context-switch.rst create mode 100644 Documentation/scheduler/overview.rst create mode 100644 Documentation/scheduler/sched-cas.rst create mode 100644 Documentation/scheduler/sched-data-structs.rst create mode 100644 Documentation/scheduler/sched-debugging.rst create mode 100644 Documentation/scheduler/sched-features.rst create mode 100644 Documentation/scheduler/scheduler-api.rst create mode 100644 Documentation/scheduler/x86-context-switch.rst
Signature · 1 line
2.17.1
RFC PATCH v6 1/3 docs: scheduler: Restructure scheduler documentation.
From: John Mathew <[email protected]>
Add new sections to enable addition of new documentation on the scheduler. Existing documentation is moved under the related new sections. The sections are
- overview
- sched-features
- arch-specific.rst
- sched-debugging.rst
--- Documentation/scheduler/arch-specific.rst | 11 ++++++++ Documentation/scheduler/index.rst | 30 ++++++++++++--------- Documentation/scheduler/overview.rst | 5 ++++ Documentation/scheduler/sched-debugging.rst | 14 ++++++++++ Documentation/scheduler/sched-features.rst | 20 ++++++++++++++ 5 files changed, 67 insertions(+), 13 deletions(-) create mode 100644 Documentation/scheduler/arch-specific.rst create mode 100644 Documentation/scheduler/overview.rst create mode 100644 Documentation/scheduler/sched-debugging.rst create mode 100644 Documentation/scheduler/sched-features.rst
Documentation/scheduler/arch-specific.rst new file +11 -0
@@ -0,0 +1,11 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Architecture Specific Scheduler Implementation Differences +========================================================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2
Documentation/scheduler/index.rst +17 -13
@@ -1,23 +1,27 @@ +.. SPDX-License-Identifier: GPL-2.0+ + =============== Linux Scheduler =============== -.. toctree:: - :maxdepth: 1 +This documentation outlines the Linux kernel scheduler with its concepts, +details about the scheduler design and its data structures and architecture +specific implementation differences. - completion - sched-arch - sched-bwc - sched-deadline - sched-design-CFS - sched-domains - sched-energy - sched-nice-design - sched-rt-group - sched-stats +.. class:: toc-title + + Table of contents - text_files +.. toctree:: + :maxdepth: 2 + + overview + sched-design-CFS + sched-features + arch-specific + sched-debugging + scheduler-api .. only:: subproject and html
Documentation/scheduler/overview.rst new file +5 -0
@@ -0,0 +1,5 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +==================== +Scheduler overview +====================
Documentation/scheduler/sched-debugging.rst new file +14 -0
@@ -0,0 +1,14 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Scheduler Debugging Interface +============================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 + + sched-stats + text_files
Documentation/scheduler/sched-features.rst new file +20 -0
@@ -0,0 +1,20 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Scheduler Features +===================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 + + sched-arch + sched-bwc + sched-deadline + sched-domains + sched-energy + sched-nice-design + sched-rt-group + completion
Signature · 1 line
2.17.1
RFC PATCH v6 2/3 docs: scheduler: Add scheduler overview documentation
In reply to john mathewFrom: John Mathew <[email protected]>
Add documentation for
-scheduler overview
-scheduler state transtion
-CFS overview
-scheduler data structs
Add rst for scheduler APIs and modify sched/core.c to add kernel-doc comments.
--- Documentation/scheduler/cfs-overview.rst | 102 +++++++ Documentation/scheduler/index.rst | 2 + Documentation/scheduler/overview.rst | 288 ++++++++++++++++++ Documentation/scheduler/sched-cas.rst | 92 ++++++ .../scheduler/sched-data-structs.rst | 182 +++++++++++ Documentation/scheduler/sched-features.rst | 1 + Documentation/scheduler/scheduler-api.rst | 31 ++ kernel/sched/core.c | 28 +- kernel/sched/sched.h | 169 +++++++++- 9 files changed, 888 insertions(+), 7 deletions(-) create mode 100644 Documentation/scheduler/cfs-overview.rst create mode 100644 Documentation/scheduler/sched-cas.rst create mode 100644 Documentation/scheduler/sched-data-structs.rst create mode 100644 Documentation/scheduler/scheduler-api.rst
Documentation/scheduler/cfs-overview.rst new file +102 -0
@@ -0,0 +1,102 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +============= +CFS Overview +============= + +Linux 2.6.23 introduced a modular scheduler core and a Completely Fair +Scheduler (CFS) implemented as a scheduling module. A brief overview of the +CFS design is provided in :doc:`sched-design-CFS` + +In addition there have been many improvements to the CFS, a few of which are + +**Thermal Pressure**: +Scale CPU capacity mechanism for CFS so it knows how much CPU capacity is left +for its use after higher priority sched classes (RT, DL), IRQs and +'Thermal Pressure' have reduced the 'original' CPU capacity. +Thermal pressure on a CPU means the maximum possible capacity is +unavailable due to thermal events. + +** Optimizations to NUMA balancing**: +When gathering NUMA statistics, information about whether a core is Idle +is also cached. In case of an imbalance, instead of doing a second scan of +the node runqueues, the idle core is used as the migration target. When +doing so multiple tasks can attempt to select an idle CPU but fail, because +a NUMA balance is active on that CPU. In this case an alternative idle CPU +scanned. Another optimization is to terminate the search for swap candidate +when a reasonable one is found instead of searching all the CPUs on the +target domain. + +**Asymmetric CPU capacity wakeup scan**: +Previous assumption that CPU capacities within an SD_SHARE_PKG_RESOURCES +domain (sd_llc) are homogeneous didn't hold for newer generations of big.LITTLE +systems (DynamIQ) which can accommodate CPUs of different compute capacity +within a single LLC domain. A new idle sibling helper function was added +which took CPU capacity into account. The policy is to pick the first idle +CPU which is big enough for the task (task_util * margin < cpu_capacity). +If no idle CPU is big enough, the idle CPU with the highest capacity is +picked. + +**Optimized idle core selection**: +Skipped looping through all the threads of a core to evaluate if the +core is idle or not. If a thread of a core is not idle, evaluation of +other threads of the core can be skipped. + +**Load balance aggressively for SCHED_IDLE CPUs**: +Newly-woken task is preferred to be enqueued on a SCHED_IDLE CPU instead +of other busy or idle CPUs. Also load balancer is made to migrate tasks more +aggressively to a SCHED_IDLE CPU. Fair scheduler now does the next +load balance soon after the last non-SCHED_IDLE task is dequeued from a +runqueue, i.e. making the CPU SCHED_IDLE. Also the the busy_factor +used with the balance interval to prevent frequent load balancing +is ignored for such CPU's. + +**Load balancing algorithm Reworked**: +Some heuristics in the load balancing algorithm became meaningless because +of the rework of the scheduler's metrics like the introduction of PELT. +Those heuristics were removed. The new load balancing algorithm also fixes +several pending wrong tasks placement + + * the 1 task per CPU case with asymmetric system + * the case of CFS task preempted by other class + * the case of tasks not evenly spread on groups with spare capacity + +Also the load balance decisions have been consolidated in the 3 separate +functions. +* update_sd_pick_busiest() select the busiest sched_group. +* find_busiest_group() checks if there is an imbalance between local and +busiest group. +* calculate_imbalance() decides what have to be moved. + +**Energy-aware wake-ups speeded up**: +Algorithmic complexity of the EAS was reduced from O(n^2) to O(n). +Previous algorithm resulted in prohibitively high wake-up latencies on +systems with complex energy models, such as systems with per-CPU DVFS. +The EAS wake-up path was re-factored to compute the energy 'delta' on a +per-performance domain basis, rather than the whole system. + +**Selection of an energy-efficient CPU on task wake-up**: +An Energy efficient CPU is found by estimating the impact on system-level +active energy resulting from the placement of the task on the CPU with the +highest spare capacity in each performance domain. Energy Model (EM) is +used for this. This strategy spreads tasks in a performance domain and avoids overly +aggressive task packing. The best CPU energy-wise is then selected if it +saves a large enough amount of energy with respect to prev_cpu. + +**Consider misfit tasks when load-balancing**: +A task which ends up on a CPU which doesn't suit its compute demand is +identified as a misfit task in asymmetric CPU capacity systems. These +'misfit' tasks are migrated to CPUs with higher compute capacity to ensure +better throughput. A new group_type: group_misfit_task is added and indicates this +scenario. Tweaks to the load-balance code are done to make the migrations +happen. Misfit balancing is done between a source group of lower per-CPU +capacity and destination group of higher compute capacity. Otherwise, misfit +balancing is ignored. + + +**Make schedstats a runtime tunable that is disabled by default**: +A kernel command-line and sysctl tunable was added to enable or disable +schedstats on demand (when it's built in). It is disabled by default. +The benefits are dependent on how scheduler-intensive the workload is. + +
Documentation/scheduler/index.rst +2 -0
@@ -17,6 +17,8 @@ specific implementation differences. :maxdepth: 2 overview + sched-data-structs + cfs-overview sched-design-CFS sched-features arch-specific
Documentation/scheduler/overview.rst +288 -0
291 lines not on this page · raw message
Documentation/scheduler/sched-cas.rst new file +92 -0
92 lines not on this page · raw message
Documentation/scheduler/sched-data-structs.rst new file +182 -0
182 lines not on this page · raw message
Documentation/scheduler/sched-features.rst +1 -0
@@ -17,4 +17,5 @@ Scheduler Features sched-energy sched-nice-design sched-rt-group + sched-cas completion
Documentation/scheduler/scheduler-api.rst new file +31 -0
@@ -0,0 +1,31 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +============================= +Scheduler related functions +============================= + + +.. kernel-doc:: kernel/sched/core.c + :functions: __schedule + +.. kernel-doc:: kernel/sched/core.c + :functions: scheduler_tick + +.. kernel-doc:: kernel/sched/core.c + :functions: try_to_wake_up + +.. kernel-doc:: kernel/sched/core.c + :functions: do_task_dead + +.. kernel-doc:: kernel/sched/core.c + :functions: preempt_schedule_irq + +.. kernel-doc:: kernel/sched/core.c + :functions: prepare_task_switch + +.. kernel-doc:: kernel/sched/core.c + :functions: finish_task_switch + +.. kernel-doc:: kernel/sched/sched.h + :functions: rq +
kernel/sched/core.c +24 -4
@@ -3576,9 +3576,13 @@ void arch_set_thermal_pressure(struct cpumask *cpus,WRITE_ONCE (per_cpu (thermal_pressure, cpu), th_pressure); } -/* +/** +* scheduler_tick - sched tick timer handler +* * This function gets called by the timer code, with HZ frequency. * We call it with interrupts disabled. +* +* Return: 0. */ void scheduler_tick (void ) {
@@ -3959,8 +3963,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)BUG (); } -/* -* __schedule() is the main scheduler function. +/** +* __schedule() - the main scheduler function. +* +* @preempt: preemption enabled/disabled * * The main means of driving the scheduler and thus entering this function are: *
@@ -4089,6 +4095,12 @@ static void __sched notrace __schedule(bool preempt)balance_callback (rq); } +/** +* do_task_dead - handle task exit +* +* Changes the the task state to TASK_DEAD and calls +* schedule to pick next task to run. +*/ void __noreturn do_task_dead (void ) {/* Causes final put_task_struct in finish_task_switch(): */
@@ -4320,7 +4332,8 @@ EXPORT_SYMBOL_GPL(preempt_schedule_notrace);#endif /* CONFIG_PREEMPTION */ -/* +/** +* preempt_schedule_irq - schedule from irq context * This is the entry point to schedule() from kernel preemption * off of irq context. * Note, that this is called and return with irqs disabled. This will
@@ -5618,6 +5631,13 @@ SYSCALL_DEFINE0(sched_yield) }#ifndef CONFIG_PREEMPTION +/** +* _cond_resched - explicit rescheduling +* +* gives the scheduler a chance to run a higher-priority process +* +* Return: 1 if reschedule was done, 0 if reschedule not done. +*/ int __sched _cond_resched(void) {if (should_resched (0 )) {
kernel/sched/sched.h +166 -3
185 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH v6 3/3 docs: scheduler: Add introduction to scheduler context-switch
In reply to john mathewFrom: John Mathew <[email protected]>
Add documentation for introduction to
-context-switch
-x86 context-switch
-MIPS context switch
--- Documentation/scheduler/arch-specific.rst | 3 + Documentation/scheduler/context-switching.rst | 125 ++++++++++++++++++ Documentation/scheduler/index.rst | 1 + .../scheduler/mips-context-switch.rst | 89 +++++++++++++ .../scheduler/x86-context-switch.rst | 65 +++++++++ 5 files changed, 283 insertions(+) create mode 100644 Documentation/scheduler/context-switching.rst create mode 100644 Documentation/scheduler/mips-context-switch.rst create mode 100644 Documentation/scheduler/x86-context-switch.rst
Documentation/scheduler/arch-specific.rst +3 -0
@@ -9,3 +9,6 @@ Architecture Specific Scheduler Implementation Differences .. toctree:: :maxdepth: 2 + + x86-context-switch + mips-context-switch
Documentation/scheduler/context-switching.rst new file +125 -0
125 lines not on this page · raw message
Documentation/scheduler/index.rst +1 -0
@@ -20,6 +20,7 @@ specific implementation differences. sched-data-structs cfs-overview sched-design-CFS + context-switching sched-features arch-specific sched-debugging
Documentation/scheduler/mips-context-switch.rst new file +89 -0
89 lines not on this page · raw message
Documentation/scheduler/x86-context-switch.rst new file +65 -0
65 lines not on this page · raw message
Signature · 1 line
2.17.1