NetBSD/sys/kern/sched_4bsd.c

570 lines
15 KiB
C

/* $NetBSD: sched_4bsd.c,v 1.46 2022/10/26 23:24:09 riastradh Exp $ */
/*
* Copyright (c) 1999, 2000, 2004, 2006, 2007, 2008, 2019, 2020
* The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
* NASA Ames Research Center, by Charles M. Hannum, Andrew Doran, and
* Daniel Sieger.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/*
* Copyright (c) 1982, 1986, 1990, 1991, 1993
* The Regents of the University of California. All rights reserved.
* (c) UNIX System Laboratories, Inc.
* All or some portions of this file are derived from material licensed
* to the University of California by American Telephone and Telegraph
* Co. or Unix System Laboratories, Inc. and are reproduced herein with
* the permission of UNIX System Laboratories, Inc.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* @(#)kern_synch.c 8.9 (Berkeley) 5/19/95
*/
#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: sched_4bsd.c,v 1.46 2022/10/26 23:24:09 riastradh Exp $");
#include "opt_ddb.h"
#include "opt_lockdebug.h"
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/callout.h>
#include <sys/cpu.h>
#include <sys/proc.h>
#include <sys/kernel.h>
#include <sys/resourcevar.h>
#include <sys/sched.h>
#include <sys/sysctl.h>
#include <sys/lockdebug.h>
#include <sys/intr.h>
#include <sys/atomic.h>
static void updatepri(struct lwp *);
static void resetpriority(struct lwp *);
/* Number of hardclock ticks per sched_tick() */
u_int sched_rrticks __read_mostly;
/*
* Force switch among equal priority processes every 100ms.
* Called from hardclock every hz/10 == sched_rrticks hardclock ticks.
*/
/* ARGSUSED */
void
sched_tick(struct cpu_info *ci)
{
struct schedstate_percpu *spc = &ci->ci_schedstate;
pri_t pri = PRI_NONE;
lwp_t *l;
spc->spc_ticks = sched_rrticks;
if (CURCPU_IDLE_P()) {
spc_lock(ci);
sched_resched_cpu(ci, MAXPRI_KTHREAD, true);
/* spc now unlocked */
return;
}
l = ci->ci_onproc;
if (l == NULL) {
return;
}
/*
* Can only be spc_lwplock or a turnstile lock at this point
* (if we interrupted priority inheritance trylock dance).
*/
KASSERT(l->l_mutex != spc->spc_mutex);
switch (l->l_class) {
case SCHED_FIFO:
/* No timeslicing for FIFO jobs. */
break;
case SCHED_RR:
/* Force it into mi_switch() to look for other jobs to run. */
pri = MAXPRI_KERNEL_RT;
break;
default:
if (spc->spc_flags & SPCF_SHOULDYIELD) {
/*
* Process is stuck in kernel somewhere, probably
* due to buggy or inefficient code. Force a
* kernel preemption.
*/
pri = MAXPRI_KERNEL_RT;
} else if (spc->spc_flags & SPCF_SEENRR) {
/*
* The process has already been through a roundrobin
* without switching and may be hogging the CPU.
* Indicate that the process should yield.
*/
pri = MAXPRI_KTHREAD;
spc->spc_flags |= SPCF_SHOULDYIELD;
} else if ((spc->spc_flags & SPCF_1STCLASS) == 0) {
/*
* For SMT or asymmetric systems push a little
* harder: if this is not a 1st class CPU, try to
* find a better one to run this LWP.
*/
pri = MAXPRI_KTHREAD;
spc->spc_flags |= SPCF_SHOULDYIELD;
} else {
spc->spc_flags |= SPCF_SEENRR;
}
break;
}
if (pri != PRI_NONE) {
spc_lock(ci);
sched_resched_cpu(ci, pri, true);
/* spc now unlocked */
}
}
/*
* Why PRIO_MAX - 2? From setpriority(2):
*
* prio is a value in the range -20 to 20. The default priority is
* 0; lower priorities cause more favorable scheduling. A value of
* 19 or 20 will schedule a process only when nothing at priority <=
* 0 is runnable.
*
* This gives estcpu influence over 18 priority levels, and leaves nice
* with 40 levels. One way to think about it is that nice has 20 levels
* either side of estcpu's 18.
*/
#define ESTCPU_SHIFT 11
#define ESTCPU_MAX ((PRIO_MAX - 2) << ESTCPU_SHIFT)
#define ESTCPU_ACCUM (1 << (ESTCPU_SHIFT - 1))
#define ESTCPULIM(e) uimin((e), ESTCPU_MAX)
/*
* The main parameter used by this algorithm is 'l_estcpu'. It is an estimate
* of the recent CPU utilization of the thread.
*
* l_estcpu is:
* - increased each time the hardclock ticks and the thread is found to
* be executing, in sched_schedclock() called from hardclock()
* - decreased (filtered) on each sched tick, in sched_pstats_hook()
* If the lwp is sleeping for more than a second, we don't touch l_estcpu: it
* will be updated in sched_setrunnable() when the lwp wakes up, in burst mode
* (ie, we decrease it n times).
*
* Note that hardclock updates l_estcpu and l_cpticks independently.
*
* -----------------------------------------------------------------------------
*
* Here we describe how l_estcpu is decreased.
*
* Constants for digital decay (filter):
* 90% of l_estcpu usage in (5 * loadavg) seconds
*
* We wish to decay away 90% of l_estcpu in (5 * loadavg) seconds. That is, we
* want to compute a value of decay such that the following loop:
* for (i = 0; i < (5 * loadavg); i++)
* l_estcpu *= decay;
* will result in
* l_estcpu *= 0.1;
* for all values of loadavg.
*
* Mathematically this loop can be expressed by saying:
* decay ** (5 * loadavg) ~= .1
*
* And finally, the corresponding value of decay we're using is:
* decay = (2 * loadavg) / (2 * loadavg + 1)
*
* -----------------------------------------------------------------------------
*
* Now, let's prove that the value of decay stated above will always fulfill
* the equation:
* decay ** (5 * loadavg) ~= .1
*
* If we compute b as:
* b = 2 * loadavg
* then
* decay = b / (b + 1)
*
* We now need to prove two things:
* 1) Given [factor ** (5 * loadavg) =~ .1], prove [factor == b/(b+1)].
* 2) Given [b/(b+1) ** power =~ .1], prove [power == (5 * loadavg)].
*
* Facts:
* * For x real: exp(x) = 0! + x**1/1! + x**2/2! + ...
* Therefore, for x close to zero, exp(x) =~ 1 + x.
* In turn, for b large enough, exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
*
* * For b large enough, (b-1)/b =~ b/(b+1).
*
* * For x belonging to [-1;1[, ln(1-x) = - x - x**2/2 - x**3/3 - ...
* Therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
*
* * ln(0.1) =~ -2.30
*
* Proof of (1):
* factor ** (5 * loadavg) =~ 0.1
* => ln(factor) =~ -2.30 / (5 * loadavg)
* => factor =~ exp(-1 / ((5 / 2.30) * loadavg))
* =~ exp(-1 / (2 * loadavg))
* =~ exp(-1 / b)
* =~ (b - 1) / b
* =~ b / (b + 1)
* =~ (2 * loadavg) / ((2 * loadavg) + 1)
*
* Proof of (2):
* (b / (b + 1)) ** power =~ .1
* => power * ln(b / (b + 1)) =~ -2.30
* => power * (-1 / (b + 1)) =~ -2.30
* => power =~ 2.30 * (b + 1)
* => power =~ 4.60 * loadavg + 2.30
* => power =~ 5 * loadavg
*
* Conclusion: decay = (2 * loadavg) / (2 * loadavg + 1)
*/
/* See calculations above */
#define loadfactor(loadavg) (2 * (loadavg))
static fixpt_t
decay_cpu(fixpt_t loadfac, fixpt_t estcpu)
{
if (estcpu == 0) {
return 0;
}
#if !defined(_LP64)
/* avoid 64bit arithmetics. */
#define FIXPT_MAX ((fixpt_t)((UINTMAX_C(1) << sizeof(fixpt_t) * CHAR_BIT) - 1))
if (__predict_true(loadfac <= FIXPT_MAX / ESTCPU_MAX)) {
return estcpu * loadfac / (loadfac + FSCALE);
}
#endif
return (uint64_t)estcpu * loadfac / (loadfac + FSCALE);
}
static fixpt_t
decay_cpu_batch(fixpt_t loadfac, fixpt_t estcpu, unsigned int n)
{
/*
* For all load averages >= 1 and max l_estcpu of (255 << ESTCPU_SHIFT),
* if we slept for at least seven times the loadfactor, we will decay
* l_estcpu to less than (1 << ESTCPU_SHIFT), and therefore we can
* return zero directly.
*
* Note that our ESTCPU_MAX is actually much smaller than
* (255 << ESTCPU_SHIFT).
*/
if ((n << FSHIFT) >= 7 * loadfac) {
return 0;
}
while (estcpu != 0 && n > 1) {
estcpu = decay_cpu(loadfac, estcpu);
n--;
}
return estcpu;
}
/*
* sched_pstats_hook:
*
* Periodically called from sched_pstats(); used to recalculate priorities.
*/
void
sched_pstats_hook(struct lwp *l, int batch)
{
fixpt_t loadfac;
/*
* If the LWP has slept an entire second, stop recalculating
* its priority until it wakes up.
*/
KASSERT(lwp_locked(l, NULL));
if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP ||
l->l_stat == LSSUSPENDED) {
if (l->l_slptime > 1) {
return;
}
}
loadfac = loadfactor(averunnable.ldavg[0]);
l->l_estcpu = decay_cpu(loadfac, l->l_estcpu);
resetpriority(l);
}
/*
* Recalculate the priority of an LWP after it has slept for a while.
*/
static void
updatepri(struct lwp *l)
{
fixpt_t loadfac;
KASSERT(lwp_locked(l, NULL));
KASSERT(l->l_slptime > 1);
loadfac = loadfactor(averunnable.ldavg[0]);
l->l_slptime--; /* the first time was done in sched_pstats */
l->l_estcpu = decay_cpu_batch(loadfac, l->l_estcpu, l->l_slptime);
resetpriority(l);
}
void
sched_rqinit(void)
{
}
void
sched_setrunnable(struct lwp *l)
{
if (l->l_slptime > 1)
updatepri(l);
}
void
sched_nice(struct proc *p, int n)
{
struct lwp *l;
KASSERT(mutex_owned(p->p_lock));
p->p_nice = n;
LIST_FOREACH(l, &p->p_lwps, l_sibling) {
lwp_lock(l);
resetpriority(l);
lwp_unlock(l);
}
}
/*
* Recompute the priority of an LWP. Arrange to reschedule if
* the resulting priority is better than that of the current LWP.
*/
static void
resetpriority(struct lwp *l)
{
pri_t pri;
struct proc *p = l->l_proc;
KASSERT(lwp_locked(l, NULL));
if (l->l_class != SCHED_OTHER)
return;
/* See comments above ESTCPU_SHIFT definition. */
pri = (PRI_KERNEL - 1) - (l->l_estcpu >> ESTCPU_SHIFT) - p->p_nice;
pri = imax(pri, 0);
if (pri != l->l_priority)
lwp_changepri(l, pri);
}
/*
* We adjust the priority of the current LWP. The priority of a LWP
* gets worse as it accumulates CPU time. The CPU usage estimator (l_estcpu)
* is increased here. The formula for computing priorities will compute a
* different value each time l_estcpu increases. This can cause a switch,
* but unless the priority crosses a PPQ boundary the actual queue will not
* change. The CPU usage estimator ramps up quite quickly when the process
* is running (linearly), and decays away exponentially, at a rate which is
* proportionally slower when the system is busy. The basic principle is
* that the system will 90% forget that the process used a lot of CPU time
* in (5 * loadavg) seconds. This causes the system to favor processes which
* haven't run much recently, and to round-robin among other processes.
*/
void
sched_schedclock(struct lwp *l)
{
if (l->l_class != SCHED_OTHER)
return;
KASSERT(!CURCPU_IDLE_P());
l->l_estcpu = ESTCPULIM(l->l_estcpu + ESTCPU_ACCUM);
lwp_lock(l);
resetpriority(l);
lwp_unlock(l);
}
/*
* sched_proc_fork:
*
* Inherit the parent's scheduler history.
*/
void
sched_proc_fork(struct proc *parent, struct proc *child)
{
lwp_t *pl;
KASSERT(mutex_owned(parent->p_lock));
pl = LIST_FIRST(&parent->p_lwps);
child->p_estcpu_inherited = pl->l_estcpu;
child->p_forktime = sched_pstats_ticks;
}
/*
* sched_proc_exit:
*
* Chargeback parents for the sins of their children.
*/
void
sched_proc_exit(struct proc *parent, struct proc *child)
{
fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
fixpt_t estcpu;
lwp_t *pl, *cl;
/* XXX Only if parent != init?? */
mutex_enter(parent->p_lock);
pl = LIST_FIRST(&parent->p_lwps);
cl = LIST_FIRST(&child->p_lwps);
estcpu = decay_cpu_batch(loadfac, child->p_estcpu_inherited,
sched_pstats_ticks - child->p_forktime);
if (cl->l_estcpu > estcpu) {
lwp_lock(pl);
pl->l_estcpu = ESTCPULIM(pl->l_estcpu + cl->l_estcpu - estcpu);
lwp_unlock(pl);
}
mutex_exit(parent->p_lock);
}
void
sched_wakeup(struct lwp *l)
{
}
void
sched_slept(struct lwp *l)
{
}
void
sched_lwp_fork(struct lwp *l1, struct lwp *l2)
{
l2->l_estcpu = l1->l_estcpu;
}
void
sched_lwp_collect(struct lwp *t)
{
lwp_t *l;
/* Absorb estcpu value of collected LWP. */
l = curlwp;
lwp_lock(l);
l->l_estcpu += t->l_estcpu;
lwp_unlock(l);
}
void
sched_oncpu(lwp_t *l)
{
}
void
sched_newts(lwp_t *l)
{
}
/*
* Sysctl nodes and initialization.
*/
static int
sysctl_sched_rtts(SYSCTLFN_ARGS)
{
struct sysctlnode node;
int rttsms = hztoms(sched_rrticks);
node = *rnode;
node.sysctl_data = &rttsms;
return sysctl_lookup(SYSCTLFN_CALL(&node));
}
SYSCTL_SETUP(sysctl_sched_4bsd_setup, "sysctl sched setup")
{
const struct sysctlnode *node = NULL;
sysctl_createv(clog, 0, NULL, &node,
CTLFLAG_PERMANENT,
CTLTYPE_NODE, "sched",
SYSCTL_DESCR("Scheduler options"),
NULL, 0, NULL, 0,
CTL_KERN, CTL_CREATE, CTL_EOL);
if (node == NULL)
return;
sched_rrticks = hz / 10;
sysctl_createv(NULL, 0, &node, NULL,
CTLFLAG_PERMANENT,
CTLTYPE_STRING, "name", NULL,
NULL, 0, __UNCONST("4.4BSD"), 0,
CTL_CREATE, CTL_EOL);
sysctl_createv(NULL, 0, &node, NULL,
CTLFLAG_PERMANENT,
CTLTYPE_INT, "rtts",
SYSCTL_DESCR("Round-robin time quantum (in milliseconds)"),
sysctl_sched_rtts, 0, NULL, 0,
CTL_CREATE, CTL_EOL);
}