Skip to contentSkip to conversation

Fixes

PATCH New john mathew 2 participants 7 messages May 13, 2020 – May 14, 2020

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

PATCH 1/1 Fixes

---
 Documentation/scheduler/cfs-overview.rst      | 113 ++++++------
 Documentation/scheduler/sched-cas.rst         |  74 ++++++++
 .../scheduler/sched-data-structs.rst          | 163 +++++-------------
 Documentation/scheduler/sched-design-CFS.rst  |  20 +++
 Documentation/scheduler/sched-features.rst    |   1 +
 5 files changed, 192 insertions(+), 179 deletions(-)
 create mode 100644 Documentation/scheduler/sched-cas.rst
Documentation/scheduler/cfs-overview.rst +51 -62
index b717f2d3e340..3ce559f285f7 100644
@@ -6,26 +6,26 @@ 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`
+CFS design is provided in :doc: `sched-design-CFS`
 
 In addition there have been many improvements to the CFS, a few of which are
 
 **Thermal Pressure**:
-cpu_capacity initially reflects the maximum possible capacity of a CPU.
-Thermal pressure on a CPU means this maximum possible capacity is
-unavailable due to thermal events. Average thermal pressure for a CPU
-is now subtracted from its maximum possible capacity so that cpu_capacity
-reflects the remaining maximum capacity.
-
-**Use Idle CPU for NUMA balancing**:
-Idle CPU is used as a migration target instead of comparing tasks.
-Information on an idle core is cached while gathering statistics
-and this is used to avoid a second scan of the node runqueues if load is
-not imbalanced. Preference is given to an idle core rather than an
-idle SMT sibling to avoid packing HT siblings due to linearly scanning
-the node cpumask. Multiple tasks can attempt to select an idle CPU but
-fail because a NUMA balance is active on that CPU, in this case instead of
-failing, an alternative idle CPU scanned.
+Scale CPU capacity mechanism for CFS so it knows how much CPU capacity is left
+for its use after higher priority sched classes (RT, DL), IRQs and
+'Thermal Pressure' have reduced the 'original' CPU capacity.
+Thermal pressure on a CPU means the maximum possible capacity is
+unavailable due to thermal events.
+
+** Optimizations to NUMA balancing**:
+When gathering NUMA statistics, information about whether a core is Idle
+is also cached. In case of an imbalance, instead of doing a second scan of
+the node runqueues, the idle core is used as the migration target. When
+doing so multiple tasks can attempt to select an idle CPU but fail, because
+a NUMA balance is active on that CPU. In this case an alternative idle CPU
+scanned. Another optimization is to terminate the search for swap candidate
+when a reasonable one is found instead of searching all the CPUs on the
+target domain.
 
 **Asymmetric CPU capacity wakeup scan**:
 Previous assumption that CPU capacities within an SD_SHARE_PKG_RESOURCES
@@ -38,34 +38,24 @@ If no idle CPU is big enough, the idle CPU with the highest capacity is
 picked.
 
 **Optimized idle core selection**:
-Previously all threads of a core were looped through to evaluate if the
-core is idle or not. This was unnecessary. If a thread of a core is not
-idle, skip evaluating other threads of a core. Also while clearing the
-cpumask, bits of all CPUs of a core can be cleared in one shot.
+Skipped looping through all the threads of a core to evaluate if the
+core is idle or not. If a thread of a core is not idle, evaluation of
+other threads of the core can be skipped.
 
 **Load balance aggressively for SCHED_IDLE CPUs**:
-The fair scheduler performs periodic load balance on every CPU to check
-if it can pull some tasks from other busy CPUs. The duration of this
-periodic load balance is set to scheduler domain's balance_interval and
-multiplied by a busy_factor (set to 32 by default) for the busy CPUs. This
-multiplication is done for busy CPUs to avoid doing load balance too
-often and rather spend more time executing actual task. While that is
-the right thing to do for the CPUs busy with SCHED_OTHER or SCHED_BATCH
-tasks, it may not be the optimal thing for CPUs running only SCHED_IDLE
-tasks. With the recent enhancements in the fair scheduler around SCHED_IDLE
-CPUs, it is now preferred to enqueue a newly-woken task to a SCHED_IDLE
-CPU instead of other busy or idle CPUs. The same reasoning is applied
-to the load balancer as well to make it migrate tasks more aggressively
-to a SCHED_IDLE CPU, as that will reduce the scheduling latency of the
-migrated (SCHED_OTHER) tasks. Fair scheduler now does the next
+Newly-woken task is preferred to be  enqueued on a SCHED_IDLE CPU instead
+of other busy or idle CPUs. Also load balancer is made to migrate tasks more
+aggressively to a SCHED_IDLE CPU. Fair scheduler now does the next
 load balance soon after the last non-SCHED_IDLE task is dequeued from a
-runqueue, i.e. making the CPU SCHED_IDLE.
+runqueue, i.e. making the CPU SCHED_IDLE. Also the the busy_factor
+used with the balance interval to prevent frequent load balancing
+is ignored for such CPU's.
 
 **Load balancing algorithm Reworked**:
-The load balancing algorithm contained some heuristics which became
-meaningless since the rework of the scheduler's metrics like the
-introduction of PELT. The new load balancing algorithm fixes several
-pending wrong tasks placement
+Some heuristics in the load balancing algorithm became meaningless because
+of the rework of the scheduler's metrics like the introduction of PELT.
+Those heuristics were removed. The new load balancing algorithm also fixes
+several pending wrong tasks placement
 
  * the 1 task per CPU case with asymmetric system
  * the case of CFS task preempted by other class
@@ -73,41 +63,40 @@ pending wrong tasks placement
 
 Also the load balance decisions have been consolidated in the 3 separate
 functions.
+* update_sd_pick_busiest() select the busiest sched_group.
+* find_busiest_group() checks if there is an imbalance between local and
+busiest group.
+* calculate_imbalance() decides what have to be moved.
 
 **Energy-aware wake-ups speeded up**:
-EAS computes the energy impact of migrating a waking task when deciding
-on which CPU it should run. However, the previous approach had high algorithmic
-complexity, which resulted in prohibitively high wake-up latencies on
-systems with complex energy models, such as systems with per-CPU DVFS. On
-such systems, the algorithm complexity was O(n^2). To address this,
-the EAS wake-up path was re-factored to compute the energy 'delta' on a
-per-performance domain basis, rather than system-wide, which brings the
-complexity down to O(n).
+Algorithmic complexity of the EAS was reduced from O(n^2) to O(n).
+Previous algorithm resulted in prohibitively high wake-up latencies on
+systems with complex energy models, such as systems with per-CPU DVFS.
+The EAS wake-up path was re-factored to compute the energy 'delta' on a
+per-performance domain basis, rather than the whole system.
 
 **Selection of an energy-efficient CPU on task wake-up**:
-If an Energy Model (EM) is available and if the system isn't overutilized,
-waking tasks are re-routed into an energy-aware placement algorithm.
-The selection of an energy-efficient CPU for a task is achieved by estimating
-the impact on system-level active energy resulting from the placement of the
-task on the CPU with the highest spare capacity in each performance domain.
-This strategy spreads tasks in a performance domain and avoids overly
+An Energy efficient CPU is found by estimating the impact on system-level
+active energy resulting from the placement of the task on the CPU with the
+highest spare capacity in each performance domain. Energy Model (EM) is
+used for this. This strategy spreads tasks in a performance domain and avoids overly
 aggressive task packing. The best CPU energy-wise is then selected if it
 saves a large enough amount of energy with respect to prev_cpu.
 
 **Consider misfit tasks when load-balancing**:
-On asymmetric CPU capacity systems load intensive tasks can end up on
-CPUs that don't suit their compute demand. In this scenario 'misfit'
-tasks are migrated to CPUs with higher compute capacity to ensure better
-throughput. A new group_type: group_misfit_task is added and indicates this
+A task which ends up on a CPU which doesn't suit its compute demand is
+identified as a misfit task in asymmetric CPU capacity systems. These
+'misfit' tasks are migrated to CPUs with higher compute capacity to ensure
+better throughput. A new group_type: group_misfit_task is added and indicates this
 scenario. Tweaks to the load-balance code are done to make the migrations
 happen. Misfit balancing is done between a source group of lower per-CPU
 capacity and destination group of higher compute capacity. Otherwise, misfit
 balancing is ignored.
 
+
 **Make schedstats a runtime tunable that is disabled by default**:
-schedstats is very useful during debugging and performance tuning but it
-incurred overhead to calculate the stats. A kernel command-line and sysctl
-tunable was added to enable or disable schedstats on demand (when it's built in).
-It is disabled by default. The benefits are dependent on how
-scheduler-intensive the workload is.
+A kernel command-line and sysctl tunable was added to enable or disable
+schedstats on demand (when it's built in). It is disabled by default.
+The benefits are dependent on how scheduler-intensive the workload is.
+
 
Documentation/scheduler/sched-cas.rst new file +74 -0

74 lines not on this page · raw message

Documentation/scheduler/sched-data-structs.rst +46 -117

198 lines not on this page · raw message

Documentation/scheduler/sched-design-CFS.rst +20 -0
index a96c72651877..0556783019cf 100644
@@ -44,6 +44,26 @@ value (i.e., the task which executed least so far).  CFS always tries to split
 up CPU time between runnable tasks as close to "ideal multitasking hardware" as
 possible.
 
+vruntime of the task based on the formula ::
+
+    vruntime += delta_exec * (NICE_0_LOAD/se->load);
+
+where:
+
+* delta_exec is the time in nanoseconds spent by the task since the last time
+  vruntime was updated.
+* NICE_0_LOAD is the load of a task with default priority.
+* se->load: sched_entity load_weight. load_weight is the obtained by mapping
+  of priority value to the capacity of the standard CPU which is done in
+  the array :c:type:`sched_prio_to_weight[]`. The array contains mappings
+  for the nice values from -20 to 19. Nice value 0 is mapped to 1024. Each
+  entry advances by approximately 1.25 which means for every increment in
+  nice value the task gets 10% less CPU and vice versa.
+  When the se->load is updated the se->avg is also updated for SMP
+  configurations. Load balancing decisions are based (amongst other things)
+  on the sums of se.avg.load_avg, which is the 'load' signal generated via
+  PELT. PELT(Per-entity load tracking) is described in :doc: `sched-pelt`.
+
 Most of the rest of CFS's design just falls out of this really simple concept,
 with a few add-on embellishments like nice levels, multiprocessing and various
 algorithm variants to recognize sleepers.
Documentation/scheduler/sched-features.rst +1 -0
index 1afbd9cc8d52..e576c7d9e556 100644
@@ -17,4 +17,5 @@ Scheduler Features
    sched-energy
    sched-nice-design
    sched-rt-group
+   sched-cas
    completion
Signature · 1 line
2.17.1
#1 lore raw

v4 cover Add scheduler overview documentation

version 4:
-Added section on Capacity-Aware Scheduling -Reworded CFS recently added features. -Removed vruntime description from scheduler structs -Added description of idle and stopper sched classses

version 3:
-Fix spelling, spacing and typo errors.

version 2:
- Remove :c:func: directive as it was redundant
- Limit document width (line symbol count) to 75
- Replace dot file with ASCII art
- Describe prepare_task_switch(), ASID use, kernel/user transtion, MIPS FPU affinity correctly
- Add missing references to files
- Removed internal APIs from scheduler API reference
- Described rq struct member as kernel-doc comments
- Replaced CFS history with CFS current status
- Added documentation for sched_class fields
- Refined explanation of context swtich functionality
- Replace CFS history with recent changes
- Added kernel-doc comments for struct rq

John Mathew (3):
docs: scheduler: Restructure scheduler documentation.
docs: scheduler: Add scheduler overview documentation
docs: scheduler: Add introduction to scheduler context-switch

 Documentation/scheduler/arch-specific.rst     |  14 +
 Documentation/scheduler/cfs-overview.rst      | 102 ++++++
 Documentation/scheduler/context-switching.rst | 125 ++++++++
 Documentation/scheduler/index.rst             |  33 +-
 .../scheduler/mips-context-switch.rst         |  89 ++++++
 Documentation/scheduler/overview.rst          | 293 ++++++++++++++++++
 Documentation/scheduler/sched-cas.rst         |  90 ++++++
 .../scheduler/sched-data-structs.rst          | 182 +++++++++++
 Documentation/scheduler/sched-debugging.rst   |  14 +
 Documentation/scheduler/sched-features.rst    |  21 ++
 Documentation/scheduler/scheduler-api.rst     |  31 ++
 .../scheduler/x86-context-switch.rst          |  65 ++++
 kernel/sched/core.c                           |  28 +-
 kernel/sched/sched.h                          | 169 +++++++++-
 14 files changed, 1236 insertions(+), 20 deletions(-)
 create mode 100644 Documentation/scheduler/arch-specific.rst
 create mode 100644 Documentation/scheduler/cfs-overview.rst
 create mode 100644 Documentation/scheduler/context-switching.rst
 create mode 100644 Documentation/scheduler/mips-context-switch.rst
 create mode 100644 Documentation/scheduler/overview.rst
 create mode 100644 Documentation/scheduler/sched-cas.rst
 create mode 100644 Documentation/scheduler/sched-data-structs.rst
 create mode 100644 Documentation/scheduler/sched-debugging.rst
 create mode 100644 Documentation/scheduler/sched-features.rst
 create mode 100644 Documentation/scheduler/scheduler-api.rst
 create mode 100644 Documentation/scheduler/x86-context-switch.rst
Signature · 1 line
2.17.1
#2 lore raw

RFC PATCH v4 1/3 docs: scheduler: Restructure scheduler documentation.

In reply to john mathew

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
new file mode 100644
index 000000000000..c9c34863d994
@@ -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
index 69074e5de9c4..9bdccea74af9 100644
@@ -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
new file mode 100644
index 000000000000..aee16feefc61
@@ -0,0 +1,5 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+====================
+Scheduler overview
+====================
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 +20 -0
new file mode 100644
index 000000000000..1afbd9cc8d52
@@ -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
#3 lore raw

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

In reply to john mathew

From: John Mathew <[email protected]>

Add documentation for
-scheduler overview
-scheduler state transtion
-CFS overview
-scheduler data structs

Add rst for scheduler APIs and modify sched/core.c to add kernel-doc comments.

---
 Documentation/scheduler/cfs-overview.rst      | 102 +++++++
 Documentation/scheduler/index.rst             |   2 +
 Documentation/scheduler/overview.rst          | 288 ++++++++++++++++++
 Documentation/scheduler/sched-cas.rst         |  90 ++++++
 .../scheduler/sched-data-structs.rst          | 182 +++++++++++
 Documentation/scheduler/sched-features.rst    |   1 +
 Documentation/scheduler/scheduler-api.rst     |  31 ++
 kernel/sched/core.c                           |  28 +-
 kernel/sched/sched.h                          | 169 +++++++++-
 9 files changed, 886 insertions(+), 7 deletions(-)
 create mode 100644 Documentation/scheduler/cfs-overview.rst
 create mode 100644 Documentation/scheduler/sched-cas.rst
 create mode 100644 Documentation/scheduler/sched-data-structs.rst
 create mode 100644 Documentation/scheduler/scheduler-api.rst
Documentation/scheduler/cfs-overview.rst new file +102 -0
new file mode 100644
index 000000000000..34f336b8ec86
@@ -0,0 +1,102 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+=============
+CFS Overview
+=============
+
+Linux 2.6.23 introduced a modular scheduler core and a Completely Fair
+Scheduler (CFS) implemented as a scheduling module. A brief overview of the
+CFS design is provided in :doc:`sched-design-CFS`
+
+In addition there have been many improvements to the CFS, a few of which are
+
+**Thermal Pressure**:
+Scale CPU capacity mechanism for CFS so it knows how much CPU capacity is left
+for its use after higher priority sched classes (RT, DL), IRQs and
+'Thermal Pressure' have reduced the 'original' CPU capacity.
+Thermal pressure on a CPU means the maximum possible capacity is
+unavailable due to thermal events.
+
+** Optimizations to NUMA balancing**:
+When gathering NUMA statistics, information about whether a core is Idle
+is also cached. In case of an imbalance, instead of doing a second scan of
+the node runqueues, the idle core is used as the migration target. When
+doing so multiple tasks can attempt to select an idle CPU but fail, because
+a NUMA balance is active on that CPU. In this case an alternative idle CPU
+scanned. Another optimization is to terminate the search for swap candidate
+when a reasonable one is found instead of searching all the CPUs on the
+target domain.
+
+**Asymmetric CPU capacity wakeup scan**:
+Previous assumption that CPU capacities within an SD_SHARE_PKG_RESOURCES
+domain (sd_llc) are homogeneous didn't hold for newer generations of big.LITTLE
+systems (DynamIQ) which can accommodate CPUs of different compute capacity
+within a single LLC domain. A new idle sibling helper function was added
+which took CPU capacity into account. The policy is to pick the first idle
+CPU which is big enough for the task (task_util * margin < cpu_capacity).
+If no idle CPU is big enough, the idle CPU with the highest capacity is
+picked.
+
+**Optimized idle core selection**:
+Skipped looping through all the threads of a core to evaluate if the
+core is idle or not. If a thread of a core is not idle, evaluation of
+other threads of the core can be skipped.
+
+**Load balance aggressively for SCHED_IDLE CPUs**:
+Newly-woken task is preferred to be  enqueued on a SCHED_IDLE CPU instead
+of other busy or idle CPUs. Also load balancer is made to migrate tasks more
+aggressively to a SCHED_IDLE CPU. Fair scheduler now does the next
+load balance soon after the last non-SCHED_IDLE task is dequeued from a
+runqueue, i.e. making the CPU SCHED_IDLE. Also the the busy_factor
+used with the balance interval to prevent frequent load balancing
+is ignored for such CPU's.
+
+**Load balancing algorithm Reworked**:
+Some heuristics in the load balancing algorithm became meaningless because
+of the rework of the scheduler's metrics like the introduction of PELT.
+Those heuristics were removed. The new load balancing algorithm also fixes
+several pending wrong tasks placement
+
+ * the 1 task per CPU case with asymmetric system
+ * the case of CFS task preempted by other class
+ * the case of tasks not evenly spread on groups with spare capacity
+
+Also the load balance decisions have been consolidated in the 3 separate
+functions.
+* update_sd_pick_busiest() select the busiest sched_group.
+* find_busiest_group() checks if there is an imbalance between local and
+busiest group.
+* calculate_imbalance() decides what have to be moved.
+
+**Energy-aware wake-ups speeded up**:
+Algorithmic complexity of the EAS was reduced from O(n^2) to O(n).
+Previous algorithm resulted in prohibitively high wake-up latencies on
+systems with complex energy models, such as systems with per-CPU DVFS.
+The EAS wake-up path was re-factored to compute the energy 'delta' on a
+per-performance domain basis, rather than the whole system.
+
+**Selection of an energy-efficient CPU on task wake-up**:
+An Energy efficient CPU is found by estimating the impact on system-level
+active energy resulting from the placement of the task on the CPU with the
+highest spare capacity in each performance domain. Energy Model (EM) is
+used for this. This strategy spreads tasks in a performance domain and avoids overly
+aggressive task packing. The best CPU energy-wise is then selected if it
+saves a large enough amount of energy with respect to prev_cpu.
+
+**Consider misfit tasks when load-balancing**:
+A task which ends up on a CPU which doesn't suit its compute demand is
+identified as a misfit task in asymmetric CPU capacity systems. These
+'misfit' tasks are migrated to CPUs with higher compute capacity to ensure
+better throughput. A new group_type: group_misfit_task is added and indicates this
+scenario. Tweaks to the load-balance code are done to make the migrations
+happen. Misfit balancing is done between a source group of lower per-CPU
+capacity and destination group of higher compute capacity. Otherwise, misfit
+balancing is ignored.
+
+
+**Make schedstats a runtime tunable that is disabled by default**:
+A kernel command-line and sysctl tunable was added to enable or disable
+schedstats on demand (when it's built in). It is disabled by default.
+The benefits are dependent on how scheduler-intensive the workload is.
+
+
Documentation/scheduler/index.rst +2 -0
index 9bdccea74af9..f311abe5b711 100644
@@ -17,6 +17,8 @@ specific implementation differences.
     :maxdepth: 2
 
     overview
+    sched-data-structs
+    cfs-overview
     sched-design-CFS
     sched-features
     arch-specific
Documentation/scheduler/overview.rst +288 -0

291 lines not on this page · raw message

Documentation/scheduler/sched-cas.rst new file +90 -0

90 lines not on this page · raw message

Documentation/scheduler/sched-data-structs.rst new file +182 -0

182 lines not on this page · raw message

Documentation/scheduler/sched-features.rst +1 -0
index 1afbd9cc8d52..e576c7d9e556 100644
@@ -17,4 +17,5 @@ Scheduler Features
    sched-energy
    sched-nice-design
    sched-rt-group
+   sched-cas
    completion
Documentation/scheduler/scheduler-api.rst new file +31 -0
new file mode 100644
index 000000000000..1fc6bd4c2908
@@ -0,0 +1,31 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+=============================
+Scheduler related functions
+=============================
+
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: __schedule
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: scheduler_tick
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: try_to_wake_up
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: do_task_dead
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: preempt_schedule_irq
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: prepare_task_switch
+
+.. kernel-doc:: kernel/sched/core.c
+	:functions: finish_task_switch
+
+.. kernel-doc:: kernel/sched/sched.h
+	:functions: rq
+
kernel/sched/core.c +24 -4
index 9a2fbf98fd6f..b349ed9b4d92 100644
@@ -3576,9 +3576,13 @@ void arch_set_thermal_pressure(struct cpumask *cpus,
 		WRITE_ONCE(per_cpu(thermal_pressure, cpu), th_pressure);
 }
 
-/*
+/**
+ * scheduler_tick - sched tick timer handler
+ *
  * This function gets called by the timer code, with HZ frequency.
  * We call it with interrupts disabled.
+ *
+ * Return: 0.
  */
 void scheduler_tick(void)
 {
@@ -3959,8 +3963,10 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	BUG();
 }
 
-/*
- * __schedule() is the main scheduler function.
+/**
+ * __schedule() - the main scheduler function.
+ *
+ * @preempt: preemption enabled/disabled
  *
  * The main means of driving the scheduler and thus entering this function are:
  *
@@ -4089,6 +4095,12 @@ static void __sched notrace __schedule(bool preempt)
 	balance_callback(rq);
 }
 
+/**
+ * do_task_dead - handle task exit
+ *
+ * Changes the the task state to TASK_DEAD and calls
+ * schedule to pick next task to run.
+ */
 void __noreturn do_task_dead(void)
 {
 	/* Causes final put_task_struct in finish_task_switch(): */
@@ -4320,7 +4332,8 @@ EXPORT_SYMBOL_GPL(preempt_schedule_notrace);
 
 #endif /* CONFIG_PREEMPTION */
 
-/*
+/**
+ * preempt_schedule_irq - schedule from irq context
  * This is the entry point to schedule() from kernel preemption
  * off of irq context.
  * Note, that this is called and return with irqs disabled. This will
@@ -5618,6 +5631,13 @@ SYSCALL_DEFINE0(sched_yield)
 }
 
 #ifndef CONFIG_PREEMPTION
+/**
+ * _cond_resched - explicit rescheduling
+ *
+ * gives the scheduler a chance to run a higher-priority process
+ *
+ * Return: 1 if reschedule was done, 0 if reschedule not done.
+ */
 int __sched _cond_resched(void)
 {
 	if (should_resched(0)) {
kernel/sched/sched.h +166 -3

185 lines not on this page · raw message

Signature · 1 line
2.17.1
#4 lore raw

Re: [RFC PATCH v4 2/3] docs: scheduler: Add scheduler overview documentation

Documentation/scheduler/sched-cas.rst line 6

Quoted 4 lines · john mathew

+=========================

Documentation/scheduler/sched-cas.rst new file +3 -0
+Capacity-Aware Scheduling
+=========================
+

Thanks for taking a jab at this. At a glance it looks okay, with one comment below.

FWIW I still intend to write a more pamphlet-sized thing, I'll toss something out in the coming weeks - depending on where this goes, I might base it on this.

Quoted 9 lines
Documentation/scheduler/sched-cas.rst new file +9 -0
+Scheduling load balancing on Asymmetric Multiprocessor systems was improved
+through the introduction of Capacity-Aware Scheduling. It identifies the
+most efficient CPU to assign a task based on its capacity. This capacity
+may be asymmetric due to heterogeneous computing architecture such
+as ARM big.LITTLE. Scheduler gets information about asymmetric capacities
+when the scheduler domain hierarchy is built using build_sched_domains().
+CPU capacities are provided to the scheduler topology code through the
+architecture specific implementation of the arch_scale_cpu_capacity().
+The SD_ASYM_CPUCAPACITY flag is set by the scheduler topology for a domain

Documentation/scheduler/sched-cas.rst line 25

Quoted 10 lines
Documentation/scheduler/sched-cas.rst new file +10 -0
+in the hierarchy where all CPU capacities are visible for any cpu's point
+of view on asymmetric CPU capacity systems. The scheduler can then take
+capacity asymmetry into account when load balancing.
+
+Initial CPU capacities are derived from the Device Tree and CPU frequency.
+For RISC-V & ARM64 it is done in drivers/base/arch_topology.c. A cpu-map
+device tree is parsed to obtain the cpu topology and the initial CPU capacity
+is set using the CPUFreq subsystem. A callback is registered to the CPUFreq
+subsystem to rebuild sched_domains when CPU frequency changes.
+

We don't rebuild domains on frequency changes (that would be ludicrous!), rather we do that on policy changes. It's mostly because we need to wait for cpufreq to be loaded before having a complete view over the capacities of the CPUs (which is a mix of µarch and frequencies), i.e. we need to rebuild the SD's again once cpufreq comes up.

#5 lore raw

Re: [RFC PATCH v4 2/3] docs: scheduler: Add scheduler overview documentation

Quoted 32 lines · Valentin Schneider

Documentation/scheduler/sched-cas.rst line 6

Quoted 4 lines · john mathew

+=========================

Documentation/scheduler/sched-cas.rst new file +3 -0
+Capacity-Aware Scheduling
+=========================
+

Thanks for taking a jab at this. At a glance it looks okay, with one comment below.

FWIW I still intend to write a more pamphlet-sized thing, I'll toss something out in the coming weeks - depending on where this goes, I might base it on this.

Quoted 17 lines
Documentation/scheduler/sched-cas.rst new file +17 -0
+Scheduling load balancing on Asymmetric Multiprocessor systems was improved
+through the introduction of Capacity-Aware Scheduling. It identifies the
+most efficient CPU to assign a task based on its capacity. This capacity
+may be asymmetric due to heterogeneous computing architecture such
+as ARM big.LITTLE. Scheduler gets information about asymmetric capacities
+when the scheduler domain hierarchy is built using build_sched_domains().
+CPU capacities are provided to the scheduler topology code through the
+architecture specific implementation of the arch_scale_cpu_capacity().
+The SD_ASYM_CPUCAPACITY flag is set by the scheduler topology for a domain
+in the hierarchy where all CPU capacities are visible for any cpu's point
+of view on asymmetric CPU capacity systems. The scheduler can then take
+capacity asymmetry into account when load balancing.
+
+Initial CPU capacities are derived from the Device Tree and CPU frequency.
+For RISC-V & ARM64 it is done in drivers/base/arch_topology.c. A cpu-map
+device tree is parsed to obtain the cpu topology and the initial CPU capacity
+is set using the CPUFreq subsystem. A callback is registered to the CPUFreq
Quoted 8 lines

Documentation/scheduler/sched-cas.rst line 25

Quoted 2 lines
Documentation/scheduler/sched-cas.rst new file +2 -0
+subsystem to rebuild sched_domains when CPU frequency changes.
+

We don't rebuild domains on frequency changes (that would be ludicrous!), rather we do that on policy changes. It's mostly because we need to wait for cpufreq to be loaded before having a complete view over the capacities of the CPUs (which is a mix of µarch and frequencies), i.e. we need to rebuild the SD's again once cpufreq comes up.

Fixed in v5 of the patchset.
Thanks

#6 lore raw

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

In reply to john mathew

From: John Mathew <[email protected]>

Add documentation for introduction to
-context-switch
-x86 context-switch
-MIPS context switch

---
 Documentation/scheduler/arch-specific.rst     |   3 +
 Documentation/scheduler/context-switching.rst | 125 ++++++++++++++++++
 Documentation/scheduler/index.rst             |   1 +
 .../scheduler/mips-context-switch.rst         |  89 +++++++++++++
 .../scheduler/x86-context-switch.rst          |  65 +++++++++
 5 files changed, 283 insertions(+)
 create mode 100644 Documentation/scheduler/context-switching.rst
 create mode 100644 Documentation/scheduler/mips-context-switch.rst
 create mode 100644 Documentation/scheduler/x86-context-switch.rst
Documentation/scheduler/arch-specific.rst +3 -0
index c9c34863d994..65dc393b605f 100644
@@ -9,3 +9,6 @@ Architecture Specific Scheduler Implementation Differences
 
 .. toctree::
    :maxdepth: 2
+
+   x86-context-switch
+   mips-context-switch
Documentation/scheduler/context-switching.rst new file +125 -0

125 lines not on this page · raw message

Documentation/scheduler/index.rst +1 -0
index f311abe5b711..691fdfe32954 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 +65 -0

65 lines not on this page · raw message

Signature · 1 line
2.17.1