sched_ule.c revision 121790
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 27#include <sys/cdefs.h> 28__FBSDID("$FreeBSD: head/sys/kern/sched_ule.c 121790 2003-10-31 11:16:04Z jeff $"); 29 30#include <sys/param.h> 31#include <sys/systm.h> 32#include <sys/kernel.h> 33#include <sys/ktr.h> 34#include <sys/lock.h> 35#include <sys/mutex.h> 36#include <sys/proc.h> 37#include <sys/resource.h> 38#include <sys/sched.h> 39#include <sys/smp.h> 40#include <sys/sx.h> 41#include <sys/sysctl.h> 42#include <sys/sysproto.h> 43#include <sys/vmmeter.h> 44#ifdef DDB 45#include <ddb/ddb.h> 46#endif 47#ifdef KTRACE 48#include <sys/uio.h> 49#include <sys/ktrace.h> 50#endif 51 52#include <machine/cpu.h> 53#include <machine/smp.h> 54 55#define KTR_ULE KTR_NFS 56 57/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 58/* XXX This is bogus compatability crap for ps */ 59static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 60SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 61 62static void sched_setup(void *dummy); 63SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 64 65static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED"); 66 67static int sched_strict; 68SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, ""); 69 70static int slice_min = 1; 71SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, ""); 72 73static int slice_max = 10; 74SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, ""); 75 76int realstathz; 77int tickincr = 1; 78 79#ifdef SMP 80/* Callout to handle load balancing SMP systems. */ 81static struct callout kseq_lb_callout; 82#endif 83 84/* 85 * These datastructures are allocated within their parent datastructure but 86 * are scheduler specific. 87 */ 88 89struct ke_sched { 90 int ske_slice; 91 struct runq *ske_runq; 92 /* The following variables are only used for pctcpu calculation */ 93 int ske_ltick; /* Last tick that we were running on */ 94 int ske_ftick; /* First tick that we were running on */ 95 int ske_ticks; /* Tick count */ 96 /* CPU that we have affinity for. */ 97 u_char ske_cpu; 98}; 99#define ke_slice ke_sched->ske_slice 100#define ke_runq ke_sched->ske_runq 101#define ke_ltick ke_sched->ske_ltick 102#define ke_ftick ke_sched->ske_ftick 103#define ke_ticks ke_sched->ske_ticks 104#define ke_cpu ke_sched->ske_cpu 105#define ke_assign ke_procq.tqe_next 106 107#define KEF_ASSIGNED KEF_SCHED0 /* KSE is being migrated. */ 108 109struct kg_sched { 110 int skg_slptime; /* Number of ticks we vol. slept */ 111 int skg_runtime; /* Number of ticks we were running */ 112}; 113#define kg_slptime kg_sched->skg_slptime 114#define kg_runtime kg_sched->skg_runtime 115 116struct td_sched { 117 int std_slptime; 118}; 119#define td_slptime td_sched->std_slptime 120 121struct td_sched td_sched; 122struct ke_sched ke_sched; 123struct kg_sched kg_sched; 124 125struct ke_sched *kse0_sched = &ke_sched; 126struct kg_sched *ksegrp0_sched = &kg_sched; 127struct p_sched *proc0_sched = NULL; 128struct td_sched *thread0_sched = &td_sched; 129 130/* 131 * The priority is primarily determined by the interactivity score. Thus, we 132 * give lower(better) priorities to kse groups that use less CPU. The nice 133 * value is then directly added to this to allow nice to have some effect 134 * on latency. 135 * 136 * PRI_RANGE: Total priority range for timeshare threads. 137 * PRI_NRESV: Number of nice values. 138 * PRI_BASE: The start of the dynamic range. 139 */ 140#define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1) 141#define SCHED_PRI_NRESV PRIO_TOTAL 142#define SCHED_PRI_NHALF (PRIO_TOTAL / 2) 143#define SCHED_PRI_NTHRESH (SCHED_PRI_NHALF - 1) 144#define SCHED_PRI_BASE (PRI_MIN_TIMESHARE) 145#define SCHED_PRI_INTERACT(score) \ 146 ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX) 147 148/* 149 * These determine the interactivity of a process. 150 * 151 * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate 152 * before throttling back. 153 * SLP_RUN_THROTTLE: Divisor for reducing slp/run time at fork time. 154 * INTERACT_MAX: Maximum interactivity value. Smaller is better. 155 * INTERACT_THRESH: Threshhold for placement on the current runq. 156 */ 157#define SCHED_SLP_RUN_MAX ((hz * 5) << 10) 158#define SCHED_SLP_RUN_THROTTLE (100) 159#define SCHED_INTERACT_MAX (100) 160#define SCHED_INTERACT_HALF (SCHED_INTERACT_MAX / 2) 161#define SCHED_INTERACT_THRESH (30) 162 163/* 164 * These parameters and macros determine the size of the time slice that is 165 * granted to each thread. 166 * 167 * SLICE_MIN: Minimum time slice granted, in units of ticks. 168 * SLICE_MAX: Maximum time slice granted. 169 * SLICE_RANGE: Range of available time slices scaled by hz. 170 * SLICE_SCALE: The number slices granted per val in the range of [0, max]. 171 * SLICE_NICE: Determine the amount of slice granted to a scaled nice. 172 */ 173#define SCHED_SLICE_MIN (slice_min) 174#define SCHED_SLICE_MAX (slice_max) 175#define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1) 176#define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max)) 177#define SCHED_SLICE_NICE(nice) \ 178 (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH)) 179 180/* 181 * This macro determines whether or not the kse belongs on the current or 182 * next run queue. 183 * 184 * XXX nice value should effect how interactive a kg is. 185 */ 186#define SCHED_INTERACTIVE(kg) \ 187 (sched_interact_score(kg) < SCHED_INTERACT_THRESH) 188#define SCHED_CURR(kg, ke) \ 189 (ke->ke_thread->td_priority != kg->kg_user_pri || \ 190 SCHED_INTERACTIVE(kg)) 191 192/* 193 * Cpu percentage computation macros and defines. 194 * 195 * SCHED_CPU_TIME: Number of seconds to average the cpu usage across. 196 * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across. 197 */ 198 199#define SCHED_CPU_TIME 10 200#define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME) 201 202/* 203 * kseq - per processor runqs and statistics. 204 */ 205 206#define KSEQ_NCLASS (PRI_IDLE + 1) /* Number of run classes. */ 207 208struct kseq { 209 struct runq ksq_idle; /* Queue of IDLE threads. */ 210 struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */ 211 struct runq *ksq_next; /* Next timeshare queue. */ 212 struct runq *ksq_curr; /* Current queue. */ 213 int ksq_loads[KSEQ_NCLASS]; /* Load for each class */ 214 int ksq_load; /* Aggregate load. */ 215 short ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */ 216 short ksq_nicemin; /* Least nice. */ 217#ifdef SMP 218 unsigned int ksq_rslices; /* Slices on run queue */ 219 int ksq_cpus; /* Count of CPUs in this kseq. */ 220 struct kse *ksq_assigned; /* KSEs assigned by another CPU. */ 221#endif 222}; 223 224/* 225 * One kse queue per processor. 226 */ 227#ifdef SMP 228static int kseq_idle; 229static struct kseq kseq_cpu[MAXCPU]; 230static struct kseq *kseq_idmap[MAXCPU]; 231#define KSEQ_SELF() (kseq_idmap[PCPU_GET(cpuid)]) 232#define KSEQ_CPU(x) (kseq_idmap[(x)]) 233#else 234static struct kseq kseq_cpu; 235#define KSEQ_SELF() (&kseq_cpu) 236#define KSEQ_CPU(x) (&kseq_cpu) 237#endif 238 239static void sched_slice(struct kse *ke); 240static void sched_priority(struct ksegrp *kg); 241static int sched_interact_score(struct ksegrp *kg); 242static void sched_interact_update(struct ksegrp *kg); 243static void sched_pctcpu_update(struct kse *ke); 244 245/* Operations on per processor queues */ 246static struct kse * kseq_choose(struct kseq *kseq); 247static void kseq_setup(struct kseq *kseq); 248static void kseq_add(struct kseq *kseq, struct kse *ke); 249static void kseq_rem(struct kseq *kseq, struct kse *ke); 250static void kseq_nice_add(struct kseq *kseq, int nice); 251static void kseq_nice_rem(struct kseq *kseq, int nice); 252void kseq_print(int cpu); 253#ifdef SMP 254#if 0 255static int sched_pickcpu(void); 256#endif 257static struct kse *runq_steal(struct runq *rq); 258static struct kseq *kseq_load_highest(void); 259static void kseq_balance(void *arg); 260static void kseq_move(struct kseq *from, int cpu); 261static int kseq_find(void); 262static void kseq_notify(struct kse *ke, int cpu); 263static void kseq_assign(struct kseq *); 264static struct kse *kseq_steal(struct kseq *kseq); 265#endif 266 267void 268kseq_print(int cpu) 269{ 270 struct kseq *kseq; 271 int i; 272 273 kseq = KSEQ_CPU(cpu); 274 275 printf("kseq:\n"); 276 printf("\tload: %d\n", kseq->ksq_load); 277 printf("\tload ITHD: %d\n", kseq->ksq_loads[PRI_ITHD]); 278 printf("\tload REALTIME: %d\n", kseq->ksq_loads[PRI_REALTIME]); 279 printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]); 280 printf("\tload IDLE: %d\n", kseq->ksq_loads[PRI_IDLE]); 281 printf("\tnicemin:\t%d\n", kseq->ksq_nicemin); 282 printf("\tnice counts:\n"); 283 for (i = 0; i < PRIO_TOTAL + 1; i++) 284 if (kseq->ksq_nice[i]) 285 printf("\t\t%d = %d\n", 286 i - SCHED_PRI_NHALF, kseq->ksq_nice[i]); 287} 288 289static void 290kseq_add(struct kseq *kseq, struct kse *ke) 291{ 292 mtx_assert(&sched_lock, MA_OWNED); 293 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++; 294 kseq->ksq_load++; 295 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 296 CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))", 297 ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority, 298 ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin); 299 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 300 kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice); 301#ifdef SMP 302 kseq->ksq_rslices += ke->ke_slice; 303#endif 304} 305 306static void 307kseq_rem(struct kseq *kseq, struct kse *ke) 308{ 309 mtx_assert(&sched_lock, MA_OWNED); 310 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--; 311 kseq->ksq_load--; 312 ke->ke_runq = NULL; 313 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) 314 kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice); 315#ifdef SMP 316 kseq->ksq_rslices -= ke->ke_slice; 317#endif 318} 319 320static void 321kseq_nice_add(struct kseq *kseq, int nice) 322{ 323 mtx_assert(&sched_lock, MA_OWNED); 324 /* Normalize to zero. */ 325 kseq->ksq_nice[nice + SCHED_PRI_NHALF]++; 326 if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1) 327 kseq->ksq_nicemin = nice; 328} 329 330static void 331kseq_nice_rem(struct kseq *kseq, int nice) 332{ 333 int n; 334 335 mtx_assert(&sched_lock, MA_OWNED); 336 /* Normalize to zero. */ 337 n = nice + SCHED_PRI_NHALF; 338 kseq->ksq_nice[n]--; 339 KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count.")); 340 341 /* 342 * If this wasn't the smallest nice value or there are more in 343 * this bucket we can just return. Otherwise we have to recalculate 344 * the smallest nice. 345 */ 346 if (nice != kseq->ksq_nicemin || 347 kseq->ksq_nice[n] != 0 || 348 kseq->ksq_loads[PRI_TIMESHARE] == 0) 349 return; 350 351 for (; n < SCHED_PRI_NRESV + 1; n++) 352 if (kseq->ksq_nice[n]) { 353 kseq->ksq_nicemin = n - SCHED_PRI_NHALF; 354 return; 355 } 356} 357 358#ifdef SMP 359/* 360 * kseq_balance is a simple CPU load balancing algorithm. It operates by 361 * finding the least loaded and most loaded cpu and equalizing their load 362 * by migrating some processes. 363 * 364 * Dealing only with two CPUs at a time has two advantages. Firstly, most 365 * installations will only have 2 cpus. Secondly, load balancing too much at 366 * once can have an unpleasant effect on the system. The scheduler rarely has 367 * enough information to make perfect decisions. So this algorithm chooses 368 * algorithm simplicity and more gradual effects on load in larger systems. 369 * 370 * It could be improved by considering the priorities and slices assigned to 371 * each task prior to balancing them. There are many pathological cases with 372 * any approach and so the semi random algorithm below may work as well as any. 373 * 374 */ 375static void 376kseq_balance(void *arg) 377{ 378 struct kseq *kseq; 379 int high_load; 380 int low_load; 381 int high_cpu; 382 int low_cpu; 383 int move; 384 int diff; 385 int i; 386 387 high_cpu = 0; 388 low_cpu = 0; 389 high_load = 0; 390 low_load = -1; 391 392 mtx_lock_spin(&sched_lock); 393 if (smp_started == 0) 394 goto out; 395 396 for (i = 0; i < mp_maxid; i++) { 397 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0) 398 continue; 399 kseq = KSEQ_CPU(i); 400 if (kseq->ksq_load > high_load) { 401 high_load = kseq->ksq_load; 402 high_cpu = i; 403 } 404 if (low_load == -1 || kseq->ksq_load < low_load) { 405 low_load = kseq->ksq_load; 406 low_cpu = i; 407 } 408 } 409 410 kseq = KSEQ_CPU(high_cpu); 411 412 high_load = kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] + 413 kseq->ksq_loads[PRI_REALTIME]; 414 /* 415 * Nothing to do. 416 */ 417 if (high_load < kseq->ksq_cpus + 1) 418 goto out; 419 420 high_load -= kseq->ksq_cpus; 421 422 if (low_load >= high_load) 423 goto out; 424 425 diff = high_load - low_load; 426 move = diff / 2; 427 if (diff & 0x1) 428 move++; 429 430 for (i = 0; i < move; i++) 431 kseq_move(kseq, low_cpu); 432 433out: 434 mtx_unlock_spin(&sched_lock); 435 callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL); 436 437 return; 438} 439 440static struct kseq * 441kseq_load_highest(void) 442{ 443 struct kseq *kseq; 444 int load; 445 int cpu; 446 int i; 447 448 mtx_assert(&sched_lock, MA_OWNED); 449 cpu = 0; 450 load = 0; 451 452 for (i = 0; i < mp_maxid; i++) { 453 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0) 454 continue; 455 kseq = KSEQ_CPU(i); 456 if (kseq->ksq_load > load) { 457 load = kseq->ksq_load; 458 cpu = i; 459 } 460 } 461 kseq = KSEQ_CPU(cpu); 462 463 if ((kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] + 464 kseq->ksq_loads[PRI_REALTIME]) > kseq->ksq_cpus) 465 return (kseq); 466 467 return (NULL); 468} 469 470static void 471kseq_move(struct kseq *from, int cpu) 472{ 473 struct kse *ke; 474 475 ke = kseq_steal(from); 476 runq_remove(ke->ke_runq, ke); 477 ke->ke_state = KES_THREAD; 478 kseq_rem(from, ke); 479 480 ke->ke_cpu = cpu; 481 sched_add(ke->ke_thread); 482} 483 484static int 485kseq_find(void) 486{ 487 struct kseq *high; 488 489 if (!smp_started) 490 return (0); 491 if (kseq_idle & PCPU_GET(cpumask)) 492 return (0); 493 /* 494 * Find the cpu with the highest load and steal one proc. 495 */ 496 if ((high = kseq_load_highest()) == NULL || 497 high == KSEQ_SELF()) { 498 /* 499 * If we couldn't find one, set ourselves in the 500 * idle map. 501 */ 502 atomic_set_int(&kseq_idle, PCPU_GET(cpumask)); 503 return (0); 504 } 505 /* 506 * Remove this kse from this kseq and runq and then requeue 507 * on the current processor. We now have a load of one! 508 */ 509 kseq_move(high, PCPU_GET(cpuid)); 510 511 return (1); 512} 513 514static void 515kseq_assign(struct kseq *kseq) 516{ 517 struct kse *nke; 518 struct kse *ke; 519 520 do { 521 ke = kseq->ksq_assigned; 522 } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke, NULL)); 523 for (; ke != NULL; ke = nke) { 524 nke = ke->ke_assign; 525 ke->ke_flags &= ~KEF_ASSIGNED; 526 sched_add(ke->ke_thread); 527 } 528} 529 530static void 531kseq_notify(struct kse *ke, int cpu) 532{ 533 struct kseq *kseq; 534 struct thread *td; 535 struct pcpu *pcpu; 536 537 ke->ke_flags |= KEF_ASSIGNED; 538 539 kseq = KSEQ_CPU(cpu); 540 541 /* 542 * Place a KSE on another cpu's queue and force a resched. 543 */ 544 do { 545 ke->ke_assign = kseq->ksq_assigned; 546 } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke->ke_assign, ke)); 547 pcpu = pcpu_find(cpu); 548 td = pcpu->pc_curthread; 549 if (ke->ke_thread->td_priority < td->td_priority || 550 td == pcpu->pc_idlethread) { 551 td->td_flags |= TDF_NEEDRESCHED; 552 ipi_selected(1 << cpu, IPI_AST); 553 } 554} 555 556static struct kse * 557runq_steal(struct runq *rq) 558{ 559 struct rqhead *rqh; 560 struct rqbits *rqb; 561 struct kse *ke; 562 int word; 563 int bit; 564 565 mtx_assert(&sched_lock, MA_OWNED); 566 rqb = &rq->rq_status; 567 for (word = 0; word < RQB_LEN; word++) { 568 if (rqb->rqb_bits[word] == 0) 569 continue; 570 for (bit = 0; bit < RQB_BPW; bit++) { 571 if ((rqb->rqb_bits[word] & (1 << bit)) == 0) 572 continue; 573 rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)]; 574 TAILQ_FOREACH(ke, rqh, ke_procq) { 575 if (PRI_BASE(ke->ke_ksegrp->kg_pri_class) != 576 PRI_ITHD) 577 return (ke); 578 } 579 } 580 } 581 return (NULL); 582} 583 584static struct kse * 585kseq_steal(struct kseq *kseq) 586{ 587 struct kse *ke; 588 589 if ((ke = runq_steal(kseq->ksq_curr)) != NULL) 590 return (ke); 591 if ((ke = runq_steal(kseq->ksq_next)) != NULL) 592 return (ke); 593 return (runq_steal(&kseq->ksq_idle)); 594} 595#endif /* SMP */ 596 597/* 598 * Pick the highest priority task we have and return it. 599 */ 600 601static struct kse * 602kseq_choose(struct kseq *kseq) 603{ 604 struct kse *ke; 605 struct runq *swap; 606 607 mtx_assert(&sched_lock, MA_OWNED); 608 swap = NULL; 609 610 for (;;) { 611 ke = runq_choose(kseq->ksq_curr); 612 if (ke == NULL) { 613 /* 614 * We already swaped once and didn't get anywhere. 615 */ 616 if (swap) 617 break; 618 swap = kseq->ksq_curr; 619 kseq->ksq_curr = kseq->ksq_next; 620 kseq->ksq_next = swap; 621 continue; 622 } 623 /* 624 * If we encounter a slice of 0 the kse is in a 625 * TIMESHARE kse group and its nice was too far out 626 * of the range that receives slices. 627 */ 628 if (ke->ke_slice == 0) { 629 runq_remove(ke->ke_runq, ke); 630 sched_slice(ke); 631 ke->ke_runq = kseq->ksq_next; 632 runq_add(ke->ke_runq, ke); 633 continue; 634 } 635 return (ke); 636 } 637 638 return (runq_choose(&kseq->ksq_idle)); 639} 640 641static void 642kseq_setup(struct kseq *kseq) 643{ 644 runq_init(&kseq->ksq_timeshare[0]); 645 runq_init(&kseq->ksq_timeshare[1]); 646 runq_init(&kseq->ksq_idle); 647 648 kseq->ksq_curr = &kseq->ksq_timeshare[0]; 649 kseq->ksq_next = &kseq->ksq_timeshare[1]; 650 651 kseq->ksq_loads[PRI_ITHD] = 0; 652 kseq->ksq_loads[PRI_REALTIME] = 0; 653 kseq->ksq_loads[PRI_TIMESHARE] = 0; 654 kseq->ksq_loads[PRI_IDLE] = 0; 655 kseq->ksq_load = 0; 656#ifdef SMP 657 kseq->ksq_rslices = 0; 658 kseq->ksq_assigned = NULL; 659#endif 660} 661 662static void 663sched_setup(void *dummy) 664{ 665#ifdef SMP 666 int i; 667#endif 668 669 slice_min = (hz/100); /* 10ms */ 670 slice_max = (hz/7); /* ~140ms */ 671 672#ifdef SMP 673 /* init kseqs */ 674 /* Create the idmap. */ 675#ifdef ULE_HTT_EXPERIMENTAL 676 if (smp_topology == NULL) { 677#else 678 if (1) { 679#endif 680 for (i = 0; i < MAXCPU; i++) { 681 kseq_setup(&kseq_cpu[i]); 682 kseq_idmap[i] = &kseq_cpu[i]; 683 kseq_cpu[i].ksq_cpus = 1; 684 } 685 } else { 686 int j; 687 688 for (i = 0; i < smp_topology->ct_count; i++) { 689 struct cpu_group *cg; 690 691 cg = &smp_topology->ct_group[i]; 692 kseq_setup(&kseq_cpu[i]); 693 694 for (j = 0; j < MAXCPU; j++) 695 if ((cg->cg_mask & (1 << j)) != 0) 696 kseq_idmap[j] = &kseq_cpu[i]; 697 kseq_cpu[i].ksq_cpus = cg->cg_count; 698 } 699 } 700 callout_init(&kseq_lb_callout, CALLOUT_MPSAFE); 701 kseq_balance(NULL); 702#else 703 kseq_setup(KSEQ_SELF()); 704#endif 705 mtx_lock_spin(&sched_lock); 706 kseq_add(KSEQ_SELF(), &kse0); 707 mtx_unlock_spin(&sched_lock); 708} 709 710/* 711 * Scale the scheduling priority according to the "interactivity" of this 712 * process. 713 */ 714static void 715sched_priority(struct ksegrp *kg) 716{ 717 int pri; 718 719 if (kg->kg_pri_class != PRI_TIMESHARE) 720 return; 721 722 pri = SCHED_PRI_INTERACT(sched_interact_score(kg)); 723 pri += SCHED_PRI_BASE; 724 pri += kg->kg_nice; 725 726 if (pri > PRI_MAX_TIMESHARE) 727 pri = PRI_MAX_TIMESHARE; 728 else if (pri < PRI_MIN_TIMESHARE) 729 pri = PRI_MIN_TIMESHARE; 730 731 kg->kg_user_pri = pri; 732 733 return; 734} 735 736/* 737 * Calculate a time slice based on the properties of the kseg and the runq 738 * that we're on. This is only for PRI_TIMESHARE ksegrps. 739 */ 740static void 741sched_slice(struct kse *ke) 742{ 743 struct kseq *kseq; 744 struct ksegrp *kg; 745 746 kg = ke->ke_ksegrp; 747 kseq = KSEQ_CPU(ke->ke_cpu); 748 749 /* 750 * Rationale: 751 * KSEs in interactive ksegs get the minimum slice so that we 752 * quickly notice if it abuses its advantage. 753 * 754 * KSEs in non-interactive ksegs are assigned a slice that is 755 * based on the ksegs nice value relative to the least nice kseg 756 * on the run queue for this cpu. 757 * 758 * If the KSE is less nice than all others it gets the maximum 759 * slice and other KSEs will adjust their slice relative to 760 * this when they first expire. 761 * 762 * There is 20 point window that starts relative to the least 763 * nice kse on the run queue. Slice size is determined by 764 * the kse distance from the last nice ksegrp. 765 * 766 * If you are outside of the window you will get no slice and 767 * you will be reevaluated each time you are selected on the 768 * run queue. 769 * 770 */ 771 772 if (!SCHED_INTERACTIVE(kg)) { 773 int nice; 774 775 nice = kg->kg_nice + (0 - kseq->ksq_nicemin); 776 if (kseq->ksq_loads[PRI_TIMESHARE] == 0 || 777 kg->kg_nice < kseq->ksq_nicemin) 778 ke->ke_slice = SCHED_SLICE_MAX; 779 else if (nice <= SCHED_PRI_NTHRESH) 780 ke->ke_slice = SCHED_SLICE_NICE(nice); 781 else 782 ke->ke_slice = 0; 783 } else 784 ke->ke_slice = SCHED_SLICE_MIN; 785 786 CTR6(KTR_ULE, 787 "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)", 788 ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin, 789 kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg)); 790 791 /* 792 * Check to see if we need to scale back the slp and run time 793 * in the kg. This will cause us to forget old interactivity 794 * while maintaining the current ratio. 795 */ 796 sched_interact_update(kg); 797 798 return; 799} 800 801static void 802sched_interact_update(struct ksegrp *kg) 803{ 804 int ratio; 805 806 if ((kg->kg_runtime + kg->kg_slptime) > SCHED_SLP_RUN_MAX) { 807 ratio = ((SCHED_SLP_RUN_MAX * 15) / (kg->kg_runtime + 808 kg->kg_slptime )); 809 kg->kg_runtime = (kg->kg_runtime * ratio) / 16; 810 kg->kg_slptime = (kg->kg_slptime * ratio) / 16; 811 } 812} 813 814static int 815sched_interact_score(struct ksegrp *kg) 816{ 817 int div; 818 819 if (kg->kg_runtime > kg->kg_slptime) { 820 div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF); 821 return (SCHED_INTERACT_HALF + 822 (SCHED_INTERACT_HALF - (kg->kg_slptime / div))); 823 } if (kg->kg_slptime > kg->kg_runtime) { 824 div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF); 825 return (kg->kg_runtime / div); 826 } 827 828 /* 829 * This can happen if slptime and runtime are 0. 830 */ 831 return (0); 832 833} 834 835/* 836 * This is only somewhat accurate since given many processes of the same 837 * priority they will switch when their slices run out, which will be 838 * at most SCHED_SLICE_MAX. 839 */ 840int 841sched_rr_interval(void) 842{ 843 return (SCHED_SLICE_MAX); 844} 845 846static void 847sched_pctcpu_update(struct kse *ke) 848{ 849 /* 850 * Adjust counters and watermark for pctcpu calc. 851 */ 852 if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) { 853 /* 854 * Shift the tick count out so that the divide doesn't 855 * round away our results. 856 */ 857 ke->ke_ticks <<= 10; 858 ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) * 859 SCHED_CPU_TICKS; 860 ke->ke_ticks >>= 10; 861 } else 862 ke->ke_ticks = 0; 863 ke->ke_ltick = ticks; 864 ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS; 865} 866 867#if 0 868/* XXX Should be changed to kseq_load_lowest() */ 869int 870sched_pickcpu(void) 871{ 872 struct kseq *kseq; 873 int load; 874 int cpu; 875 int i; 876 877 mtx_assert(&sched_lock, MA_OWNED); 878 if (!smp_started) 879 return (0); 880 881 load = 0; 882 cpu = 0; 883 884 for (i = 0; i < mp_maxid; i++) { 885 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0) 886 continue; 887 kseq = KSEQ_CPU(i); 888 if (kseq->ksq_load < load) { 889 cpu = i; 890 load = kseq->ksq_load; 891 } 892 } 893 894 CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu); 895 return (cpu); 896} 897#endif 898 899void 900sched_prio(struct thread *td, u_char prio) 901{ 902 struct kse *ke; 903 904 ke = td->td_kse; 905 mtx_assert(&sched_lock, MA_OWNED); 906 if (TD_ON_RUNQ(td)) { 907 /* 908 * If the priority has been elevated due to priority 909 * propagation, we may have to move ourselves to a new 910 * queue. We still call adjustrunqueue below in case kse 911 * needs to fix things up. 912 */ 913 if (ke && (ke->ke_flags & KEF_ASSIGNED) == 0 && 914 ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) { 915 runq_remove(ke->ke_runq, ke); 916 ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr; 917 runq_add(ke->ke_runq, ke); 918 } 919 adjustrunqueue(td, prio); 920 } else 921 td->td_priority = prio; 922} 923 924void 925sched_switch(struct thread *td) 926{ 927 struct thread *newtd; 928 struct kse *ke; 929 930 mtx_assert(&sched_lock, MA_OWNED); 931 932 ke = td->td_kse; 933 934 td->td_last_kse = ke; 935 td->td_lastcpu = td->td_oncpu; 936 td->td_oncpu = NOCPU; 937 td->td_flags &= ~TDF_NEEDRESCHED; 938 939 if (TD_IS_RUNNING(td)) { 940 if (td->td_proc->p_flag & P_SA) { 941 kseq_rem(KSEQ_CPU(ke->ke_cpu), ke); 942 setrunqueue(td); 943 } else { 944 /* 945 * This queue is always correct except for idle threads 946 * which have a higher priority due to priority 947 * propagation. 948 */ 949 if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE) { 950 if (td->td_priority < PRI_MIN_IDLE) 951 ke->ke_runq = KSEQ_SELF()->ksq_curr; 952 else 953 ke->ke_runq = &KSEQ_SELF()->ksq_idle; 954 } 955 runq_add(ke->ke_runq, ke); 956 /* setrunqueue(td); */ 957 } 958 } else { 959 if (ke->ke_runq) 960 kseq_rem(KSEQ_CPU(ke->ke_cpu), ke); 961 /* 962 * We will not be on the run queue. So we must be 963 * sleeping or similar. 964 */ 965 if (td->td_proc->p_flag & P_SA) 966 kse_reassign(ke); 967 } 968 newtd = choosethread(); 969 if (td != newtd) 970 cpu_switch(td, newtd); 971 sched_lock.mtx_lock = (uintptr_t)td; 972 973 td->td_oncpu = PCPU_GET(cpuid); 974} 975 976void 977sched_nice(struct ksegrp *kg, int nice) 978{ 979 struct kse *ke; 980 struct thread *td; 981 struct kseq *kseq; 982 983 PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED); 984 mtx_assert(&sched_lock, MA_OWNED); 985 /* 986 * We need to adjust the nice counts for running KSEs. 987 */ 988 if (kg->kg_pri_class == PRI_TIMESHARE) 989 FOREACH_KSE_IN_GROUP(kg, ke) { 990 if (ke->ke_runq == NULL) 991 continue; 992 kseq = KSEQ_CPU(ke->ke_cpu); 993 kseq_nice_rem(kseq, kg->kg_nice); 994 kseq_nice_add(kseq, nice); 995 } 996 kg->kg_nice = nice; 997 sched_priority(kg); 998 FOREACH_THREAD_IN_GROUP(kg, td) 999 td->td_flags |= TDF_NEEDRESCHED; 1000} 1001 1002void 1003sched_sleep(struct thread *td, u_char prio) 1004{ 1005 mtx_assert(&sched_lock, MA_OWNED); 1006 1007 td->td_slptime = ticks; 1008 td->td_priority = prio; 1009 1010 CTR2(KTR_ULE, "sleep kse %p (tick: %d)", 1011 td->td_kse, td->td_slptime); 1012} 1013 1014void 1015sched_wakeup(struct thread *td) 1016{ 1017 mtx_assert(&sched_lock, MA_OWNED); 1018 1019 /* 1020 * Let the kseg know how long we slept for. This is because process 1021 * interactivity behavior is modeled in the kseg. 1022 */ 1023 if (td->td_slptime) { 1024 struct ksegrp *kg; 1025 int hzticks; 1026 1027 kg = td->td_ksegrp; 1028 hzticks = ticks - td->td_slptime; 1029 kg->kg_slptime += hzticks << 10; 1030 sched_interact_update(kg); 1031 sched_priority(kg); 1032 if (td->td_kse) 1033 sched_slice(td->td_kse); 1034 CTR2(KTR_ULE, "wakeup kse %p (%d ticks)", 1035 td->td_kse, hzticks); 1036 td->td_slptime = 0; 1037 } 1038 setrunqueue(td); 1039} 1040 1041/* 1042 * Penalize the parent for creating a new child and initialize the child's 1043 * priority. 1044 */ 1045void 1046sched_fork(struct proc *p, struct proc *p1) 1047{ 1048 1049 mtx_assert(&sched_lock, MA_OWNED); 1050 1051 sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1)); 1052 sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1)); 1053 sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1)); 1054} 1055 1056void 1057sched_fork_kse(struct kse *ke, struct kse *child) 1058{ 1059 1060 child->ke_slice = 1; /* Attempt to quickly learn interactivity. */ 1061 child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */ 1062 child->ke_runq = NULL; 1063 1064 /* Grab our parents cpu estimation information. */ 1065 child->ke_ticks = ke->ke_ticks; 1066 child->ke_ltick = ke->ke_ltick; 1067 child->ke_ftick = ke->ke_ftick; 1068} 1069 1070void 1071sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child) 1072{ 1073 1074 PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED); 1075 /* XXX Need something better here */ 1076 1077 child->kg_slptime = kg->kg_slptime / SCHED_SLP_RUN_THROTTLE; 1078 child->kg_runtime = kg->kg_runtime / SCHED_SLP_RUN_THROTTLE; 1079 kg->kg_runtime += tickincr << 10; 1080 sched_interact_update(kg); 1081 1082 child->kg_user_pri = kg->kg_user_pri; 1083 child->kg_nice = kg->kg_nice; 1084} 1085 1086void 1087sched_fork_thread(struct thread *td, struct thread *child) 1088{ 1089} 1090 1091void 1092sched_class(struct ksegrp *kg, int class) 1093{ 1094 struct kseq *kseq; 1095 struct kse *ke; 1096 1097 mtx_assert(&sched_lock, MA_OWNED); 1098 if (kg->kg_pri_class == class) 1099 return; 1100 1101 FOREACH_KSE_IN_GROUP(kg, ke) { 1102 if (ke->ke_state != KES_ONRUNQ && 1103 ke->ke_state != KES_THREAD) 1104 continue; 1105 kseq = KSEQ_CPU(ke->ke_cpu); 1106 1107 kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--; 1108 kseq->ksq_loads[PRI_BASE(class)]++; 1109 1110 if (kg->kg_pri_class == PRI_TIMESHARE) 1111 kseq_nice_rem(kseq, kg->kg_nice); 1112 else if (class == PRI_TIMESHARE) 1113 kseq_nice_add(kseq, kg->kg_nice); 1114 } 1115 1116 kg->kg_pri_class = class; 1117} 1118 1119/* 1120 * Return some of the child's priority and interactivity to the parent. 1121 */ 1122void 1123sched_exit(struct proc *p, struct proc *child) 1124{ 1125 /* XXX Need something better here */ 1126 mtx_assert(&sched_lock, MA_OWNED); 1127 sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child)); 1128 sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child)); 1129} 1130 1131void 1132sched_exit_kse(struct kse *ke, struct kse *child) 1133{ 1134 kseq_rem(KSEQ_CPU(child->ke_cpu), child); 1135} 1136 1137void 1138sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child) 1139{ 1140 /* kg->kg_slptime += child->kg_slptime; */ 1141 kg->kg_runtime += child->kg_runtime; 1142 sched_interact_update(kg); 1143} 1144 1145void 1146sched_exit_thread(struct thread *td, struct thread *child) 1147{ 1148} 1149 1150void 1151sched_clock(struct thread *td) 1152{ 1153 struct kseq *kseq; 1154 struct ksegrp *kg; 1155 struct kse *ke; 1156 1157 /* 1158 * sched_setup() apparently happens prior to stathz being set. We 1159 * need to resolve the timers earlier in the boot so we can avoid 1160 * calculating this here. 1161 */ 1162 if (realstathz == 0) { 1163 realstathz = stathz ? stathz : hz; 1164 tickincr = hz / realstathz; 1165 /* 1166 * XXX This does not work for values of stathz that are much 1167 * larger than hz. 1168 */ 1169 if (tickincr == 0) 1170 tickincr = 1; 1171 } 1172 1173 ke = td->td_kse; 1174 kg = ke->ke_ksegrp; 1175 1176 mtx_assert(&sched_lock, MA_OWNED); 1177 KASSERT((td != NULL), ("schedclock: null thread pointer")); 1178 1179 /* Adjust ticks for pctcpu */ 1180 ke->ke_ticks++; 1181 ke->ke_ltick = ticks; 1182 1183 /* Go up to one second beyond our max and then trim back down */ 1184 if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick) 1185 sched_pctcpu_update(ke); 1186 1187 if (td->td_flags & TDF_IDLETD) 1188 return; 1189 1190 CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)", 1191 ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10); 1192 /* 1193 * We only do slicing code for TIMESHARE ksegrps. 1194 */ 1195 if (kg->kg_pri_class != PRI_TIMESHARE) 1196 return; 1197 /* 1198 * We used a tick charge it to the ksegrp so that we can compute our 1199 * interactivity. 1200 */ 1201 kg->kg_runtime += tickincr << 10; 1202 sched_interact_update(kg); 1203 1204 /* 1205 * We used up one time slice. 1206 */ 1207 ke->ke_slice--; 1208 kseq = KSEQ_SELF(); 1209#ifdef SMP 1210 kseq->ksq_rslices--; 1211#endif 1212 1213 if (ke->ke_slice > 0) 1214 return; 1215 /* 1216 * We're out of time, recompute priorities and requeue. 1217 */ 1218 kseq_rem(kseq, ke); 1219 sched_priority(kg); 1220 sched_slice(ke); 1221 if (SCHED_CURR(kg, ke)) 1222 ke->ke_runq = kseq->ksq_curr; 1223 else 1224 ke->ke_runq = kseq->ksq_next; 1225 kseq_add(kseq, ke); 1226 td->td_flags |= TDF_NEEDRESCHED; 1227} 1228 1229int 1230sched_runnable(void) 1231{ 1232 struct kseq *kseq; 1233 int load; 1234 1235 load = 1; 1236 1237 mtx_lock_spin(&sched_lock); 1238 kseq = KSEQ_SELF(); 1239#ifdef SMP 1240 if (kseq->ksq_assigned) 1241 kseq_assign(kseq); 1242#endif 1243 if ((curthread->td_flags & TDF_IDLETD) != 0) { 1244 if (kseq->ksq_load > 0) 1245 goto out; 1246 } else 1247 if (kseq->ksq_load - 1 > 0) 1248 goto out; 1249 load = 0; 1250out: 1251 mtx_unlock_spin(&sched_lock); 1252 return (load); 1253} 1254 1255void 1256sched_userret(struct thread *td) 1257{ 1258 struct ksegrp *kg; 1259 1260 kg = td->td_ksegrp; 1261 1262 if (td->td_priority != kg->kg_user_pri) { 1263 mtx_lock_spin(&sched_lock); 1264 td->td_priority = kg->kg_user_pri; 1265 mtx_unlock_spin(&sched_lock); 1266 } 1267} 1268 1269struct kse * 1270sched_choose(void) 1271{ 1272 struct kseq *kseq; 1273 struct kse *ke; 1274 1275 mtx_assert(&sched_lock, MA_OWNED); 1276 kseq = KSEQ_SELF(); 1277#ifdef SMP 1278retry: 1279 if (kseq->ksq_assigned) 1280 kseq_assign(kseq); 1281#endif 1282 ke = kseq_choose(kseq); 1283 if (ke) { 1284#ifdef SMP 1285 if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE) 1286 if (kseq_find()) 1287 goto retry; 1288#endif 1289 runq_remove(ke->ke_runq, ke); 1290 ke->ke_state = KES_THREAD; 1291 1292 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) { 1293 CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)", 1294 ke, ke->ke_runq, ke->ke_slice, 1295 ke->ke_thread->td_priority); 1296 } 1297 return (ke); 1298 } 1299#ifdef SMP 1300 if (kseq_find()) 1301 goto retry; 1302#endif 1303 1304 return (NULL); 1305} 1306 1307void 1308sched_add(struct thread *td) 1309{ 1310 struct kseq *kseq; 1311 struct ksegrp *kg; 1312 struct kse *ke; 1313 int class; 1314 1315 mtx_assert(&sched_lock, MA_OWNED); 1316 ke = td->td_kse; 1317 kg = td->td_ksegrp; 1318 if (ke->ke_flags & KEF_ASSIGNED) 1319 return; 1320 kseq = KSEQ_SELF(); 1321 KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE")); 1322 KASSERT((ke->ke_thread->td_kse != NULL), 1323 ("sched_add: No KSE on thread")); 1324 KASSERT(ke->ke_state != KES_ONRUNQ, 1325 ("sched_add: kse %p (%s) already in run queue", ke, 1326 ke->ke_proc->p_comm)); 1327 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1328 ("sched_add: process swapped out")); 1329 KASSERT(ke->ke_runq == NULL, 1330 ("sched_add: KSE %p is still assigned to a run queue", ke)); 1331 1332 class = PRI_BASE(kg->kg_pri_class); 1333 switch (class) { 1334 case PRI_ITHD: 1335 case PRI_REALTIME: 1336 ke->ke_runq = kseq->ksq_curr; 1337 ke->ke_slice = SCHED_SLICE_MAX; 1338 ke->ke_cpu = PCPU_GET(cpuid); 1339 break; 1340 case PRI_TIMESHARE: 1341#ifdef SMP 1342 if (ke->ke_cpu != PCPU_GET(cpuid)) { 1343 kseq_notify(ke, ke->ke_cpu); 1344 return; 1345 } 1346#endif 1347 if (SCHED_CURR(kg, ke)) 1348 ke->ke_runq = kseq->ksq_curr; 1349 else 1350 ke->ke_runq = kseq->ksq_next; 1351 break; 1352 case PRI_IDLE: 1353#ifdef SMP 1354 if (ke->ke_cpu != PCPU_GET(cpuid)) { 1355 kseq_notify(ke, ke->ke_cpu); 1356 return; 1357 } 1358#endif 1359 /* 1360 * This is for priority prop. 1361 */ 1362 if (ke->ke_thread->td_priority < PRI_MIN_IDLE) 1363 ke->ke_runq = kseq->ksq_curr; 1364 else 1365 ke->ke_runq = &kseq->ksq_idle; 1366 ke->ke_slice = SCHED_SLICE_MIN; 1367 break; 1368 default: 1369 panic("Unknown pri class.\n"); 1370 break; 1371 } 1372#ifdef SMP 1373 /* 1374 * If there are any idle processors, give them our extra load. 1375 */ 1376 if (kseq_idle && class != PRI_ITHD && 1377 (kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] + 1378 kseq->ksq_loads[PRI_REALTIME]) >= kseq->ksq_cpus) { 1379 int cpu; 1380 1381 /* 1382 * Multiple cpus could find this bit simultaneously but the 1383 * race shouldn't be terrible. 1384 */ 1385 cpu = ffs(kseq_idle); 1386 if (cpu) { 1387 cpu--; 1388 atomic_clear_int(&kseq_idle, 1 << cpu); 1389 ke->ke_cpu = cpu; 1390 ke->ke_runq = NULL; 1391 kseq_notify(ke, cpu); 1392 return; 1393 } 1394 } 1395 if (class == PRI_TIMESHARE || class == PRI_REALTIME) 1396 atomic_clear_int(&kseq_idle, PCPU_GET(cpumask)); 1397#endif 1398 if (td->td_priority < curthread->td_priority) 1399 curthread->td_flags |= TDF_NEEDRESCHED; 1400 1401 ke->ke_ksegrp->kg_runq_kses++; 1402 ke->ke_state = KES_ONRUNQ; 1403 1404 runq_add(ke->ke_runq, ke); 1405 kseq_add(kseq, ke); 1406} 1407 1408void 1409sched_rem(struct thread *td) 1410{ 1411 struct kseq *kseq; 1412 struct kse *ke; 1413 1414 ke = td->td_kse; 1415 /* 1416 * It is safe to just return here because sched_rem() is only ever 1417 * used in places where we're immediately going to add the 1418 * kse back on again. In that case it'll be added with the correct 1419 * thread and priority when the caller drops the sched_lock. 1420 */ 1421 if (ke->ke_flags & KEF_ASSIGNED) 1422 return; 1423 mtx_assert(&sched_lock, MA_OWNED); 1424 KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 1425 1426 ke->ke_state = KES_THREAD; 1427 ke->ke_ksegrp->kg_runq_kses--; 1428 kseq = KSEQ_CPU(ke->ke_cpu); 1429 runq_remove(ke->ke_runq, ke); 1430 kseq_rem(kseq, ke); 1431} 1432 1433fixpt_t 1434sched_pctcpu(struct thread *td) 1435{ 1436 fixpt_t pctcpu; 1437 struct kse *ke; 1438 1439 pctcpu = 0; 1440 ke = td->td_kse; 1441 if (ke == NULL) 1442 return (0); 1443 1444 mtx_lock_spin(&sched_lock); 1445 if (ke->ke_ticks) { 1446 int rtick; 1447 1448 /* 1449 * Don't update more frequently than twice a second. Allowing 1450 * this causes the cpu usage to decay away too quickly due to 1451 * rounding errors. 1452 */ 1453 if (ke->ke_ltick < (ticks - (hz / 2))) 1454 sched_pctcpu_update(ke); 1455 /* How many rtick per second ? */ 1456 rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS); 1457 pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT; 1458 } 1459 1460 ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick; 1461 mtx_unlock_spin(&sched_lock); 1462 1463 return (pctcpu); 1464} 1465 1466int 1467sched_sizeof_kse(void) 1468{ 1469 return (sizeof(struct kse) + sizeof(struct ke_sched)); 1470} 1471 1472int 1473sched_sizeof_ksegrp(void) 1474{ 1475 return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 1476} 1477 1478int 1479sched_sizeof_proc(void) 1480{ 1481 return (sizeof(struct proc)); 1482} 1483 1484int 1485sched_sizeof_thread(void) 1486{ 1487 return (sizeof(struct thread) + sizeof(struct td_sched)); 1488} 1489