Skip to contentSkip to conversation

Add scheduler overview documentation

RFC PATCH In review John Mathew 2 participants 7 messages Sep 2, 2020 – Sep 9, 2020

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
new file mode 100644
index 000000000000..3e5af3a0695e
@@ -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
index 88900aabdbf7..6e88a070c503 100644
@@ -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
new file mode 100644
index 000000000000..a1d2d26629eb
@@ -0,0 +1,5 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+====================
+Scheduler overview
+====================
\ No newline at end of file
Documentation/scheduler/sched-debugging.rst new file +14 -0
new file mode 100644
index 000000000000..e332069f99d6
@@ -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
new file mode 100644
index 000000000000..8eb90e86e489
@@ -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
#2 lore raw

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.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 +0 -0
new file mode 100644
index 000000000000..3e5af3a0695e

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
index 88900aabdbf7..6e88a070c503 100644
@@ -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 +0 -0
new file mode 100644
index 000000000000..a1d2d26629eb

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
+====================
\ No newline at end of file

That could be the cause for the git am errors.

Quoted 40 lines
Documentation/scheduler/sched-debugging.rst new file +14 -0
new file mode 100644
index 000000000000..e332069f99d6
@@ -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 +14 -0
new file mode 100644
index 000000000000..8eb90e86e489
@@ -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
#3 lore raw

RFC PATCH v8 2/3 docs: scheduler: Add scheduler overview documentation

In reply to John Mathew

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             |   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
new file mode 100644
index 000000000000..1524c24da897
@@ -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
index 6e88a070c503..e3b1d4fc1604 100644
@@ -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
new file mode 100644
index 000000000000..6b9cb03d0d86
@@ -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
index 2d95dc3f4644..99a3b5ab4039 100644
@@ -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
#4 lore raw

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 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 +1 -0
new file mode 100644
index 000000000000..1524c24da897
@@ -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
index 6e88a070c503..e3b1d4fc1604 100644
@@ -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 +0 -0
index a1d2d26629eb..f2fb8f419919 100644

Documentation/scheduler/overview.rst line 7

Quoted 8 lines
Documentation/scheduler/overview.rst +3 -1
@@ -2,4 +2,296 @@
 
 ====================
 Scheduler overview
-====================
\ No newline at end of file
+====================
+
+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

#5 lore raw

RFC PATCH v8 3/3 docs: scheduler: Add introduction to scheduler context-switch

In reply to John Mathew

Add 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
index 3e5af3a0695e..65dc393b605f 100644
@@ -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
index e3b1d4fc1604..fc7ee056f3bb 100644
@@ -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
#6 lore raw
In reply to John Mathew
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