Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/kern/sched_4bsd.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /*- 2 * Copyright (c) 1982, 1986, 1990, 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * (c) UNIX System Laboratories, Inc. 5 * All or some portions of this file are derived from material licensed 6 * to the University of California by American Telephone and Telegraph 7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8 * the permission of UNIX System Laboratories, Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 4. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include <sys/cdefs.h> 36 __FBSDID("$FreeBSD: releng/5.4/sys/kern/sched_4bsd.c 145335 2005-04-20 19:11:07Z cvs2svn $"); 37 38 #define kse td_sched 39 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/kernel.h> 43 #include <sys/ktr.h> 44 #include <sys/lock.h> 45 #include <sys/kthread.h> 46 #include <sys/mutex.h> 47 #include <sys/proc.h> 48 #include <sys/resourcevar.h> 49 #include <sys/sched.h> 50 #include <sys/smp.h> 51 #include <sys/sysctl.h> 52 #include <sys/sx.h> 53 #include <machine/smp.h> 54 55 /* 56 * INVERSE_ESTCPU_WEIGHT is only suitable for statclock() frequencies in 57 * the range 100-256 Hz (approximately). 58 */ 59 #define ESTCPULIM(e) \ 60 min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * (PRIO_MAX - PRIO_MIN) - \ 61 RQ_PPQ) + INVERSE_ESTCPU_WEIGHT - 1) 62 #ifdef SMP 63 #define INVERSE_ESTCPU_WEIGHT (8 * smp_cpus) 64 #else 65 #define INVERSE_ESTCPU_WEIGHT 8 /* 1 / (priorities per estcpu level). */ 66 #endif 67 #define NICE_WEIGHT 1 /* Priorities per nice level. */ 68 69 /* 70 * The schedulable entity that can be given a context to run. 71 * A process may have several of these. Probably one per processor 72 * but posibly a few more. In this universe they are grouped 73 * with a KSEG that contains the priority and niceness 74 * for the group. 75 */ 76 struct kse { 77 TAILQ_ENTRY(kse) ke_kglist; /* (*) Queue of KSEs in ke_ksegrp. */ 78 TAILQ_ENTRY(kse) ke_kgrlist; /* (*) Queue of KSEs in this state. */ 79 TAILQ_ENTRY(kse) ke_procq; /* (j/z) Run queue. */ 80 struct thread *ke_thread; /* (*) Active associated thread. */ 81 fixpt_t ke_pctcpu; /* (j) %cpu during p_swtime. */ 82 char ke_rqindex; /* (j) Run queue index. */ 83 enum { 84 KES_THREAD = 0x0, /* slaved to thread state */ 85 KES_ONRUNQ 86 } ke_state; /* (j) KSE status. */ 87 int ke_cpticks; /* (j) Ticks of cpu time. */ 88 struct runq *ke_runq; /* runq the kse is currently on */ 89 }; 90 91 #define ke_proc ke_thread->td_proc 92 #define ke_ksegrp ke_thread->td_ksegrp 93 94 #define td_kse td_sched 95 96 /* flags kept in td_flags */ 97 #define TDF_DIDRUN TDF_SCHED0 /* KSE actually ran. */ 98 #define TDF_EXIT TDF_SCHED1 /* KSE is being killed. */ 99 #define TDF_BOUND TDF_SCHED2 100 101 #define ke_flags ke_thread->td_flags 102 #define KEF_DIDRUN TDF_DIDRUN /* KSE actually ran. */ 103 #define KEF_EXIT TDF_EXIT /* KSE is being killed. */ 104 #define KEF_BOUND TDF_BOUND /* stuck to one CPU */ 105 106 #define SKE_RUNQ_PCPU(ke) \ 107 ((ke)->ke_runq != 0 && (ke)->ke_runq != &runq) 108 109 struct kg_sched { 110 struct thread *skg_last_assigned; /* (j) Last thread assigned to */ 111 /* the system scheduler. */ 112 int skg_avail_opennings; /* (j) Num KSEs requested in group. */ 113 int skg_concurrency; /* (j) Num KSEs requested in group. */ 114 int skg_runq_kses; /* (j) Num KSEs on runq. */ 115 }; 116 #define kg_last_assigned kg_sched->skg_last_assigned 117 #define kg_avail_opennings kg_sched->skg_avail_opennings 118 #define kg_concurrency kg_sched->skg_concurrency 119 #define kg_runq_kses kg_sched->skg_runq_kses 120 121 #define SLOT_RELEASE(kg) \ 122 do { \ 123 kg->kg_avail_opennings++; \ 124 CTR3(KTR_RUNQ, "kg %p(%d) Slot released (->%d)", \ 125 kg, \ 126 kg->kg_concurrency, \ 127 kg->kg_avail_opennings); \ 128 /* KASSERT((kg->kg_avail_opennings <= kg->kg_concurrency), \ 129 ("slots out of whack"));*/ \ 130 } while (0) 131 132 #define SLOT_USE(kg) \ 133 do { \ 134 kg->kg_avail_opennings--; \ 135 CTR3(KTR_RUNQ, "kg %p(%d) Slot used (->%d)", \ 136 kg, \ 137 kg->kg_concurrency, \ 138 kg->kg_avail_opennings); \ 139 /* KASSERT((kg->kg_avail_opennings >= 0), \ 140 ("slots out of whack"));*/ \ 141 } while (0) 142 143 /* 144 * KSE_CAN_MIGRATE macro returns true if the kse can migrate between 145 * cpus. 146 */ 147 #define KSE_CAN_MIGRATE(ke) \ 148 ((ke)->ke_thread->td_pinned == 0 && ((ke)->ke_flags & KEF_BOUND) == 0) 149 150 static struct kse kse0; 151 static struct kg_sched kg_sched0; 152 153 static int sched_tdcnt; /* Total runnable threads in the system. */ 154 static int sched_quantum; /* Roundrobin scheduling quantum in ticks. */ 155 #define SCHED_QUANTUM (hz / 10) /* Default sched quantum */ 156 157 static struct callout roundrobin_callout; 158 159 static void slot_fill(struct ksegrp *kg); 160 static struct kse *sched_choose(void); /* XXX Should be thread * */ 161 162 static void setup_runqs(void); 163 static void roundrobin(void *arg); 164 static void schedcpu(void); 165 static void schedcpu_thread(void); 166 static void sched_setup(void *dummy); 167 static void maybe_resched(struct thread *td); 168 static void updatepri(struct ksegrp *kg); 169 static void resetpriority(struct ksegrp *kg); 170 #ifdef SMP 171 static int forward_wakeup(int cpunum); 172 #endif 173 174 static struct kproc_desc sched_kp = { 175 "schedcpu", 176 schedcpu_thread, 177 NULL 178 }; 179 SYSINIT(schedcpu, SI_SUB_RUN_SCHEDULER, SI_ORDER_FIRST, kproc_start, &sched_kp) 180 SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL) 181 182 /* 183 * Global run queue. 184 */ 185 static struct runq runq; 186 187 #ifdef SMP 188 /* 189 * Per-CPU run queues 190 */ 191 static struct runq runq_pcpu[MAXCPU]; 192 #endif 193 194 static void 195 setup_runqs(void) 196 { 197 #ifdef SMP 198 int i; 199 200 for (i = 0; i < MAXCPU; ++i) 201 runq_init(&runq_pcpu[i]); 202 #endif 203 204 runq_init(&runq); 205 } 206 207 static int 208 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS) 209 { 210 int error, new_val; 211 212 new_val = sched_quantum * tick; 213 error = sysctl_handle_int(oidp, &new_val, 0, req); 214 if (error != 0 || req->newptr == NULL) 215 return (error); 216 if (new_val < tick) 217 return (EINVAL); 218 sched_quantum = new_val / tick; 219 hogticks = 2 * sched_quantum; 220 return (0); 221 } 222 223 SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RD, 0, "Scheduler"); 224 225 SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "4BSD", 0, 226 "Scheduler name"); 227 228 SYSCTL_PROC(_kern_sched, OID_AUTO, quantum, CTLTYPE_INT | CTLFLAG_RW, 229 0, sizeof sched_quantum, sysctl_kern_quantum, "I", 230 "Roundrobin scheduling quantum in microseconds"); 231 232 #ifdef SMP 233 /* Enable forwarding of wakeups to all other cpus */ 234 SYSCTL_NODE(_kern_sched, OID_AUTO, ipiwakeup, CTLFLAG_RD, NULL, "Kernel SMP"); 235 236 static int forward_wakeup_enabled = 1; 237 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, enabled, CTLFLAG_RW, 238 &forward_wakeup_enabled, 0, 239 "Forwarding of wakeup to idle CPUs"); 240 241 static int forward_wakeups_requested = 0; 242 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, requested, CTLFLAG_RD, 243 &forward_wakeups_requested, 0, 244 "Requests for Forwarding of wakeup to idle CPUs"); 245 246 static int forward_wakeups_delivered = 0; 247 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, delivered, CTLFLAG_RD, 248 &forward_wakeups_delivered, 0, 249 "Completed Forwarding of wakeup to idle CPUs"); 250 251 static int forward_wakeup_use_mask = 1; 252 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, usemask, CTLFLAG_RW, 253 &forward_wakeup_use_mask, 0, 254 "Use the mask of idle cpus"); 255 256 static int forward_wakeup_use_loop = 0; 257 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, useloop, CTLFLAG_RW, 258 &forward_wakeup_use_loop, 0, 259 "Use a loop to find idle cpus"); 260 261 static int forward_wakeup_use_single = 0; 262 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, onecpu, CTLFLAG_RW, 263 &forward_wakeup_use_single, 0, 264 "Only signal one idle cpu"); 265 266 static int forward_wakeup_use_htt = 0; 267 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, htt2, CTLFLAG_RW, 268 &forward_wakeup_use_htt, 0, 269 "account for htt"); 270 271 #endif 272 static int sched_followon = 0; 273 SYSCTL_INT(_kern_sched, OID_AUTO, followon, CTLFLAG_RW, 274 &sched_followon, 0, 275 "allow threads to share a quantum"); 276 277 static int sched_pfollowons = 0; 278 SYSCTL_INT(_kern_sched, OID_AUTO, pfollowons, CTLFLAG_RD, 279 &sched_pfollowons, 0, 280 "number of followons done to a different ksegrp"); 281 282 static int sched_kgfollowons = 0; 283 static __inline void 284 sched_load_add(void) 285 { 286 sched_tdcnt++; 287 CTR1(KTR_SCHED, "global load: %d", sched_tdcnt); 288 } 289 290 static __inline void 291 sched_load_rem(void) 292 { 293 sched_tdcnt--; 294 CTR1(KTR_SCHED, "global load: %d", sched_tdcnt); 295 } 296 SYSCTL_INT(_kern_sched, OID_AUTO, kgfollowons, CTLFLAG_RD, 297 &sched_kgfollowons, 0, 298 "number of followons done in a ksegrp"); 299 300 /* 301 * Arrange to reschedule if necessary, taking the priorities and 302 * schedulers into account. 303 */ 304 static void 305 maybe_resched(struct thread *td) 306 { 307 308 mtx_assert(&sched_lock, MA_OWNED); 309 if (td->td_priority < curthread->td_priority) 310 curthread->td_flags |= TDF_NEEDRESCHED; 311 } 312 313 /* 314 * Force switch among equal priority processes every 100ms. 315 * We don't actually need to force a context switch of the current process. 316 * The act of firing the event triggers a context switch to softclock() and 317 * then switching back out again which is equivalent to a preemption, thus 318 * no further work is needed on the local CPU. 319 */ 320 /* ARGSUSED */ 321 static void 322 roundrobin(void *arg) 323 { 324 325 #ifdef SMP 326 mtx_lock_spin(&sched_lock); 327 forward_roundrobin(); 328 mtx_unlock_spin(&sched_lock); 329 #endif 330 331 callout_reset(&roundrobin_callout, sched_quantum, roundrobin, NULL); 332 } 333 334 /* 335 * Constants for digital decay and forget: 336 * 90% of (kg_estcpu) usage in 5 * loadav time 337 * 95% of (ke_pctcpu) usage in 60 seconds (load insensitive) 338 * Note that, as ps(1) mentions, this can let percentages 339 * total over 100% (I've seen 137.9% for 3 processes). 340 * 341 * Note that schedclock() updates kg_estcpu and p_cpticks asynchronously. 342 * 343 * We wish to decay away 90% of kg_estcpu in (5 * loadavg) seconds. 344 * That is, the system wants to compute a value of decay such 345 * that the following for loop: 346 * for (i = 0; i < (5 * loadavg); i++) 347 * kg_estcpu *= decay; 348 * will compute 349 * kg_estcpu *= 0.1; 350 * for all values of loadavg: 351 * 352 * Mathematically this loop can be expressed by saying: 353 * decay ** (5 * loadavg) ~= .1 354 * 355 * The system computes decay as: 356 * decay = (2 * loadavg) / (2 * loadavg + 1) 357 * 358 * We wish to prove that the system's computation of decay 359 * will always fulfill the equation: 360 * decay ** (5 * loadavg) ~= .1 361 * 362 * If we compute b as: 363 * b = 2 * loadavg 364 * then 365 * decay = b / (b + 1) 366 * 367 * We now need to prove two things: 368 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1) 369 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg) 370 * 371 * Facts: 372 * For x close to zero, exp(x) =~ 1 + x, since 373 * exp(x) = 0! + x**1/1! + x**2/2! + ... . 374 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b. 375 * For x close to zero, ln(1+x) =~ x, since 376 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1 377 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1). 378 * ln(.1) =~ -2.30 379 * 380 * Proof of (1): 381 * Solve (factor)**(power) =~ .1 given power (5*loadav): 382 * solving for factor, 383 * ln(factor) =~ (-2.30/5*loadav), or 384 * factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) = 385 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED 386 * 387 * Proof of (2): 388 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)): 389 * solving for power, 390 * power*ln(b/(b+1)) =~ -2.30, or 391 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED 392 * 393 * Actual power values for the implemented algorithm are as follows: 394 * loadav: 1 2 3 4 395 * power: 5.68 10.32 14.94 19.55 396 */ 397 398 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */ 399 #define loadfactor(loadav) (2 * (loadav)) 400 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE)) 401 402 /* decay 95% of `ke_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 403 static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 404 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, ""); 405 406 /* 407 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the 408 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below 409 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT). 410 * 411 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used: 412 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits). 413 * 414 * If you don't want to bother with the faster/more-accurate formula, you 415 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate 416 * (more general) method of calculating the %age of CPU used by a process. 417 */ 418 #define CCPU_SHIFT 11 419 420 /* 421 * Recompute process priorities, every hz ticks. 422 * MP-safe, called without the Giant mutex. 423 */ 424 /* ARGSUSED */ 425 static void 426 schedcpu(void) 427 { 428 register fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 429 struct thread *td; 430 struct proc *p; 431 struct kse *ke; 432 struct ksegrp *kg; 433 int awake, realstathz; 434 435 realstathz = stathz ? stathz : hz; 436 sx_slock(&allproc_lock); 437 FOREACH_PROC_IN_SYSTEM(p) { 438 /* 439 * Prevent state changes and protect run queue. 440 */ 441 mtx_lock_spin(&sched_lock); 442 /* 443 * Increment time in/out of memory. We ignore overflow; with 444 * 16-bit int's (remember them?) overflow takes 45 days. 445 */ 446 p->p_swtime++; 447 FOREACH_KSEGRP_IN_PROC(p, kg) { 448 awake = 0; 449 FOREACH_THREAD_IN_GROUP(kg, td) { 450 ke = td->td_kse; 451 /* 452 * Increment sleep time (if sleeping). We 453 * ignore overflow, as above. 454 */ 455 /* 456 * The kse slptimes are not touched in wakeup 457 * because the thread may not HAVE a KSE. 458 */ 459 if (ke->ke_state == KES_ONRUNQ) { 460 awake = 1; 461 ke->ke_flags &= ~KEF_DIDRUN; 462 } else if ((ke->ke_state == KES_THREAD) && 463 (TD_IS_RUNNING(td))) { 464 awake = 1; 465 /* Do not clear KEF_DIDRUN */ 466 } else if (ke->ke_flags & KEF_DIDRUN) { 467 awake = 1; 468 ke->ke_flags &= ~KEF_DIDRUN; 469 } 470 471 /* 472 * ke_pctcpu is only for ps and ttyinfo(). 473 * Do it per kse, and add them up at the end? 474 * XXXKSE 475 */ 476 ke->ke_pctcpu = (ke->ke_pctcpu * ccpu) >> 477 FSHIFT; 478 /* 479 * If the kse has been idle the entire second, 480 * stop recalculating its priority until 481 * it wakes up. 482 */ 483 if (ke->ke_cpticks == 0) 484 continue; 485 #if (FSHIFT >= CCPU_SHIFT) 486 ke->ke_pctcpu += (realstathz == 100) 487 ? ((fixpt_t) ke->ke_cpticks) << 488 (FSHIFT - CCPU_SHIFT) : 489 100 * (((fixpt_t) ke->ke_cpticks) 490 << (FSHIFT - CCPU_SHIFT)) / realstathz; 491 #else 492 ke->ke_pctcpu += ((FSCALE - ccpu) * 493 (ke->ke_cpticks * 494 FSCALE / realstathz)) >> FSHIFT; 495 #endif 496 ke->ke_cpticks = 0; 497 } /* end of kse loop */ 498 /* 499 * If there are ANY running threads in this KSEGRP, 500 * then don't count it as sleeping. 501 */ 502 if (awake) { 503 if (kg->kg_slptime > 1) { 504 /* 505 * In an ideal world, this should not 506 * happen, because whoever woke us 507 * up from the long sleep should have 508 * unwound the slptime and reset our 509 * priority before we run at the stale 510 * priority. Should KASSERT at some 511 * point when all the cases are fixed. 512 */ 513 updatepri(kg); 514 } 515 kg->kg_slptime = 0; 516 } else 517 kg->kg_slptime++; 518 if (kg->kg_slptime > 1) 519 continue; 520 kg->kg_estcpu = decay_cpu(loadfac, kg->kg_estcpu); 521 resetpriority(kg); 522 FOREACH_THREAD_IN_GROUP(kg, td) { 523 if (td->td_priority >= PUSER) { 524 sched_prio(td, kg->kg_user_pri); 525 } 526 } 527 } /* end of ksegrp loop */ 528 mtx_unlock_spin(&sched_lock); 529 } /* end of process loop */ 530 sx_sunlock(&allproc_lock); 531 } 532 533 /* 534 * Main loop for a kthread that executes schedcpu once a second. 535 */ 536 static void 537 schedcpu_thread(void) 538 { 539 int nowake; 540 541 for (;;) { 542 schedcpu(); 543 tsleep(&nowake, curthread->td_priority, "-", hz); 544 } 545 } 546 547 /* 548 * Recalculate the priority of a process after it has slept for a while. 549 * For all load averages >= 1 and max kg_estcpu of 255, sleeping for at 550 * least six times the loadfactor will decay kg_estcpu to zero. 551 */ 552 static void 553 updatepri(struct ksegrp *kg) 554 { 555 register fixpt_t loadfac; 556 register unsigned int newcpu; 557 558 loadfac = loadfactor(averunnable.ldavg[0]); 559 if (kg->kg_slptime > 5 * loadfac) 560 kg->kg_estcpu = 0; 561 else { 562 newcpu = kg->kg_estcpu; 563 kg->kg_slptime--; /* was incremented in schedcpu() */ 564 while (newcpu && --kg->kg_slptime) 565 newcpu = decay_cpu(loadfac, newcpu); 566 kg->kg_estcpu = newcpu; 567 } 568 resetpriority(kg); 569 } 570 571 /* 572 * Compute the priority of a process when running in user mode. 573 * Arrange to reschedule if the resulting priority is better 574 * than that of the current process. 575 */ 576 static void 577 resetpriority(struct ksegrp *kg) 578 { 579 register unsigned int newpriority; 580 struct thread *td; 581 582 if (kg->kg_pri_class == PRI_TIMESHARE) { 583 newpriority = PUSER + kg->kg_estcpu / INVERSE_ESTCPU_WEIGHT + 584 NICE_WEIGHT * (kg->kg_proc->p_nice - PRIO_MIN); 585 newpriority = min(max(newpriority, PRI_MIN_TIMESHARE), 586 PRI_MAX_TIMESHARE); 587 kg->kg_user_pri = newpriority; 588 } 589 FOREACH_THREAD_IN_GROUP(kg, td) { 590 maybe_resched(td); /* XXXKSE silly */ 591 } 592 } 593 594 /* ARGSUSED */ 595 static void 596 sched_setup(void *dummy) 597 { 598 setup_runqs(); 599 600 if (sched_quantum == 0) 601 sched_quantum = SCHED_QUANTUM; 602 hogticks = 2 * sched_quantum; 603 604 callout_init(&roundrobin_callout, CALLOUT_MPSAFE); 605 606 /* Kick off timeout driven events by calling first time. */ 607 roundrobin(NULL); 608 609 /* Account for thread0. */ 610 sched_load_add(); 611 } 612 613 /* External interfaces start here */ 614 /* 615 * Very early in the boot some setup of scheduler-specific 616 * parts of proc0 and of soem scheduler resources needs to be done. 617 * Called from: 618 * proc0_init() 619 */ 620 void 621 schedinit(void) 622 { 623 /* 624 * Set up the scheduler specific parts of proc0. 625 */ 626 proc0.p_sched = NULL; /* XXX */ 627 ksegrp0.kg_sched = &kg_sched0; 628 thread0.td_sched = &kse0; 629 kse0.ke_thread = &thread0; 630 kse0.ke_state = KES_THREAD; 631 kg_sched0.skg_concurrency = 1; 632 kg_sched0.skg_avail_opennings = 0; /* we are already running */ 633 } 634 635 int 636 sched_runnable(void) 637 { 638 #ifdef SMP 639 return runq_check(&runq) + runq_check(&runq_pcpu[PCPU_GET(cpuid)]); 640 #else 641 return runq_check(&runq); 642 #endif 643 } 644 645 int 646 sched_rr_interval(void) 647 { 648 if (sched_quantum == 0) 649 sched_quantum = SCHED_QUANTUM; 650 return (sched_quantum); 651 } 652 653 /* 654 * We adjust the priority of the current process. The priority of 655 * a process gets worse as it accumulates CPU time. The cpu usage 656 * estimator (kg_estcpu) is increased here. resetpriority() will 657 * compute a different priority each time kg_estcpu increases by 658 * INVERSE_ESTCPU_WEIGHT 659 * (until MAXPRI is reached). The cpu usage estimator ramps up 660 * quite quickly when the process is running (linearly), and decays 661 * away exponentially, at a rate which is proportionally slower when 662 * the system is busy. The basic principle is that the system will 663 * 90% forget that the process used a lot of CPU time in 5 * loadav 664 * seconds. This causes the system to favor processes which haven't 665 * run much recently, and to round-robin among other processes. 666 */ 667 void 668 sched_clock(struct thread *td) 669 { 670 struct ksegrp *kg; 671 struct kse *ke; 672 673 mtx_assert(&sched_lock, MA_OWNED); 674 kg = td->td_ksegrp; 675 ke = td->td_kse; 676 677 ke->ke_cpticks++; 678 kg->kg_estcpu = ESTCPULIM(kg->kg_estcpu + 1); 679 if ((kg->kg_estcpu % INVERSE_ESTCPU_WEIGHT) == 0) { 680 resetpriority(kg); 681 if (td->td_priority >= PUSER) 682 td->td_priority = kg->kg_user_pri; 683 } 684 } 685 686 /* 687 * charge childs scheduling cpu usage to parent. 688 * 689 * XXXKSE assume only one thread & kse & ksegrp keep estcpu in each ksegrp. 690 * Charge it to the ksegrp that did the wait since process estcpu is sum of 691 * all ksegrps, this is strictly as expected. Assume that the child process 692 * aggregated all the estcpu into the 'built-in' ksegrp. 693 */ 694 void 695 sched_exit(struct proc *p, struct thread *td) 696 { 697 sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), td); 698 sched_exit_thread(FIRST_THREAD_IN_PROC(p), td); 699 } 700 701 void 702 sched_exit_ksegrp(struct ksegrp *kg, struct thread *childtd) 703 { 704 705 mtx_assert(&sched_lock, MA_OWNED); 706 kg->kg_estcpu = ESTCPULIM(kg->kg_estcpu + childtd->td_ksegrp->kg_estcpu); 707 } 708 709 void 710 sched_exit_thread(struct thread *td, struct thread *child) 711 { 712 CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d", 713 child, child->td_proc->p_comm, child->td_priority); 714 if ((child->td_proc->p_flag & P_NOLOAD) == 0) 715 sched_load_rem(); 716 } 717 718 void 719 sched_fork(struct thread *td, struct thread *childtd) 720 { 721 sched_fork_ksegrp(td, childtd->td_ksegrp); 722 sched_fork_thread(td, childtd); 723 } 724 725 void 726 sched_fork_ksegrp(struct thread *td, struct ksegrp *child) 727 { 728 mtx_assert(&sched_lock, MA_OWNED); 729 child->kg_estcpu = td->td_ksegrp->kg_estcpu; 730 } 731 732 void 733 sched_fork_thread(struct thread *td, struct thread *childtd) 734 { 735 sched_newthread(childtd); 736 } 737 738 void 739 sched_nice(struct proc *p, int nice) 740 { 741 struct ksegrp *kg; 742 743 PROC_LOCK_ASSERT(p, MA_OWNED); 744 mtx_assert(&sched_lock, MA_OWNED); 745 p->p_nice = nice; 746 FOREACH_KSEGRP_IN_PROC(p, kg) { 747 resetpriority(kg); 748 } 749 } 750 751 void 752 sched_class(struct ksegrp *kg, int class) 753 { 754 mtx_assert(&sched_lock, MA_OWNED); 755 kg->kg_pri_class = class; 756 } 757 758 /* 759 * Adjust the priority of a thread. 760 * This may include moving the thread within the KSEGRP, 761 * changing the assignment of a kse to the thread, 762 * and moving a KSE in the system run queue. 763 */ 764 void 765 sched_prio(struct thread *td, u_char prio) 766 { 767 CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)", 768 td, td->td_proc->p_comm, td->td_priority, prio, curthread, 769 curthread->td_proc->p_comm); 770 771 mtx_assert(&sched_lock, MA_OWNED); 772 if (TD_ON_RUNQ(td)) { 773 adjustrunqueue(td, prio); 774 } else { 775 td->td_priority = prio; 776 } 777 } 778 779 void 780 sched_sleep(struct thread *td) 781 { 782 783 mtx_assert(&sched_lock, MA_OWNED); 784 td->td_ksegrp->kg_slptime = 0; 785 td->td_base_pri = td->td_priority; 786 } 787 788 static void remrunqueue(struct thread *td); 789 790 void 791 sched_switch(struct thread *td, struct thread *newtd, int flags) 792 { 793 struct kse *ke; 794 struct ksegrp *kg; 795 struct proc *p; 796 797 ke = td->td_kse; 798 p = td->td_proc; 799 800 mtx_assert(&sched_lock, MA_OWNED); 801 802 if ((p->p_flag & P_NOLOAD) == 0) 803 sched_load_rem(); 804 /* 805 * We are volunteering to switch out so we get to nominate 806 * a successor for the rest of our quantum 807 * First try another thread in our ksegrp, and then look for 808 * other ksegrps in our process. 809 */ 810 if (sched_followon && 811 (p->p_flag & P_HADTHREADS) && 812 (flags & SW_VOL) && 813 newtd == NULL) { 814 /* lets schedule another thread from this process */ 815 kg = td->td_ksegrp; 816 if ((newtd = TAILQ_FIRST(&kg->kg_runq))) { 817 remrunqueue(newtd); 818 sched_kgfollowons++; 819 } else { 820 FOREACH_KSEGRP_IN_PROC(p, kg) { 821 if ((newtd = TAILQ_FIRST(&kg->kg_runq))) { 822 sched_pfollowons++; 823 remrunqueue(newtd); 824 break; 825 } 826 } 827 } 828 } 829 830 td->td_lastcpu = td->td_oncpu; 831 td->td_flags &= ~TDF_NEEDRESCHED; 832 td->td_pflags &= ~TDP_OWEPREEMPT; 833 td->td_oncpu = NOCPU; 834 /* 835 * At the last moment, if this thread is still marked RUNNING, 836 * then put it back on the run queue as it has not been suspended 837 * or stopped or any thing else similar. We never put the idle 838 * threads on the run queue, however. 839 */ 840 if (td == PCPU_GET(idlethread)) 841 TD_SET_CAN_RUN(td); 842 else { 843 SLOT_RELEASE(td->td_ksegrp); 844 if (TD_IS_RUNNING(td)) { 845 /* Put us back on the run queue (kse and all). */ 846 setrunqueue(td, (flags & SW_PREEMPT) ? 847 SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED : 848 SRQ_OURSELF|SRQ_YIELDING); 849 } else if (p->p_flag & P_HADTHREADS) { 850 /* 851 * We will not be on the run queue. So we must be 852 * sleeping or similar. As it's available, 853 * someone else can use the KSE if they need it. 854 * It's NOT available if we are about to need it 855 */ 856 if (newtd == NULL || newtd->td_ksegrp != td->td_ksegrp) 857 slot_fill(td->td_ksegrp); 858 } 859 } 860 if (newtd) { 861 /* 862 * The thread we are about to run needs to be counted 863 * as if it had been added to the run queue and selected. 864 * It came from: 865 * * A preemption 866 * * An upcall 867 * * A followon 868 */ 869 KASSERT((newtd->td_inhibitors == 0), 870 ("trying to run inhibitted thread")); 871 SLOT_USE(newtd->td_ksegrp); 872 newtd->td_kse->ke_flags |= KEF_DIDRUN; 873 TD_SET_RUNNING(newtd); 874 if ((newtd->td_proc->p_flag & P_NOLOAD) == 0) 875 sched_load_add(); 876 } else { 877 newtd = choosethread(); 878 } 879 880 if (td != newtd) 881 cpu_switch(td, newtd); 882 sched_lock.mtx_lock = (uintptr_t)td; 883 td->td_oncpu = PCPU_GET(cpuid); 884 } 885 886 void 887 sched_wakeup(struct thread *td) 888 { 889 struct ksegrp *kg; 890 891 mtx_assert(&sched_lock, MA_OWNED); 892 kg = td->td_ksegrp; 893 if (kg->kg_slptime > 1) 894 updatepri(kg); 895 kg->kg_slptime = 0; 896 setrunqueue(td, SRQ_BORING); 897 } 898 899 #ifdef SMP 900 /* enable HTT_2 if you have a 2-way HTT cpu.*/ 901 static int 902 forward_wakeup(int cpunum) 903 { 904 cpumask_t map, me, dontuse; 905 cpumask_t map2; 906 struct pcpu *pc; 907 cpumask_t id, map3; 908 909 mtx_assert(&sched_lock, MA_OWNED); 910 911 CTR0(KTR_RUNQ, "forward_wakeup()"); 912 913 if ((!forward_wakeup_enabled) || 914 (forward_wakeup_use_mask == 0 && forward_wakeup_use_loop == 0)) 915 return (0); 916 if (!smp_started || cold || panicstr) 917 return (0); 918 919 forward_wakeups_requested++; 920 921 /* 922 * check the idle mask we received against what we calculated before 923 * in the old version. 924 */ 925 me = PCPU_GET(cpumask); 926 /* 927 * don't bother if we should be doing it ourself.. 928 */ 929 if ((me & idle_cpus_mask) && (cpunum == NOCPU || me == (1 << cpunum))) 930 return (0); 931 932 dontuse = me | stopped_cpus | hlt_cpus_mask; 933 map3 = 0; 934 if (forward_wakeup_use_loop) { 935 SLIST_FOREACH(pc, &cpuhead, pc_allcpu) { 936 id = pc->pc_cpumask; 937 if ( (id & dontuse) == 0 && 938 pc->pc_curthread == pc->pc_idlethread) { 939 map3 |= id; 940 } 941 } 942 } 943 944 if (forward_wakeup_use_mask) { 945 map = 0; 946 map = idle_cpus_mask & ~dontuse; 947 948 /* If they are both on, compare and use loop if different */ 949 if (forward_wakeup_use_loop) { 950 if (map != map3) { 951 printf("map (%02X) != map3 (%02X)\n", 952 map, map3); 953 map = map3; 954 } 955 } 956 } else { 957 map = map3; 958 } 959 /* If we only allow a specific CPU, then mask off all the others */ 960 if (cpunum != NOCPU) { 961 KASSERT((cpunum <= mp_maxcpus),("forward_wakeup: bad cpunum.")); 962 map &= (1 << cpunum); 963 } else { 964 /* Try choose an idle die. */ 965 if (forward_wakeup_use_htt) { 966 map2 = (map & (map >> 1)) & 0x5555; 967 if (map2) { 968 map = map2; 969 } 970 } 971 972 /* set only one bit */ 973 if (forward_wakeup_use_single) { 974 map = map & ((~map) + 1); 975 } 976 } 977 if (map) { 978 forward_wakeups_delivered++; 979 ipi_selected(map, IPI_AST); 980 return (1); 981 } 982 if (cpunum == NOCPU) 983 printf("forward_wakeup: Idle processor not found\n"); 984 return (0); 985 } 986 #endif 987 988 void 989 sched_add(struct thread *td, int flags) 990 { 991 struct kse *ke; 992 #ifdef SMP 993 int forwarded = 0; 994 int cpu; 995 #endif 996 997 ke = td->td_kse; 998 mtx_assert(&sched_lock, MA_OWNED); 999 CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)", 1000 td, td->td_proc->p_comm, td->td_priority, curthread, 1001 curthread->td_proc->p_comm); 1002 KASSERT(ke->ke_state != KES_ONRUNQ, 1003 ("sched_add: kse %p (%s) already in run queue", ke, 1004 ke->ke_proc->p_comm)); 1005 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1006 ("sched_add: process swapped out")); 1007 1008 #ifdef SMP 1009 if (KSE_CAN_MIGRATE(ke)) { 1010 CTR2(KTR_RUNQ, 1011 "sched_add: adding kse:%p (td:%p) to gbl runq", ke, td); 1012 cpu = NOCPU; 1013 ke->ke_runq = &runq; 1014 } else { 1015 if (!SKE_RUNQ_PCPU(ke)) 1016 ke->ke_runq = &runq_pcpu[(cpu = PCPU_GET(cpuid))]; 1017 else 1018 cpu = td->td_lastcpu; 1019 CTR3(KTR_RUNQ, 1020 "sched_add: Put kse:%p(td:%p) on cpu%d runq", ke, td, cpu); 1021 } 1022 #else 1023 CTR2(KTR_RUNQ, "sched_add: adding kse:%p (td:%p) to runq", ke, td); 1024 ke->ke_runq = &runq; 1025 1026 #endif 1027 /* 1028 * If we are yielding (on the way out anyhow) 1029 * or the thread being saved is US, 1030 * then don't try be smart about preemption 1031 * or kicking off another CPU 1032 * as it won't help and may hinder. 1033 * In the YIEDLING case, we are about to run whoever is 1034 * being put in the queue anyhow, and in the 1035 * OURSELF case, we are puting ourself on the run queue 1036 * which also only happens when we are about to yield. 1037 */ 1038 if((flags & SRQ_YIELDING) == 0) { 1039 #ifdef SMP 1040 cpumask_t me = PCPU_GET(cpumask); 1041 int idle = idle_cpus_mask & me; 1042 /* 1043 * Only try to kick off another CPU if 1044 * the thread is unpinned 1045 * or pinned to another cpu, 1046 * and there are other available and idle CPUs. 1047 * if we are idle, or it's an interrupt, 1048 * then skip straight to preemption. 1049 */ 1050 if ( (! idle) && ((flags & SRQ_INTR) == 0) && 1051 (idle_cpus_mask & ~(hlt_cpus_mask | me)) && 1052 ( KSE_CAN_MIGRATE(ke) || 1053 ke->ke_runq != &runq_pcpu[PCPU_GET(cpuid)])) { 1054 forwarded = forward_wakeup(cpu); 1055 } 1056 /* 1057 * If we failed to kick off another cpu, then look to 1058 * see if we should preempt this CPU. Only allow this 1059 * if it is not pinned or IS pinned to this CPU. 1060 * If we are the idle thread, we also try do preempt. 1061 * as it will be quicker and being idle, we won't 1062 * lose in doing so.. 1063 */ 1064 if ((!forwarded) && 1065 (ke->ke_runq == &runq || 1066 ke->ke_runq == &runq_pcpu[PCPU_GET(cpuid)])) 1067 #endif 1068 1069 { 1070 if (maybe_preempt(td)) 1071 return; 1072 } 1073 } 1074 if ((td->td_proc->p_flag & P_NOLOAD) == 0) 1075 sched_load_add(); 1076 SLOT_USE(td->td_ksegrp); 1077 runq_add(ke->ke_runq, ke, flags); 1078 ke->ke_ksegrp->kg_runq_kses++; 1079 ke->ke_state = KES_ONRUNQ; 1080 maybe_resched(td); 1081 } 1082 1083 void 1084 sched_rem(struct thread *td) 1085 { 1086 struct kse *ke; 1087 1088 ke = td->td_kse; 1089 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1090 ("sched_rem: process swapped out")); 1091 KASSERT((ke->ke_state == KES_ONRUNQ), 1092 ("sched_rem: KSE not on run queue")); 1093 mtx_assert(&sched_lock, MA_OWNED); 1094 1095 CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)", 1096 td, td->td_proc->p_comm, td->td_priority, curthread, 1097 curthread->td_proc->p_comm); 1098 if ((td->td_proc->p_flag & P_NOLOAD) == 0) 1099 sched_load_rem(); 1100 SLOT_RELEASE(td->td_ksegrp); 1101 runq_remove(ke->ke_runq, ke); 1102 1103 ke->ke_state = KES_THREAD; 1104 td->td_ksegrp->kg_runq_kses--; 1105 } 1106 1107 /* 1108 * Select threads to run. 1109 * Notice that the running threads still consume a slot. 1110 */ 1111 struct kse * 1112 sched_choose(void) 1113 { 1114 struct kse *ke; 1115 struct runq *rq; 1116 1117 #ifdef SMP 1118 struct kse *kecpu; 1119 1120 rq = &runq; 1121 ke = runq_choose(&runq); 1122 kecpu = runq_choose(&runq_pcpu[PCPU_GET(cpuid)]); 1123 1124 if (ke == NULL || 1125 (kecpu != NULL && 1126 kecpu->ke_thread->td_priority < ke->ke_thread->td_priority)) { 1127 CTR2(KTR_RUNQ, "choosing kse %p from pcpu runq %d", kecpu, 1128 PCPU_GET(cpuid)); 1129 ke = kecpu; 1130 rq = &runq_pcpu[PCPU_GET(cpuid)]; 1131 } else { 1132 CTR1(KTR_RUNQ, "choosing kse %p from main runq", ke); 1133 } 1134 1135 #else 1136 rq = &runq; 1137 ke = runq_choose(&runq); 1138 #endif 1139 1140 if (ke != NULL) { 1141 runq_remove(rq, ke); 1142 ke->ke_state = KES_THREAD; 1143 ke->ke_ksegrp->kg_runq_kses--; 1144 1145 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 1146 ("sched_choose: process swapped out")); 1147 } 1148 return (ke); 1149 } 1150 1151 void 1152 sched_userret(struct thread *td) 1153 { 1154 struct ksegrp *kg; 1155 /* 1156 * XXX we cheat slightly on the locking here to avoid locking in 1157 * the usual case. Setting td_priority here is essentially an 1158 * incomplete workaround for not setting it properly elsewhere. 1159 * Now that some interrupt handlers are threads, not setting it 1160 * properly elsewhere can clobber it in the window between setting 1161 * it here and returning to user mode, so don't waste time setting 1162 * it perfectly here. 1163 */ 1164 kg = td->td_ksegrp; 1165 if (td->td_priority != kg->kg_user_pri) { 1166 mtx_lock_spin(&sched_lock); 1167 td->td_priority = kg->kg_user_pri; 1168 mtx_unlock_spin(&sched_lock); 1169 } 1170 } 1171 1172 void 1173 sched_bind(struct thread *td, int cpu) 1174 { 1175 struct kse *ke; 1176 1177 mtx_assert(&sched_lock, MA_OWNED); 1178 KASSERT(TD_IS_RUNNING(td), 1179 ("sched_bind: cannot bind non-running thread")); 1180 1181 ke = td->td_kse; 1182 1183 ke->ke_flags |= KEF_BOUND; 1184 #ifdef SMP 1185 ke->ke_runq = &runq_pcpu[cpu]; 1186 if (PCPU_GET(cpuid) == cpu) 1187 return; 1188 1189 ke->ke_state = KES_THREAD; 1190 1191 mi_switch(SW_VOL, NULL); 1192 #endif 1193 } 1194 1195 void 1196 sched_unbind(struct thread* td) 1197 { 1198 mtx_assert(&sched_lock, MA_OWNED); 1199 td->td_kse->ke_flags &= ~KEF_BOUND; 1200 } 1201 1202 int 1203 sched_load(void) 1204 { 1205 return (sched_tdcnt); 1206 } 1207 1208 int 1209 sched_sizeof_ksegrp(void) 1210 { 1211 return (sizeof(struct ksegrp) + sizeof(struct kg_sched)); 1212 } 1213 int 1214 sched_sizeof_proc(void) 1215 { 1216 return (sizeof(struct proc)); 1217 } 1218 int 1219 sched_sizeof_thread(void) 1220 { 1221 return (sizeof(struct thread) + sizeof(struct kse)); 1222 } 1223 1224 fixpt_t 1225 sched_pctcpu(struct thread *td) 1226 { 1227 struct kse *ke; 1228 1229 ke = td->td_kse; 1230 return (ke->ke_pctcpu); 1231 1232 return (0); 1233 } 1234 #define KERN_SWITCH_INCLUDE 1 1235 #include "kern/kern_switch.c"
Cache object: 5d43eea9e08ca0e0cf1b0ecfd90133c0
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]