scheduler: Add scheduler overview
Subsystems (3)
v7 cover scheduler: Add scheduler overview
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 7:
-Fix overview description
-Removed rst headers
-Removed kernel-doc for struct rq and meged it as struct
member comments
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 | 59 ++++ Documentation/scheduler/context-switching.rst | 126 ++++++++ Documentation/scheduler/index.rst | 33 +- .../scheduler/mips-context-switch.rst | 89 ++++++ Documentation/scheduler/overview.rst | 290 ++++++++++++++++++ Documentation/scheduler/sched-cas.rst | 92 ++++++ .../scheduler/sched-data-structs.rst | 176 +++++++++++ Documentation/scheduler/sched-debugging.rst | 14 + Documentation/scheduler/sched-features.rst | 21 ++ Documentation/scheduler/scheduler-api.rst | 25 ++ .../scheduler/x86-context-switch.rst | 64 ++++ kernel/sched/core.c | 21 +- kernel/sched/sched.h | 61 ++++ 14 files changed, 1068 insertions(+), 17 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 v7 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 v7 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 | 59 ++++ Documentation/scheduler/index.rst | 2 + Documentation/scheduler/overview.rst | 285 ++++++++++++++++++ Documentation/scheduler/sched-cas.rst | 92 ++++++ .../scheduler/sched-data-structs.rst | 176 +++++++++++ Documentation/scheduler/sched-features.rst | 1 + Documentation/scheduler/scheduler-api.rst | 25 ++ kernel/sched/core.c | 21 +- kernel/sched/sched.h | 61 ++++ 9 files changed, 718 insertions(+), 4 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 +59 -0
@@ -0,0 +1,59 @@ +.. 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 + +Tracking available capacity +--------------------------- +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. + +NUMA balancing +-------------- +Attempt to migrate tasks to the NUMA Node where the frequently accessed memory +pages belongs. The scheduler gets information about memory placement through the +paging mechanism. Scheduler periodically scans the virtual memory of the tasks +and make them inaccessible by changing the memory protection. The flag +MM_CP_PROT_NUMA indicates this purpose. When the task attempts to access +the memory again a page fault occurs. Scheduler traps the fault and increments +the counters in a task specific array corresponding to the NUMA node id. +There array is divided in to four regions: faults_memory, faults_cpu, +faults_memory_buffer and faults_cpu_buffer, where faults_memory is the +exponential decaying average of faults on a per-node basis. The 'preferred +node' is found by looping through the array and finding the node with the +highest number of faults. Migration to the preferred node is done periodically +by either swapping two tasks tasks between their respective CPUs or +just moving a task to its preferred node CPU. It the migration or move fails +it will be retried. + +Energy Aware Scheduling +----------------------- +For asymmetric CPU capacity topologies, an Energy Model is used to figure out +which of the CPU candidates is the most energy-efficient. Capacity is the +amount of work which a CPU can perform at its highest frequency which is +calculated by the Per-Entity Load Tracking (PELT) mechanism. +EAS is described at :doc:`sched-energy` + +Capacity Aware Scheduling +-------------------------- +Migrate a task to a CPU which meets its compute demand. In asymmetric CPU +capacity topologies CFS scheduler frequently updates the 'Misfit' status of +tasks and migrate them to CPU's of higher capacity. Also during wakeups the +a CPU with sufficient capacity is found for executing the task. CAS is +described at :doc:`sched-cas` + + + + + +
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 +285 -0
288 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 +176 -0
176 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 +25 -0
@@ -0,0 +1,25 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +============================= +Scheduler related functions +============================= + + +.. 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/sched/core.c +17 -4
@@ -3639,9 +3639,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 ) {
@@ -4032,8 +4036,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: *
@@ -4162,6 +4168,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(): */
@@ -4393,7 +4405,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
kernel/sched/sched.h +61 -0
140 lines not on this page · raw message
Signature · 1 line
2.17.1
RFC PATCH v7 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 | 126 ++++++++++++++++++ Documentation/scheduler/index.rst | 1 + .../scheduler/mips-context-switch.rst | 89 +++++++++++++ .../scheduler/x86-context-switch.rst | 64 +++++++++ 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 +126 -0
126 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 +64 -0
64 lines not on this page · raw message
Signature · 1 line
2.17.1