1 /* $OpenBSD: sched_bsd.c,v 1.21 2009/04/14 09:13:25 art Exp $ */ 2 /* $NetBSD: kern_synch.c,v 1.37 1996/04/22 01:38:37 christos Exp $ */ 3 4 /*- 5 * Copyright (c) 1982, 1986, 1990, 1991, 1993 6 * The Regents of the University of California. All rights reserved. 7 * (c) UNIX System Laboratories, Inc. 8 * All or some portions of this file are derived from material licensed 9 * to the University of California by American Telephone and Telegraph 10 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 11 * the permission of UNIX System Laboratories, Inc. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 * 37 * @(#)kern_synch.c 8.6 (Berkeley) 1/21/94 38 */ 39 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/proc.h> 43 #include <sys/kernel.h> 44 #include <sys/buf.h> 45 #include <sys/signalvar.h> 46 #include <sys/resourcevar.h> 47 #include <uvm/uvm_extern.h> 48 #include <sys/sched.h> 49 #include <sys/timeout.h> 50 51 #ifdef KTRACE 52 #include <sys/ktrace.h> 53 #endif 54 55 #include <machine/cpu.h> 56 57 int lbolt; /* once a second sleep address */ 58 int rrticks_init; /* # of hardclock ticks per roundrobin() */ 59 60 #ifdef MULTIPROCESSOR 61 struct __mp_lock sched_lock; 62 #endif 63 64 void scheduler_start(void); 65 66 void roundrobin(struct cpu_info *); 67 void schedcpu(void *); 68 void updatepri(struct proc *); 69 void endtsleep(void *); 70 71 void 72 scheduler_start(void) 73 { 74 static struct timeout schedcpu_to; 75 76 /* 77 * We avoid polluting the global namespace by keeping the scheduler 78 * timeouts static in this function. 79 * We setup the timeouts here and kick schedcpu and roundrobin once to 80 * make them do their job. 81 */ 82 83 timeout_set(&schedcpu_to, schedcpu, &schedcpu_to); 84 85 rrticks_init = hz / 10; 86 schedcpu(&schedcpu_to); 87 } 88 89 /* 90 * Force switch among equal priority processes every 100ms. 91 */ 92 void 93 roundrobin(struct cpu_info *ci) 94 { 95 struct schedstate_percpu *spc = &ci->ci_schedstate; 96 int s; 97 98 spc->spc_rrticks = rrticks_init; 99 100 if (ci->ci_curproc != NULL) { 101 s = splstatclock(); 102 if (spc->spc_schedflags & SPCF_SEENRR) { 103 /* 104 * The process has already been through a roundrobin 105 * without switching and may be hogging the CPU. 106 * Indicate that the process should yield. 107 */ 108 spc->spc_schedflags |= SPCF_SHOULDYIELD; 109 } else { 110 spc->spc_schedflags |= SPCF_SEENRR; 111 } 112 splx(s); 113 } 114 115 if (spc->spc_nrun) 116 need_resched(ci); 117 } 118 119 /* 120 * Constants for digital decay and forget: 121 * 90% of (p_estcpu) usage in 5 * loadav time 122 * 95% of (p_pctcpu) usage in 60 seconds (load insensitive) 123 * Note that, as ps(1) mentions, this can let percentages 124 * total over 100% (I've seen 137.9% for 3 processes). 125 * 126 * Note that hardclock updates p_estcpu and p_cpticks independently. 127 * 128 * We wish to decay away 90% of p_estcpu in (5 * loadavg) seconds. 129 * That is, the system wants to compute a value of decay such 130 * that the following for loop: 131 * for (i = 0; i < (5 * loadavg); i++) 132 * p_estcpu *= decay; 133 * will compute 134 * p_estcpu *= 0.1; 135 * for all values of loadavg: 136 * 137 * Mathematically this loop can be expressed by saying: 138 * decay ** (5 * loadavg) ~= .1 139 * 140 * The system computes decay as: 141 * decay = (2 * loadavg) / (2 * loadavg + 1) 142 * 143 * We wish to prove that the system's computation of decay 144 * will always fulfill the equation: 145 * decay ** (5 * loadavg) ~= .1 146 * 147 * If we compute b as: 148 * b = 2 * loadavg 149 * then 150 * decay = b / (b + 1) 151 * 152 * We now need to prove two things: 153 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1) 154 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg) 155 * 156 * Facts: 157 * For x close to zero, exp(x) =~ 1 + x, since 158 * exp(x) = 0! + x**1/1! + x**2/2! + ... . 159 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b. 160 * For x close to zero, ln(1+x) =~ x, since 161 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1 162 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1). 163 * ln(.1) =~ -2.30 164 * 165 * Proof of (1): 166 * Solve (factor)**(power) =~ .1 given power (5*loadav): 167 * solving for factor, 168 * ln(factor) =~ (-2.30/5*loadav), or 169 * factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) = 170 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED 171 * 172 * Proof of (2): 173 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)): 174 * solving for power, 175 * power*ln(b/(b+1)) =~ -2.30, or 176 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED 177 * 178 * Actual power values for the implemented algorithm are as follows: 179 * loadav: 1 2 3 4 180 * power: 5.68 10.32 14.94 19.55 181 */ 182 183 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */ 184 #define loadfactor(loadav) (2 * (loadav)) 185 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE)) 186 187 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 188 fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 189 190 /* 191 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the 192 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below 193 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT). 194 * 195 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used: 196 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits). 197 * 198 * If you don't want to bother with the faster/more-accurate formula, you 199 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate 200 * (more general) method of calculating the %age of CPU used by a process. 201 */ 202 #define CCPU_SHIFT 11 203 204 /* 205 * Recompute process priorities, every hz ticks. 206 */ 207 void 208 schedcpu(void *arg) 209 { 210 struct timeout *to = (struct timeout *)arg; 211 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 212 struct proc *p; 213 int s; 214 unsigned int newcpu; 215 int phz; 216 217 /* 218 * If we have a statistics clock, use that to calculate CPU 219 * time, otherwise revert to using the profiling clock (which, 220 * in turn, defaults to hz if there is no separate profiling 221 * clock available) 222 */ 223 phz = stathz ? stathz : profhz; 224 KASSERT(phz); 225 226 LIST_FOREACH(p, &allproc, p_list) { 227 /* 228 * Increment time in/out of memory and sleep time 229 * (if sleeping). We ignore overflow; with 16-bit int's 230 * (remember them?) overflow takes 45 days. 231 */ 232 p->p_swtime++; 233 if (p->p_stat == SSLEEP || p->p_stat == SSTOP) 234 p->p_slptime++; 235 p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT; 236 /* 237 * If the process has slept the entire second, 238 * stop recalculating its priority until it wakes up. 239 */ 240 if (p->p_slptime > 1) 241 continue; 242 SCHED_LOCK(s); 243 /* 244 * p_pctcpu is only for ps. 245 */ 246 #if (FSHIFT >= CCPU_SHIFT) 247 p->p_pctcpu += (phz == 100)? 248 ((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT): 249 100 * (((fixpt_t) p->p_cpticks) 250 << (FSHIFT - CCPU_SHIFT)) / phz; 251 #else 252 p->p_pctcpu += ((FSCALE - ccpu) * 253 (p->p_cpticks * FSCALE / phz)) >> FSHIFT; 254 #endif 255 p->p_cpticks = 0; 256 newcpu = (u_int) decay_cpu(loadfac, p->p_estcpu); 257 p->p_estcpu = newcpu; 258 resetpriority(p); 259 if (p->p_priority >= PUSER) { 260 if (p->p_stat == SRUN && 261 (p->p_priority / SCHED_PPQ) != 262 (p->p_usrpri / SCHED_PPQ)) { 263 remrunqueue(p); 264 p->p_priority = p->p_usrpri; 265 setrunqueue(p); 266 } else 267 p->p_priority = p->p_usrpri; 268 } 269 SCHED_UNLOCK(s); 270 } 271 uvm_meter(); 272 wakeup(&lbolt); 273 timeout_add_sec(to, 1); 274 } 275 276 /* 277 * Recalculate the priority of a process after it has slept for a while. 278 * For all load averages >= 1 and max p_estcpu of 255, sleeping for at 279 * least six times the loadfactor will decay p_estcpu to zero. 280 */ 281 void 282 updatepri(struct proc *p) 283 { 284 unsigned int newcpu = p->p_estcpu; 285 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 286 287 SCHED_ASSERT_LOCKED(); 288 289 if (p->p_slptime > 5 * loadfac) 290 p->p_estcpu = 0; 291 else { 292 p->p_slptime--; /* the first time was done in schedcpu */ 293 while (newcpu && --p->p_slptime) 294 newcpu = (int) decay_cpu(loadfac, newcpu); 295 p->p_estcpu = newcpu; 296 } 297 resetpriority(p); 298 } 299 300 /* 301 * General yield call. Puts the current process back on its run queue and 302 * performs a voluntary context switch. 303 */ 304 void 305 yield(void) 306 { 307 struct proc *p = curproc; 308 int s; 309 310 SCHED_LOCK(s); 311 p->p_priority = p->p_usrpri; 312 p->p_stat = SRUN; 313 setrunqueue(p); 314 p->p_stats->p_ru.ru_nvcsw++; 315 mi_switch(); 316 SCHED_UNLOCK(s); 317 } 318 319 /* 320 * General preemption call. Puts the current process back on its run queue 321 * and performs an involuntary context switch. If a process is supplied, 322 * we switch to that process. Otherwise, we use the normal process selection 323 * criteria. 324 */ 325 void 326 preempt(struct proc *newp) 327 { 328 struct proc *p = curproc; 329 int s; 330 331 /* 332 * XXX Switching to a specific process is not supported yet. 333 */ 334 if (newp != NULL) 335 panic("preempt: cpu_preempt not yet implemented"); 336 337 SCHED_LOCK(s); 338 p->p_priority = p->p_usrpri; 339 p->p_stat = SRUN; 340 p->p_cpu = sched_choosecpu(p); 341 setrunqueue(p); 342 p->p_stats->p_ru.ru_nivcsw++; 343 mi_switch(); 344 SCHED_UNLOCK(s); 345 } 346 347 void 348 mi_switch(void) 349 { 350 struct schedstate_percpu *spc = &curcpu()->ci_schedstate; 351 struct proc *p = curproc; 352 struct proc *nextproc; 353 struct rlimit *rlim; 354 struct timeval tv; 355 #ifdef MULTIPROCESSOR 356 int hold_count; 357 int sched_count; 358 #endif 359 360 KASSERT(p->p_stat != SONPROC); 361 362 SCHED_ASSERT_LOCKED(); 363 364 #ifdef MULTIPROCESSOR 365 /* 366 * Release the kernel_lock, as we are about to yield the CPU. 367 */ 368 sched_count = __mp_release_all_but_one(&sched_lock); 369 if (p->p_flag & P_BIGLOCK) 370 hold_count = __mp_release_all(&kernel_lock); 371 #endif 372 373 /* 374 * Compute the amount of time during which the current 375 * process was running, and add that to its total so far. 376 */ 377 microuptime(&tv); 378 if (timercmp(&tv, &spc->spc_runtime, <)) { 379 #if 0 380 printf("uptime is not monotonic! " 381 "tv=%lu.%06lu, runtime=%lu.%06lu\n", 382 tv.tv_sec, tv.tv_usec, spc->spc_runtime.tv_sec, 383 spc->spc_runtime.tv_usec); 384 #endif 385 } else { 386 timersub(&tv, &spc->spc_runtime, &tv); 387 timeradd(&p->p_rtime, &tv, &p->p_rtime); 388 } 389 390 /* 391 * Check if the process exceeds its cpu resource allocation. 392 * If over max, kill it. 393 */ 394 rlim = &p->p_rlimit[RLIMIT_CPU]; 395 if ((rlim_t)p->p_rtime.tv_sec >= rlim->rlim_cur) { 396 if ((rlim_t)p->p_rtime.tv_sec >= rlim->rlim_max) { 397 psignal(p, SIGKILL); 398 } else { 399 psignal(p, SIGXCPU); 400 if (rlim->rlim_cur < rlim->rlim_max) 401 rlim->rlim_cur += 5; 402 } 403 } 404 405 /* 406 * Process is about to yield the CPU; clear the appropriate 407 * scheduling flags. 408 */ 409 spc->spc_schedflags &= ~SPCF_SWITCHCLEAR; 410 411 nextproc = sched_chooseproc(); 412 413 if (p != nextproc) { 414 uvmexp.swtch++; 415 cpu_switchto(p, nextproc); 416 } else { 417 p->p_stat = SONPROC; 418 } 419 420 clear_resched(curcpu()); 421 422 SCHED_ASSERT_LOCKED(); 423 424 /* 425 * To preserve lock ordering, we need to release the sched lock 426 * and grab it after we grab the big lock. 427 * In the future, when the sched lock isn't recursive, we'll 428 * just release it here. 429 */ 430 #ifdef MULTIPROCESSOR 431 __mp_unlock(&sched_lock); 432 #endif 433 434 SCHED_ASSERT_UNLOCKED(); 435 436 /* 437 * We're running again; record our new start time. We might 438 * be running on a new CPU now, so don't use the cache'd 439 * schedstate_percpu pointer. 440 */ 441 KASSERT(p->p_cpu == curcpu()); 442 443 microuptime(&p->p_cpu->ci_schedstate.spc_runtime); 444 445 #ifdef MULTIPROCESSOR 446 /* 447 * Reacquire the kernel_lock now. We do this after we've 448 * released the scheduler lock to avoid deadlock, and before 449 * we reacquire the interlock and the scheduler lock. 450 */ 451 if (p->p_flag & P_BIGLOCK) 452 __mp_acquire_count(&kernel_lock, hold_count); 453 __mp_acquire_count(&sched_lock, sched_count + 1); 454 #endif 455 } 456 457 static __inline void 458 resched_proc(struct proc *p, u_char pri) 459 { 460 struct cpu_info *ci; 461 462 /* 463 * XXXSMP 464 * Since p->p_cpu persists across a context switch, 465 * this gives us *very weak* processor affinity, in 466 * that we notify the CPU on which the process last 467 * ran that it should try to switch. 468 * 469 * This does not guarantee that the process will run on 470 * that processor next, because another processor might 471 * grab it the next time it performs a context switch. 472 * 473 * This also does not handle the case where its last 474 * CPU is running a higher-priority process, but every 475 * other CPU is running a lower-priority process. There 476 * are ways to handle this situation, but they're not 477 * currently very pretty, and we also need to weigh the 478 * cost of moving a process from one CPU to another. 479 * 480 * XXXSMP 481 * There is also the issue of locking the other CPU's 482 * sched state, which we currently do not do. 483 */ 484 ci = (p->p_cpu != NULL) ? p->p_cpu : curcpu(); 485 if (pri < ci->ci_schedstate.spc_curpriority) 486 need_resched(ci); 487 } 488 489 /* 490 * Change process state to be runnable, 491 * placing it on the run queue if it is in memory, 492 * and awakening the swapper if it isn't in memory. 493 */ 494 void 495 setrunnable(struct proc *p) 496 { 497 SCHED_ASSERT_LOCKED(); 498 499 switch (p->p_stat) { 500 case 0: 501 case SRUN: 502 case SONPROC: 503 case SZOMB: 504 case SDEAD: 505 case SIDL: 506 default: 507 panic("setrunnable"); 508 case SSTOP: 509 /* 510 * If we're being traced (possibly because someone attached us 511 * while we were stopped), check for a signal from the debugger. 512 */ 513 if ((p->p_flag & P_TRACED) != 0 && p->p_xstat != 0) 514 atomic_setbits_int(&p->p_siglist, sigmask(p->p_xstat)); 515 case SSLEEP: 516 unsleep(p); /* e.g. when sending signals */ 517 break; 518 } 519 p->p_stat = SRUN; 520 p->p_cpu = sched_choosecpu(p); 521 setrunqueue(p); 522 if (p->p_slptime > 1) 523 updatepri(p); 524 p->p_slptime = 0; 525 resched_proc(p, p->p_priority); 526 } 527 528 /* 529 * Compute the priority of a process when running in user mode. 530 * Arrange to reschedule if the resulting priority is better 531 * than that of the current process. 532 */ 533 void 534 resetpriority(struct proc *p) 535 { 536 unsigned int newpriority; 537 538 SCHED_ASSERT_LOCKED(); 539 540 newpriority = PUSER + p->p_estcpu + NICE_WEIGHT * (p->p_nice - NZERO); 541 newpriority = min(newpriority, MAXPRI); 542 p->p_usrpri = newpriority; 543 resched_proc(p, p->p_usrpri); 544 } 545 546 /* 547 * We adjust the priority of the current process. The priority of a process 548 * gets worse as it accumulates CPU time. The cpu usage estimator (p_estcpu) 549 * is increased here. The formula for computing priorities (in kern_synch.c) 550 * will compute a different value each time p_estcpu increases. This can 551 * cause a switch, but unless the priority crosses a PPQ boundary the actual 552 * queue will not change. The cpu usage estimator ramps up quite quickly 553 * when the process is running (linearly), and decays away exponentially, at 554 * a rate which is proportionally slower when the system is busy. The basic 555 * principle is that the system will 90% forget that the process used a lot 556 * of CPU time in 5 * loadav seconds. This causes the system to favor 557 * processes which haven't run much recently, and to round-robin among other 558 * processes. 559 */ 560 561 void 562 schedclock(struct proc *p) 563 { 564 int s; 565 566 SCHED_LOCK(s); 567 p->p_estcpu = ESTCPULIM(p->p_estcpu + 1); 568 resetpriority(p); 569 if (p->p_priority >= PUSER) 570 p->p_priority = p->p_usrpri; 571 SCHED_UNLOCK(s); 572 } 573