135e6168fSJeff Roberson /*- 215dc847eSJeff Roberson * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org> 335e6168fSJeff Roberson * All rights reserved. 435e6168fSJeff Roberson * 535e6168fSJeff Roberson * Redistribution and use in source and binary forms, with or without 635e6168fSJeff Roberson * modification, are permitted provided that the following conditions 735e6168fSJeff Roberson * are met: 835e6168fSJeff Roberson * 1. Redistributions of source code must retain the above copyright 935e6168fSJeff Roberson * notice unmodified, this list of conditions, and the following 1035e6168fSJeff Roberson * disclaimer. 1135e6168fSJeff Roberson * 2. Redistributions in binary form must reproduce the above copyright 1235e6168fSJeff Roberson * notice, this list of conditions and the following disclaimer in the 1335e6168fSJeff Roberson * documentation and/or other materials provided with the distribution. 1435e6168fSJeff Roberson * 1535e6168fSJeff Roberson * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1635e6168fSJeff Roberson * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1735e6168fSJeff Roberson * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1835e6168fSJeff Roberson * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1935e6168fSJeff Roberson * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2035e6168fSJeff Roberson * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2135e6168fSJeff Roberson * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2235e6168fSJeff Roberson * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2335e6168fSJeff Roberson * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2435e6168fSJeff Roberson * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2535e6168fSJeff Roberson */ 2635e6168fSJeff Roberson 27677b542eSDavid E. O'Brien #include <sys/cdefs.h> 28677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$"); 29677b542eSDavid E. O'Brien 3035e6168fSJeff Roberson #include <sys/param.h> 3135e6168fSJeff Roberson #include <sys/systm.h> 3235e6168fSJeff Roberson #include <sys/kernel.h> 3335e6168fSJeff Roberson #include <sys/ktr.h> 3435e6168fSJeff Roberson #include <sys/lock.h> 3535e6168fSJeff Roberson #include <sys/mutex.h> 3635e6168fSJeff Roberson #include <sys/proc.h> 37245f3abfSJeff Roberson #include <sys/resource.h> 3835e6168fSJeff Roberson #include <sys/sched.h> 3935e6168fSJeff Roberson #include <sys/smp.h> 4035e6168fSJeff Roberson #include <sys/sx.h> 4135e6168fSJeff Roberson #include <sys/sysctl.h> 4235e6168fSJeff Roberson #include <sys/sysproto.h> 4335e6168fSJeff Roberson #include <sys/vmmeter.h> 4435e6168fSJeff Roberson #ifdef DDB 4535e6168fSJeff Roberson #include <ddb/ddb.h> 4635e6168fSJeff Roberson #endif 4735e6168fSJeff Roberson #ifdef KTRACE 4835e6168fSJeff Roberson #include <sys/uio.h> 4935e6168fSJeff Roberson #include <sys/ktrace.h> 5035e6168fSJeff Roberson #endif 5135e6168fSJeff Roberson 5235e6168fSJeff Roberson #include <machine/cpu.h> 5335e6168fSJeff Roberson 5415dc847eSJeff Roberson #define KTR_ULE KTR_NFS 5515dc847eSJeff Roberson 5635e6168fSJeff Roberson /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 5735e6168fSJeff Roberson /* XXX This is bogus compatability crap for ps */ 5835e6168fSJeff Roberson static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 5935e6168fSJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 6035e6168fSJeff Roberson 6135e6168fSJeff Roberson static void sched_setup(void *dummy); 6235e6168fSJeff Roberson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 6335e6168fSJeff Roberson 6415dc847eSJeff Roberson static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED"); 65e1f89c22SJeff Roberson 6615dc847eSJeff Roberson static int sched_strict; 6715dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, ""); 6815dc847eSJeff Roberson 6915dc847eSJeff Roberson static int slice_min = 1; 7015dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, ""); 7115dc847eSJeff Roberson 72210491d3SJeff Roberson static int slice_max = 10; 7315dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, ""); 7415dc847eSJeff Roberson 7515dc847eSJeff Roberson int realstathz; 7615dc847eSJeff Roberson int tickincr = 1; 77783caefbSJeff Roberson 78356500a3SJeff Roberson #ifdef SMP 79356500a3SJeff Roberson /* Callout to handle load balancing SMP systems. */ 80356500a3SJeff Roberson static struct callout kseq_lb_callout; 81356500a3SJeff Roberson #endif 82356500a3SJeff Roberson 8335e6168fSJeff Roberson /* 8435e6168fSJeff Roberson * These datastructures are allocated within their parent datastructure but 8535e6168fSJeff Roberson * are scheduler specific. 8635e6168fSJeff Roberson */ 8735e6168fSJeff Roberson 8835e6168fSJeff Roberson struct ke_sched { 8935e6168fSJeff Roberson int ske_slice; 9035e6168fSJeff Roberson struct runq *ske_runq; 9135e6168fSJeff Roberson /* The following variables are only used for pctcpu calculation */ 9235e6168fSJeff Roberson int ske_ltick; /* Last tick that we were running on */ 9335e6168fSJeff Roberson int ske_ftick; /* First tick that we were running on */ 9435e6168fSJeff Roberson int ske_ticks; /* Tick count */ 9515dc847eSJeff Roberson /* CPU that we have affinity for. */ 96cd6e33dfSJeff Roberson u_char ske_cpu; 9735e6168fSJeff Roberson }; 9835e6168fSJeff Roberson #define ke_slice ke_sched->ske_slice 9935e6168fSJeff Roberson #define ke_runq ke_sched->ske_runq 10035e6168fSJeff Roberson #define ke_ltick ke_sched->ske_ltick 10135e6168fSJeff Roberson #define ke_ftick ke_sched->ske_ftick 10235e6168fSJeff Roberson #define ke_ticks ke_sched->ske_ticks 103cd6e33dfSJeff Roberson #define ke_cpu ke_sched->ske_cpu 10435e6168fSJeff Roberson 10535e6168fSJeff Roberson struct kg_sched { 106407b0157SJeff Roberson int skg_slptime; /* Number of ticks we vol. slept */ 107407b0157SJeff Roberson int skg_runtime; /* Number of ticks we were running */ 10835e6168fSJeff Roberson }; 10935e6168fSJeff Roberson #define kg_slptime kg_sched->skg_slptime 110407b0157SJeff Roberson #define kg_runtime kg_sched->skg_runtime 11135e6168fSJeff Roberson 11235e6168fSJeff Roberson struct td_sched { 11335e6168fSJeff Roberson int std_slptime; 11435e6168fSJeff Roberson }; 11535e6168fSJeff Roberson #define td_slptime td_sched->std_slptime 11635e6168fSJeff Roberson 1175d7ef00cSJeff Roberson struct td_sched td_sched; 11835e6168fSJeff Roberson struct ke_sched ke_sched; 11935e6168fSJeff Roberson struct kg_sched kg_sched; 12035e6168fSJeff Roberson 12135e6168fSJeff Roberson struct ke_sched *kse0_sched = &ke_sched; 12235e6168fSJeff Roberson struct kg_sched *ksegrp0_sched = &kg_sched; 12335e6168fSJeff Roberson struct p_sched *proc0_sched = NULL; 12435e6168fSJeff Roberson struct td_sched *thread0_sched = &td_sched; 12535e6168fSJeff Roberson 12635e6168fSJeff Roberson /* 12735e6168fSJeff Roberson * This priority range has 20 priorities on either end that are reachable 12835e6168fSJeff Roberson * only through nice values. 129e1f89c22SJeff Roberson * 130e1f89c22SJeff Roberson * PRI_RANGE: Total priority range for timeshare threads. 131e1f89c22SJeff Roberson * PRI_NRESV: Reserved priorities for nice. 132e1f89c22SJeff Roberson * PRI_BASE: The start of the dynamic range. 133e1f89c22SJeff Roberson * DYN_RANGE: Number of priorities that are available int the dynamic 134e1f89c22SJeff Roberson * priority range. 13535e6168fSJeff Roberson */ 136407b0157SJeff Roberson #define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1) 137245f3abfSJeff Roberson #define SCHED_PRI_NRESV PRIO_TOTAL 13898c9b132SJeff Roberson #define SCHED_PRI_NHALF (PRIO_TOTAL / 2) 13915dc847eSJeff Roberson #define SCHED_PRI_NTHRESH (SCHED_PRI_NHALF - 1) 140e1f89c22SJeff Roberson #define SCHED_PRI_BASE ((SCHED_PRI_NRESV / 2) + PRI_MIN_TIMESHARE) 141e1f89c22SJeff Roberson #define SCHED_DYN_RANGE (SCHED_PRI_RANGE - SCHED_PRI_NRESV) 14215dc847eSJeff Roberson #define SCHED_PRI_INTERACT(score) \ 143210491d3SJeff Roberson ((score) * SCHED_DYN_RANGE / SCHED_INTERACT_MAX) 14435e6168fSJeff Roberson 14535e6168fSJeff Roberson /* 146e1f89c22SJeff Roberson * These determine the interactivity of a process. 14735e6168fSJeff Roberson * 148407b0157SJeff Roberson * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate 149407b0157SJeff Roberson * before throttling back. 150e1f89c22SJeff Roberson * SLP_RUN_THROTTLE: Divisor for reducing slp/run time. 151210491d3SJeff Roberson * INTERACT_MAX: Maximum interactivity value. Smaller is better. 152e1f89c22SJeff Roberson * INTERACT_THRESH: Threshhold for placement on the current runq. 15335e6168fSJeff Roberson */ 1544b60e324SJeff Roberson #define SCHED_SLP_RUN_MAX ((hz * 2) << 10) 1553c124732SJeff Roberson #define SCHED_SLP_RUN_THROTTLE (2) 156210491d3SJeff Roberson #define SCHED_INTERACT_MAX (100) 157210491d3SJeff Roberson #define SCHED_INTERACT_HALF (SCHED_INTERACT_MAX / 2) 158210491d3SJeff Roberson #define SCHED_INTERACT_THRESH (20) 159e1f89c22SJeff Roberson 16035e6168fSJeff Roberson /* 16135e6168fSJeff Roberson * These parameters and macros determine the size of the time slice that is 16235e6168fSJeff Roberson * granted to each thread. 16335e6168fSJeff Roberson * 16435e6168fSJeff Roberson * SLICE_MIN: Minimum time slice granted, in units of ticks. 16535e6168fSJeff Roberson * SLICE_MAX: Maximum time slice granted. 16635e6168fSJeff Roberson * SLICE_RANGE: Range of available time slices scaled by hz. 167245f3abfSJeff Roberson * SLICE_SCALE: The number slices granted per val in the range of [0, max]. 168245f3abfSJeff Roberson * SLICE_NICE: Determine the amount of slice granted to a scaled nice. 16935e6168fSJeff Roberson */ 17015dc847eSJeff Roberson #define SCHED_SLICE_MIN (slice_min) 17115dc847eSJeff Roberson #define SCHED_SLICE_MAX (slice_max) 17235e6168fSJeff Roberson #define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1) 17335e6168fSJeff Roberson #define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max)) 174245f3abfSJeff Roberson #define SCHED_SLICE_NICE(nice) \ 17515dc847eSJeff Roberson (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH)) 17635e6168fSJeff Roberson 17735e6168fSJeff Roberson /* 17835e6168fSJeff Roberson * This macro determines whether or not the kse belongs on the current or 17935e6168fSJeff Roberson * next run queue. 180407b0157SJeff Roberson * 181407b0157SJeff Roberson * XXX nice value should effect how interactive a kg is. 18235e6168fSJeff Roberson */ 18315dc847eSJeff Roberson #define SCHED_INTERACTIVE(kg) \ 18415dc847eSJeff Roberson (sched_interact_score(kg) < SCHED_INTERACT_THRESH) 185a5f099d0SJeff Roberson #define SCHED_CURR(kg, ke) \ 18615dc847eSJeff Roberson (ke->ke_thread->td_priority < PRI_MIN_TIMESHARE || SCHED_INTERACTIVE(kg)) 18735e6168fSJeff Roberson 18835e6168fSJeff Roberson /* 18935e6168fSJeff Roberson * Cpu percentage computation macros and defines. 19035e6168fSJeff Roberson * 19135e6168fSJeff Roberson * SCHED_CPU_TIME: Number of seconds to average the cpu usage across. 19235e6168fSJeff Roberson * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across. 19335e6168fSJeff Roberson */ 19435e6168fSJeff Roberson 1955053d272SJeff Roberson #define SCHED_CPU_TIME 10 19635e6168fSJeff Roberson #define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME) 19735e6168fSJeff Roberson 19835e6168fSJeff Roberson /* 19915dc847eSJeff Roberson * kseq - per processor runqs and statistics. 20035e6168fSJeff Roberson */ 20135e6168fSJeff Roberson 20215dc847eSJeff Roberson #define KSEQ_NCLASS (PRI_IDLE + 1) /* Number of run classes. */ 20315dc847eSJeff Roberson 20435e6168fSJeff Roberson struct kseq { 205a8949de2SJeff Roberson struct runq ksq_idle; /* Queue of IDLE threads. */ 20615dc847eSJeff Roberson struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */ 20715dc847eSJeff Roberson struct runq *ksq_next; /* Next timeshare queue. */ 20815dc847eSJeff Roberson struct runq *ksq_curr; /* Current queue. */ 20915dc847eSJeff Roberson int ksq_loads[KSEQ_NCLASS]; /* Load for each class */ 21015dc847eSJeff Roberson int ksq_load; /* Aggregate load. */ 21115dc847eSJeff Roberson short ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */ 21215dc847eSJeff Roberson short ksq_nicemin; /* Least nice. */ 2135d7ef00cSJeff Roberson #ifdef SMP 2145d7ef00cSJeff Roberson unsigned int ksq_rslices; /* Slices on run queue */ 2155d7ef00cSJeff Roberson #endif 21635e6168fSJeff Roberson }; 21735e6168fSJeff Roberson 21835e6168fSJeff Roberson /* 21935e6168fSJeff Roberson * One kse queue per processor. 22035e6168fSJeff Roberson */ 2210a016a05SJeff Roberson #ifdef SMP 22235e6168fSJeff Roberson struct kseq kseq_cpu[MAXCPU]; 2230a016a05SJeff Roberson #define KSEQ_SELF() (&kseq_cpu[PCPU_GET(cpuid)]) 2240a016a05SJeff Roberson #define KSEQ_CPU(x) (&kseq_cpu[(x)]) 2250a016a05SJeff Roberson #else 2260a016a05SJeff Roberson struct kseq kseq_cpu; 2270a016a05SJeff Roberson #define KSEQ_SELF() (&kseq_cpu) 2280a016a05SJeff Roberson #define KSEQ_CPU(x) (&kseq_cpu) 2290a016a05SJeff Roberson #endif 23035e6168fSJeff Roberson 231245f3abfSJeff Roberson static void sched_slice(struct kse *ke); 23215dc847eSJeff Roberson static void sched_priority(struct ksegrp *kg); 233e1f89c22SJeff Roberson static int sched_interact_score(struct ksegrp *kg); 2344b60e324SJeff Roberson static void sched_interact_update(struct ksegrp *kg); 23535e6168fSJeff Roberson void sched_pctcpu_update(struct kse *ke); 23635e6168fSJeff Roberson int sched_pickcpu(void); 23735e6168fSJeff Roberson 2385d7ef00cSJeff Roberson /* Operations on per processor queues */ 2390a016a05SJeff Roberson static struct kse * kseq_choose(struct kseq *kseq); 2400a016a05SJeff Roberson static void kseq_setup(struct kseq *kseq); 241a8949de2SJeff Roberson static void kseq_add(struct kseq *kseq, struct kse *ke); 24215dc847eSJeff Roberson static void kseq_rem(struct kseq *kseq, struct kse *ke); 24315dc847eSJeff Roberson static void kseq_nice_add(struct kseq *kseq, int nice); 24415dc847eSJeff Roberson static void kseq_nice_rem(struct kseq *kseq, int nice); 2457cd650a9SJeff Roberson void kseq_print(int cpu); 2465d7ef00cSJeff Roberson #ifdef SMP 2475d7ef00cSJeff Roberson struct kseq * kseq_load_highest(void); 248356500a3SJeff Roberson void kseq_balance(void *arg); 249356500a3SJeff Roberson void kseq_move(struct kseq *from, int cpu); 2505d7ef00cSJeff Roberson #endif 2515d7ef00cSJeff Roberson 25215dc847eSJeff Roberson void 2537cd650a9SJeff Roberson kseq_print(int cpu) 25415dc847eSJeff Roberson { 2557cd650a9SJeff Roberson struct kseq *kseq; 25615dc847eSJeff Roberson int i; 25715dc847eSJeff Roberson 2587cd650a9SJeff Roberson kseq = KSEQ_CPU(cpu); 25915dc847eSJeff Roberson 26015dc847eSJeff Roberson printf("kseq:\n"); 26115dc847eSJeff Roberson printf("\tload: %d\n", kseq->ksq_load); 26215dc847eSJeff Roberson printf("\tload ITHD: %d\n", kseq->ksq_loads[PRI_ITHD]); 26315dc847eSJeff Roberson printf("\tload REALTIME: %d\n", kseq->ksq_loads[PRI_REALTIME]); 26415dc847eSJeff Roberson printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]); 26515dc847eSJeff Roberson printf("\tload IDLE: %d\n", kseq->ksq_loads[PRI_IDLE]); 26615dc847eSJeff Roberson printf("\tnicemin:\t%d\n", kseq->ksq_nicemin); 26715dc847eSJeff Roberson printf("\tnice counts:\n"); 26815dc847eSJeff Roberson for (i = 0; i < PRIO_TOTAL + 1; i++) 26915dc847eSJeff Roberson if (kseq->ksq_nice[i]) 27015dc847eSJeff Roberson printf("\t\t%d = %d\n", 27115dc847eSJeff Roberson i - SCHED_PRI_NHALF, kseq->ksq_nice[i]); 27215dc847eSJeff Roberson } 27315dc847eSJeff Roberson 274a8949de2SJeff Roberson static void 2755d7ef00cSJeff Roberson kseq_add(struct kseq *kseq, struct kse *ke) 2765d7ef00cSJeff Roberson { 277b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 278b5c4c4a7SJeff Roberson kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++; 27915dc847eSJeff Roberson kseq->ksq_load++; 28015dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 28115dc847eSJeff Roberson CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))", 28215dc847eSJeff Roberson ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority, 28315dc847eSJeff Roberson ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin); 28415dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 28515dc847eSJeff Roberson kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice); 2865d7ef00cSJeff Roberson #ifdef SMP 2875d7ef00cSJeff Roberson kseq->ksq_rslices += ke->ke_slice; 2885d7ef00cSJeff Roberson #endif 2895d7ef00cSJeff Roberson } 29015dc847eSJeff Roberson 291a8949de2SJeff Roberson static void 2925d7ef00cSJeff Roberson kseq_rem(struct kseq *kseq, struct kse *ke) 2935d7ef00cSJeff Roberson { 294b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 295b5c4c4a7SJeff Roberson kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--; 29615dc847eSJeff Roberson kseq->ksq_load--; 29715dc847eSJeff Roberson ke->ke_runq = NULL; 29815dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 29915dc847eSJeff Roberson kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice); 3005d7ef00cSJeff Roberson #ifdef SMP 3015d7ef00cSJeff Roberson kseq->ksq_rslices -= ke->ke_slice; 3025d7ef00cSJeff Roberson #endif 3035d7ef00cSJeff Roberson } 3045d7ef00cSJeff Roberson 30515dc847eSJeff Roberson static void 30615dc847eSJeff Roberson kseq_nice_add(struct kseq *kseq, int nice) 30715dc847eSJeff Roberson { 308b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 30915dc847eSJeff Roberson /* Normalize to zero. */ 31015dc847eSJeff Roberson kseq->ksq_nice[nice + SCHED_PRI_NHALF]++; 311b90816f1SJeff Roberson if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1) 31215dc847eSJeff Roberson kseq->ksq_nicemin = nice; 31315dc847eSJeff Roberson } 31415dc847eSJeff Roberson 31515dc847eSJeff Roberson static void 31615dc847eSJeff Roberson kseq_nice_rem(struct kseq *kseq, int nice) 31715dc847eSJeff Roberson { 31815dc847eSJeff Roberson int n; 31915dc847eSJeff Roberson 320b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 32115dc847eSJeff Roberson /* Normalize to zero. */ 32215dc847eSJeff Roberson n = nice + SCHED_PRI_NHALF; 32315dc847eSJeff Roberson kseq->ksq_nice[n]--; 32415dc847eSJeff Roberson KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count.")); 32515dc847eSJeff Roberson 32615dc847eSJeff Roberson /* 32715dc847eSJeff Roberson * If this wasn't the smallest nice value or there are more in 32815dc847eSJeff Roberson * this bucket we can just return. Otherwise we have to recalculate 32915dc847eSJeff Roberson * the smallest nice. 33015dc847eSJeff Roberson */ 33115dc847eSJeff Roberson if (nice != kseq->ksq_nicemin || 33215dc847eSJeff Roberson kseq->ksq_nice[n] != 0 || 33315dc847eSJeff Roberson kseq->ksq_loads[PRI_TIMESHARE] == 0) 33415dc847eSJeff Roberson return; 33515dc847eSJeff Roberson 33615dc847eSJeff Roberson for (; n < SCHED_PRI_NRESV + 1; n++) 33715dc847eSJeff Roberson if (kseq->ksq_nice[n]) { 33815dc847eSJeff Roberson kseq->ksq_nicemin = n - SCHED_PRI_NHALF; 33915dc847eSJeff Roberson return; 34015dc847eSJeff Roberson } 34115dc847eSJeff Roberson } 34215dc847eSJeff Roberson 3435d7ef00cSJeff Roberson #ifdef SMP 344356500a3SJeff Roberson /* 345356500a3SJeff Roberson * kseq_balance is a simple CPU load balancing algorithm. It operates by 346356500a3SJeff Roberson * finding the least loaded and most loaded cpu and equalizing their load 347356500a3SJeff Roberson * by migrating some processes. 348356500a3SJeff Roberson * 349356500a3SJeff Roberson * Dealing only with two CPUs at a time has two advantages. Firstly, most 350356500a3SJeff Roberson * installations will only have 2 cpus. Secondly, load balancing too much at 351356500a3SJeff Roberson * once can have an unpleasant effect on the system. The scheduler rarely has 352356500a3SJeff Roberson * enough information to make perfect decisions. So this algorithm chooses 353356500a3SJeff Roberson * algorithm simplicity and more gradual effects on load in larger systems. 354356500a3SJeff Roberson * 355356500a3SJeff Roberson * It could be improved by considering the priorities and slices assigned to 356356500a3SJeff Roberson * each task prior to balancing them. There are many pathological cases with 357356500a3SJeff Roberson * any approach and so the semi random algorithm below may work as well as any. 358356500a3SJeff Roberson * 359356500a3SJeff Roberson */ 360356500a3SJeff Roberson void 361356500a3SJeff Roberson kseq_balance(void *arg) 362356500a3SJeff Roberson { 363356500a3SJeff Roberson struct kseq *kseq; 364356500a3SJeff Roberson int high_load; 365356500a3SJeff Roberson int low_load; 366356500a3SJeff Roberson int high_cpu; 367356500a3SJeff Roberson int low_cpu; 368356500a3SJeff Roberson int move; 369356500a3SJeff Roberson int diff; 370356500a3SJeff Roberson int i; 371356500a3SJeff Roberson 372356500a3SJeff Roberson high_cpu = 0; 373356500a3SJeff Roberson low_cpu = 0; 374356500a3SJeff Roberson high_load = 0; 375356500a3SJeff Roberson low_load = -1; 376356500a3SJeff Roberson 377356500a3SJeff Roberson mtx_lock_spin(&sched_lock); 378356500a3SJeff Roberson for (i = 0; i < mp_maxid; i++) { 379356500a3SJeff Roberson if (CPU_ABSENT(i)) 380356500a3SJeff Roberson continue; 381356500a3SJeff Roberson kseq = KSEQ_CPU(i); 382356500a3SJeff Roberson if (kseq->ksq_load > high_load) { 383356500a3SJeff Roberson high_load = kseq->ksq_load; 384356500a3SJeff Roberson high_cpu = i; 385356500a3SJeff Roberson } 386356500a3SJeff Roberson if (low_load == -1 || kseq->ksq_load < low_load) { 387356500a3SJeff Roberson low_load = kseq->ksq_load; 388356500a3SJeff Roberson low_cpu = i; 389356500a3SJeff Roberson } 390356500a3SJeff Roberson } 391356500a3SJeff Roberson 392356500a3SJeff Roberson /* 393356500a3SJeff Roberson * Nothing to do. 394356500a3SJeff Roberson */ 395356500a3SJeff Roberson if (high_load < 2 || low_load == high_load) 396356500a3SJeff Roberson goto out; 397356500a3SJeff Roberson 398356500a3SJeff Roberson diff = high_load - low_load; 399356500a3SJeff Roberson move = diff / 2; 400356500a3SJeff Roberson if (diff & 0x1) 401356500a3SJeff Roberson move++; 402356500a3SJeff Roberson 403356500a3SJeff Roberson for (i = 0; i < move; i++) 404356500a3SJeff Roberson kseq_move(KSEQ_CPU(high_cpu), low_cpu); 405356500a3SJeff Roberson 406356500a3SJeff Roberson out: 407356500a3SJeff Roberson mtx_unlock_spin(&sched_lock); 408356500a3SJeff Roberson callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL); 409356500a3SJeff Roberson 410356500a3SJeff Roberson return; 411356500a3SJeff Roberson } 412356500a3SJeff Roberson 4135d7ef00cSJeff Roberson struct kseq * 4145d7ef00cSJeff Roberson kseq_load_highest(void) 4155d7ef00cSJeff Roberson { 4165d7ef00cSJeff Roberson struct kseq *kseq; 4175d7ef00cSJeff Roberson int load; 4185d7ef00cSJeff Roberson int cpu; 4195d7ef00cSJeff Roberson int i; 4205d7ef00cSJeff Roberson 421b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 4225d7ef00cSJeff Roberson cpu = 0; 4235d7ef00cSJeff Roberson load = 0; 4245d7ef00cSJeff Roberson 4255d7ef00cSJeff Roberson for (i = 0; i < mp_maxid; i++) { 4265d7ef00cSJeff Roberson if (CPU_ABSENT(i)) 4275d7ef00cSJeff Roberson continue; 4285d7ef00cSJeff Roberson kseq = KSEQ_CPU(i); 42915dc847eSJeff Roberson if (kseq->ksq_load > load) { 43015dc847eSJeff Roberson load = kseq->ksq_load; 4315d7ef00cSJeff Roberson cpu = i; 4325d7ef00cSJeff Roberson } 4335d7ef00cSJeff Roberson } 43458177de2SJeff Roberson if (load > 1) 4355d7ef00cSJeff Roberson return (KSEQ_CPU(cpu)); 4365d7ef00cSJeff Roberson 4375d7ef00cSJeff Roberson return (NULL); 4385d7ef00cSJeff Roberson } 439356500a3SJeff Roberson 440356500a3SJeff Roberson void 441356500a3SJeff Roberson kseq_move(struct kseq *from, int cpu) 442356500a3SJeff Roberson { 443356500a3SJeff Roberson struct kse *ke; 444356500a3SJeff Roberson 445356500a3SJeff Roberson ke = kseq_choose(from); 446356500a3SJeff Roberson runq_remove(ke->ke_runq, ke); 447356500a3SJeff Roberson ke->ke_state = KES_THREAD; 448356500a3SJeff Roberson kseq_rem(from, ke); 449356500a3SJeff Roberson 450356500a3SJeff Roberson ke->ke_cpu = cpu; 451356500a3SJeff Roberson sched_add(ke); 452356500a3SJeff Roberson } 4535d7ef00cSJeff Roberson #endif 4545d7ef00cSJeff Roberson 4555d7ef00cSJeff Roberson struct kse * 4565d7ef00cSJeff Roberson kseq_choose(struct kseq *kseq) 4575d7ef00cSJeff Roberson { 4585d7ef00cSJeff Roberson struct kse *ke; 4595d7ef00cSJeff Roberson struct runq *swap; 4605d7ef00cSJeff Roberson 461b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 46215dc847eSJeff Roberson swap = NULL; 463a8949de2SJeff Roberson 46415dc847eSJeff Roberson for (;;) { 46515dc847eSJeff Roberson ke = runq_choose(kseq->ksq_curr); 46615dc847eSJeff Roberson if (ke == NULL) { 46715dc847eSJeff Roberson /* 46815dc847eSJeff Roberson * We already swaped once and didn't get anywhere. 46915dc847eSJeff Roberson */ 47015dc847eSJeff Roberson if (swap) 47115dc847eSJeff Roberson break; 4725d7ef00cSJeff Roberson swap = kseq->ksq_curr; 4735d7ef00cSJeff Roberson kseq->ksq_curr = kseq->ksq_next; 4745d7ef00cSJeff Roberson kseq->ksq_next = swap; 47515dc847eSJeff Roberson continue; 476a8949de2SJeff Roberson } 47715dc847eSJeff Roberson /* 47815dc847eSJeff Roberson * If we encounter a slice of 0 the kse is in a 47915dc847eSJeff Roberson * TIMESHARE kse group and its nice was too far out 48015dc847eSJeff Roberson * of the range that receives slices. 48115dc847eSJeff Roberson */ 48215dc847eSJeff Roberson if (ke->ke_slice == 0) { 48315dc847eSJeff Roberson runq_remove(ke->ke_runq, ke); 48415dc847eSJeff Roberson sched_slice(ke); 48515dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 48615dc847eSJeff Roberson runq_add(ke->ke_runq, ke); 48715dc847eSJeff Roberson continue; 48815dc847eSJeff Roberson } 48915dc847eSJeff Roberson return (ke); 49015dc847eSJeff Roberson } 49115dc847eSJeff Roberson 492a8949de2SJeff Roberson return (runq_choose(&kseq->ksq_idle)); 493245f3abfSJeff Roberson } 4940a016a05SJeff Roberson 4950a016a05SJeff Roberson static void 4960a016a05SJeff Roberson kseq_setup(struct kseq *kseq) 4970a016a05SJeff Roberson { 49815dc847eSJeff Roberson runq_init(&kseq->ksq_timeshare[0]); 49915dc847eSJeff Roberson runq_init(&kseq->ksq_timeshare[1]); 500a8949de2SJeff Roberson runq_init(&kseq->ksq_idle); 50115dc847eSJeff Roberson 50215dc847eSJeff Roberson kseq->ksq_curr = &kseq->ksq_timeshare[0]; 50315dc847eSJeff Roberson kseq->ksq_next = &kseq->ksq_timeshare[1]; 50415dc847eSJeff Roberson 50515dc847eSJeff Roberson kseq->ksq_loads[PRI_ITHD] = 0; 50615dc847eSJeff Roberson kseq->ksq_loads[PRI_REALTIME] = 0; 50715dc847eSJeff Roberson kseq->ksq_loads[PRI_TIMESHARE] = 0; 50815dc847eSJeff Roberson kseq->ksq_loads[PRI_IDLE] = 0; 5097cd650a9SJeff Roberson kseq->ksq_load = 0; 5105d7ef00cSJeff Roberson #ifdef SMP 5115d7ef00cSJeff Roberson kseq->ksq_rslices = 0; 5125d7ef00cSJeff Roberson #endif 5130a016a05SJeff Roberson } 5140a016a05SJeff Roberson 51535e6168fSJeff Roberson static void 51635e6168fSJeff Roberson sched_setup(void *dummy) 51735e6168fSJeff Roberson { 51835e6168fSJeff Roberson int i; 51935e6168fSJeff Roberson 52015dc847eSJeff Roberson slice_min = (hz/100); 52115dc847eSJeff Roberson slice_max = (hz/10); 522e1f89c22SJeff Roberson 52335e6168fSJeff Roberson mtx_lock_spin(&sched_lock); 52435e6168fSJeff Roberson /* init kseqs */ 5250a016a05SJeff Roberson for (i = 0; i < MAXCPU; i++) 5260a016a05SJeff Roberson kseq_setup(KSEQ_CPU(i)); 52715dc847eSJeff Roberson 52815dc847eSJeff Roberson kseq_add(KSEQ_SELF(), &kse0); 52935e6168fSJeff Roberson mtx_unlock_spin(&sched_lock); 530356500a3SJeff Roberson #ifdef SMP 531356500a3SJeff Roberson callout_init(&kseq_lb_callout, 1); 532356500a3SJeff Roberson kseq_balance(NULL); 533356500a3SJeff Roberson #endif 53435e6168fSJeff Roberson } 53535e6168fSJeff Roberson 53635e6168fSJeff Roberson /* 53735e6168fSJeff Roberson * Scale the scheduling priority according to the "interactivity" of this 53835e6168fSJeff Roberson * process. 53935e6168fSJeff Roberson */ 54015dc847eSJeff Roberson static void 54135e6168fSJeff Roberson sched_priority(struct ksegrp *kg) 54235e6168fSJeff Roberson { 54335e6168fSJeff Roberson int pri; 54435e6168fSJeff Roberson 54535e6168fSJeff Roberson if (kg->kg_pri_class != PRI_TIMESHARE) 54615dc847eSJeff Roberson return; 54735e6168fSJeff Roberson 54815dc847eSJeff Roberson pri = SCHED_PRI_INTERACT(sched_interact_score(kg)); 549e1f89c22SJeff Roberson pri += SCHED_PRI_BASE; 55035e6168fSJeff Roberson pri += kg->kg_nice; 55135e6168fSJeff Roberson 55235e6168fSJeff Roberson if (pri > PRI_MAX_TIMESHARE) 55335e6168fSJeff Roberson pri = PRI_MAX_TIMESHARE; 55435e6168fSJeff Roberson else if (pri < PRI_MIN_TIMESHARE) 55535e6168fSJeff Roberson pri = PRI_MIN_TIMESHARE; 55635e6168fSJeff Roberson 55735e6168fSJeff Roberson kg->kg_user_pri = pri; 55835e6168fSJeff Roberson 55915dc847eSJeff Roberson return; 56035e6168fSJeff Roberson } 56135e6168fSJeff Roberson 56235e6168fSJeff Roberson /* 563245f3abfSJeff Roberson * Calculate a time slice based on the properties of the kseg and the runq 564a8949de2SJeff Roberson * that we're on. This is only for PRI_TIMESHARE ksegrps. 56535e6168fSJeff Roberson */ 566245f3abfSJeff Roberson static void 567245f3abfSJeff Roberson sched_slice(struct kse *ke) 56835e6168fSJeff Roberson { 56915dc847eSJeff Roberson struct kseq *kseq; 570245f3abfSJeff Roberson struct ksegrp *kg; 57135e6168fSJeff Roberson 572245f3abfSJeff Roberson kg = ke->ke_ksegrp; 57315dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 57435e6168fSJeff Roberson 575245f3abfSJeff Roberson /* 576245f3abfSJeff Roberson * Rationale: 577245f3abfSJeff Roberson * KSEs in interactive ksegs get the minimum slice so that we 578245f3abfSJeff Roberson * quickly notice if it abuses its advantage. 579245f3abfSJeff Roberson * 580245f3abfSJeff Roberson * KSEs in non-interactive ksegs are assigned a slice that is 581245f3abfSJeff Roberson * based on the ksegs nice value relative to the least nice kseg 582245f3abfSJeff Roberson * on the run queue for this cpu. 583245f3abfSJeff Roberson * 584245f3abfSJeff Roberson * If the KSE is less nice than all others it gets the maximum 585245f3abfSJeff Roberson * slice and other KSEs will adjust their slice relative to 586245f3abfSJeff Roberson * this when they first expire. 587245f3abfSJeff Roberson * 588245f3abfSJeff Roberson * There is 20 point window that starts relative to the least 589245f3abfSJeff Roberson * nice kse on the run queue. Slice size is determined by 590245f3abfSJeff Roberson * the kse distance from the last nice ksegrp. 591245f3abfSJeff Roberson * 592245f3abfSJeff Roberson * If you are outside of the window you will get no slice and 593245f3abfSJeff Roberson * you will be reevaluated each time you are selected on the 594245f3abfSJeff Roberson * run queue. 595245f3abfSJeff Roberson * 596245f3abfSJeff Roberson */ 597245f3abfSJeff Roberson 59815dc847eSJeff Roberson if (!SCHED_INTERACTIVE(kg)) { 599245f3abfSJeff Roberson int nice; 600245f3abfSJeff Roberson 60115dc847eSJeff Roberson nice = kg->kg_nice + (0 - kseq->ksq_nicemin); 60215dc847eSJeff Roberson if (kseq->ksq_loads[PRI_TIMESHARE] == 0 || 60315dc847eSJeff Roberson kg->kg_nice < kseq->ksq_nicemin) 604245f3abfSJeff Roberson ke->ke_slice = SCHED_SLICE_MAX; 60515dc847eSJeff Roberson else if (nice <= SCHED_PRI_NTHRESH) 606245f3abfSJeff Roberson ke->ke_slice = SCHED_SLICE_NICE(nice); 607245f3abfSJeff Roberson else 608245f3abfSJeff Roberson ke->ke_slice = 0; 609245f3abfSJeff Roberson } else 610245f3abfSJeff Roberson ke->ke_slice = SCHED_SLICE_MIN; 61135e6168fSJeff Roberson 61215dc847eSJeff Roberson CTR6(KTR_ULE, 61315dc847eSJeff Roberson "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)", 61415dc847eSJeff Roberson ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin, 61515dc847eSJeff Roberson kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg)); 61615dc847eSJeff Roberson 617407b0157SJeff Roberson /* 618a8949de2SJeff Roberson * Check to see if we need to scale back the slp and run time 619a8949de2SJeff Roberson * in the kg. This will cause us to forget old interactivity 620a8949de2SJeff Roberson * while maintaining the current ratio. 621407b0157SJeff Roberson */ 6224b60e324SJeff Roberson sched_interact_update(kg); 623407b0157SJeff Roberson 624245f3abfSJeff Roberson return; 62535e6168fSJeff Roberson } 62635e6168fSJeff Roberson 6274b60e324SJeff Roberson static void 6284b60e324SJeff Roberson sched_interact_update(struct ksegrp *kg) 6294b60e324SJeff Roberson { 6304b60e324SJeff Roberson if ((kg->kg_runtime + kg->kg_slptime) > SCHED_SLP_RUN_MAX) { 6314b60e324SJeff Roberson kg->kg_runtime = (kg->kg_runtime / 5) * 4; 6324b60e324SJeff Roberson kg->kg_slptime = (kg->kg_slptime / 5) * 4; 6334b60e324SJeff Roberson } 6344b60e324SJeff Roberson } 6354b60e324SJeff Roberson 636e1f89c22SJeff Roberson static int 637e1f89c22SJeff Roberson sched_interact_score(struct ksegrp *kg) 638e1f89c22SJeff Roberson { 639210491d3SJeff Roberson int div; 640e1f89c22SJeff Roberson 641e1f89c22SJeff Roberson if (kg->kg_runtime > kg->kg_slptime) { 642210491d3SJeff Roberson div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF); 643210491d3SJeff Roberson return (SCHED_INTERACT_HALF + 644210491d3SJeff Roberson (SCHED_INTERACT_HALF - (kg->kg_slptime / div))); 645210491d3SJeff Roberson } if (kg->kg_slptime > kg->kg_runtime) { 646210491d3SJeff Roberson div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF); 647210491d3SJeff Roberson return (kg->kg_runtime / div); 648e1f89c22SJeff Roberson } 649e1f89c22SJeff Roberson 650210491d3SJeff Roberson /* 651210491d3SJeff Roberson * This can happen if slptime and runtime are 0. 652210491d3SJeff Roberson */ 653210491d3SJeff Roberson return (0); 654e1f89c22SJeff Roberson 655e1f89c22SJeff Roberson } 656e1f89c22SJeff Roberson 65715dc847eSJeff Roberson /* 65815dc847eSJeff Roberson * This is only somewhat accurate since given many processes of the same 65915dc847eSJeff Roberson * priority they will switch when their slices run out, which will be 66015dc847eSJeff Roberson * at most SCHED_SLICE_MAX. 66115dc847eSJeff Roberson */ 66235e6168fSJeff Roberson int 66335e6168fSJeff Roberson sched_rr_interval(void) 66435e6168fSJeff Roberson { 66535e6168fSJeff Roberson return (SCHED_SLICE_MAX); 66635e6168fSJeff Roberson } 66735e6168fSJeff Roberson 66835e6168fSJeff Roberson void 66935e6168fSJeff Roberson sched_pctcpu_update(struct kse *ke) 67035e6168fSJeff Roberson { 67135e6168fSJeff Roberson /* 67235e6168fSJeff Roberson * Adjust counters and watermark for pctcpu calc. 673210491d3SJeff Roberson */ 674210491d3SJeff Roberson 675210491d3SJeff Roberson /* 67665c8760dSJeff Roberson * Shift the tick count out so that the divide doesn't round away 67765c8760dSJeff Roberson * our results. 67865c8760dSJeff Roberson */ 67965c8760dSJeff Roberson ke->ke_ticks <<= 10; 68035e6168fSJeff Roberson ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick)) * 68135e6168fSJeff Roberson SCHED_CPU_TICKS; 68265c8760dSJeff Roberson ke->ke_ticks >>= 10; 68335e6168fSJeff Roberson ke->ke_ltick = ticks; 68435e6168fSJeff Roberson ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS; 68535e6168fSJeff Roberson } 68635e6168fSJeff Roberson 68735e6168fSJeff Roberson #ifdef SMP 6885d7ef00cSJeff Roberson /* XXX Should be changed to kseq_load_lowest() */ 68935e6168fSJeff Roberson int 69035e6168fSJeff Roberson sched_pickcpu(void) 69135e6168fSJeff Roberson { 6920a016a05SJeff Roberson struct kseq *kseq; 69335e6168fSJeff Roberson int load; 6940a016a05SJeff Roberson int cpu; 69535e6168fSJeff Roberson int i; 69635e6168fSJeff Roberson 697b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 69835e6168fSJeff Roberson if (!smp_started) 69935e6168fSJeff Roberson return (0); 70035e6168fSJeff Roberson 7010a016a05SJeff Roberson load = 0; 7020a016a05SJeff Roberson cpu = 0; 70335e6168fSJeff Roberson 70435e6168fSJeff Roberson for (i = 0; i < mp_maxid; i++) { 70535e6168fSJeff Roberson if (CPU_ABSENT(i)) 70635e6168fSJeff Roberson continue; 7070a016a05SJeff Roberson kseq = KSEQ_CPU(i); 70815dc847eSJeff Roberson if (kseq->ksq_load < load) { 70935e6168fSJeff Roberson cpu = i; 71015dc847eSJeff Roberson load = kseq->ksq_load; 71135e6168fSJeff Roberson } 71235e6168fSJeff Roberson } 71335e6168fSJeff Roberson 71435e6168fSJeff Roberson CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu); 71535e6168fSJeff Roberson return (cpu); 71635e6168fSJeff Roberson } 71735e6168fSJeff Roberson #else 71835e6168fSJeff Roberson int 71935e6168fSJeff Roberson sched_pickcpu(void) 72035e6168fSJeff Roberson { 72135e6168fSJeff Roberson return (0); 72235e6168fSJeff Roberson } 72335e6168fSJeff Roberson #endif 72435e6168fSJeff Roberson 72535e6168fSJeff Roberson void 72635e6168fSJeff Roberson sched_prio(struct thread *td, u_char prio) 72735e6168fSJeff Roberson { 72835e6168fSJeff Roberson struct kse *ke; 72935e6168fSJeff Roberson struct runq *rq; 73035e6168fSJeff Roberson 73135e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 73235e6168fSJeff Roberson ke = td->td_kse; 73335e6168fSJeff Roberson td->td_priority = prio; 73435e6168fSJeff Roberson 73535e6168fSJeff Roberson if (TD_ON_RUNQ(td)) { 73635e6168fSJeff Roberson rq = ke->ke_runq; 73735e6168fSJeff Roberson 73835e6168fSJeff Roberson runq_remove(rq, ke); 73935e6168fSJeff Roberson runq_add(rq, ke); 74035e6168fSJeff Roberson } 74135e6168fSJeff Roberson } 74235e6168fSJeff Roberson 74335e6168fSJeff Roberson void 74435e6168fSJeff Roberson sched_switchout(struct thread *td) 74535e6168fSJeff Roberson { 74635e6168fSJeff Roberson struct kse *ke; 74735e6168fSJeff Roberson 74835e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 74935e6168fSJeff Roberson 75035e6168fSJeff Roberson ke = td->td_kse; 75135e6168fSJeff Roberson 75235e6168fSJeff Roberson td->td_last_kse = ke; 753060563ecSJulian Elischer td->td_lastcpu = td->td_oncpu; 754060563ecSJulian Elischer td->td_oncpu = NOCPU; 7554a338afdSJulian Elischer td->td_flags &= ~TDF_NEEDRESCHED; 75635e6168fSJeff Roberson 75735e6168fSJeff Roberson if (TD_IS_RUNNING(td)) { 758210491d3SJeff Roberson /* 759210491d3SJeff Roberson * This queue is always correct except for idle threads which 760210491d3SJeff Roberson * have a higher priority due to priority propagation. 761210491d3SJeff Roberson */ 762210491d3SJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE && 763210491d3SJeff Roberson ke->ke_thread->td_priority > PRI_MIN_IDLE) 764210491d3SJeff Roberson ke->ke_runq = KSEQ_SELF()->ksq_curr; 76515dc847eSJeff Roberson runq_add(ke->ke_runq, ke); 76615dc847eSJeff Roberson /* setrunqueue(td); */ 76735e6168fSJeff Roberson return; 768e1f89c22SJeff Roberson } 76915dc847eSJeff Roberson if (ke->ke_runq) 77015dc847eSJeff Roberson kseq_rem(KSEQ_CPU(ke->ke_cpu), ke); 77135e6168fSJeff Roberson /* 77235e6168fSJeff Roberson * We will not be on the run queue. So we must be 77335e6168fSJeff Roberson * sleeping or similar. 77435e6168fSJeff Roberson */ 7750e2a4d3aSDavid Xu if (td->td_proc->p_flag & P_SA) 77635e6168fSJeff Roberson kse_reassign(ke); 77735e6168fSJeff Roberson } 77835e6168fSJeff Roberson 77935e6168fSJeff Roberson void 78035e6168fSJeff Roberson sched_switchin(struct thread *td) 78135e6168fSJeff Roberson { 78235e6168fSJeff Roberson /* struct kse *ke = td->td_kse; */ 78335e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 78435e6168fSJeff Roberson 785060563ecSJulian Elischer td->td_oncpu = PCPU_GET(cpuid); 78635e6168fSJeff Roberson } 78735e6168fSJeff Roberson 78835e6168fSJeff Roberson void 78935e6168fSJeff Roberson sched_nice(struct ksegrp *kg, int nice) 79035e6168fSJeff Roberson { 79115dc847eSJeff Roberson struct kse *ke; 79235e6168fSJeff Roberson struct thread *td; 79315dc847eSJeff Roberson struct kseq *kseq; 79435e6168fSJeff Roberson 7950b5318c8SJohn Baldwin PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED); 7960b5318c8SJohn Baldwin mtx_assert(&sched_lock, MA_OWNED); 79715dc847eSJeff Roberson /* 79815dc847eSJeff Roberson * We need to adjust the nice counts for running KSEs. 79915dc847eSJeff Roberson */ 80015dc847eSJeff Roberson if (kg->kg_pri_class == PRI_TIMESHARE) 80115dc847eSJeff Roberson FOREACH_KSE_IN_GROUP(kg, ke) { 80215dc847eSJeff Roberson if (ke->ke_state != KES_ONRUNQ && 80315dc847eSJeff Roberson ke->ke_state != KES_THREAD) 80415dc847eSJeff Roberson continue; 80515dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 80615dc847eSJeff Roberson kseq_nice_rem(kseq, kg->kg_nice); 80715dc847eSJeff Roberson kseq_nice_add(kseq, nice); 80815dc847eSJeff Roberson } 80935e6168fSJeff Roberson kg->kg_nice = nice; 81035e6168fSJeff Roberson sched_priority(kg); 81115dc847eSJeff Roberson FOREACH_THREAD_IN_GROUP(kg, td) 8124a338afdSJulian Elischer td->td_flags |= TDF_NEEDRESCHED; 81335e6168fSJeff Roberson } 81435e6168fSJeff Roberson 81535e6168fSJeff Roberson void 81635e6168fSJeff Roberson sched_sleep(struct thread *td, u_char prio) 81735e6168fSJeff Roberson { 81835e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 81935e6168fSJeff Roberson 82035e6168fSJeff Roberson td->td_slptime = ticks; 82135e6168fSJeff Roberson td->td_priority = prio; 82235e6168fSJeff Roberson 82315dc847eSJeff Roberson CTR2(KTR_ULE, "sleep kse %p (tick: %d)", 82415dc847eSJeff Roberson td->td_kse, td->td_slptime); 82535e6168fSJeff Roberson } 82635e6168fSJeff Roberson 82735e6168fSJeff Roberson void 82835e6168fSJeff Roberson sched_wakeup(struct thread *td) 82935e6168fSJeff Roberson { 83035e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 83135e6168fSJeff Roberson 83235e6168fSJeff Roberson /* 83335e6168fSJeff Roberson * Let the kseg know how long we slept for. This is because process 83435e6168fSJeff Roberson * interactivity behavior is modeled in the kseg. 83535e6168fSJeff Roberson */ 83635e6168fSJeff Roberson if (td->td_slptime) { 837f1e8dc4aSJeff Roberson struct ksegrp *kg; 83815dc847eSJeff Roberson int hzticks; 839f1e8dc4aSJeff Roberson 840f1e8dc4aSJeff Roberson kg = td->td_ksegrp; 84115dc847eSJeff Roberson hzticks = ticks - td->td_slptime; 84215dc847eSJeff Roberson kg->kg_slptime += hzticks << 10; 8434b60e324SJeff Roberson sched_interact_update(kg); 844f1e8dc4aSJeff Roberson sched_priority(kg); 8454b60e324SJeff Roberson if (td->td_kse) 8464b60e324SJeff Roberson sched_slice(td->td_kse); 84715dc847eSJeff Roberson CTR2(KTR_ULE, "wakeup kse %p (%d ticks)", 84815dc847eSJeff Roberson td->td_kse, hzticks); 84935e6168fSJeff Roberson td->td_slptime = 0; 850f1e8dc4aSJeff Roberson } 85135e6168fSJeff Roberson setrunqueue(td); 85235e6168fSJeff Roberson if (td->td_priority < curthread->td_priority) 8534a338afdSJulian Elischer curthread->td_flags |= TDF_NEEDRESCHED; 85435e6168fSJeff Roberson } 85535e6168fSJeff Roberson 85635e6168fSJeff Roberson /* 85735e6168fSJeff Roberson * Penalize the parent for creating a new child and initialize the child's 85835e6168fSJeff Roberson * priority. 85935e6168fSJeff Roberson */ 86035e6168fSJeff Roberson void 86115dc847eSJeff Roberson sched_fork(struct proc *p, struct proc *p1) 86235e6168fSJeff Roberson { 86335e6168fSJeff Roberson 86435e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 86535e6168fSJeff Roberson 86615dc847eSJeff Roberson sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1)); 86715dc847eSJeff Roberson sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1)); 86815dc847eSJeff Roberson sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1)); 86915dc847eSJeff Roberson } 87015dc847eSJeff Roberson 87115dc847eSJeff Roberson void 87215dc847eSJeff Roberson sched_fork_kse(struct kse *ke, struct kse *child) 87315dc847eSJeff Roberson { 8742056d0a1SJohn Baldwin 875210491d3SJeff Roberson child->ke_slice = 1; /* Attempt to quickly learn interactivity. */ 87615dc847eSJeff Roberson child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */ 87715dc847eSJeff Roberson child->ke_runq = NULL; 87815dc847eSJeff Roberson 87915dc847eSJeff Roberson /* 88015dc847eSJeff Roberson * Claim that we've been running for one second for statistical 88115dc847eSJeff Roberson * purposes. 88215dc847eSJeff Roberson */ 88315dc847eSJeff Roberson child->ke_ticks = 0; 88415dc847eSJeff Roberson child->ke_ltick = ticks; 88515dc847eSJeff Roberson child->ke_ftick = ticks - hz; 88615dc847eSJeff Roberson } 88715dc847eSJeff Roberson 88815dc847eSJeff Roberson void 88915dc847eSJeff Roberson sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child) 89015dc847eSJeff Roberson { 8912056d0a1SJohn Baldwin 8922056d0a1SJohn Baldwin PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED); 89335e6168fSJeff Roberson /* XXX Need something better here */ 894210491d3SJeff Roberson 895210491d3SJeff Roberson child->kg_slptime = kg->kg_slptime; 896210491d3SJeff Roberson child->kg_runtime = kg->kg_runtime; 8974b60e324SJeff Roberson kg->kg_runtime += tickincr << 10; 8984b60e324SJeff Roberson sched_interact_update(kg); 89915dc847eSJeff Roberson 90035e6168fSJeff Roberson child->kg_user_pri = kg->kg_user_pri; 90115dc847eSJeff Roberson child->kg_nice = kg->kg_nice; 902c9f25d8fSJeff Roberson } 903c9f25d8fSJeff Roberson 90415dc847eSJeff Roberson void 90515dc847eSJeff Roberson sched_fork_thread(struct thread *td, struct thread *child) 90615dc847eSJeff Roberson { 90715dc847eSJeff Roberson } 90815dc847eSJeff Roberson 90915dc847eSJeff Roberson void 91015dc847eSJeff Roberson sched_class(struct ksegrp *kg, int class) 91115dc847eSJeff Roberson { 91215dc847eSJeff Roberson struct kseq *kseq; 91315dc847eSJeff Roberson struct kse *ke; 91415dc847eSJeff Roberson 9152056d0a1SJohn Baldwin mtx_assert(&sched_lock, MA_OWNED); 91615dc847eSJeff Roberson if (kg->kg_pri_class == class) 91715dc847eSJeff Roberson return; 91815dc847eSJeff Roberson 91915dc847eSJeff Roberson FOREACH_KSE_IN_GROUP(kg, ke) { 92015dc847eSJeff Roberson if (ke->ke_state != KES_ONRUNQ && 92115dc847eSJeff Roberson ke->ke_state != KES_THREAD) 92215dc847eSJeff Roberson continue; 92315dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 92415dc847eSJeff Roberson 925b5c4c4a7SJeff Roberson kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--; 926b5c4c4a7SJeff Roberson kseq->ksq_loads[PRI_BASE(class)]++; 92715dc847eSJeff Roberson 92815dc847eSJeff Roberson if (kg->kg_pri_class == PRI_TIMESHARE) 92915dc847eSJeff Roberson kseq_nice_rem(kseq, kg->kg_nice); 93015dc847eSJeff Roberson else if (class == PRI_TIMESHARE) 93115dc847eSJeff Roberson kseq_nice_add(kseq, kg->kg_nice); 93215dc847eSJeff Roberson } 93315dc847eSJeff Roberson 93415dc847eSJeff Roberson kg->kg_pri_class = class; 93535e6168fSJeff Roberson } 93635e6168fSJeff Roberson 93735e6168fSJeff Roberson /* 93835e6168fSJeff Roberson * Return some of the child's priority and interactivity to the parent. 93935e6168fSJeff Roberson */ 94035e6168fSJeff Roberson void 94115dc847eSJeff Roberson sched_exit(struct proc *p, struct proc *child) 94235e6168fSJeff Roberson { 94335e6168fSJeff Roberson /* XXX Need something better here */ 94435e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 945141ad61cSJeff Roberson sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child)); 946210491d3SJeff Roberson sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child)); 947141ad61cSJeff Roberson } 948141ad61cSJeff Roberson 949141ad61cSJeff Roberson void 950141ad61cSJeff Roberson sched_exit_kse(struct kse *ke, struct kse *child) 951141ad61cSJeff Roberson { 952141ad61cSJeff Roberson kseq_rem(KSEQ_CPU(child->ke_cpu), child); 953141ad61cSJeff Roberson } 954141ad61cSJeff Roberson 955141ad61cSJeff Roberson void 956141ad61cSJeff Roberson sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child) 957141ad61cSJeff Roberson { 9584b60e324SJeff Roberson /* kg->kg_slptime += child->kg_slptime; */ 959210491d3SJeff Roberson kg->kg_runtime += child->kg_runtime; 9604b60e324SJeff Roberson sched_interact_update(kg); 961141ad61cSJeff Roberson } 962141ad61cSJeff Roberson 963141ad61cSJeff Roberson void 964141ad61cSJeff Roberson sched_exit_thread(struct thread *td, struct thread *child) 965141ad61cSJeff Roberson { 96635e6168fSJeff Roberson } 96735e6168fSJeff Roberson 96835e6168fSJeff Roberson void 96915dc847eSJeff Roberson sched_clock(struct kse *ke) 97035e6168fSJeff Roberson { 97135e6168fSJeff Roberson struct kseq *kseq; 9720a016a05SJeff Roberson struct ksegrp *kg; 97315dc847eSJeff Roberson struct thread *td; 97415dc847eSJeff Roberson #if 0 97515dc847eSJeff Roberson struct kse *nke; 97615dc847eSJeff Roberson #endif 97735e6168fSJeff Roberson 97815dc847eSJeff Roberson /* 97915dc847eSJeff Roberson * sched_setup() apparently happens prior to stathz being set. We 98015dc847eSJeff Roberson * need to resolve the timers earlier in the boot so we can avoid 98115dc847eSJeff Roberson * calculating this here. 98215dc847eSJeff Roberson */ 98315dc847eSJeff Roberson if (realstathz == 0) { 98415dc847eSJeff Roberson realstathz = stathz ? stathz : hz; 98515dc847eSJeff Roberson tickincr = hz / realstathz; 98615dc847eSJeff Roberson /* 98715dc847eSJeff Roberson * XXX This does not work for values of stathz that are much 98815dc847eSJeff Roberson * larger than hz. 98915dc847eSJeff Roberson */ 99015dc847eSJeff Roberson if (tickincr == 0) 99115dc847eSJeff Roberson tickincr = 1; 99215dc847eSJeff Roberson } 99335e6168fSJeff Roberson 99415dc847eSJeff Roberson td = ke->ke_thread; 99515dc847eSJeff Roberson kg = ke->ke_ksegrp; 99635e6168fSJeff Roberson 9970a016a05SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 9980a016a05SJeff Roberson KASSERT((td != NULL), ("schedclock: null thread pointer")); 9990a016a05SJeff Roberson 10000a016a05SJeff Roberson /* Adjust ticks for pctcpu */ 100165c8760dSJeff Roberson ke->ke_ticks++; 1002d465fb95SJeff Roberson ke->ke_ltick = ticks; 1003a8949de2SJeff Roberson 1004d465fb95SJeff Roberson /* Go up to one second beyond our max and then trim back down */ 1005d465fb95SJeff Roberson if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick) 1006d465fb95SJeff Roberson sched_pctcpu_update(ke); 1007d465fb95SJeff Roberson 100843fdafb1SJulian Elischer if (td->td_flags & TDF_IDLETD) 100935e6168fSJeff Roberson return; 10100a016a05SJeff Roberson 101115dc847eSJeff Roberson CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)", 101215dc847eSJeff Roberson ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10); 1013c9f25d8fSJeff Roberson 101435e6168fSJeff Roberson /* 1015a8949de2SJeff Roberson * We only do slicing code for TIMESHARE ksegrps. 1016a8949de2SJeff Roberson */ 1017a8949de2SJeff Roberson if (kg->kg_pri_class != PRI_TIMESHARE) 1018a8949de2SJeff Roberson return; 1019a8949de2SJeff Roberson /* 102015dc847eSJeff Roberson * Check for a higher priority task on the run queue. This can happen 102115dc847eSJeff Roberson * on SMP if another processor woke up a process on our runq. 102235e6168fSJeff Roberson */ 102315dc847eSJeff Roberson kseq = KSEQ_SELF(); 102415dc847eSJeff Roberson #if 0 102515dc847eSJeff Roberson if (kseq->ksq_load > 1 && (nke = kseq_choose(kseq)) != NULL) { 102615dc847eSJeff Roberson if (sched_strict && 102715dc847eSJeff Roberson nke->ke_thread->td_priority < td->td_priority) 102815dc847eSJeff Roberson td->td_flags |= TDF_NEEDRESCHED; 102915dc847eSJeff Roberson else if (nke->ke_thread->td_priority < 103015dc847eSJeff Roberson td->td_priority SCHED_PRIO_SLOP) 103115dc847eSJeff Roberson 103215dc847eSJeff Roberson if (nke->ke_thread->td_priority < td->td_priority) 103315dc847eSJeff Roberson td->td_flags |= TDF_NEEDRESCHED; 103415dc847eSJeff Roberson } 103515dc847eSJeff Roberson #endif 103615dc847eSJeff Roberson /* 103715dc847eSJeff Roberson * We used a tick charge it to the ksegrp so that we can compute our 103815dc847eSJeff Roberson * interactivity. 103915dc847eSJeff Roberson */ 104015dc847eSJeff Roberson kg->kg_runtime += tickincr << 10; 10414b60e324SJeff Roberson sched_interact_update(kg); 1042407b0157SJeff Roberson 104335e6168fSJeff Roberson /* 104435e6168fSJeff Roberson * We used up one time slice. 104535e6168fSJeff Roberson */ 104635e6168fSJeff Roberson ke->ke_slice--; 104715dc847eSJeff Roberson #ifdef SMP 1048c36ccfa2SJeff Roberson kseq->ksq_rslices--; 104915dc847eSJeff Roberson #endif 105015dc847eSJeff Roberson 105115dc847eSJeff Roberson if (ke->ke_slice > 0) 105215dc847eSJeff Roberson return; 105335e6168fSJeff Roberson /* 105415dc847eSJeff Roberson * We're out of time, recompute priorities and requeue. 105535e6168fSJeff Roberson */ 105615dc847eSJeff Roberson kseq_rem(kseq, ke); 1057e1f89c22SJeff Roberson sched_priority(kg); 105815dc847eSJeff Roberson sched_slice(ke); 105915dc847eSJeff Roberson if (SCHED_CURR(kg, ke)) 106015dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 106115dc847eSJeff Roberson else 106215dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 106315dc847eSJeff Roberson kseq_add(kseq, ke); 10644a338afdSJulian Elischer td->td_flags |= TDF_NEEDRESCHED; 106535e6168fSJeff Roberson } 106635e6168fSJeff Roberson 106735e6168fSJeff Roberson int 106835e6168fSJeff Roberson sched_runnable(void) 106935e6168fSJeff Roberson { 107035e6168fSJeff Roberson struct kseq *kseq; 1071b90816f1SJeff Roberson int load; 107235e6168fSJeff Roberson 1073b90816f1SJeff Roberson load = 1; 1074b90816f1SJeff Roberson 1075b90816f1SJeff Roberson mtx_lock_spin(&sched_lock); 10760a016a05SJeff Roberson kseq = KSEQ_SELF(); 107735e6168fSJeff Roberson 107815dc847eSJeff Roberson if (kseq->ksq_load) 1079b90816f1SJeff Roberson goto out; 1080c9f25d8fSJeff Roberson #ifdef SMP 10810a016a05SJeff Roberson /* 10820a016a05SJeff Roberson * For SMP we may steal other processor's KSEs. Just search until we 10830a016a05SJeff Roberson * verify that at least on other cpu has a runnable task. 10840a016a05SJeff Roberson */ 1085c9f25d8fSJeff Roberson if (smp_started) { 1086c9f25d8fSJeff Roberson int i; 1087c9f25d8fSJeff Roberson 1088c9f25d8fSJeff Roberson for (i = 0; i < mp_maxid; i++) { 1089c9f25d8fSJeff Roberson if (CPU_ABSENT(i)) 1090c9f25d8fSJeff Roberson continue; 10910a016a05SJeff Roberson kseq = KSEQ_CPU(i); 10927cd650a9SJeff Roberson if (kseq->ksq_load > 1) 1093b90816f1SJeff Roberson goto out; 1094c9f25d8fSJeff Roberson } 1095c9f25d8fSJeff Roberson } 1096c9f25d8fSJeff Roberson #endif 1097b90816f1SJeff Roberson load = 0; 1098b90816f1SJeff Roberson out: 1099b90816f1SJeff Roberson mtx_unlock_spin(&sched_lock); 1100b90816f1SJeff Roberson return (load); 110135e6168fSJeff Roberson } 110235e6168fSJeff Roberson 110335e6168fSJeff Roberson void 110435e6168fSJeff Roberson sched_userret(struct thread *td) 110535e6168fSJeff Roberson { 110635e6168fSJeff Roberson struct ksegrp *kg; 1107210491d3SJeff Roberson struct kseq *kseq; 1108210491d3SJeff Roberson struct kse *ke; 110935e6168fSJeff Roberson 111035e6168fSJeff Roberson kg = td->td_ksegrp; 111135e6168fSJeff Roberson 111235e6168fSJeff Roberson if (td->td_priority != kg->kg_user_pri) { 111335e6168fSJeff Roberson mtx_lock_spin(&sched_lock); 111435e6168fSJeff Roberson td->td_priority = kg->kg_user_pri; 1115210491d3SJeff Roberson kseq = KSEQ_SELF(); 1116210491d3SJeff Roberson if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE && 1117210491d3SJeff Roberson kseq->ksq_load > 1 && 1118210491d3SJeff Roberson (ke = kseq_choose(kseq)) != NULL && 1119210491d3SJeff Roberson ke->ke_thread->td_priority < td->td_priority) 1120210491d3SJeff Roberson curthread->td_flags |= TDF_NEEDRESCHED; 112135e6168fSJeff Roberson mtx_unlock_spin(&sched_lock); 112235e6168fSJeff Roberson } 112335e6168fSJeff Roberson } 112435e6168fSJeff Roberson 1125c9f25d8fSJeff Roberson struct kse * 1126c9f25d8fSJeff Roberson sched_choose(void) 1127c9f25d8fSJeff Roberson { 11280a016a05SJeff Roberson struct kseq *kseq; 1129c9f25d8fSJeff Roberson struct kse *ke; 113015dc847eSJeff Roberson 1131b90816f1SJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 113215dc847eSJeff Roberson #ifdef SMP 1133245f3abfSJeff Roberson retry: 113415dc847eSJeff Roberson #endif 1135c36ccfa2SJeff Roberson kseq = KSEQ_SELF(); 11360a016a05SJeff Roberson ke = kseq_choose(kseq); 113735e6168fSJeff Roberson if (ke) { 113815dc847eSJeff Roberson runq_remove(ke->ke_runq, ke); 113935e6168fSJeff Roberson ke->ke_state = KES_THREAD; 1140245f3abfSJeff Roberson 114115dc847eSJeff Roberson if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) { 114215dc847eSJeff Roberson CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)", 114315dc847eSJeff Roberson ke, ke->ke_runq, ke->ke_slice, 114415dc847eSJeff Roberson ke->ke_thread->td_priority); 1145245f3abfSJeff Roberson } 114615dc847eSJeff Roberson return (ke); 114735e6168fSJeff Roberson } 114835e6168fSJeff Roberson 1149c9f25d8fSJeff Roberson #ifdef SMP 1150c36ccfa2SJeff Roberson if (smp_started) { 1151c9f25d8fSJeff Roberson /* 1152c9f25d8fSJeff Roberson * Find the cpu with the highest load and steal one proc. 1153c9f25d8fSJeff Roberson */ 1154c36ccfa2SJeff Roberson if ((kseq = kseq_load_highest()) == NULL) 1155c36ccfa2SJeff Roberson return (NULL); 1156c36ccfa2SJeff Roberson 1157c36ccfa2SJeff Roberson /* 1158c36ccfa2SJeff Roberson * Remove this kse from this kseq and runq and then requeue 1159c36ccfa2SJeff Roberson * on the current processor. Then we will dequeue it 1160c36ccfa2SJeff Roberson * normally above. 1161c36ccfa2SJeff Roberson */ 1162356500a3SJeff Roberson kseq_move(kseq, PCPU_GET(cpuid)); 116315dc847eSJeff Roberson goto retry; 1164c9f25d8fSJeff Roberson } 1165c9f25d8fSJeff Roberson #endif 116615dc847eSJeff Roberson 116715dc847eSJeff Roberson return (NULL); 116835e6168fSJeff Roberson } 116935e6168fSJeff Roberson 117035e6168fSJeff Roberson void 117135e6168fSJeff Roberson sched_add(struct kse *ke) 117235e6168fSJeff Roberson { 1173c9f25d8fSJeff Roberson struct kseq *kseq; 117415dc847eSJeff Roberson struct ksegrp *kg; 1175c9f25d8fSJeff Roberson 11765d7ef00cSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 11775d7ef00cSJeff Roberson KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE")); 11785d7ef00cSJeff Roberson KASSERT((ke->ke_thread->td_kse != NULL), 11795d7ef00cSJeff Roberson ("sched_add: No KSE on thread")); 11805d7ef00cSJeff Roberson KASSERT(ke->ke_state != KES_ONRUNQ, 11815d7ef00cSJeff Roberson ("sched_add: kse %p (%s) already in run queue", ke, 11825d7ef00cSJeff Roberson ke->ke_proc->p_comm)); 11835d7ef00cSJeff Roberson KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 11845d7ef00cSJeff Roberson ("sched_add: process swapped out")); 11859bca28a7SJeff Roberson KASSERT(ke->ke_runq == NULL, 11869bca28a7SJeff Roberson ("sched_add: KSE %p is still assigned to a run queue", ke)); 11875d7ef00cSJeff Roberson 118815dc847eSJeff Roberson kg = ke->ke_ksegrp; 118915dc847eSJeff Roberson 1190b5c4c4a7SJeff Roberson switch (PRI_BASE(kg->kg_pri_class)) { 1191a8949de2SJeff Roberson case PRI_ITHD: 1192a8949de2SJeff Roberson case PRI_REALTIME: 1193a6ed4186SJeff Roberson kseq = KSEQ_SELF(); 119415dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 119515dc847eSJeff Roberson ke->ke_slice = SCHED_SLICE_MAX; 11967cd650a9SJeff Roberson ke->ke_cpu = PCPU_GET(cpuid); 1197a8949de2SJeff Roberson break; 1198a8949de2SJeff Roberson case PRI_TIMESHARE: 1199a8949de2SJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 120015dc847eSJeff Roberson if (SCHED_CURR(kg, ke)) 120115dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 120215dc847eSJeff Roberson else 120315dc847eSJeff Roberson ke->ke_runq = kseq->ksq_next; 120415dc847eSJeff Roberson break; 120515dc847eSJeff Roberson case PRI_IDLE: 120615dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 120715dc847eSJeff Roberson /* 120815dc847eSJeff Roberson * This is for priority prop. 120915dc847eSJeff Roberson */ 1210210491d3SJeff Roberson if (ke->ke_thread->td_priority > PRI_MIN_IDLE) 121115dc847eSJeff Roberson ke->ke_runq = kseq->ksq_curr; 121215dc847eSJeff Roberson else 121315dc847eSJeff Roberson ke->ke_runq = &kseq->ksq_idle; 121415dc847eSJeff Roberson ke->ke_slice = SCHED_SLICE_MIN; 121515dc847eSJeff Roberson break; 121615dc847eSJeff Roberson default: 121715dc847eSJeff Roberson panic("Unknown pri class.\n"); 1218a8949de2SJeff Roberson break; 1219a6ed4186SJeff Roberson } 1220a8949de2SJeff Roberson 122135e6168fSJeff Roberson ke->ke_ksegrp->kg_runq_kses++; 122235e6168fSJeff Roberson ke->ke_state = KES_ONRUNQ; 122335e6168fSJeff Roberson 122415dc847eSJeff Roberson runq_add(ke->ke_runq, ke); 12259bca28a7SJeff Roberson kseq_add(kseq, ke); 122635e6168fSJeff Roberson } 122735e6168fSJeff Roberson 122835e6168fSJeff Roberson void 122935e6168fSJeff Roberson sched_rem(struct kse *ke) 123035e6168fSJeff Roberson { 123115dc847eSJeff Roberson struct kseq *kseq; 123215dc847eSJeff Roberson 123335e6168fSJeff Roberson mtx_assert(&sched_lock, MA_OWNED); 12349bca28a7SJeff Roberson KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 123535e6168fSJeff Roberson 123635e6168fSJeff Roberson ke->ke_state = KES_THREAD; 123735e6168fSJeff Roberson ke->ke_ksegrp->kg_runq_kses--; 123815dc847eSJeff Roberson kseq = KSEQ_CPU(ke->ke_cpu); 123915dc847eSJeff Roberson runq_remove(ke->ke_runq, ke); 124015dc847eSJeff Roberson kseq_rem(kseq, ke); 124135e6168fSJeff Roberson } 124235e6168fSJeff Roberson 124335e6168fSJeff Roberson fixpt_t 124435e6168fSJeff Roberson sched_pctcpu(struct kse *ke) 124535e6168fSJeff Roberson { 124635e6168fSJeff Roberson fixpt_t pctcpu; 124735e6168fSJeff Roberson 124835e6168fSJeff Roberson pctcpu = 0; 124935e6168fSJeff Roberson 1250b90816f1SJeff Roberson mtx_lock_spin(&sched_lock); 125135e6168fSJeff Roberson if (ke->ke_ticks) { 125235e6168fSJeff Roberson int rtick; 125335e6168fSJeff Roberson 125435e6168fSJeff Roberson /* Update to account for time potentially spent sleeping */ 125535e6168fSJeff Roberson ke->ke_ltick = ticks; 1256210491d3SJeff Roberson /* 1257210491d3SJeff Roberson * Don't update more frequently than twice a second. Allowing 1258210491d3SJeff Roberson * this causes the cpu usage to decay away too quickly due to 1259210491d3SJeff Roberson * rounding errors. 1260210491d3SJeff Roberson */ 1261210491d3SJeff Roberson if (ke->ke_ltick < (ticks - (hz / 2))) 126235e6168fSJeff Roberson sched_pctcpu_update(ke); 126335e6168fSJeff Roberson 126435e6168fSJeff Roberson /* How many rtick per second ? */ 1265210491d3SJeff Roberson rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS); 12667121cce5SScott Long pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT; 126735e6168fSJeff Roberson } 126835e6168fSJeff Roberson 126935e6168fSJeff Roberson ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick; 1270828e7683SJohn Baldwin mtx_unlock_spin(&sched_lock); 127135e6168fSJeff Roberson 127235e6168fSJeff Roberson return (pctcpu); 127335e6168fSJeff Roberson } 127435e6168fSJeff Roberson 127535e6168fSJeff Roberson int 127635e6168fSJeff Roberson sched_sizeof_kse(void) 127735e6168fSJeff Roberson { 127835e6168fSJeff Roberson return (sizeof(struct kse) + sizeof(struct ke_sched)); 127935e6168fSJeff Roberson } 128035e6168fSJeff Roberson 128135e6168fSJeff Roberson int 128235e6168fSJeff Roberson sched_sizeof_ksegrp(void) 128335e6168fSJeff Roberson { 128435e6168fSJeff Roberson return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 128535e6168fSJeff Roberson } 128635e6168fSJeff Roberson 128735e6168fSJeff Roberson int 128835e6168fSJeff Roberson sched_sizeof_proc(void) 128935e6168fSJeff Roberson { 129035e6168fSJeff Roberson return (sizeof(struct proc)); 129135e6168fSJeff Roberson } 129235e6168fSJeff Roberson 129335e6168fSJeff Roberson int 129435e6168fSJeff Roberson sched_sizeof_thread(void) 129535e6168fSJeff Roberson { 129635e6168fSJeff Roberson return (sizeof(struct thread) + sizeof(struct td_sched)); 129735e6168fSJeff Roberson } 1298