sched_ule.c revision 114471
1/*- 2 * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 * 26 * $FreeBSD: head/sys/kern/sched_ule.c 114471 2003-05-02 00:33:12Z julian $ 27 */ 28 29#include <sys/param.h> 30#include <sys/systm.h> 31#include <sys/kernel.h> 32#include <sys/ktr.h> 33#include <sys/lock.h> 34#include <sys/mutex.h> 35#include <sys/proc.h> 36#include <sys/resource.h> 37#include <sys/sched.h> 38#include <sys/smp.h> 39#include <sys/sx.h> 40#include <sys/sysctl.h> 41#include <sys/sysproto.h> 42#include <sys/vmmeter.h> 43#ifdef DDB 44#include <ddb/ddb.h> 45#endif 46#ifdef KTRACE 47#include <sys/uio.h> 48#include <sys/ktrace.h> 49#endif 50 51#include <machine/cpu.h> 52 53#define KTR_ULE KTR_NFS 54 55/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 56/* XXX This is bogus compatability crap for ps */ 57static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 58SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 59 60static void sched_setup(void *dummy); 61SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 62 63static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED"); 64 65static int sched_strict; 66SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, ""); 67 68static int slice_min = 1; 69SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, ""); 70 71static int slice_max = 2; 72SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, ""); 73 74int realstathz; 75int tickincr = 1; 76 77/* 78 * These datastructures are allocated within their parent datastructure but 79 * are scheduler specific. 80 */ 81 82struct ke_sched { 83 int ske_slice; 84 struct runq *ske_runq; 85 /* The following variables are only used for pctcpu calculation */ 86 int ske_ltick; /* Last tick that we were running on */ 87 int ske_ftick; /* First tick that we were running on */ 88 int ske_ticks; /* Tick count */ 89 /* CPU that we have affinity for. */ 90 u_char ske_cpu; 91}; 92#define ke_slice ke_sched->ske_slice 93#define ke_runq ke_sched->ske_runq 94#define ke_ltick ke_sched->ske_ltick 95#define ke_ftick ke_sched->ske_ftick 96#define ke_ticks ke_sched->ske_ticks 97#define ke_cpu ke_sched->ske_cpu 98 99struct kg_sched { 100 int skg_slptime; /* Number of ticks we vol. slept */ 101 int skg_runtime; /* Number of ticks we were running */ 102}; 103#define kg_slptime kg_sched->skg_slptime 104#define kg_runtime kg_sched->skg_runtime 105 106struct td_sched { 107 int std_slptime; 108}; 109#define td_slptime td_sched->std_slptime 110 111struct td_sched td_sched; 112struct ke_sched ke_sched; 113struct kg_sched kg_sched; 114 115struct ke_sched *kse0_sched = &ke_sched; 116struct kg_sched *ksegrp0_sched = &kg_sched; 117struct p_sched *proc0_sched = NULL; 118struct td_sched *thread0_sched = &td_sched; 119 120/* 121 * This priority range has 20 priorities on either end that are reachable 122 * only through nice values. 123 * 124 * PRI_RANGE: Total priority range for timeshare threads. 125 * PRI_NRESV: Reserved priorities for nice. 126 * PRI_BASE: The start of the dynamic range. 127 * DYN_RANGE: Number of priorities that are available int the dynamic 128 * priority range. 129 */ 130#define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1) 131#define SCHED_PRI_NRESV PRIO_TOTAL 132#define SCHED_PRI_NHALF (PRIO_TOTAL / 2) 133#define SCHED_PRI_NTHRESH (SCHED_PRI_NHALF - 1) 134#define SCHED_PRI_BASE ((SCHED_PRI_NRESV / 2) + PRI_MIN_TIMESHARE) 135#define SCHED_DYN_RANGE (SCHED_PRI_RANGE - SCHED_PRI_NRESV) 136#define SCHED_PRI_INTERACT(score) \ 137 ((score) * SCHED_DYN_RANGE / SCHED_INTERACT_RANGE) 138 139/* 140 * These determine the interactivity of a process. 141 * 142 * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate 143 * before throttling back. 144 * SLP_RUN_THROTTLE: Divisor for reducing slp/run time. 145 * INTERACT_RANGE: Range of interactivity values. Smaller is better. 146 * INTERACT_HALF: Convenience define, half of the interactivity range. 147 * INTERACT_THRESH: Threshhold for placement on the current runq. 148 */ 149#define SCHED_SLP_RUN_MAX ((hz / 10) << 10) 150#define SCHED_SLP_RUN_THROTTLE (10) 151#define SCHED_INTERACT_RANGE (100) 152#define SCHED_INTERACT_HALF (SCHED_INTERACT_RANGE / 2) 153#define SCHED_INTERACT_THRESH (10) 154 155/* 156 * These parameters and macros determine the size of the time slice that is 157 * granted to each thread. 158 * 159 * SLICE_MIN: Minimum time slice granted, in units of ticks. 160 * SLICE_MAX: Maximum time slice granted. 161 * SLICE_RANGE: Range of available time slices scaled by hz. 162 * SLICE_SCALE: The number slices granted per val in the range of [0, max]. 163 * SLICE_NICE: Determine the amount of slice granted to a scaled nice. 164 */ 165#define SCHED_SLICE_MIN (slice_min) 166#define SCHED_SLICE_MAX (slice_max) 167#define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1) 168#define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max)) 169#define SCHED_SLICE_NICE(nice) \ 170 (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH)) 171 172/* 173 * This macro determines whether or not the kse belongs on the current or 174 * next run queue. 175 * 176 * XXX nice value should effect how interactive a kg is. 177 */ 178#define SCHED_INTERACTIVE(kg) \ 179 (sched_interact_score(kg) < SCHED_INTERACT_THRESH) 180#define SCHED_CURR(kg, ke) \ 181 (ke->ke_thread->td_priority < PRI_MIN_TIMESHARE || SCHED_INTERACTIVE(kg)) 182 183/* 184 * Cpu percentage computation macros and defines. 185 * 186 * SCHED_CPU_TIME: Number of seconds to average the cpu usage across. 187 * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across. 188 */ 189 190#define SCHED_CPU_TIME 10 191#define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME) 192 193/* 194 * kseq - per processor runqs and statistics. 195 */ 196 197#define KSEQ_NCLASS (PRI_IDLE + 1) /* Number of run classes. */ 198 199struct kseq { 200 struct runq ksq_idle; /* Queue of IDLE threads. */ 201 struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */ 202 struct runq *ksq_next; /* Next timeshare queue. */ 203 struct runq *ksq_curr; /* Current queue. */ 204 int ksq_loads[KSEQ_NCLASS]; /* Load for each class */ 205 int ksq_load; /* Aggregate load. */ 206 short ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */ 207 short ksq_nicemin; /* Least nice. */ 208#ifdef SMP 209 unsigned int ksq_rslices; /* Slices on run queue */ 210#endif 211}; 212 213/* 214 * One kse queue per processor. 215 */ 216#ifdef SMP 217struct kseq kseq_cpu[MAXCPU]; 218#define KSEQ_SELF() (&kseq_cpu[PCPU_GET(cpuid)]) 219#define KSEQ_CPU(x) (&kseq_cpu[(x)]) 220#else 221struct kseq kseq_cpu; 222#define KSEQ_SELF() (&kseq_cpu) 223#define KSEQ_CPU(x) (&kseq_cpu) 224#endif 225 226static void sched_slice(struct kse *ke); 227static void sched_priority(struct ksegrp *kg); 228static int sched_interact_score(struct ksegrp *kg); 229void sched_pctcpu_update(struct kse *ke); 230int sched_pickcpu(void); 231 232/* Operations on per processor queues */ 233static struct kse * kseq_choose(struct kseq *kseq); 234static void kseq_setup(struct kseq *kseq); 235static void kseq_add(struct kseq *kseq, struct kse *ke); 236static void kseq_rem(struct kseq *kseq, struct kse *ke); 237static void kseq_nice_add(struct kseq *kseq, int nice); 238static void kseq_nice_rem(struct kseq *kseq, int nice); 239void kseq_print(int cpu); 240#ifdef SMP 241struct kseq * kseq_load_highest(void); 242#endif 243 244void 245kseq_print(int cpu) 246{ 247 struct kseq *kseq; 248 int i; 249 250 kseq = KSEQ_CPU(cpu); 251 252 printf("kseq:\n"); 253 printf("\tload: %d\n", kseq->ksq_load); 254 printf("\tload ITHD: %d\n", kseq->ksq_loads[PRI_ITHD]); 255 printf("\tload REALTIME: %d\n", kseq->ksq_loads[PRI_REALTIME]); 256 printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]); 257 printf("\tload IDLE: %d\n", kseq->ksq_loads[PRI_IDLE]); 258 printf("\tnicemin:\t%d\n", kseq->ksq_nicemin); 259 printf("\tnice counts:\n"); 260 for (i = 0; i < PRIO_TOTAL + 1; i++) 261 if (kseq->ksq_nice[i]) 262 printf("\t\t%d = %d\n", 263 i - SCHED_PRI_NHALF, kseq->ksq_nice[i]); 264} 265 266static void 267kseq_add(struct kseq *kseq, struct kse *ke) 268{ 269 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++; 270 kseq->ksq_load++; 271 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 272 CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))", 273 ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority, 274 ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin); 275 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 276 kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice); 277#ifdef SMP 278 kseq->ksq_rslices += ke->ke_slice; 279#endif 280} 281 282static void 283kseq_rem(struct kseq *kseq, struct kse *ke) 284{ 285 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--; 286 kseq->ksq_load--; 287 ke->ke_runq = NULL; 288 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 289 kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice); 290#ifdef SMP 291 kseq->ksq_rslices -= ke->ke_slice; 292#endif 293} 294 295static void 296kseq_nice_add(struct kseq *kseq, int nice) 297{ 298 /* Normalize to zero. */ 299 kseq->ksq_nice[nice + SCHED_PRI_NHALF]++; 300 if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 0) 301 kseq->ksq_nicemin = nice; 302} 303 304static void 305kseq_nice_rem(struct kseq *kseq, int nice) 306{ 307 int n; 308 309 /* Normalize to zero. */ 310 n = nice + SCHED_PRI_NHALF; 311 kseq->ksq_nice[n]--; 312 KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count.")); 313 314 /* 315 * If this wasn't the smallest nice value or there are more in 316 * this bucket we can just return. Otherwise we have to recalculate 317 * the smallest nice. 318 */ 319 if (nice != kseq->ksq_nicemin || 320 kseq->ksq_nice[n] != 0 || 321 kseq->ksq_loads[PRI_TIMESHARE] == 0) 322 return; 323 324 for (; n < SCHED_PRI_NRESV + 1; n++) 325 if (kseq->ksq_nice[n]) { 326 kseq->ksq_nicemin = n - SCHED_PRI_NHALF; 327 return; 328 } 329} 330 331#ifdef SMP 332struct kseq * 333kseq_load_highest(void) 334{ 335 struct kseq *kseq; 336 int load; 337 int cpu; 338 int i; 339 340 cpu = 0; 341 load = 0; 342 343 for (i = 0; i < mp_maxid; i++) { 344 if (CPU_ABSENT(i)) 345 continue; 346 kseq = KSEQ_CPU(i); 347 if (kseq->ksq_load > load) { 348 load = kseq->ksq_load; 349 cpu = i; 350 } 351 } 352 if (load > 1) 353 return (KSEQ_CPU(cpu)); 354 355 return (NULL); 356} 357#endif 358 359struct kse * 360kseq_choose(struct kseq *kseq) 361{ 362 struct kse *ke; 363 struct runq *swap; 364 365 swap = NULL; 366 367 for (;;) { 368 ke = runq_choose(kseq->ksq_curr); 369 if (ke == NULL) { 370 /* 371 * We already swaped once and didn't get anywhere. 372 */ 373 if (swap) 374 break; 375 swap = kseq->ksq_curr; 376 kseq->ksq_curr = kseq->ksq_next; 377 kseq->ksq_next = swap; 378 continue; 379 } 380 /* 381 * If we encounter a slice of 0 the kse is in a 382 * TIMESHARE kse group and its nice was too far out 383 * of the range that receives slices. 384 */ 385 if (ke->ke_slice == 0) { 386 runq_remove(ke->ke_runq, ke); 387 sched_slice(ke); 388 ke->ke_runq = kseq->ksq_next; 389 runq_add(ke->ke_runq, ke); 390 continue; 391 } 392 return (ke); 393 } 394 395 return (runq_choose(&kseq->ksq_idle)); 396} 397 398static void 399kseq_setup(struct kseq *kseq) 400{ 401 runq_init(&kseq->ksq_timeshare[0]); 402 runq_init(&kseq->ksq_timeshare[1]); 403 runq_init(&kseq->ksq_idle); 404 405 kseq->ksq_curr = &kseq->ksq_timeshare[0]; 406 kseq->ksq_next = &kseq->ksq_timeshare[1]; 407 408 kseq->ksq_loads[PRI_ITHD] = 0; 409 kseq->ksq_loads[PRI_REALTIME] = 0; 410 kseq->ksq_loads[PRI_TIMESHARE] = 0; 411 kseq->ksq_loads[PRI_IDLE] = 0; 412 kseq->ksq_load = 0; 413#ifdef SMP 414 kseq->ksq_rslices = 0; 415#endif 416} 417 418static void 419sched_setup(void *dummy) 420{ 421 int i; 422 423 slice_min = (hz/100); 424 slice_max = (hz/10); 425 426 mtx_lock_spin(&sched_lock); 427 /* init kseqs */ 428 for (i = 0; i < MAXCPU; i++) 429 kseq_setup(KSEQ_CPU(i)); 430 431 kseq_add(KSEQ_SELF(), &kse0); 432 mtx_unlock_spin(&sched_lock); 433} 434 435/* 436 * Scale the scheduling priority according to the "interactivity" of this 437 * process. 438 */ 439static void 440sched_priority(struct ksegrp *kg) 441{ 442 int pri; 443 444 if (kg->kg_pri_class != PRI_TIMESHARE) 445 return; 446 447 pri = SCHED_PRI_INTERACT(sched_interact_score(kg)); 448 pri += SCHED_PRI_BASE; 449 pri += kg->kg_nice; 450 451 if (pri > PRI_MAX_TIMESHARE) 452 pri = PRI_MAX_TIMESHARE; 453 else if (pri < PRI_MIN_TIMESHARE) 454 pri = PRI_MIN_TIMESHARE; 455 456 kg->kg_user_pri = pri; 457 458 return; 459} 460 461/* 462 * Calculate a time slice based on the properties of the kseg and the runq 463 * that we're on. This is only for PRI_TIMESHARE ksegrps. 464 */ 465static void 466sched_slice(struct kse *ke) 467{ 468 struct kseq *kseq; 469 struct ksegrp *kg; 470 471 kg = ke->ke_ksegrp; 472 kseq = KSEQ_CPU(ke->ke_cpu); 473 474 /* 475 * Rationale: 476 * KSEs in interactive ksegs get the minimum slice so that we 477 * quickly notice if it abuses its advantage. 478 * 479 * KSEs in non-interactive ksegs are assigned a slice that is 480 * based on the ksegs nice value relative to the least nice kseg 481 * on the run queue for this cpu. 482 * 483 * If the KSE is less nice than all others it gets the maximum 484 * slice and other KSEs will adjust their slice relative to 485 * this when they first expire. 486 * 487 * There is 20 point window that starts relative to the least 488 * nice kse on the run queue. Slice size is determined by 489 * the kse distance from the last nice ksegrp. 490 * 491 * If you are outside of the window you will get no slice and 492 * you will be reevaluated each time you are selected on the 493 * run queue. 494 * 495 */ 496 497 if (!SCHED_INTERACTIVE(kg)) { 498 int nice; 499 500 nice = kg->kg_nice + (0 - kseq->ksq_nicemin); 501 if (kseq->ksq_loads[PRI_TIMESHARE] == 0 || 502 kg->kg_nice < kseq->ksq_nicemin) 503 ke->ke_slice = SCHED_SLICE_MAX; 504 else if (nice <= SCHED_PRI_NTHRESH) 505 ke->ke_slice = SCHED_SLICE_NICE(nice); 506 else 507 ke->ke_slice = 0; 508 } else 509 ke->ke_slice = SCHED_SLICE_MIN; 510 511 CTR6(KTR_ULE, 512 "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)", 513 ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin, 514 kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg)); 515 516 /* 517 * Check to see if we need to scale back the slp and run time 518 * in the kg. This will cause us to forget old interactivity 519 * while maintaining the current ratio. 520 */ 521 CTR4(KTR_ULE, "Slp vs Run %p (Slp %d, Run %d, Score %d)", 522 ke, kg->kg_slptime >> 10, kg->kg_runtime >> 10, 523 sched_interact_score(kg)); 524 525 if ((kg->kg_runtime + kg->kg_slptime) > SCHED_SLP_RUN_MAX) { 526 kg->kg_runtime /= SCHED_SLP_RUN_THROTTLE; 527 kg->kg_slptime /= SCHED_SLP_RUN_THROTTLE; 528 } 529 CTR4(KTR_ULE, "Slp vs Run(2) %p (Slp %d, Run %d, Score %d)", 530 ke, kg->kg_slptime >> 10, kg->kg_runtime >> 10, 531 sched_interact_score(kg)); 532 533 return; 534} 535 536static int 537sched_interact_score(struct ksegrp *kg) 538{ 539 int big; 540 int small; 541 int base; 542 543 if (kg->kg_runtime > kg->kg_slptime) { 544 big = kg->kg_runtime; 545 small = kg->kg_slptime; 546 base = SCHED_INTERACT_HALF; 547 } else { 548 big = kg->kg_slptime; 549 small = kg->kg_runtime; 550 base = 0; 551 } 552 553 big /= SCHED_INTERACT_HALF; 554 if (big != 0) 555 small /= big; 556 else 557 small = 0; 558 559 small += base; 560 /* XXX Factor in nice */ 561 return (small); 562} 563 564/* 565 * This is only somewhat accurate since given many processes of the same 566 * priority they will switch when their slices run out, which will be 567 * at most SCHED_SLICE_MAX. 568 */ 569int 570sched_rr_interval(void) 571{ 572 return (SCHED_SLICE_MAX); 573} 574 575void 576sched_pctcpu_update(struct kse *ke) 577{ 578 /* 579 * Adjust counters and watermark for pctcpu calc. 580 * 581 * Shift the tick count out so that the divide doesn't round away 582 * our results. 583 */ 584 ke->ke_ticks <<= 10; 585 ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick)) * 586 SCHED_CPU_TICKS; 587 ke->ke_ticks >>= 10; 588 ke->ke_ltick = ticks; 589 ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS; 590} 591 592#ifdef SMP 593/* XXX Should be changed to kseq_load_lowest() */ 594int 595sched_pickcpu(void) 596{ 597 struct kseq *kseq; 598 int load; 599 int cpu; 600 int i; 601 602 if (!smp_started) 603 return (0); 604 605 load = 0; 606 cpu = 0; 607 608 for (i = 0; i < mp_maxid; i++) { 609 if (CPU_ABSENT(i)) 610 continue; 611 kseq = KSEQ_CPU(i); 612 if (kseq->ksq_load < load) { 613 cpu = i; 614 load = kseq->ksq_load; 615 } 616 } 617 618 CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu); 619 return (cpu); 620} 621#else 622int 623sched_pickcpu(void) 624{ 625 return (0); 626} 627#endif 628 629void 630sched_prio(struct thread *td, u_char prio) 631{ 632 struct kse *ke; 633 struct runq *rq; 634 635 mtx_assert(&sched_lock, MA_OWNED); 636 ke = td->td_kse; 637 td->td_priority = prio; 638 639 if (TD_ON_RUNQ(td)) { 640 rq = ke->ke_runq; 641 642 runq_remove(rq, ke); 643 runq_add(rq, ke); 644 } 645} 646 647void 648sched_switchout(struct thread *td) 649{ 650 struct kse *ke; 651 652 mtx_assert(&sched_lock, MA_OWNED); 653 654 ke = td->td_kse; 655 656 td->td_last_kse = ke; 657 td->td_lastcpu = td->td_oncpu; 658 td->td_oncpu = NOCPU; 659 td->td_flags &= ~TDF_NEEDRESCHED; 660 661 if (TD_IS_RUNNING(td)) { 662 runq_add(ke->ke_runq, ke); 663 /* setrunqueue(td); */ 664 return; 665 } 666 if (ke->ke_runq) 667 kseq_rem(KSEQ_CPU(ke->ke_cpu), ke); 668 /* 669 * We will not be on the run queue. So we must be 670 * sleeping or similar. 671 */ 672 if (td->td_proc->p_flag & P_THREADED) 673 kse_reassign(ke); 674} 675 676void 677sched_switchin(struct thread *td) 678{ 679 /* struct kse *ke = td->td_kse; */ 680 mtx_assert(&sched_lock, MA_OWNED); 681 682 td->td_oncpu = PCPU_GET(cpuid); 683 684 if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE && 685 td->td_priority != td->td_ksegrp->kg_user_pri) 686 curthread->td_flags |= TDF_NEEDRESCHED; 687} 688 689void 690sched_nice(struct ksegrp *kg, int nice) 691{ 692 struct kse *ke; 693 struct thread *td; 694 struct kseq *kseq; 695 696 PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED); 697 mtx_assert(&sched_lock, MA_OWNED); 698 /* 699 * We need to adjust the nice counts for running KSEs. 700 */ 701 if (kg->kg_pri_class == PRI_TIMESHARE) 702 FOREACH_KSE_IN_GROUP(kg, ke) { 703 if (ke->ke_state != KES_ONRUNQ && 704 ke->ke_state != KES_THREAD) 705 continue; 706 kseq = KSEQ_CPU(ke->ke_cpu); 707 kseq_nice_rem(kseq, kg->kg_nice); 708 kseq_nice_add(kseq, nice); 709 } 710 kg->kg_nice = nice; 711 sched_priority(kg); 712 FOREACH_THREAD_IN_GROUP(kg, td) 713 td->td_flags |= TDF_NEEDRESCHED; 714} 715 716void 717sched_sleep(struct thread *td, u_char prio) 718{ 719 mtx_assert(&sched_lock, MA_OWNED); 720 721 td->td_slptime = ticks; 722 td->td_priority = prio; 723 724 CTR2(KTR_ULE, "sleep kse %p (tick: %d)", 725 td->td_kse, td->td_slptime); 726} 727 728void 729sched_wakeup(struct thread *td) 730{ 731 mtx_assert(&sched_lock, MA_OWNED); 732 733 /* 734 * Let the kseg know how long we slept for. This is because process 735 * interactivity behavior is modeled in the kseg. 736 */ 737 if (td->td_slptime) { 738 struct ksegrp *kg; 739 int hzticks; 740 741 kg = td->td_ksegrp; 742 hzticks = ticks - td->td_slptime; 743 kg->kg_slptime += hzticks << 10; 744 sched_priority(kg); 745 CTR2(KTR_ULE, "wakeup kse %p (%d ticks)", 746 td->td_kse, hzticks); 747 td->td_slptime = 0; 748 } 749 setrunqueue(td); 750 if (td->td_priority < curthread->td_priority) 751 curthread->td_flags |= TDF_NEEDRESCHED; 752} 753 754/* 755 * Penalize the parent for creating a new child and initialize the child's 756 * priority. 757 */ 758void 759sched_fork(struct proc *p, struct proc *p1) 760{ 761 762 mtx_assert(&sched_lock, MA_OWNED); 763 764 sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1)); 765 sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1)); 766 sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1)); 767} 768 769void 770sched_fork_kse(struct kse *ke, struct kse *child) 771{ 772 773 child->ke_slice = ke->ke_slice; 774 child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */ 775 child->ke_runq = NULL; 776 777 /* 778 * Claim that we've been running for one second for statistical 779 * purposes. 780 */ 781 child->ke_ticks = 0; 782 child->ke_ltick = ticks; 783 child->ke_ftick = ticks - hz; 784} 785 786void 787sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child) 788{ 789 790 PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED); 791 /* XXX Need something better here */ 792 if (kg->kg_slptime > kg->kg_runtime) { 793 child->kg_slptime = SCHED_DYN_RANGE; 794 child->kg_runtime = kg->kg_slptime / SCHED_DYN_RANGE; 795 } else { 796 child->kg_runtime = SCHED_DYN_RANGE; 797 child->kg_slptime = kg->kg_runtime / SCHED_DYN_RANGE; 798 } 799 800 child->kg_user_pri = kg->kg_user_pri; 801 child->kg_nice = kg->kg_nice; 802} 803 804void 805sched_fork_thread(struct thread *td, struct thread *child) 806{ 807} 808 809void 810sched_class(struct ksegrp *kg, int class) 811{ 812 struct kseq *kseq; 813 struct kse *ke; 814 815 mtx_assert(&sched_lock, MA_OWNED); 816 if (kg->kg_pri_class == class) 817 return; 818 819 FOREACH_KSE_IN_GROUP(kg, ke) { 820 if (ke->ke_state != KES_ONRUNQ && 821 ke->ke_state != KES_THREAD) 822 continue; 823 kseq = KSEQ_CPU(ke->ke_cpu); 824 825 kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--; 826 kseq->ksq_loads[PRI_BASE(class)]++; 827 828 if (kg->kg_pri_class == PRI_TIMESHARE) 829 kseq_nice_rem(kseq, kg->kg_nice); 830 else if (class == PRI_TIMESHARE) 831 kseq_nice_add(kseq, kg->kg_nice); 832 } 833 834 kg->kg_pri_class = class; 835} 836 837/* 838 * Return some of the child's priority and interactivity to the parent. 839 */ 840void 841sched_exit(struct proc *p, struct proc *child) 842{ 843 /* XXX Need something better here */ 844 mtx_assert(&sched_lock, MA_OWNED); 845 sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child)); 846} 847 848void 849sched_exit_kse(struct kse *ke, struct kse *child) 850{ 851 kseq_rem(KSEQ_CPU(child->ke_cpu), child); 852} 853 854void 855sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child) 856{ 857} 858 859void 860sched_exit_thread(struct thread *td, struct thread *child) 861{ 862} 863 864void 865sched_clock(struct kse *ke) 866{ 867 struct kseq *kseq; 868 struct ksegrp *kg; 869 struct thread *td; 870#if 0 871 struct kse *nke; 872#endif 873 874 /* 875 * sched_setup() apparently happens prior to stathz being set. We 876 * need to resolve the timers earlier in the boot so we can avoid 877 * calculating this here. 878 */ 879 if (realstathz == 0) { 880 realstathz = stathz ? stathz : hz; 881 tickincr = hz / realstathz; 882 /* 883 * XXX This does not work for values of stathz that are much 884 * larger than hz. 885 */ 886 if (tickincr == 0) 887 tickincr = 1; 888 } 889 890 td = ke->ke_thread; 891 kg = ke->ke_ksegrp; 892 893 mtx_assert(&sched_lock, MA_OWNED); 894 KASSERT((td != NULL), ("schedclock: null thread pointer")); 895 896 /* Adjust ticks for pctcpu */ 897 ke->ke_ticks++; 898 ke->ke_ltick = ticks; 899 900 /* Go up to one second beyond our max and then trim back down */ 901 if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick) 902 sched_pctcpu_update(ke); 903 904 if (td->td_flags & TD_IDLETD) 905 return; 906 907 CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)", 908 ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10); 909 910 /* 911 * We only do slicing code for TIMESHARE ksegrps. 912 */ 913 if (kg->kg_pri_class != PRI_TIMESHARE) 914 return; 915 /* 916 * Check for a higher priority task on the run queue. This can happen 917 * on SMP if another processor woke up a process on our runq. 918 */ 919 kseq = KSEQ_SELF(); 920#if 0 921 if (kseq->ksq_load > 1 && (nke = kseq_choose(kseq)) != NULL) { 922 if (sched_strict && 923 nke->ke_thread->td_priority < td->td_priority) 924 td->td_flags |= TDF_NEEDRESCHED; 925 else if (nke->ke_thread->td_priority < 926 td->td_priority SCHED_PRIO_SLOP) 927 928 if (nke->ke_thread->td_priority < td->td_priority) 929 td->td_flags |= TDF_NEEDRESCHED; 930 } 931#endif 932 /* 933 * We used a tick charge it to the ksegrp so that we can compute our 934 * interactivity. 935 */ 936 kg->kg_runtime += tickincr << 10; 937 938 /* 939 * We used up one time slice. 940 */ 941 ke->ke_slice--; 942#ifdef SMP 943 kseq->ksq_rslices--; 944#endif 945 946 if (ke->ke_slice > 0) 947 return; 948 /* 949 * We're out of time, recompute priorities and requeue. 950 */ 951 kseq_rem(kseq, ke); 952 sched_priority(kg); 953 sched_slice(ke); 954 if (SCHED_CURR(kg, ke)) 955 ke->ke_runq = kseq->ksq_curr; 956 else 957 ke->ke_runq = kseq->ksq_next; 958 kseq_add(kseq, ke); 959 td->td_flags |= TDF_NEEDRESCHED; 960} 961 962int 963sched_runnable(void) 964{ 965 struct kseq *kseq; 966 967 kseq = KSEQ_SELF(); 968 969 if (kseq->ksq_load) 970 return (1); 971#ifdef SMP 972 /* 973 * For SMP we may steal other processor's KSEs. Just search until we 974 * verify that at least on other cpu has a runnable task. 975 */ 976 if (smp_started) { 977 int i; 978 979 for (i = 0; i < mp_maxid; i++) { 980 if (CPU_ABSENT(i)) 981 continue; 982 kseq = KSEQ_CPU(i); 983 if (kseq->ksq_load > 1) 984 return (1); 985 } 986 } 987#endif 988 return (0); 989} 990 991void 992sched_userret(struct thread *td) 993{ 994 struct ksegrp *kg; 995 996 kg = td->td_ksegrp; 997 998 if (td->td_priority != kg->kg_user_pri) { 999 mtx_lock_spin(&sched_lock); 1000 td->td_priority = kg->kg_user_pri; 1001 mtx_unlock_spin(&sched_lock); 1002 } 1003} 1004 1005struct kse * 1006sched_choose(void) 1007{ 1008 struct kseq *kseq; 1009 struct kse *ke; 1010 1011#ifdef SMP 1012retry: 1013#endif 1014 kseq = KSEQ_SELF(); 1015 ke = kseq_choose(kseq); 1016 if (ke) { 1017 runq_remove(ke->ke_runq, ke); 1018 ke->ke_state = KES_THREAD; 1019 1020 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) { 1021 CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)", 1022 ke, ke->ke_runq, ke->ke_slice, 1023 ke->ke_thread->td_priority); 1024 } 1025 return (ke); 1026 } 1027 1028#ifdef SMP 1029 if (smp_started) { 1030 /* 1031 * Find the cpu with the highest load and steal one proc. 1032 */ 1033 if ((kseq = kseq_load_highest()) == NULL) 1034 return (NULL); 1035 1036 /* 1037 * Remove this kse from this kseq and runq and then requeue 1038 * on the current processor. Then we will dequeue it 1039 * normally above. 1040 */ 1041 ke = kseq_choose(kseq); 1042 runq_remove(ke->ke_runq, ke); 1043 ke->ke_state = KES_THREAD; 1044 kseq_rem(kseq, ke); 1045 1046 ke->ke_cpu = PCPU_GET(cpuid); 1047 sched_add(ke); 1048 goto retry; 1049 } 1050#endif 1051 1052 return (NULL); 1053} 1054 1055void 1056sched_add(struct kse *ke) 1057{ 1058 struct kseq *kseq; 1059 struct ksegrp *kg; 1060 1061 mtx_assert(&sched_lock, MA_OWNED); 1062 KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE")); 1063 KASSERT((ke->ke_thread->td_kse != NULL), 1064 ("sched_add: No KSE on thread")); 1065 KASSERT(ke->ke_state != KES_ONRUNQ, 1066 ("sched_add: kse %p (%s) already in run queue", ke, 1067 ke->ke_proc->p_comm)); 1068 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1069 ("sched_add: process swapped out")); 1070 KASSERT(ke->ke_runq == NULL, 1071 ("sched_add: KSE %p is still assigned to a run queue", ke)); 1072 1073 kg = ke->ke_ksegrp; 1074 1075 switch (PRI_BASE(kg->kg_pri_class)) { 1076 case PRI_ITHD: 1077 case PRI_REALTIME: 1078 kseq = KSEQ_SELF(); 1079 ke->ke_runq = kseq->ksq_curr; 1080 ke->ke_slice = SCHED_SLICE_MAX; 1081 ke->ke_cpu = PCPU_GET(cpuid); 1082 break; 1083 case PRI_TIMESHARE: 1084 kseq = KSEQ_CPU(ke->ke_cpu); 1085 if (SCHED_CURR(kg, ke)) 1086 ke->ke_runq = kseq->ksq_curr; 1087 else 1088 ke->ke_runq = kseq->ksq_next; 1089 break; 1090 case PRI_IDLE: 1091 kseq = KSEQ_CPU(ke->ke_cpu); 1092 /* 1093 * This is for priority prop. 1094 */ 1095 if (ke->ke_thread->td_priority < PRI_MAX_TIMESHARE) 1096 ke->ke_runq = kseq->ksq_curr; 1097 else 1098 ke->ke_runq = &kseq->ksq_idle; 1099 ke->ke_slice = SCHED_SLICE_MIN; 1100 break; 1101 default: 1102 panic("Unknown pri class.\n"); 1103 break; 1104 } 1105 1106 ke->ke_ksegrp->kg_runq_kses++; 1107 ke->ke_state = KES_ONRUNQ; 1108 1109 runq_add(ke->ke_runq, ke); 1110 kseq_add(kseq, ke); 1111} 1112 1113void 1114sched_rem(struct kse *ke) 1115{ 1116 struct kseq *kseq; 1117 1118 mtx_assert(&sched_lock, MA_OWNED); 1119 KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 1120 1121 ke->ke_state = KES_THREAD; 1122 ke->ke_ksegrp->kg_runq_kses--; 1123 kseq = KSEQ_CPU(ke->ke_cpu); 1124 runq_remove(ke->ke_runq, ke); 1125 kseq_rem(kseq, ke); 1126} 1127 1128fixpt_t 1129sched_pctcpu(struct kse *ke) 1130{ 1131 fixpt_t pctcpu; 1132 1133 pctcpu = 0; 1134 1135 if (ke->ke_ticks) { 1136 int rtick; 1137 1138 /* Update to account for time potentially spent sleeping */ 1139 ke->ke_ltick = ticks; 1140 sched_pctcpu_update(ke); 1141 1142 /* How many rtick per second ? */ 1143 rtick = ke->ke_ticks / SCHED_CPU_TIME; 1144 pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT; 1145 } 1146 1147 mtx_lock_spin(&sched_lock); 1148 ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick; 1149 mtx_unlock_spin(&sched_lock); 1150 1151 return (pctcpu); 1152} 1153 1154int 1155sched_sizeof_kse(void) 1156{ 1157 return (sizeof(struct kse) + sizeof(struct ke_sched)); 1158} 1159 1160int 1161sched_sizeof_ksegrp(void) 1162{ 1163 return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 1164} 1165 1166int 1167sched_sizeof_proc(void) 1168{ 1169 return (sizeof(struct proc)); 1170} 1171 1172int 1173sched_sizeof_thread(void) 1174{ 1175 return (sizeof(struct thread) + sizeof(struct td_sched)); 1176} 1177