sched_ule.c revision 113660
1109864Sjeff/*- 2113357Sjeff * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org> 3109864Sjeff * All rights reserved. 4109864Sjeff * 5109864Sjeff * Redistribution and use in source and binary forms, with or without 6109864Sjeff * modification, are permitted provided that the following conditions 7109864Sjeff * are met: 8109864Sjeff * 1. Redistributions of source code must retain the above copyright 9109864Sjeff * notice unmodified, this list of conditions, and the following 10109864Sjeff * disclaimer. 11109864Sjeff * 2. Redistributions in binary form must reproduce the above copyright 12109864Sjeff * notice, this list of conditions and the following disclaimer in the 13109864Sjeff * documentation and/or other materials provided with the distribution. 14109864Sjeff * 15109864Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16109864Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17109864Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18109864Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19109864Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20109864Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21109864Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22109864Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23109864Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24109864Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25109864Sjeff * 26109864Sjeff * $FreeBSD: head/sys/kern/sched_ule.c 113660 2003-04-18 05:24:10Z jeff $ 27109864Sjeff */ 28109864Sjeff 29109864Sjeff#include <sys/param.h> 30109864Sjeff#include <sys/systm.h> 31109864Sjeff#include <sys/kernel.h> 32109864Sjeff#include <sys/ktr.h> 33109864Sjeff#include <sys/lock.h> 34109864Sjeff#include <sys/mutex.h> 35109864Sjeff#include <sys/proc.h> 36112966Sjeff#include <sys/resource.h> 37109864Sjeff#include <sys/sched.h> 38109864Sjeff#include <sys/smp.h> 39109864Sjeff#include <sys/sx.h> 40109864Sjeff#include <sys/sysctl.h> 41109864Sjeff#include <sys/sysproto.h> 42109864Sjeff#include <sys/vmmeter.h> 43109864Sjeff#ifdef DDB 44109864Sjeff#include <ddb/ddb.h> 45109864Sjeff#endif 46109864Sjeff#ifdef KTRACE 47109864Sjeff#include <sys/uio.h> 48109864Sjeff#include <sys/ktrace.h> 49109864Sjeff#endif 50109864Sjeff 51109864Sjeff#include <machine/cpu.h> 52109864Sjeff 53113357Sjeff#define KTR_ULE KTR_NFS 54113357Sjeff 55109864Sjeff/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 56109864Sjeff/* XXX This is bogus compatability crap for ps */ 57109864Sjeffstatic fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 58109864SjeffSYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 59109864Sjeff 60109864Sjeffstatic void sched_setup(void *dummy); 61109864SjeffSYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 62109864Sjeff 63113357Sjeffstatic SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED"); 64113357Sjeff 65113357Sjeffstatic int sched_strict; 66113357SjeffSYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, ""); 67113357Sjeff 68113357Sjeffstatic int slice_min = 1; 69113357SjeffSYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, ""); 70113357Sjeff 71113357Sjeffstatic int slice_max = 2; 72113357SjeffSYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, ""); 73113357Sjeff 74111857Sjeffint realstathz; 75113357Sjeffint tickincr = 1; 76111857Sjeff 77109864Sjeff/* 78109864Sjeff * These datastructures are allocated within their parent datastructure but 79109864Sjeff * are scheduler specific. 80109864Sjeff */ 81109864Sjeff 82109864Sjeffstruct ke_sched { 83109864Sjeff int ske_slice; 84109864Sjeff struct runq *ske_runq; 85109864Sjeff /* The following variables are only used for pctcpu calculation */ 86109864Sjeff int ske_ltick; /* Last tick that we were running on */ 87109864Sjeff int ske_ftick; /* First tick that we were running on */ 88109864Sjeff int ske_ticks; /* Tick count */ 89113357Sjeff /* CPU that we have affinity for. */ 90110260Sjeff u_char ske_cpu; 91109864Sjeff}; 92109864Sjeff#define ke_slice ke_sched->ske_slice 93109864Sjeff#define ke_runq ke_sched->ske_runq 94109864Sjeff#define ke_ltick ke_sched->ske_ltick 95109864Sjeff#define ke_ftick ke_sched->ske_ftick 96109864Sjeff#define ke_ticks ke_sched->ske_ticks 97110260Sjeff#define ke_cpu ke_sched->ske_cpu 98109864Sjeff 99109864Sjeffstruct kg_sched { 100110645Sjeff int skg_slptime; /* Number of ticks we vol. slept */ 101110645Sjeff int skg_runtime; /* Number of ticks we were running */ 102109864Sjeff}; 103109864Sjeff#define kg_slptime kg_sched->skg_slptime 104110645Sjeff#define kg_runtime kg_sched->skg_runtime 105109864Sjeff 106109864Sjeffstruct td_sched { 107109864Sjeff int std_slptime; 108109864Sjeff}; 109109864Sjeff#define td_slptime td_sched->std_slptime 110109864Sjeff 111110267Sjeffstruct td_sched td_sched; 112109864Sjeffstruct ke_sched ke_sched; 113109864Sjeffstruct kg_sched kg_sched; 114109864Sjeff 115109864Sjeffstruct ke_sched *kse0_sched = &ke_sched; 116109864Sjeffstruct kg_sched *ksegrp0_sched = &kg_sched; 117109864Sjeffstruct p_sched *proc0_sched = NULL; 118109864Sjeffstruct td_sched *thread0_sched = &td_sched; 119109864Sjeff 120109864Sjeff/* 121109864Sjeff * This priority range has 20 priorities on either end that are reachable 122109864Sjeff * only through nice values. 123111857Sjeff * 124111857Sjeff * PRI_RANGE: Total priority range for timeshare threads. 125111857Sjeff * PRI_NRESV: Reserved priorities for nice. 126111857Sjeff * PRI_BASE: The start of the dynamic range. 127111857Sjeff * DYN_RANGE: Number of priorities that are available int the dynamic 128111857Sjeff * priority range. 129109864Sjeff */ 130111857Sjeff#define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1) 131112966Sjeff#define SCHED_PRI_NRESV PRIO_TOTAL 132112970Sjeff#define SCHED_PRI_NHALF (PRIO_TOTAL / 2) 133113357Sjeff#define SCHED_PRI_NTHRESH (SCHED_PRI_NHALF - 1) 134111857Sjeff#define SCHED_PRI_BASE ((SCHED_PRI_NRESV / 2) + PRI_MIN_TIMESHARE) 135111857Sjeff#define SCHED_DYN_RANGE (SCHED_PRI_RANGE - SCHED_PRI_NRESV) 136113357Sjeff#define SCHED_PRI_INTERACT(score) \ 137113357Sjeff ((score) * SCHED_DYN_RANGE / SCHED_INTERACT_RANGE) 138109864Sjeff 139109864Sjeff/* 140111857Sjeff * These determine the interactivity of a process. 141109864Sjeff * 142110645Sjeff * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate 143110645Sjeff * before throttling back. 144111857Sjeff * SLP_RUN_THROTTLE: Divisor for reducing slp/run time. 145111857Sjeff * INTERACT_RANGE: Range of interactivity values. Smaller is better. 146111857Sjeff * INTERACT_HALF: Convenience define, half of the interactivity range. 147111857Sjeff * INTERACT_THRESH: Threshhold for placement on the current runq. 148109864Sjeff */ 149113357Sjeff#define SCHED_SLP_RUN_MAX ((hz / 10) << 10) 150110645Sjeff#define SCHED_SLP_RUN_THROTTLE (10) 151111857Sjeff#define SCHED_INTERACT_RANGE (100) 152111857Sjeff#define SCHED_INTERACT_HALF (SCHED_INTERACT_RANGE / 2) 153111857Sjeff#define SCHED_INTERACT_THRESH (10) 154111857Sjeff 155109864Sjeff/* 156109864Sjeff * These parameters and macros determine the size of the time slice that is 157109864Sjeff * granted to each thread. 158109864Sjeff * 159109864Sjeff * SLICE_MIN: Minimum time slice granted, in units of ticks. 160109864Sjeff * SLICE_MAX: Maximum time slice granted. 161109864Sjeff * SLICE_RANGE: Range of available time slices scaled by hz. 162112966Sjeff * SLICE_SCALE: The number slices granted per val in the range of [0, max]. 163112966Sjeff * SLICE_NICE: Determine the amount of slice granted to a scaled nice. 164109864Sjeff */ 165113357Sjeff#define SCHED_SLICE_MIN (slice_min) 166113357Sjeff#define SCHED_SLICE_MAX (slice_max) 167111857Sjeff#define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1) 168109864Sjeff#define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max)) 169112966Sjeff#define SCHED_SLICE_NICE(nice) \ 170113357Sjeff (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH)) 171109864Sjeff 172109864Sjeff/* 173109864Sjeff * This macro determines whether or not the kse belongs on the current or 174109864Sjeff * next run queue. 175110645Sjeff * 176110645Sjeff * XXX nice value should effect how interactive a kg is. 177109864Sjeff */ 178113357Sjeff#define SCHED_INTERACTIVE(kg) \ 179113357Sjeff (sched_interact_score(kg) < SCHED_INTERACT_THRESH) 180113417Sjeff#define SCHED_CURR(kg, ke) \ 181113357Sjeff (ke->ke_thread->td_priority < PRI_MIN_TIMESHARE || SCHED_INTERACTIVE(kg)) 182109864Sjeff 183109864Sjeff/* 184109864Sjeff * Cpu percentage computation macros and defines. 185109864Sjeff * 186109864Sjeff * SCHED_CPU_TIME: Number of seconds to average the cpu usage across. 187109864Sjeff * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across. 188109864Sjeff */ 189109864Sjeff 190112971Sjeff#define SCHED_CPU_TIME 10 191109864Sjeff#define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME) 192109864Sjeff 193109864Sjeff/* 194113357Sjeff * kseq - per processor runqs and statistics. 195109864Sjeff */ 196109864Sjeff 197113357Sjeff#define KSEQ_NCLASS (PRI_IDLE + 1) /* Number of run classes. */ 198113357Sjeff 199109864Sjeffstruct kseq { 200113357Sjeff struct runq ksq_idle; /* Queue of IDLE threads. */ 201113357Sjeff struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */ 202113357Sjeff struct runq *ksq_next; /* Next timeshare queue. */ 203113357Sjeff struct runq *ksq_curr; /* Current queue. */ 204113357Sjeff int ksq_loads[KSEQ_NCLASS]; /* Load for each class */ 205113357Sjeff int ksq_load; /* Aggregate load. */ 206113357Sjeff short ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */ 207113357Sjeff short ksq_nicemin; /* Least nice. */ 208110267Sjeff#ifdef SMP 209110267Sjeff unsigned int ksq_rslices; /* Slices on run queue */ 210110267Sjeff#endif 211109864Sjeff}; 212109864Sjeff 213109864Sjeff/* 214109864Sjeff * One kse queue per processor. 215109864Sjeff */ 216110028Sjeff#ifdef SMP 217109864Sjeffstruct kseq kseq_cpu[MAXCPU]; 218110028Sjeff#define KSEQ_SELF() (&kseq_cpu[PCPU_GET(cpuid)]) 219110028Sjeff#define KSEQ_CPU(x) (&kseq_cpu[(x)]) 220110028Sjeff#else 221110028Sjeffstruct kseq kseq_cpu; 222110028Sjeff#define KSEQ_SELF() (&kseq_cpu) 223110028Sjeff#define KSEQ_CPU(x) (&kseq_cpu) 224110028Sjeff#endif 225109864Sjeff 226112966Sjeffstatic void sched_slice(struct kse *ke); 227113357Sjeffstatic void sched_priority(struct ksegrp *kg); 228111857Sjeffstatic int sched_interact_score(struct ksegrp *kg); 229109864Sjeffvoid sched_pctcpu_update(struct kse *ke); 230109864Sjeffint sched_pickcpu(void); 231109864Sjeff 232110267Sjeff/* Operations on per processor queues */ 233110028Sjeffstatic struct kse * kseq_choose(struct kseq *kseq); 234110028Sjeffstatic void kseq_setup(struct kseq *kseq); 235112994Sjeffstatic void kseq_add(struct kseq *kseq, struct kse *ke); 236113357Sjeffstatic void kseq_rem(struct kseq *kseq, struct kse *ke); 237113357Sjeffstatic void kseq_nice_add(struct kseq *kseq, int nice); 238113357Sjeffstatic void kseq_nice_rem(struct kseq *kseq, int nice); 239113660Sjeffvoid kseq_print(int cpu); 240110267Sjeff#ifdef SMP 241110267Sjeffstruct kseq * kseq_load_highest(void); 242110267Sjeff#endif 243110028Sjeff 244113357Sjeffvoid 245113660Sjeffkseq_print(int cpu) 246110267Sjeff{ 247113660Sjeff struct kseq *kseq; 248113357Sjeff int i; 249112994Sjeff 250113660Sjeff kseq = KSEQ_CPU(cpu); 251112994Sjeff 252113357Sjeff printf("kseq:\n"); 253113357Sjeff printf("\tload: %d\n", kseq->ksq_load); 254113357Sjeff printf("\tload ITHD: %d\n", kseq->ksq_loads[PRI_ITHD]); 255113357Sjeff printf("\tload REALTIME: %d\n", kseq->ksq_loads[PRI_REALTIME]); 256113357Sjeff printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]); 257113357Sjeff printf("\tload IDLE: %d\n", kseq->ksq_loads[PRI_IDLE]); 258113357Sjeff printf("\tnicemin:\t%d\n", kseq->ksq_nicemin); 259113357Sjeff printf("\tnice counts:\n"); 260113357Sjeff for (i = 0; i < PRIO_TOTAL + 1; i++) 261113357Sjeff if (kseq->ksq_nice[i]) 262113357Sjeff printf("\t\t%d = %d\n", 263113357Sjeff i - SCHED_PRI_NHALF, kseq->ksq_nice[i]); 264113357Sjeff} 265112994Sjeff 266113357Sjeffstatic void 267113357Sjeffkseq_add(struct kseq *kseq, struct kse *ke) 268113357Sjeff{ 269113386Sjeff kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++; 270113357Sjeff kseq->ksq_load++; 271113357Sjeff if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 272113357Sjeff CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))", 273113357Sjeff ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority, 274113357Sjeff ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin); 275113357Sjeff if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 276113357Sjeff kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice); 277110267Sjeff#ifdef SMP 278110267Sjeff kseq->ksq_rslices += ke->ke_slice; 279110267Sjeff#endif 280110267Sjeff} 281113357Sjeff 282112994Sjeffstatic void 283110267Sjeffkseq_rem(struct kseq *kseq, struct kse *ke) 284110267Sjeff{ 285113386Sjeff kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--; 286113357Sjeff kseq->ksq_load--; 287113357Sjeff ke->ke_runq = NULL; 288113357Sjeff if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 289113357Sjeff kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice); 290110267Sjeff#ifdef SMP 291110267Sjeff kseq->ksq_rslices -= ke->ke_slice; 292110267Sjeff#endif 293110267Sjeff} 294110267Sjeff 295113357Sjeffstatic void 296113357Sjeffkseq_nice_add(struct kseq *kseq, int nice) 297110267Sjeff{ 298113357Sjeff /* Normalize to zero. */ 299113357Sjeff kseq->ksq_nice[nice + SCHED_PRI_NHALF]++; 300113357Sjeff if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 0) 301113357Sjeff kseq->ksq_nicemin = nice; 302110267Sjeff} 303110267Sjeff 304113357Sjeffstatic void 305113357Sjeffkseq_nice_rem(struct kseq *kseq, int nice) 306110267Sjeff{ 307113357Sjeff int n; 308113357Sjeff 309113357Sjeff /* Normalize to zero. */ 310113357Sjeff n = nice + SCHED_PRI_NHALF; 311113357Sjeff kseq->ksq_nice[n]--; 312113357Sjeff KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count.")); 313113357Sjeff 314113357Sjeff /* 315113357Sjeff * If this wasn't the smallest nice value or there are more in 316113357Sjeff * this bucket we can just return. Otherwise we have to recalculate 317113357Sjeff * the smallest nice. 318113357Sjeff */ 319113357Sjeff if (nice != kseq->ksq_nicemin || 320113357Sjeff kseq->ksq_nice[n] != 0 || 321113357Sjeff kseq->ksq_loads[PRI_TIMESHARE] == 0) 322113357Sjeff return; 323113357Sjeff 324113357Sjeff for (; n < SCHED_PRI_NRESV + 1; n++) 325113357Sjeff if (kseq->ksq_nice[n]) { 326113357Sjeff kseq->ksq_nicemin = n - SCHED_PRI_NHALF; 327113357Sjeff return; 328113357Sjeff } 329110267Sjeff} 330110267Sjeff 331113357Sjeff#ifdef SMP 332110267Sjeffstruct kseq * 333110267Sjeffkseq_load_highest(void) 334110267Sjeff{ 335110267Sjeff struct kseq *kseq; 336110267Sjeff int load; 337110267Sjeff int cpu; 338110267Sjeff int i; 339110267Sjeff 340110267Sjeff cpu = 0; 341110267Sjeff load = 0; 342110267Sjeff 343110267Sjeff for (i = 0; i < mp_maxid; i++) { 344110267Sjeff if (CPU_ABSENT(i)) 345110267Sjeff continue; 346110267Sjeff kseq = KSEQ_CPU(i); 347113357Sjeff if (kseq->ksq_load > load) { 348113357Sjeff load = kseq->ksq_load; 349110267Sjeff cpu = i; 350110267Sjeff } 351110267Sjeff } 352113371Sjeff if (load > 1) 353110267Sjeff return (KSEQ_CPU(cpu)); 354110267Sjeff 355110267Sjeff return (NULL); 356110267Sjeff} 357110267Sjeff#endif 358110267Sjeff 359110267Sjeffstruct kse * 360110267Sjeffkseq_choose(struct kseq *kseq) 361110267Sjeff{ 362110267Sjeff struct kse *ke; 363110267Sjeff struct runq *swap; 364110267Sjeff 365113357Sjeff swap = NULL; 366112994Sjeff 367113357Sjeff for (;;) { 368113357Sjeff ke = runq_choose(kseq->ksq_curr); 369113357Sjeff if (ke == NULL) { 370113357Sjeff /* 371113357Sjeff * We already swaped once and didn't get anywhere. 372113357Sjeff */ 373113357Sjeff if (swap) 374113357Sjeff break; 375113357Sjeff swap = kseq->ksq_curr; 376113357Sjeff kseq->ksq_curr = kseq->ksq_next; 377113357Sjeff kseq->ksq_next = swap; 378113357Sjeff continue; 379113357Sjeff } 380113357Sjeff /* 381113357Sjeff * If we encounter a slice of 0 the kse is in a 382113357Sjeff * TIMESHARE kse group and its nice was too far out 383113357Sjeff * of the range that receives slices. 384113357Sjeff */ 385113357Sjeff if (ke->ke_slice == 0) { 386113357Sjeff runq_remove(ke->ke_runq, ke); 387113357Sjeff sched_slice(ke); 388113357Sjeff ke->ke_runq = kseq->ksq_next; 389113357Sjeff runq_add(ke->ke_runq, ke); 390113357Sjeff continue; 391113357Sjeff } 392113357Sjeff return (ke); 393110267Sjeff } 394110267Sjeff 395113357Sjeff return (runq_choose(&kseq->ksq_idle)); 396110267Sjeff} 397110267Sjeff 398109864Sjeffstatic void 399110028Sjeffkseq_setup(struct kseq *kseq) 400110028Sjeff{ 401113357Sjeff runq_init(&kseq->ksq_timeshare[0]); 402113357Sjeff runq_init(&kseq->ksq_timeshare[1]); 403112994Sjeff runq_init(&kseq->ksq_idle); 404113357Sjeff 405113357Sjeff kseq->ksq_curr = &kseq->ksq_timeshare[0]; 406113357Sjeff kseq->ksq_next = &kseq->ksq_timeshare[1]; 407113357Sjeff 408113357Sjeff kseq->ksq_loads[PRI_ITHD] = 0; 409113357Sjeff kseq->ksq_loads[PRI_REALTIME] = 0; 410113357Sjeff kseq->ksq_loads[PRI_TIMESHARE] = 0; 411113357Sjeff kseq->ksq_loads[PRI_IDLE] = 0; 412113660Sjeff kseq->ksq_load = 0; 413110267Sjeff#ifdef SMP 414110267Sjeff kseq->ksq_rslices = 0; 415110267Sjeff#endif 416110028Sjeff} 417110028Sjeff 418110028Sjeffstatic void 419109864Sjeffsched_setup(void *dummy) 420109864Sjeff{ 421109864Sjeff int i; 422109864Sjeff 423113357Sjeff slice_min = (hz/100); 424113357Sjeff slice_max = (hz/10); 425111857Sjeff 426109864Sjeff mtx_lock_spin(&sched_lock); 427109864Sjeff /* init kseqs */ 428110028Sjeff for (i = 0; i < MAXCPU; i++) 429110028Sjeff kseq_setup(KSEQ_CPU(i)); 430113357Sjeff 431113357Sjeff kseq_add(KSEQ_SELF(), &kse0); 432109864Sjeff mtx_unlock_spin(&sched_lock); 433109864Sjeff} 434109864Sjeff 435109864Sjeff/* 436109864Sjeff * Scale the scheduling priority according to the "interactivity" of this 437109864Sjeff * process. 438109864Sjeff */ 439113357Sjeffstatic void 440109864Sjeffsched_priority(struct ksegrp *kg) 441109864Sjeff{ 442109864Sjeff int pri; 443109864Sjeff 444109864Sjeff if (kg->kg_pri_class != PRI_TIMESHARE) 445113357Sjeff return; 446109864Sjeff 447113357Sjeff pri = SCHED_PRI_INTERACT(sched_interact_score(kg)); 448111857Sjeff pri += SCHED_PRI_BASE; 449109864Sjeff pri += kg->kg_nice; 450109864Sjeff 451109864Sjeff if (pri > PRI_MAX_TIMESHARE) 452109864Sjeff pri = PRI_MAX_TIMESHARE; 453109864Sjeff else if (pri < PRI_MIN_TIMESHARE) 454109864Sjeff pri = PRI_MIN_TIMESHARE; 455109864Sjeff 456109864Sjeff kg->kg_user_pri = pri; 457109864Sjeff 458113357Sjeff return; 459109864Sjeff} 460109864Sjeff 461109864Sjeff/* 462112966Sjeff * Calculate a time slice based on the properties of the kseg and the runq 463112994Sjeff * that we're on. This is only for PRI_TIMESHARE ksegrps. 464109864Sjeff */ 465112966Sjeffstatic void 466112966Sjeffsched_slice(struct kse *ke) 467109864Sjeff{ 468113357Sjeff struct kseq *kseq; 469112966Sjeff struct ksegrp *kg; 470109864Sjeff 471112966Sjeff kg = ke->ke_ksegrp; 472113357Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 473109864Sjeff 474112966Sjeff /* 475112966Sjeff * Rationale: 476112966Sjeff * KSEs in interactive ksegs get the minimum slice so that we 477112966Sjeff * quickly notice if it abuses its advantage. 478112966Sjeff * 479112966Sjeff * KSEs in non-interactive ksegs are assigned a slice that is 480112966Sjeff * based on the ksegs nice value relative to the least nice kseg 481112966Sjeff * on the run queue for this cpu. 482112966Sjeff * 483112966Sjeff * If the KSE is less nice than all others it gets the maximum 484112966Sjeff * slice and other KSEs will adjust their slice relative to 485112966Sjeff * this when they first expire. 486112966Sjeff * 487112966Sjeff * There is 20 point window that starts relative to the least 488112966Sjeff * nice kse on the run queue. Slice size is determined by 489112966Sjeff * the kse distance from the last nice ksegrp. 490112966Sjeff * 491112966Sjeff * If you are outside of the window you will get no slice and 492112966Sjeff * you will be reevaluated each time you are selected on the 493112966Sjeff * run queue. 494112966Sjeff * 495112966Sjeff */ 496109864Sjeff 497113357Sjeff if (!SCHED_INTERACTIVE(kg)) { 498112966Sjeff int nice; 499112966Sjeff 500113357Sjeff nice = kg->kg_nice + (0 - kseq->ksq_nicemin); 501113357Sjeff if (kseq->ksq_loads[PRI_TIMESHARE] == 0 || 502113357Sjeff kg->kg_nice < kseq->ksq_nicemin) 503112966Sjeff ke->ke_slice = SCHED_SLICE_MAX; 504113357Sjeff else if (nice <= SCHED_PRI_NTHRESH) 505112966Sjeff ke->ke_slice = SCHED_SLICE_NICE(nice); 506112966Sjeff else 507112966Sjeff ke->ke_slice = 0; 508112966Sjeff } else 509112966Sjeff ke->ke_slice = SCHED_SLICE_MIN; 510112966Sjeff 511113357Sjeff CTR6(KTR_ULE, 512113357Sjeff "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)", 513113357Sjeff ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin, 514113357Sjeff kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg)); 515113357Sjeff 516110645Sjeff /* 517112994Sjeff * Check to see if we need to scale back the slp and run time 518112994Sjeff * in the kg. This will cause us to forget old interactivity 519112994Sjeff * while maintaining the current ratio. 520110645Sjeff */ 521113357Sjeff CTR4(KTR_ULE, "Slp vs Run %p (Slp %d, Run %d, Score %d)", 522113357Sjeff ke, kg->kg_slptime >> 10, kg->kg_runtime >> 10, 523113357Sjeff sched_interact_score(kg)); 524113357Sjeff 525110645Sjeff if ((kg->kg_runtime + kg->kg_slptime) > SCHED_SLP_RUN_MAX) { 526110645Sjeff kg->kg_runtime /= SCHED_SLP_RUN_THROTTLE; 527110645Sjeff kg->kg_slptime /= SCHED_SLP_RUN_THROTTLE; 528110645Sjeff } 529113357Sjeff CTR4(KTR_ULE, "Slp vs Run(2) %p (Slp %d, Run %d, Score %d)", 530113357Sjeff ke, kg->kg_slptime >> 10, kg->kg_runtime >> 10, 531113357Sjeff sched_interact_score(kg)); 532110645Sjeff 533112966Sjeff return; 534109864Sjeff} 535109864Sjeff 536111857Sjeffstatic int 537111857Sjeffsched_interact_score(struct ksegrp *kg) 538111857Sjeff{ 539111857Sjeff int big; 540111857Sjeff int small; 541111857Sjeff int base; 542111857Sjeff 543111857Sjeff if (kg->kg_runtime > kg->kg_slptime) { 544111857Sjeff big = kg->kg_runtime; 545111857Sjeff small = kg->kg_slptime; 546111857Sjeff base = SCHED_INTERACT_HALF; 547111857Sjeff } else { 548111857Sjeff big = kg->kg_slptime; 549111857Sjeff small = kg->kg_runtime; 550111857Sjeff base = 0; 551111857Sjeff } 552111857Sjeff 553111857Sjeff big /= SCHED_INTERACT_HALF; 554111857Sjeff if (big != 0) 555111857Sjeff small /= big; 556111857Sjeff else 557111857Sjeff small = 0; 558111857Sjeff 559111857Sjeff small += base; 560111857Sjeff /* XXX Factor in nice */ 561111857Sjeff return (small); 562111857Sjeff} 563111857Sjeff 564113357Sjeff/* 565113357Sjeff * This is only somewhat accurate since given many processes of the same 566113357Sjeff * priority they will switch when their slices run out, which will be 567113357Sjeff * at most SCHED_SLICE_MAX. 568113357Sjeff */ 569109864Sjeffint 570109864Sjeffsched_rr_interval(void) 571109864Sjeff{ 572109864Sjeff return (SCHED_SLICE_MAX); 573109864Sjeff} 574109864Sjeff 575109864Sjeffvoid 576109864Sjeffsched_pctcpu_update(struct kse *ke) 577109864Sjeff{ 578109864Sjeff /* 579109864Sjeff * Adjust counters and watermark for pctcpu calc. 580113357Sjeff * 581111793Sjeff * Shift the tick count out so that the divide doesn't round away 582111793Sjeff * our results. 583111793Sjeff */ 584111793Sjeff ke->ke_ticks <<= 10; 585109864Sjeff ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick)) * 586109864Sjeff SCHED_CPU_TICKS; 587111793Sjeff ke->ke_ticks >>= 10; 588109864Sjeff ke->ke_ltick = ticks; 589109864Sjeff ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS; 590109864Sjeff} 591109864Sjeff 592109864Sjeff#ifdef SMP 593110267Sjeff/* XXX Should be changed to kseq_load_lowest() */ 594109864Sjeffint 595109864Sjeffsched_pickcpu(void) 596109864Sjeff{ 597110028Sjeff struct kseq *kseq; 598110028Sjeff int load; 599109864Sjeff int cpu; 600109864Sjeff int i; 601109864Sjeff 602109864Sjeff if (!smp_started) 603109864Sjeff return (0); 604109864Sjeff 605110028Sjeff load = 0; 606110028Sjeff cpu = 0; 607109864Sjeff 608109864Sjeff for (i = 0; i < mp_maxid; i++) { 609109864Sjeff if (CPU_ABSENT(i)) 610109864Sjeff continue; 611110028Sjeff kseq = KSEQ_CPU(i); 612113357Sjeff if (kseq->ksq_load < load) { 613109864Sjeff cpu = i; 614113357Sjeff load = kseq->ksq_load; 615109864Sjeff } 616109864Sjeff } 617109864Sjeff 618109864Sjeff CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu); 619109864Sjeff return (cpu); 620109864Sjeff} 621109864Sjeff#else 622109864Sjeffint 623109864Sjeffsched_pickcpu(void) 624109864Sjeff{ 625109864Sjeff return (0); 626109864Sjeff} 627109864Sjeff#endif 628109864Sjeff 629109864Sjeffvoid 630109864Sjeffsched_prio(struct thread *td, u_char prio) 631109864Sjeff{ 632109864Sjeff struct kse *ke; 633109864Sjeff struct runq *rq; 634109864Sjeff 635109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 636109864Sjeff ke = td->td_kse; 637109864Sjeff td->td_priority = prio; 638109864Sjeff 639109864Sjeff if (TD_ON_RUNQ(td)) { 640109864Sjeff rq = ke->ke_runq; 641109864Sjeff 642109864Sjeff runq_remove(rq, ke); 643109864Sjeff runq_add(rq, ke); 644109864Sjeff } 645109864Sjeff} 646109864Sjeff 647109864Sjeffvoid 648109864Sjeffsched_switchout(struct thread *td) 649109864Sjeff{ 650109864Sjeff struct kse *ke; 651109864Sjeff 652109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 653109864Sjeff 654109864Sjeff ke = td->td_kse; 655109864Sjeff 656109864Sjeff td->td_last_kse = ke; 657113339Sjulian td->td_lastcpu = td->td_oncpu; 658113339Sjulian td->td_oncpu = NOCPU; 659111032Sjulian td->td_flags &= ~TDF_NEEDRESCHED; 660109864Sjeff 661109864Sjeff if (TD_IS_RUNNING(td)) { 662113357Sjeff runq_add(ke->ke_runq, ke); 663113357Sjeff /* setrunqueue(td); */ 664109864Sjeff return; 665111857Sjeff } 666113357Sjeff if (ke->ke_runq) 667113357Sjeff kseq_rem(KSEQ_CPU(ke->ke_cpu), ke); 668109864Sjeff /* 669109864Sjeff * We will not be on the run queue. So we must be 670109864Sjeff * sleeping or similar. 671109864Sjeff */ 672111585Sjulian if (td->td_proc->p_flag & P_THREADED) 673109864Sjeff kse_reassign(ke); 674109864Sjeff} 675109864Sjeff 676109864Sjeffvoid 677109864Sjeffsched_switchin(struct thread *td) 678109864Sjeff{ 679109864Sjeff /* struct kse *ke = td->td_kse; */ 680109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 681109864Sjeff 682113339Sjulian td->td_oncpu = PCPU_GET(cpuid); 683113357Sjeff 684109864Sjeff if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE && 685109864Sjeff td->td_priority != td->td_ksegrp->kg_user_pri) 686111032Sjulian curthread->td_flags |= TDF_NEEDRESCHED; 687109864Sjeff} 688109864Sjeff 689109864Sjeffvoid 690109864Sjeffsched_nice(struct ksegrp *kg, int nice) 691109864Sjeff{ 692113357Sjeff struct kse *ke; 693109864Sjeff struct thread *td; 694113357Sjeff struct kseq *kseq; 695109864Sjeff 696113357Sjeff /* 697113357Sjeff * We need to adjust the nice counts for running KSEs. 698113357Sjeff */ 699113357Sjeff if (kg->kg_pri_class == PRI_TIMESHARE) 700113357Sjeff FOREACH_KSE_IN_GROUP(kg, ke) { 701113357Sjeff if (ke->ke_state != KES_ONRUNQ && 702113357Sjeff ke->ke_state != KES_THREAD) 703113357Sjeff continue; 704113357Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 705113357Sjeff kseq_nice_rem(kseq, kg->kg_nice); 706113357Sjeff kseq_nice_add(kseq, nice); 707113357Sjeff } 708109864Sjeff kg->kg_nice = nice; 709109864Sjeff sched_priority(kg); 710113357Sjeff FOREACH_THREAD_IN_GROUP(kg, td) 711111032Sjulian td->td_flags |= TDF_NEEDRESCHED; 712109864Sjeff} 713109864Sjeff 714109864Sjeffvoid 715109864Sjeffsched_sleep(struct thread *td, u_char prio) 716109864Sjeff{ 717109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 718109864Sjeff 719109864Sjeff td->td_slptime = ticks; 720109864Sjeff td->td_priority = prio; 721109864Sjeff 722113357Sjeff CTR2(KTR_ULE, "sleep kse %p (tick: %d)", 723113357Sjeff td->td_kse, td->td_slptime); 724109864Sjeff} 725109864Sjeff 726109864Sjeffvoid 727109864Sjeffsched_wakeup(struct thread *td) 728109864Sjeff{ 729109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 730109864Sjeff 731109864Sjeff /* 732109864Sjeff * Let the kseg know how long we slept for. This is because process 733109864Sjeff * interactivity behavior is modeled in the kseg. 734109864Sjeff */ 735111788Sjeff if (td->td_slptime) { 736111788Sjeff struct ksegrp *kg; 737113357Sjeff int hzticks; 738109864Sjeff 739111788Sjeff kg = td->td_ksegrp; 740113357Sjeff hzticks = ticks - td->td_slptime; 741113357Sjeff kg->kg_slptime += hzticks << 10; 742111788Sjeff sched_priority(kg); 743113357Sjeff CTR2(KTR_ULE, "wakeup kse %p (%d ticks)", 744113357Sjeff td->td_kse, hzticks); 745111788Sjeff td->td_slptime = 0; 746109864Sjeff } 747109864Sjeff setrunqueue(td); 748109864Sjeff if (td->td_priority < curthread->td_priority) 749111032Sjulian curthread->td_flags |= TDF_NEEDRESCHED; 750109864Sjeff} 751109864Sjeff 752109864Sjeff/* 753109864Sjeff * Penalize the parent for creating a new child and initialize the child's 754109864Sjeff * priority. 755109864Sjeff */ 756109864Sjeffvoid 757113357Sjeffsched_fork(struct proc *p, struct proc *p1) 758109864Sjeff{ 759109864Sjeff 760109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 761109864Sjeff 762113357Sjeff sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1)); 763113357Sjeff sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1)); 764113357Sjeff sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1)); 765113357Sjeff} 766113357Sjeff 767113357Sjeffvoid 768113357Sjeffsched_fork_kse(struct kse *ke, struct kse *child) 769113357Sjeff{ 770113357Sjeff child->ke_slice = ke->ke_slice; 771113357Sjeff child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */ 772113357Sjeff child->ke_runq = NULL; 773113357Sjeff 774113357Sjeff /* 775113357Sjeff * Claim that we've been running for one second for statistical 776113357Sjeff * purposes. 777113357Sjeff */ 778113357Sjeff child->ke_ticks = 0; 779113357Sjeff child->ke_ltick = ticks; 780113357Sjeff child->ke_ftick = ticks - hz; 781113357Sjeff} 782113357Sjeff 783113357Sjeffvoid 784113357Sjeffsched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child) 785113357Sjeff{ 786109864Sjeff /* XXX Need something better here */ 787110645Sjeff if (kg->kg_slptime > kg->kg_runtime) { 788111857Sjeff child->kg_slptime = SCHED_DYN_RANGE; 789111857Sjeff child->kg_runtime = kg->kg_slptime / SCHED_DYN_RANGE; 790110645Sjeff } else { 791111857Sjeff child->kg_runtime = SCHED_DYN_RANGE; 792111857Sjeff child->kg_slptime = kg->kg_runtime / SCHED_DYN_RANGE; 793110645Sjeff } 794113357Sjeff 795109864Sjeff child->kg_user_pri = kg->kg_user_pri; 796113357Sjeff child->kg_nice = kg->kg_nice; 797113357Sjeff} 798109864Sjeff 799113357Sjeffvoid 800113357Sjeffsched_fork_thread(struct thread *td, struct thread *child) 801113357Sjeff{ 802113357Sjeff} 803113357Sjeff 804113357Sjeffvoid 805113357Sjeffsched_class(struct ksegrp *kg, int class) 806113357Sjeff{ 807113357Sjeff struct kseq *kseq; 808113357Sjeff struct kse *ke; 809113357Sjeff 810113357Sjeff if (kg->kg_pri_class == class) 811113357Sjeff return; 812113357Sjeff 813113357Sjeff FOREACH_KSE_IN_GROUP(kg, ke) { 814113357Sjeff if (ke->ke_state != KES_ONRUNQ && 815113357Sjeff ke->ke_state != KES_THREAD) 816113357Sjeff continue; 817113357Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 818113357Sjeff 819113386Sjeff kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--; 820113386Sjeff kseq->ksq_loads[PRI_BASE(class)]++; 821113357Sjeff 822113357Sjeff if (kg->kg_pri_class == PRI_TIMESHARE) 823113357Sjeff kseq_nice_rem(kseq, kg->kg_nice); 824113357Sjeff else if (class == PRI_TIMESHARE) 825113357Sjeff kseq_nice_add(kseq, kg->kg_nice); 826109970Sjeff } 827109970Sjeff 828113357Sjeff kg->kg_pri_class = class; 829109864Sjeff} 830109864Sjeff 831109864Sjeff/* 832109864Sjeff * Return some of the child's priority and interactivity to the parent. 833109864Sjeff */ 834109864Sjeffvoid 835113357Sjeffsched_exit(struct proc *p, struct proc *child) 836109864Sjeff{ 837109864Sjeff /* XXX Need something better here */ 838109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 839113372Sjeff sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child)); 840109864Sjeff} 841109864Sjeff 842109864Sjeffvoid 843113372Sjeffsched_exit_kse(struct kse *ke, struct kse *child) 844113372Sjeff{ 845113372Sjeff kseq_rem(KSEQ_CPU(child->ke_cpu), child); 846113372Sjeff} 847113372Sjeff 848113372Sjeffvoid 849113372Sjeffsched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child) 850113372Sjeff{ 851113372Sjeff} 852113372Sjeff 853113372Sjeffvoid 854113372Sjeffsched_exit_thread(struct thread *td, struct thread *child) 855113372Sjeff{ 856113372Sjeff} 857113372Sjeff 858113372Sjeffvoid 859113357Sjeffsched_clock(struct kse *ke) 860109864Sjeff{ 861113357Sjeff struct kseq *kseq; 862113357Sjeff struct ksegrp *kg; 863113357Sjeff struct thread *td; 864113357Sjeff#if 0 865109864Sjeff struct kse *nke; 866110267Sjeff#endif 867109864Sjeff 868113357Sjeff /* 869113357Sjeff * sched_setup() apparently happens prior to stathz being set. We 870113357Sjeff * need to resolve the timers earlier in the boot so we can avoid 871113357Sjeff * calculating this here. 872113357Sjeff */ 873113357Sjeff if (realstathz == 0) { 874113357Sjeff realstathz = stathz ? stathz : hz; 875113357Sjeff tickincr = hz / realstathz; 876113357Sjeff /* 877113357Sjeff * XXX This does not work for values of stathz that are much 878113357Sjeff * larger than hz. 879113357Sjeff */ 880113357Sjeff if (tickincr == 0) 881113357Sjeff tickincr = 1; 882113357Sjeff } 883109864Sjeff 884113357Sjeff td = ke->ke_thread; 885113357Sjeff kg = ke->ke_ksegrp; 886109864Sjeff 887110028Sjeff mtx_assert(&sched_lock, MA_OWNED); 888110028Sjeff KASSERT((td != NULL), ("schedclock: null thread pointer")); 889110028Sjeff 890110028Sjeff /* Adjust ticks for pctcpu */ 891111793Sjeff ke->ke_ticks++; 892109971Sjeff ke->ke_ltick = ticks; 893112994Sjeff 894109971Sjeff /* Go up to one second beyond our max and then trim back down */ 895109971Sjeff if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick) 896109971Sjeff sched_pctcpu_update(ke); 897109971Sjeff 898110028Sjeff if (td->td_kse->ke_flags & KEF_IDLEKSE) 899109864Sjeff return; 900110028Sjeff 901113357Sjeff CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)", 902113357Sjeff ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10); 903113357Sjeff 904110028Sjeff /* 905113357Sjeff * We only do slicing code for TIMESHARE ksegrps. 906113357Sjeff */ 907113357Sjeff if (kg->kg_pri_class != PRI_TIMESHARE) 908113357Sjeff return; 909113357Sjeff /* 910110028Sjeff * Check for a higher priority task on the run queue. This can happen 911110028Sjeff * on SMP if another processor woke up a process on our runq. 912110028Sjeff */ 913110028Sjeff kseq = KSEQ_SELF(); 914113357Sjeff#if 0 915113357Sjeff if (kseq->ksq_load > 1 && (nke = kseq_choose(kseq)) != NULL) { 916113357Sjeff if (sched_strict && 917113357Sjeff nke->ke_thread->td_priority < td->td_priority) 918113357Sjeff td->td_flags |= TDF_NEEDRESCHED; 919113357Sjeff else if (nke->ke_thread->td_priority < 920113357Sjeff td->td_priority SCHED_PRIO_SLOP) 921113357Sjeff 922113357Sjeff if (nke->ke_thread->td_priority < td->td_priority) 923113357Sjeff td->td_flags |= TDF_NEEDRESCHED; 924113357Sjeff } 925110267Sjeff#endif 926109864Sjeff /* 927110645Sjeff * We used a tick charge it to the ksegrp so that we can compute our 928113357Sjeff * interactivity. 929109864Sjeff */ 930113357Sjeff kg->kg_runtime += tickincr << 10; 931110645Sjeff 932109864Sjeff /* 933109864Sjeff * We used up one time slice. 934109864Sjeff */ 935109864Sjeff ke->ke_slice--; 936113357Sjeff#ifdef SMP 937113370Sjeff kseq->ksq_rslices--; 938113357Sjeff#endif 939113357Sjeff 940113357Sjeff if (ke->ke_slice > 0) 941113357Sjeff return; 942109864Sjeff /* 943113357Sjeff * We're out of time, recompute priorities and requeue. 944109864Sjeff */ 945113357Sjeff kseq_rem(kseq, ke); 946113357Sjeff sched_priority(kg); 947113357Sjeff sched_slice(ke); 948113357Sjeff if (SCHED_CURR(kg, ke)) 949113357Sjeff ke->ke_runq = kseq->ksq_curr; 950113357Sjeff else 951113357Sjeff ke->ke_runq = kseq->ksq_next; 952113357Sjeff kseq_add(kseq, ke); 953113357Sjeff td->td_flags |= TDF_NEEDRESCHED; 954109864Sjeff} 955109864Sjeff 956109864Sjeffint 957109864Sjeffsched_runnable(void) 958109864Sjeff{ 959109864Sjeff struct kseq *kseq; 960109864Sjeff 961110028Sjeff kseq = KSEQ_SELF(); 962109864Sjeff 963113357Sjeff if (kseq->ksq_load) 964109970Sjeff return (1); 965109970Sjeff#ifdef SMP 966110028Sjeff /* 967110028Sjeff * For SMP we may steal other processor's KSEs. Just search until we 968110028Sjeff * verify that at least on other cpu has a runnable task. 969110028Sjeff */ 970109970Sjeff if (smp_started) { 971109970Sjeff int i; 972109970Sjeff 973109970Sjeff for (i = 0; i < mp_maxid; i++) { 974109970Sjeff if (CPU_ABSENT(i)) 975109970Sjeff continue; 976110028Sjeff kseq = KSEQ_CPU(i); 977113660Sjeff if (kseq->ksq_load > 1) 978109970Sjeff return (1); 979109970Sjeff } 980109970Sjeff } 981109970Sjeff#endif 982109970Sjeff return (0); 983109864Sjeff} 984109864Sjeff 985109864Sjeffvoid 986109864Sjeffsched_userret(struct thread *td) 987109864Sjeff{ 988109864Sjeff struct ksegrp *kg; 989109864Sjeff 990109864Sjeff kg = td->td_ksegrp; 991109864Sjeff 992109864Sjeff if (td->td_priority != kg->kg_user_pri) { 993109864Sjeff mtx_lock_spin(&sched_lock); 994109864Sjeff td->td_priority = kg->kg_user_pri; 995109864Sjeff mtx_unlock_spin(&sched_lock); 996109864Sjeff } 997109864Sjeff} 998109864Sjeff 999109864Sjeffstruct kse * 1000109970Sjeffsched_choose(void) 1001109970Sjeff{ 1002110028Sjeff struct kseq *kseq; 1003109970Sjeff struct kse *ke; 1004109970Sjeff 1005113357Sjeff#ifdef SMP 1006112966Sjeffretry: 1007113357Sjeff#endif 1008113370Sjeff kseq = KSEQ_SELF(); 1009110028Sjeff ke = kseq_choose(kseq); 1010109864Sjeff if (ke) { 1011113357Sjeff runq_remove(ke->ke_runq, ke); 1012109864Sjeff ke->ke_state = KES_THREAD; 1013112966Sjeff 1014113357Sjeff if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) { 1015113357Sjeff CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)", 1016113357Sjeff ke, ke->ke_runq, ke->ke_slice, 1017113357Sjeff ke->ke_thread->td_priority); 1018113357Sjeff } 1019113357Sjeff return (ke); 1020109864Sjeff } 1021109864Sjeff 1022109970Sjeff#ifdef SMP 1023113370Sjeff if (smp_started) { 1024109970Sjeff /* 1025109970Sjeff * Find the cpu with the highest load and steal one proc. 1026109970Sjeff */ 1027113370Sjeff if ((kseq = kseq_load_highest()) == NULL) 1028113370Sjeff return (NULL); 1029113370Sjeff 1030113370Sjeff /* 1031113370Sjeff * Remove this kse from this kseq and runq and then requeue 1032113370Sjeff * on the current processor. Then we will dequeue it 1033113370Sjeff * normally above. 1034113370Sjeff */ 1035113370Sjeff ke = kseq_choose(kseq); 1036113370Sjeff runq_remove(ke->ke_runq, ke); 1037113370Sjeff ke->ke_state = KES_THREAD; 1038113370Sjeff kseq_rem(kseq, ke); 1039113370Sjeff 1040113370Sjeff ke->ke_cpu = PCPU_GET(cpuid); 1041113370Sjeff sched_add(ke); 1042113370Sjeff goto retry; 1043109970Sjeff } 1044109970Sjeff#endif 1045113357Sjeff 1046113357Sjeff return (NULL); 1047109864Sjeff} 1048109864Sjeff 1049109864Sjeffvoid 1050109864Sjeffsched_add(struct kse *ke) 1051109864Sjeff{ 1052110267Sjeff struct kseq *kseq; 1053113357Sjeff struct ksegrp *kg; 1054109864Sjeff 1055109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 1056110267Sjeff KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE")); 1057109864Sjeff KASSERT((ke->ke_thread->td_kse != NULL), 1058110267Sjeff ("sched_add: No KSE on thread")); 1059109864Sjeff KASSERT(ke->ke_state != KES_ONRUNQ, 1060110267Sjeff ("sched_add: kse %p (%s) already in run queue", ke, 1061109864Sjeff ke->ke_proc->p_comm)); 1062109864Sjeff KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1063110267Sjeff ("sched_add: process swapped out")); 1064113387Sjeff KASSERT(ke->ke_runq == NULL, 1065113387Sjeff ("sched_add: KSE %p is still assigned to a run queue", ke)); 1066109864Sjeff 1067113357Sjeff kg = ke->ke_ksegrp; 1068113357Sjeff 1069113386Sjeff switch (PRI_BASE(kg->kg_pri_class)) { 1070112994Sjeff case PRI_ITHD: 1071112994Sjeff case PRI_REALTIME: 1072112994Sjeff kseq = KSEQ_SELF(); 1073113357Sjeff ke->ke_runq = kseq->ksq_curr; 1074113357Sjeff ke->ke_slice = SCHED_SLICE_MAX; 1075113660Sjeff ke->ke_cpu = PCPU_GET(cpuid); 1076112994Sjeff break; 1077112994Sjeff case PRI_TIMESHARE: 1078113357Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 1079113387Sjeff if (SCHED_CURR(kg, ke)) 1080113387Sjeff ke->ke_runq = kseq->ksq_curr; 1081113387Sjeff else 1082113387Sjeff ke->ke_runq = kseq->ksq_next; 1083113357Sjeff break; 1084112994Sjeff case PRI_IDLE: 1085111789Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 1086113357Sjeff /* 1087113357Sjeff * This is for priority prop. 1088113357Sjeff */ 1089113357Sjeff if (ke->ke_thread->td_priority < PRI_MAX_TIMESHARE) 1090113357Sjeff ke->ke_runq = kseq->ksq_curr; 1091113357Sjeff else 1092113357Sjeff ke->ke_runq = &kseq->ksq_idle; 1093113357Sjeff ke->ke_slice = SCHED_SLICE_MIN; 1094112994Sjeff break; 1095113357Sjeff default: 1096113357Sjeff panic("Unknown pri class.\n"); 1097113357Sjeff break; 1098112994Sjeff } 1099109864Sjeff 1100109864Sjeff ke->ke_ksegrp->kg_runq_kses++; 1101109864Sjeff ke->ke_state = KES_ONRUNQ; 1102109864Sjeff 1103113357Sjeff runq_add(ke->ke_runq, ke); 1104113387Sjeff kseq_add(kseq, ke); 1105109864Sjeff} 1106109864Sjeff 1107109864Sjeffvoid 1108109864Sjeffsched_rem(struct kse *ke) 1109109864Sjeff{ 1110113357Sjeff struct kseq *kseq; 1111113357Sjeff 1112109864Sjeff mtx_assert(&sched_lock, MA_OWNED); 1113113387Sjeff KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 1114109864Sjeff 1115109864Sjeff ke->ke_state = KES_THREAD; 1116109864Sjeff ke->ke_ksegrp->kg_runq_kses--; 1117113357Sjeff kseq = KSEQ_CPU(ke->ke_cpu); 1118113357Sjeff runq_remove(ke->ke_runq, ke); 1119113357Sjeff kseq_rem(kseq, ke); 1120109864Sjeff} 1121109864Sjeff 1122109864Sjefffixpt_t 1123109864Sjeffsched_pctcpu(struct kse *ke) 1124109864Sjeff{ 1125109864Sjeff fixpt_t pctcpu; 1126109864Sjeff 1127109864Sjeff pctcpu = 0; 1128109864Sjeff 1129109864Sjeff if (ke->ke_ticks) { 1130109864Sjeff int rtick; 1131109864Sjeff 1132109864Sjeff /* Update to account for time potentially spent sleeping */ 1133109864Sjeff ke->ke_ltick = ticks; 1134109864Sjeff sched_pctcpu_update(ke); 1135109864Sjeff 1136109864Sjeff /* How many rtick per second ? */ 1137111793Sjeff rtick = ke->ke_ticks / SCHED_CPU_TIME; 1138110226Sscottl pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT; 1139109864Sjeff } 1140109864Sjeff 1141109864Sjeff ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick; 1142109864Sjeff 1143109864Sjeff return (pctcpu); 1144109864Sjeff} 1145109864Sjeff 1146109864Sjeffint 1147109864Sjeffsched_sizeof_kse(void) 1148109864Sjeff{ 1149109864Sjeff return (sizeof(struct kse) + sizeof(struct ke_sched)); 1150109864Sjeff} 1151109864Sjeff 1152109864Sjeffint 1153109864Sjeffsched_sizeof_ksegrp(void) 1154109864Sjeff{ 1155109864Sjeff return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 1156109864Sjeff} 1157109864Sjeff 1158109864Sjeffint 1159109864Sjeffsched_sizeof_proc(void) 1160109864Sjeff{ 1161109864Sjeff return (sizeof(struct proc)); 1162109864Sjeff} 1163109864Sjeff 1164109864Sjeffint 1165109864Sjeffsched_sizeof_thread(void) 1166109864Sjeff{ 1167109864Sjeff return (sizeof(struct thread) + sizeof(struct td_sched)); 1168109864Sjeff} 1169