<!DOCTYPE html>
<html lang="en" data-content_root="../">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Schedutil — The Linux Kernel documentation</title>
<link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=fa44fd50" />
<link rel="stylesheet" type="text/css" href="../_static/alabaster.css?v=3918102e" />
<script src="../_static/documentation_options.js?v=5929fcd5"></script>
<script src="../_static/doctools.js?v=9bcbadda"></script>
<script src="../_static/sphinx_highlight.js?v=dc90522c"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Utilization Clamping" href="sched-util-clamp.html" />
<link rel="prev" title="Energy Aware Scheduling" href="sched-energy.html" />
<link rel="stylesheet" href="../_static/custom.css" type="text/css" />
</head><body>
<div class="document">
<div class="sphinxsidebar" role="navigation" aria-label="Main">
<div class="sphinxsidebarwrapper">
<p class="logo"><a href="../index.html">
<img class="logo" src="../_static/logo.svg" alt="Logo of The Linux Kernel"/>
</a></p>
<h1 class="logo"><a href="../index.html">The Linux Kernel</a></h1>
<p class="blurb">6.18.50</p>
<search id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</search>
<script>document.getElementById('searchbox').style.display = "block"</script>
<p>
<h3 class="kernel-toc-contents">Contents</h3>
<input type="checkbox" class="kernel-toc-toggle" id = "kernel-toc-toggle" checked>
<label class="kernel-toc-title" for="kernel-toc-toggle"></label>
<div class="kerneltoc" id="kerneltoc">
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/development-process.html">Development process</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/submitting-patches.html">Submitting patches</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/code-of-conduct.html">Code of conduct</a></li>
<li class="toctree-l1"><a class="reference internal" href="../maintainer/index.html">Maintainer handbook</a></li>
<li class="toctree-l1"><a class="reference internal" href="../process/index.html">All development-process docs</a></li>
</ul>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../core-api/index.html">Core API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../driver-api/index.html">Driver APIs</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../subsystem-apis.html">Subsystems</a><ul class="current">
<li class="toctree-l2 current"><a class="reference internal" href="../subsystem-apis.html#core-subsystems">Core subsystems</a><ul class="current">
<li class="toctree-l3"><a class="reference internal" href="../core-api/index.html">Core API Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../driver-api/index.html">Driver implementer’s API guide</a></li>
<li class="toctree-l3"><a class="reference internal" href="../mm/index.html">Memory Management Documentation</a></li>
<li class="toctree-l3"><a class="reference internal" href="../power/index.html">Power Management</a></li>
<li class="toctree-l3 current"><a class="reference internal" href="index.html">Scheduler</a></li>
<li class="toctree-l3"><a class="reference internal" href="../timers/index.html">Timers</a></li>
<li class="toctree-l3"><a class="reference internal" href="../locking/index.html">Locking</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#human-interfaces">Human interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#networking-interfaces">Networking interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#storage-interfaces">Storage interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../subsystem-apis.html#other-subsystems">Other subsystems</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../locking/index.html">Locking</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../process/license-rules.html">Licensing rules</a></li>
<li class="toctree-l1"><a class="reference internal" href="../doc-guide/index.html">Writing documentation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/index.html">Development tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../dev-tools/testing-overview.html">Testing guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kernel-hacking/index.html">Hacking guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../trace/index.html">Tracing</a></li>
<li class="toctree-l1"><a class="reference internal" href="../fault-injection/index.html">Fault injection</a></li>
<li class="toctree-l1"><a class="reference internal" href="../livepatch/index.html">Livepatching</a></li>
<li class="toctree-l1"><a class="reference internal" href="../rust/index.html">Rust</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/index.html">Administration</a></li>
<li class="toctree-l1"><a class="reference internal" href="../kbuild/index.html">Build system</a></li>
<li class="toctree-l1"><a class="reference internal" href="../admin-guide/reporting-issues.html">Reporting issues</a></li>
<li class="toctree-l1"><a class="reference internal" href="../tools/index.html">Userspace tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../userspace-api/index.html">Userspace API</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../firmware-guide/index.html">Firmware</a></li>
<li class="toctree-l1"><a class="reference internal" href="../devicetree/index.html">Firmware and Devicetree</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../arch/index.html">CPU architectures</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../staging/index.html">Unsorted documentation</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../translations/index.html">Translations</a></li>
</ul>
</div>
<script type="text/javascript"> <!--
var sbar = document.getElementsByClassName("sphinxsidebar")[0];
let currents = document.getElementsByClassName("current")
if (currents.length) {
sbar.scrollTop = currents[currents.length - 1].offsetTop;
}
--> </script>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/scheduler/schedutil.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
</div>
</div>
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="language-selection">
English
<ul>
<li><a href="../translations/zh_CN/scheduler/schedutil.html">Chinese (Simplified)</a></li>
</ul>
</div>
<section id="schedutil">
<h1>Schedutil<a class="headerlink" href="#schedutil" title="Link to this heading">¶</a></h1>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>All this assumes a linear relation between frequency and work capacity,
we know this is flawed, but it is the best workable approximation.</p>
</div>
<section id="pelt-per-entity-load-tracking">
<h2>PELT (Per Entity Load Tracking)<a class="headerlink" href="#pelt-per-entity-load-tracking" title="Link to this heading">¶</a></h2>
<p>With PELT we track some metrics across the various scheduler entities, from
individual tasks to task-group slices to CPU runqueues. As the basis for this
we use an Exponentially Weighted Moving Average (EWMA), each period (1024us)
is decayed such that y^32 = 0.5. That is, the most recent 32ms contribute
half, while the rest of history contribute the other half.</p>
<p>Specifically:</p>
<blockquote>
<div><p>ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ...</p>
<p>ewma(u) = ewma_sum(u) / ewma_sum(1)</p>
</div></blockquote>
<p>Since this is essentially a progression of an infinite geometric series, the
results are composable, that is ewma(A) + ewma(B) = ewma(A+B). This property
is key, since it gives the ability to recompose the averages when tasks move
around.</p>
<p>Note that blocked tasks still contribute to the aggregates (task-group slices
and CPU runqueues), which reflects their expected contribution when they
resume running.</p>
<p>Using this we track 2 key metrics: ‘running’ and ‘runnable’. ‘Running’
reflects the time an entity spends on the CPU, while ‘runnable’ reflects the
time an entity spends on the runqueue. When there is only a single task these
two metrics are the same, but once there is contention for the CPU ‘running’
will decrease to reflect the fraction of time each task spends on the CPU
while ‘runnable’ will increase to reflect the amount of contention.</p>
<p>For more detail see: kernel/sched/pelt.c</p>
</section>
<section id="frequency-cpu-invariance">
<h2>Frequency / CPU Invariance<a class="headerlink" href="#frequency-cpu-invariance" title="Link to this heading">¶</a></h2>
<p>Because consuming the CPU for 50% at 1GHz is not the same as consuming the CPU
for 50% at 2GHz, nor is running 50% on a LITTLE CPU the same as running 50% on
a big CPU, we allow architectures to scale the time delta with two ratios, one
Dynamic Voltage and Frequency Scaling (DVFS) ratio and one microarch ratio.</p>
<p>For simple DVFS architectures (where software is in full control) we trivially
compute the ratio as:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> f_cur
r_dvfs := -----
f_max
</pre></div>
</div>
<p>For more dynamic systems where the hardware is in control of DVFS we use
hardware counters (Intel APERF/MPERF, ARMv8.4-AMU) to provide us this ratio.
For Intel specifically, we use:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> APERF
f_cur := ----- * P0
MPERF
4C-turbo; if available and turbo enabled
f_max := { 1C-turbo; if turbo enabled
P0; otherwise
f_cur
r_dvfs := min( 1, ----- )
f_max
</pre></div>
</div>
<p>We pick 4C turbo over 1C turbo to make it slightly more sustainable.</p>
<p>r_cpu is determined as the ratio of highest performance level of the current
CPU vs the highest performance level of any other CPU in the system.</p>
<blockquote>
<div><p>r_tot = r_dvfs * r_cpu</p>
</div></blockquote>
<p>The result is that the above ‘running’ and ‘runnable’ metrics become invariant
of DVFS and CPU type. IOW. we can transfer and compare them between CPUs.</p>
<p>For more detail see:</p>
<blockquote>
<div><ul class="simple">
<li><p>kernel/sched/pelt.h:<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">update_rq_clock_pelt()</span></code></p></li>
<li><p>arch/x86/kernel/smpboot.c:”APERF/MPERF frequency ratio computation.”</p></li>
<li><p><a class="reference internal" href="sched-capacity.html"><span class="doc">Capacity Aware Scheduling</span></a>:”1. CPU Capacity + 2. Task utilization”</p></li>
</ul>
</div></blockquote>
</section>
<section id="util-est">
<h2>UTIL_EST<a class="headerlink" href="#util-est" title="Link to this heading">¶</a></h2>
<p>Because periodic tasks have their averages decayed while they sleep, even
though when running their expected utilization will be the same, they suffer a
(DVFS) ramp-up after they are running again.</p>
<p>To alleviate this (a default enabled option) UTIL_EST drives an Infinite
Impulse Response (IIR) EWMA with the ‘running’ value on dequeue -- when it is
highest. UTIL_EST filters to instantly increase and only decay on decrease.</p>
<p>A further runqueue wide sum (of runnable tasks) is maintained of:</p>
<blockquote>
<div><p>util_est := Sum_t max( t_running, t_util_est_ewma )</p>
</div></blockquote>
<p>For more detail see: kernel/sched/fair.c:<code class="xref c c-func broken_xref docutils literal notranslate"><span class="pre">util_est_dequeue()</span></code></p>
</section>
<section id="uclamp">
<h2>UCLAMP<a class="headerlink" href="#uclamp" title="Link to this heading">¶</a></h2>
<p>It is possible to set effective u_min and u_max clamps on each CFS or RT task;
the runqueue keeps an max aggregate of these clamps for all running tasks.</p>
<p>For more detail see: include/uapi/linux/sched/types.h</p>
</section>
<section id="schedutil-dvfs">
<h2>Schedutil / DVFS<a class="headerlink" href="#schedutil-dvfs" title="Link to this heading">¶</a></h2>
<p>Every time the scheduler load tracking is updated (task wakeup, task
migration, time progression) we call out to schedutil to update the hardware
DVFS state.</p>
<p>The basis is the CPU runqueue’s ‘running’ metric, which per the above it is
the frequency invariant utilization estimate of the CPU. From this we compute
a desired frequency like:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> max( running, util_est ); if UTIL_EST
u_cfs := { running; otherwise
clamp( u_cfs + u_rt , u_min, u_max ); if UCLAMP_TASK
u_clamp := { u_cfs + u_rt; otherwise
u := u_clamp + u_irq + u_dl; [approx. see source for more detail]
f_des := min( f_max, 1.25 u * f_max )
</pre></div>
</div>
<p>XXX IO-wait: when the update is due to a task wakeup from IO-completion we
boost ‘u’ above.</p>
<p>This frequency is then used to select a P-state/OPP or directly munged into a
CPPC style request to the hardware.</p>
<p>XXX: deadline tasks (Sporadic Task Model) allows us to calculate a hard f_min
required to satisfy the workload.</p>
<p>Because these callbacks are directly from the scheduler, the DVFS hardware
interaction should be ‘fast’ and non-blocking. Schedutil supports
rate-limiting DVFS requests for when hardware interaction is slow and
expensive, this reduces effectiveness.</p>
<p>For more information see: kernel/sched/cpufreq_schedutil.c</p>
</section>
<section id="notes">
<h2>NOTES<a class="headerlink" href="#notes" title="Link to this heading">¶</a></h2>
<blockquote>
<div><ul class="simple">
<li><p>On low-load scenarios, where DVFS is most relevant, the ‘running’ numbers
will closely reflect utilization.</p></li>
<li><p>In saturated scenarios task movement will cause some transient dips,
suppose we have a CPU saturated with 4 tasks, then when we migrate a task
to an idle CPU, the old CPU will have a ‘running’ value of 0.75 while the
new CPU will gain 0.25. This is inevitable and time progression will
correct this. XXX do we still guarantee f_max due to no idle-time?</p></li>
<li><p>Much of the above is about avoiding DVFS dips, and independent DVFS domains
having to re-learn / ramp-up when load shifts.</p></li>
</ul>
</div></blockquote>
</section>
</section>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©The kernel development community.
|
Powered by <a href="https://www.sphinx-doc.org/">Sphinx 8.1.3</a>
& <a href="https://alabaster.readthedocs.io">Alabaster 0.7.16</a>
|
<a href="../_sources/scheduler/schedutil.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>