Add scheduler overview documentation
Subsystems (3)
v8 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, and context switch. Previous version of the patch was reviewed at:
https://lore.kernel.org/lkml/[email protected]/
version 8:
- Rebase
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 | 34 +- .../scheduler/mips-context-switch.rst | 89 ++++++ Documentation/scheduler/overview.rst | 297 ++++++++++++++++++ .../scheduler/sched-data-structs.rst | 176 +++++++++++ Documentation/scheduler/sched-debugging.rst | 14 + Documentation/scheduler/sched-features.rst | 25 ++ Documentation/scheduler/scheduler-api.rst | 24 ++ .../scheduler/x86-context-switch.rst | 55 ++++ kernel/sched/core.c | 21 +- kernel/sched/sched.h | 63 +++- 13 files changed, 978 insertions(+), 19 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-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 v8 1/3 docs: scheduler: Restructure scheduler documentation.
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 | 12 +++++++++ Documentation/scheduler/index.rst | 30 +++++++++++---------- Documentation/scheduler/overview.rst | 5 ++++ Documentation/scheduler/sched-debugging.rst | 14 ++++++++++ Documentation/scheduler/sched-features.rst | 25 +++++++++++++++++ 5 files changed, 72 insertions(+), 14 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 +12 -0
@@ -0,0 +1,12 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Architecture Specific Scheduler Implementation Differences +========================================================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 +
Documentation/scheduler/index.rst +16 -14
@@ -1,24 +1,26 @@ +.. 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. + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 - completion - sched-arch - sched-bwc - sched-deadline + overview sched-design-CFS - sched-domains - sched-capacity - sched-energy - sched-nice-design - sched-rt-group - sched-stats - - text_files + sched-features + arch-specific + sched-debugging .. 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 +25 -0
@@ -0,0 +1,25 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Scheduler Features +=================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 1 + + completion + sched-arch + sched-bwc + sched-deadline + sched-domains + sched-capacity + sched-energy + sched-nice-design + sched-rt-group + sched-stats + + text_files +
Signature · 1 line
2.17.1
Re: [RFC PATCH v8 1/3] docs: scheduler: Restructure scheduler documentation.
Quoted 28 lines · John Mathew
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.rstSuggested-by Lukas Bulwahn <[email protected]>Signed-off-by John Mathew <[email protected]>--- Documentation/scheduler/arch-specific.rst | 12 +++++++++ Documentation/scheduler/index.rst | 30 +++++++++++---------- Documentation/scheduler/overview.rst | 5 ++++ Documentation/scheduler/sched-debugging.rst | 14 ++++++++++ Documentation/scheduler/sched-features.rst | 25 +++++++++++++++++ 5 files changed, 72 insertions(+), 14 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.rstDocumentation/scheduler/arch-specific.rst new file +0
-0
Documentation/scheduler/arch-specific.rst line 4
Quoted 4 lines
Documentation/scheduler/arch-specific.rst new file +4
-0@@ -0,0 +1,12 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Architecture Specific Scheduler Implementation Differences +==========================================================
That is a terribly long title, how about Architecture Specifics?
I am wondering if this should be on the toplevel documentation structure directly under Linux Scheduler.
I think the x86 and MIPS context switch documentation could be placed under Process context switching in a section Architecture Specifics.
Quoted 59 lines
Documentation/scheduler/arch-specific.rst new file +8
-0+ +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 +Documentation/scheduler/index.rst +16
-14@@ -1,24 +1,26 @@ +.. 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. + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 2 - completion - sched-arch - sched-bwc - sched-deadline + overview sched-design-CFS - sched-domains - sched-capacity - sched-energy - sched-nice-design - sched-rt-group - sched-stats - - text_files + sched-features + arch-specific + sched-debugging .. only:: subproject and htmlDocumentation/scheduler/overview.rst new file +0
-0
Documentation/scheduler/overview.rst line 4
Quoted 4 lines
Documentation/scheduler/overview.rst new file +4
-0@@ -0,0 +1,5 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +==================== +Scheduler overview
s/Scheduler overview/Scheduler Overview/
for some more consistent capitalisation.
Documentation/scheduler/overview.rst line 5
Quoted 2 lines
Documentation/scheduler/overview.rst new file +1
-0+====================
That could be the cause for the git am errors.
Quoted 40 lines
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_filesDocumentation/scheduler/sched-features.rst new file +14
-0@@ -0,0 +1,25 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Scheduler Features +=================== + +.. class:: toc-title + + Table of contents + +.. toctree:: + :maxdepth: 1 + + completion + sched-arch
Documentation/scheduler/sched-features.rst line 24
Quoted 10 lines
Documentation/scheduler/sched-features.rst new file +10
-0+ sched-bwc + sched-deadline + sched-domains + sched-capacity + sched-energy + sched-nice-design + sched-rt-group + sched-stats + + text_files
I guess it is fine to place everything here for now, but more clean-up would probably move those to the appropriate documentation structure, right?
Quoted 5 lines
Documentation/scheduler/sched-features.rst new file +1
-0+Signature · 1 line
2.17.1
RFC PATCH v8 2/3 docs: scheduler: Add scheduler overview documentation
In reply to John MathewAdd 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 | 3 + Documentation/scheduler/overview.rst | 294 +++++++++++++++++- .../scheduler/sched-data-structs.rst | 176 +++++++++++ Documentation/scheduler/scheduler-api.rst | 24 ++ kernel/sched/core.c | 21 +- kernel/sched/sched.h | 63 +++- 7 files changed, 634 insertions(+), 6 deletions(-) create mode 100644 Documentation/scheduler/cfs-overview.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-capacity` + + + + + +
Documentation/scheduler/index.rst +3 -0
@@ -17,10 +17,13 @@ specific implementation differences. :maxdepth: 2 overview + sched-data-structs + cfs-overview sched-design-CFS sched-features arch-specific sched-debugging + scheduler-api .. only:: subproject and html
Documentation/scheduler/overview.rst +293 -1
298 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/scheduler-api.rst new file +24 -0
@@ -0,0 +1,24 @@ +.. 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
@@ -3976,9 +3976,13 @@ unsigned long long task_sched_runtime(struct task_struct *p)return ns; } -/* +/** +* 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 ) {
@@ -4367,8 +4371,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: *
@@ -4533,6 +4539,12 @@ static void __sched notrace __schedule(bool preempt)balance_callback (rq); } +/** +* do_task_dead - handle task exit +* +* Changes 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(): */
@@ -4764,7 +4776,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 +62 -1
142 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [RFC PATCH v8 2/3] docs: scheduler: Add scheduler overview documentation
Quoted 35 lines · John Mathew
Add documentation for
-scheduler overview
-scheduler state transtion
-CFS overview
-scheduler data structsAdd rst for scheduler APIs and modify
sched/core.cto add kernel-doc comments.Suggested-by Lukas Bulwahn <[email protected]>Co-developed-by Mostafa Chamanara <[email protected]>Signed-off-by Mostafa Chamanara <[email protected]>Co-developed-by Oleg Tsymbal <[email protected]>Signed-off-by Oleg Tsymbal <[email protected]>Signed-off-by John Mathew <[email protected]>--- Documentation/scheduler/cfs-overview.rst | 59 ++++ Documentation/scheduler/index.rst | 3 + Documentation/scheduler/overview.rst | 294 +++++++++++++++++- .../scheduler/sched-data-structs.rst | 176 +++++++++++ Documentation/scheduler/scheduler-api.rst | 24 ++ kernel/sched/core.c | 21 +- kernel/sched/sched.h | 63 +++- 7 files changed, 634 insertions(+), 6 deletions(-) create mode 100644 Documentation/scheduler/cfs-overview.rst create mode 100644 Documentation/scheduler/sched-data-structs.rst create mode 100644 Documentation/scheduler/scheduler-api.rstDocumentation/scheduler/cfs-overview.rst new file +1
-0@@ -0,0 +1,59 @@ +.. SPDX-License-Identifier: GPL-2.0+
Documentation/scheduler/cfs-overview.rst line 11
Quoted 10 lines
Documentation/scheduler/cfs-overview.rst new file +10
-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
This can be shortened to:
In addition there have been many improvements to the CFS:
Documentation/scheduler/cfs-overview.rst line 14
Quoted 3 lines
Documentation/scheduler/cfs-overview.rst new file +3
-0+ +Tracking available capacity +---------------------------
Capitalize title for local consistency with the sections below.
This below is not a full sentence:
Documentation/scheduler/cfs-overview.rst line 15
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+Scale CPU capacity mechanism for CFS so it knows how much CPU capacity is left
The "it" here refers to what?
Documentation/scheduler/cfs-overview.rst line 17
Quoted 2 lines
Documentation/scheduler/cfs-overview.rst new file +2
-0+for its use after higher priority sched classes (RT, DL), IRQs and +'Thermal Pressure' have reduced the 'original' CPU capacity.
Why are putting thermal pressure and orginal in quotes?
Documentation/scheduler/cfs-overview.rst line 22
Quoted 5 lines
Documentation/scheduler/cfs-overview.rst new file +5
-0+Thermal pressure on a CPU means the maximum possible capacity is +unavailable due to thermal events. + +NUMA balancing +--------------
Capitalize.
Again, this below is not a full sentence:
Documentation/scheduler/cfs-overview.rst line 23
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+Attempt to migrate tasks to the NUMA Node where the frequently accessed memory
why is Node capitalized here?
Documentation/scheduler/cfs-overview.rst line 24
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+pages belongs. The scheduler gets information about memory placement through the
belongs? You mean is closest placed to, right?
s/through the paging mechanism/through paging/
Documentation/scheduler/cfs-overview.rst line 25
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+paging mechanism. Scheduler periodically scans the virtual memory of the tasks
Maybe add: This works as follows:
1. The scheduler scans ...
s/Scheduler/The scheduler/
Documentation/scheduler/cfs-overview.rst line 26
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+and make them inaccessible by changing the memory protection. The flag
s/make/makes/
Documentation/scheduler/cfs-overview.rst line 27
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+MM_CP_PROT_NUMA indicates this purpose. When the task attempts to access
I think the detail on the flag is too much here for the overview.
2. When the task attempts to access the memory, this triggers a page fault and the scheduler reacts with recording some statistics on the use for the specific NUMA nodes.
3. On a periodic basis, the scheduler then migrates the task to the preffered node, i.e., the node that encountered the most memory faults.
Quoted 13 lines
Documentation/scheduler/cfs-overview.rst new file +13
-0+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 +-----------------------
Documentation/scheduler/cfs-overview.rst line 50
Quoted 10 lines
Documentation/scheduler/cfs-overview.rst new file +10
-0+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
s/CFS scheduler/, the CFS scheduler/
Documentation/scheduler/cfs-overview.rst line 51
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+tasks and migrate them to CPU's of higher capacity. Also during wakeups the
the a?
Documentation/scheduler/cfs-overview.rst line 52
Quoted 1 line
Documentation/scheduler/cfs-overview.rst new file +1
-0+a CPU with sufficient capacity is found for executing the task. CAS is
I guess it is better to use active here, rather than passive. Who finds the CPU?
Do not use an abbreviation here.
Quoted 30 lines
Documentation/scheduler/cfs-overview.rst new file +7
-0+described at :doc:`sched-capacity` + + + + + +Documentation/scheduler/index.rst +3
-0@@ -17,10 +17,13 @@ specific implementation differences. :maxdepth: 2 overview + sched-data-structs + cfs-overview sched-design-CFS sched-features arch-specific sched-debugging + scheduler-api .. only:: subproject and htmlDocumentation/scheduler/overview.rst +0
-0
Documentation/scheduler/overview.rst line 7
Quoted 8 lines
Documentation/scheduler/overview.rst +3
-1@@ -2,4 +2,296 @@ ==================== Scheduler overview -==================== +==================== + +Linux kernel implements priority-based scheduling. More than one process are
s/Linux kernel/The Linux kernel/
Documentation/scheduler/overview.rst line 12
Quoted 5 lines
Documentation/scheduler/overview.rst +5
-0+allowed to run at any given time and each process is allowed to run as if it +were the only process on the system. The process scheduler coordinates which +process runs when. In that context, it has the following tasks: + + - share CPUs equally among all currently running processes.
equally? That is not true, right?
Documentation/scheduler/overview.rst line 20
Quoted 8 lines
Documentation/scheduler/overview.rst +8
-0+ - pick appropriate process to run next if required, considering scheduling + class/policy and process priorities. + - balance processes between multiple CPUs in SMP systems. + +The scheduler attempts to be responsive for I/O bound processes and efficient +for CPU bound processes. The scheduler uses different scheduling policies +for real time and normal processes based on their respective policy +enumerations. Scheduler adds support for each policy through scheduling class
... for each policy through a scheduling class and a dedicated implementation for each scheduling class.
Documentation/scheduler/overview.rst line 22
Quoted 2 lines
Documentation/scheduler/overview.rst +2
-0+implementations for each. The five scheduling classes which scheduler provides +are:
This can be shortened to "The five scheduling classes are:"
Documentation/scheduler/overview.rst line 34
Quoted 12 lines
Documentation/scheduler/overview.rst +12
-0+ + - stop_sched_class: + It is a per-cpu maximum priority CPU monopolization mechanism. It is + exposed as a SCHED_FIFO task ('migration/X') with static priority of 99 + in the user space. This is done to make it compatible with user space and + thus to avoid growing the ABI. It is used by one CPU to stop another + in order to run a specific function, so it is only available on SMP + systems. This class is used by the scheduler for task migration between + CPUs. + + - dl_sched_class: + Implements the SCHED_DEADLINE scheduling policy. It has static priority
Here, you use "scheduling policy".
Documentation/scheduler/overview.rst line 39
Quoted 5 lines
Documentation/scheduler/overview.rst +5
-0+ of -1 in kernel space. This policy schedules each task according to the + task's deadline. The task with the earliest deadline will be served first. + + - rt_sched_class: + Implements the SCHED_RR and SCHED_FIFO policies. Real time static
... and here only "policy". Be consistent.
Documentation/scheduler/overview.rst line 49
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ priorities range from 1(low)..99 in the user space. (priority is inverted + in kernel space). It is the only scheduling class that makes use of the + static priority of the task. SCHED_FIFO is a simple scheduling algorithm + without time slicing. A SCHED_FIFO thread runs until either it is blocked + by an I/O request, it is preempted by a higher priority thread, or it + calls sched_yield(). SCHED_RR is a simple enhancement of SCHED_FIFO where + a thread is allowed to run only for a maximum time quantum. + + - fair_sched_class: + Implements the SCHED_NORMAL SCHED_BATCH and SCHED_IDLE policies. Static
double spacing before policies.
Documentation/scheduler/overview.rst line 52
Quoted 3 lines
Documentation/scheduler/overview.rst +3
-0+ priority is always 0 in the user space. A dynamic priority based on + 'nice' value is used to schedule these tasks. This priority increases each + time the the task is scheduled to run but denied to run by scheduler.
... the the... and then spacing.
Quoted 5 lines
Documentation/scheduler/overview.rst +5
-0+ This ensures fair scheduling between these tasks. Nice value is an + attribute which can be set by the user to influence scheduler to favour + a particular task. SCHED_BATCH is similar to SCHED_NORMAL with the + difference that the policy causes the scheduler to assume that the task + is CPU-intensive. SCHED_IDLE policy also has static priority 0. Nice
Documentation/scheduler/overview.rst line 67
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ value has no effect on this policy. Weight mapping is not done, instead + weight is set at a constant minimal weight WEIGHT_IDLEPRIO. Used to + run tasks at extremely low priority. + + - idle_sched_class: + Priority for idle task is irrelevant. This class is not related to + SCHED_IDLE policy. Idle tasks run when there are no other runnable tasks + on a CPU. The execute the idle loop which is responsible to put a CPU + in one of its idle states. +
This last sentence above is totally broken; I cannot parse it.
Documentation/scheduler/overview.rst line 73
Quoted 6 lines
Documentation/scheduler/overview.rst +6
-0+ +Process Management +================== + +Each process in the system is represented by struct task_struct. When a +process/thread is created, the kernel allocates a new task_struct for it.
Each process or each thread?
Documentation/scheduler/overview.rst line 77
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+The kernel then stores this task_struct in an RCU list. Macro next_task() +allows a process to obtain its next task and for_each_process() macro enables +traversal of the list. +
This is too much detail at this point of the overview.
Quoted 53 lines
Documentation/scheduler/overview.rst +53
-0+Frequently used fields of the task struct are: + + - state: The running state of the task. The possible states are: + + - TASK_RUNNING: The task is currently running or in a run queue waiting + to run. + - TASK_INTERRUPTIBLE: The task is sleeping waiting for some event to occur. + This task can be interrupted by signals. On waking up the task transitions + to TASK_RUNNING. + - TASK_UNINTERRUPTIBLE: Similar to TASK_INTERRUPTIBLE but does not wake + up on signals. Needs an explicit wake-up call to be woken up. Contributes + to loadavg. + - __TASK_TRACED: Task is being traced by another task like a debugger. + - __TASK_STOPPED: Task execution has stopped and not eligible to run. + SIGSTOP, SIGTSTP etc causes this state. The task can be continued by + the signal SIGCONT. + - TASK_PARKED: State to support kthread parking/unparking. + - TASK_DEAD: If a task dies, then it sets TASK_DEAD in tsk->state and calls + schedule one last time. The task will be never ran again. + - TASK_WAKEKILL: It works like TASK_UNINTERRUPTIBLE with the bonus that it + can respond to fatal signals. + - TASK_WAKING: To handle concurrent waking of the same task for SMP. + Indicates that someone is already waking the task. + - TASK_NOLOAD: To be used along with TASK_UNINTERRUPTIBLE to indicate + an idle task which does not contribute to loadavg. + - TASK_NEW: Set during fork(), to guarantee that no one will run the task, + a signal or any other wake event cannot wake it up and insert it on + the runqueue. + + - exit_state : The exiting state of the task. The possible states are: + + - EXIT_ZOMBIE: The task is terminated and waiting for parent to collect + the exit information of the task. + - EXIT_DEAD: After collecting the exit information the task is put to + this state and removed from the system. + + - static_prio: Used by the fair scheduling class to encode the nice level. + It does not have any effect on the SCHED_DEADLINE, SCHED_FIFO or SCHED_RR + policy tasks. + + - prio: The value of this field is used to: + + - distinguish scheduling classes. + - in the RR/FIFO static priority scheduler. + + - normal_prio: Expected priority of a task. The value of static_prio + and normal_prio are the same for non-real-time processes. For real time + processes value of prio is used. + + - rt_priority: Field used to set priority of real time tasks. Not used by the + rt_sched_class. + + - sched_class: Pointer to sched_class structure of the policy that the task
Documentation/scheduler/overview.rst line 140
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ belongs to. + + - sched_entity: Pointer to sched_entity CFS structure. + + - policy: scheduling policy of the task. See above. + + - nr_cpus_allowed: Hamming weight of the bitmask retrieved from cpumask pointer. + +New tasks are created using the fork() system call which is described +at manpage `FORK(2)` or the clone system call described at manpage `CLONE(2)`.
Is there a better way to refer to a manpage here? Maybe an URL?
Quoted 12 lines
Documentation/scheduler/overview.rst +12
-0+Users can create threads within a process to achieve parallelism. Threads +share address space, open files and other resources of the process. Threads +are created like normal tasks with their unique task_struct, but clone() +is provided with flags that enable the sharing of resources such as address +space :: + + clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0); + +The scheduler schedules task_structs so from scheduler perspective there is +no difference between threads and processes. Threads are created using +the system call pthread_create described at its manpage `PTHREAD_CREATE(3)` +POSIX threads creation is described at its manpage `PTHREADS(7)`
Documentation/scheduler/overview.rst line 162
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ +The Scheduler Entry Point +========================= + +The main scheduler entry point is an architecture independent schedule() +function defined in kernel/sched/core.c. Its objective is to find a process in +the runqueue list and then assign the CPU to it. It is invoked, directly +or in a lazy (deferred) way from many different places in the kernel. A lazy +invocation does not call the function by its name, but gives the kernel a +hint by setting a flag TIF_NEED_RESCHED. The flag is a message to the kernel
s/a flag/the flag/
Documentation/scheduler/overview.rst line 164
Quoted 2 lines
Documentation/scheduler/overview.rst +2
-0+that the scheduler should be invoked as soon as possible because another +process deserves to run. The flag should not be modified directly.
Well, then let us know how to do that correctly.
Documentation/scheduler/overview.rst line 168
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+ +Following are some places that notify the kernel to schedule which can be +classified based on the type of operations: +
I cannot follow the jump from the previous explanation to this list now. You lost me here.
Quoted 21 lines
Documentation/scheduler/overview.rst +21
-0+ - Blocking operations: Suspends the current task and directly call into + the scheduler to find something else to do. Some blocking operations are: + + - mutex_lock() + - wait_event() + - do_exit() + - preempt_schedule_irq() + + - Co-operative or voluntary preemptions: Allows another task to run at that + point subject to preemption model. Voluntary preemption model can be + set through the kernel config option: CONFIG_PREEMPT_VOLUNTARY. The + operations are: + + - cond_resched() + - cond_resched_lock() + - yield() + - preempt_enable() + + - Involuntary preemption: Marks TIF_NEED_RESCHED and wait for action + depending on preemption model. Involuntary preemption operations are: +
Documentation/scheduler/overview.rst line 199
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ - scheduler_tick() + - wake_up_process() + +Calling functions mentioned above leads to a call to __schedule(). Note +that preemption must be disabled before it is called and enabled after +the call using preempt_disable and preempt_enable functions family. + + +The steps during invocation are: +--------------------------------
I would not put the "half" sentence as subsection.
Documentation/scheduler/overview.rst line 203
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+1. Disable preemption to avoid another task preempting the scheduling + thread itself. +2. Retrieve the runqueue of current processor and its lock is obtained to + allow only one thread to modify the runqueue at a time.
Okay, 1. and 2. are written in imperative.
Documentation/scheduler/overview.rst line 208
Quoted 5 lines
Documentation/scheduler/overview.rst +5
-0+3. The state of the previously executed task when the schedule() + was called is examined. If it is not runnable and has not been + preempted in kernel mode, it is removed from the runqueue. If the + previous task has non-blocked pending signals, its state is set to + TASK_RUNNING and left in the runqueue.
Now, passive?
Documentation/scheduler/overview.rst line 212
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+4. Scheduler classes are iterated and the corresponding class hook to + pick the next suitable task to be scheduled on the CPU is called. + Since most tasks are handled by the sched_fair class, a shortcut to this + class is implemented in the beginning of the function.
Now passive.
Documentation/scheduler/overview.rst line 213
Quoted 1 line
Documentation/scheduler/overview.rst +1
-0+5. TIF_NEED_RESCHED and architecture specific need_resched flags are cleared.
Now passive, again.
Documentation/scheduler/overview.rst line 219
Quoted 6 lines
Documentation/scheduler/overview.rst +6
-0+6. If the scheduler class picks a different task from what was running + before, a context switch is performed by calling context_switch(). + Internally, context_switch() switches to the new task's memory map and + swaps the register state and stack. If scheduler class picked the same + task as the previous task, no task switch is performed and the current + task keeps running.
Passive.
Documentation/scheduler/overview.rst line 223
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+7. Balance callback list is processed. Each scheduling class can migrate tasks + between CPUs to balance load. These load balancing operations are queued + on a Balance callback list which get executed when balance_callback() is + called.
Passive.
Documentation/scheduler/overview.rst line 227
Quoted 4 lines
Documentation/scheduler/overview.rst +4
-0+8. The runqueue is unlocked and preemption is re-enabled. In case + preemption was requested during the time in which it was disabled, + schedule() is run again right away. +
Passive.
It should be consistent and I think writing it imperative is MUCH better, e.g., Process balance callback list, Unlock runqueue, etc.
Quoted 36 lines
Documentation/scheduler/overview.rst +36
-0+Scheduler State Transition +========================== + +A very high level scheduler state transition flow with a few states can +be depicted as follows. :: + + * + | + | task + | forks + v + +------------------------------+ + | TASK_NEW | + | (Ready to run) | + +------------------------------+ + | + | + v + +------------------------------------+ + | TASK_RUNNING | + +---------------> | (Ready to run) | <--+ + | +------------------------------------+ | + | | | + | | schedule() calls context_switch() | task is preempted + | v | + | +------------------------------------+ | + | | TASK_RUNNING | | + | | (Running) | ---+ + | event occurred +------------------------------------+ + | | + | | task needs to wait for event + | v + | +------------------------------------+ + | | TASK_INTERRUPTIBLE | + | | TASK_UNINTERRUPTIBLE | + +-----------------| TASK_WAKEKILL |
Documentation/scheduler/overview.rst line 273
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+ +------------------------------------+ + | + | task exits via do_exit() + v + +------------------------------+ + | TASK_DEAD | + | EXIT_ZOMBIE | + +------------------------------+ + +
I hope we can refine this high-level description to Daniel's model.
Documentation/scheduler/overview.rst line 278
Quoted 5 lines
Documentation/scheduler/overview.rst +5
-0+Scheduler provides trace events tracing all major events of the scheduler. +The trace events are defined in :: + + include/trace/events/sched.h +
John, can you explain the trace events that would occur for the transitions above in your high-level state transition?
Quoted 9 lines
Documentation/scheduler/overview.rst +9
-0+Using these trace events it is possible to model the scheduler state transition +in an automata model. The following journal paper discusses such modeling: + +Daniel B. de Oliveira, Rômulo S. de Oliveira, Tommaso Cucinotta, **A thread +synchronization model for the PREEMPT_RT Linux kernel**, *Journal of Systems +Architecture*, Volume 107, 2020, 101729, ISSN 1383-7621, +https://doi.org/10.1016/j.sysarc.2020.101729. + +To model the scheduler efficiently the system was divided in to generators
Documentation/scheduler/overview.rst line 297
Quoted 10 lines
Documentation/scheduler/overview.rst +10
-0+and specifications. Some of the generators used were "need_resched", +"sleepable" and "runnable", "thread_context" and "scheduling context". +The specifications are the necessary and sufficient conditions to call +the scheduler. New trace events were added to specify the generators +and specifications. In case a kernel event referred to more than one +event, extra fields of the kernel event was used to distinguish between +automation events. The final model was generated from parallel composition +of all generators and specifications which composed of 34 events, +12 generators and 33 specifications. This resulted in 9017 states, and +20103 transitions.
That is how far I got with my first review round.
It reads nicely so far; I think a bit of stylistic improvement is needed but you did not make me tired within few minutes (so it is readable) and I think I learned something about the scheduler :)
Thanks,
Lukas
RFC PATCH v8 3/3 docs: scheduler: Add introduction to scheduler context-switch
In reply to John MathewAdd documentation for introduction to
-context-switch
-x86 context-switch
-MIPS context switch
--- Documentation/scheduler/arch-specific.rst | 2 + Documentation/scheduler/context-switching.rst | 126 ++++++++++++++++++ Documentation/scheduler/index.rst | 1 + .../scheduler/mips-context-switch.rst | 89 +++++++++++++ .../scheduler/x86-context-switch.rst | 55 ++++++++ 5 files changed, 273 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 +2 -0
@@ -10,3 +10,5 @@ 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 +55 -0
55 lines not on this page · raw message
Signature · 1 line
2.17.1
Quoted 6 lines · John Mathew
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, and context switch. Previous version of the patch was reviewed at:
https://lore.kernel.org/lkml/[email protected]/
John, here is some first feedback to get the ball rolling:
I tried to apply your patches on v5.9-rc4, and I got those warnings:
Applying: docs: scheduler: Restructure scheduler documentation. .git/rebase-apply/patch:30: new blank line at EOF.
+
.git/rebase-apply/patch:137: new blank line at EOF.
+
warning: 2 lines add whitespace errors.
Applying: docs: scheduler: Add scheduler overview documentation .git/rebase-apply/patch:73: new blank line at EOF.
+
warning: 1 line adds whitespace errors.
Applying: docs: scheduler: Add introduction to scheduler context-switch .git/rebase-apply/patch:153: new blank line at EOF.
+
.git/rebase-apply/patch:260: new blank line at EOF.
+
warning: 2 lines add whitespace errors.
You might want to look into this. I also checked that the patch also applies on linux-next, i.e., next-20200908; so, it does not clash in an obvious way with other changes at the moment.
I did run checkpatch.pl and it warned about:
WARNING: added, moved or deleted file(s), does MAINTAINERS need updating?
No action required here.
Documentation generation (make htmldocs) shows these two new warnings with your patches applied to v5.9-rc4:
./kernel/sched/core.c:17: WARNING: Definition list ends without a blank
line; unexpected unindent.
./kernel/sched/core.c:21: WARNING: Unexpected indentation.
You might want to put those minor fixes on your remaining TODO list for this patchset as well.
I will continue to comment with more editorial points in the next hours and days, while proof-reading your additions to the documentation.
Lukas