1 /* $OpenBSD: sched_bsd.c,v 1.24 2010/09/24 13:21:30 matthew 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 97 spc->spc_rrticks = rrticks_init; 98 99 if (ci->ci_curproc != NULL) { 100 if (spc->spc_schedflags & SPCF_SEENRR) { 101 /* 102 * The process has already been through a roundrobin 103 * without switching and may be hogging the CPU. 104 * Indicate that the process should yield. 105 */ 106 atomic_setbits_int(&spc->spc_schedflags, 107 SPCF_SHOULDYIELD); 108 } else { 109 atomic_setbits_int(&spc->spc_schedflags, 110 SPCF_SEENRR); 111 } 112 } 113 114 if (spc->spc_nrun) 115 need_resched(ci); 116 } 117 118 /* 119 * Constants for digital decay and forget: 120 * 90% of (p_estcpu) usage in 5 * loadav time 121 * 95% of (p_pctcpu) usage in 60 seconds (load insensitive) 122 * Note that, as ps(1) mentions, this can let percentages 123 * total over 100% (I've seen 137.9% for 3 processes). 124 * 125 * Note that hardclock updates p_estcpu and p_cpticks independently. 126 * 127 * We wish to decay away 90% of p_estcpu in (5 * loadavg) seconds. 128 * That is, the system wants to compute a value of decay such 129 * that the following for loop: 130 * for (i = 0; i < (5 * loadavg); i++) 131 * p_estcpu *= decay; 132 * will compute 133 * p_estcpu *= 0.1; 134 * for all values of loadavg: 135 * 136 * Mathematically this loop can be expressed by saying: 137 * decay ** (5 * loadavg) ~= .1 138 * 139 * The system computes decay as: 140 * decay = (2 * loadavg) / (2 * loadavg + 1) 141 * 142 * We wish to prove that the system's computation of decay 143 * will always fulfill the equation: 144 * decay ** (5 * loadavg) ~= .1 145 * 146 * If we compute b as: 147 * b = 2 * loadavg 148 * then 149 * decay = b / (b + 1) 150 * 151 * We now need to prove two things: 152 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1) 153 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg) 154 * 155 * Facts: 156 * For x close to zero, exp(x) =~ 1 + x, since 157 * exp(x) = 0! + x**1/1! + x**2/2! + ... . 158 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b. 159 * For x close to zero, ln(1+x) =~ x, since 160 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1 161 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1). 162 * ln(.1) =~ -2.30 163 * 164 * Proof of (1): 165 * Solve (factor)**(power) =~ .1 given power (5*loadav): 166 * solving for factor, 167 * ln(factor) =~ (-2.30/5*loadav), or 168 * factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) = 169 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED 170 * 171 * Proof of (2): 172 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)): 173 * solving for power, 174 * power*ln(b/(b+1)) =~ -2.30, or 175 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED 176 * 177 * Actual power values for the implemented algorithm are as follows: 178 * loadav: 1 2 3 4 179 * power: 5.68 10.32 14.94 19.55 180 */ 181 182 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */ 183 #define loadfactor(loadav) (2 * (loadav)) 184 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE)) 185 186 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 187 fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 188 189 /* 190 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the 191 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below 192 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT). 193 * 194 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used: 195 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits). 196 * 197 * If you don't want to bother with the faster/more-accurate formula, you 198 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate 199 * (more general) method of calculating the %age of CPU used by a process. 200 */ 201 #define CCPU_SHIFT 11 202 203 /* 204 * Recompute process priorities, every second. 205 */ 206 void 207 schedcpu(void *arg) 208 { 209 struct timeout *to = (struct timeout *)arg; 210 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 211 struct proc *p; 212 int s; 213 unsigned int newcpu; 214 int phz; 215 216 /* 217 * If we have a statistics clock, use that to calculate CPU 218 * time, otherwise revert to using the profiling clock (which, 219 * in turn, defaults to hz if there is no separate profiling 220 * clock available) 221 */ 222 phz = stathz ? stathz : profhz; 223 KASSERT(phz); 224 225 LIST_FOREACH(p, &allproc, p_list) { 226 /* 227 * Increment time in/out of memory and sleep time 228 * (if sleeping). We ignore overflow; with 16-bit int's 229 * (remember them?) overflow takes 45 days. 230 */ 231 p->p_swtime++; 232 if (p->p_stat == SSLEEP || p->p_stat == SSTOP) 233 p->p_slptime++; 234 p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT; 235 /* 236 * If the process has slept the entire second, 237 * stop recalculating its priority until it wakes up. 238 */ 239 if (p->p_slptime > 1) 240 continue; 241 SCHED_LOCK(s); 242 /* 243 * p_pctcpu is only for ps. 244 */ 245 #if (FSHIFT >= CCPU_SHIFT) 246 p->p_pctcpu += (phz == 100)? 247 ((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT): 248 100 * (((fixpt_t) p->p_cpticks) 249 << (FSHIFT - CCPU_SHIFT)) / phz; 250 #else 251 p->p_pctcpu += ((FSCALE - ccpu) * 252 (p->p_cpticks * FSCALE / phz)) >> FSHIFT; 253 #endif 254 p->p_cpticks = 0; 255 newcpu = (u_int) decay_cpu(loadfac, p->p_estcpu); 256 p->p_estcpu = newcpu; 257 resetpriority(p); 258 if (p->p_priority >= PUSER) { 259 if (p->p_stat == SRUN && 260 (p->p_priority / SCHED_PPQ) != 261 (p->p_usrpri / SCHED_PPQ)) { 262 remrunqueue(p); 263 p->p_priority = p->p_usrpri; 264 setrunqueue(p); 265 } else 266 p->p_priority = p->p_usrpri; 267 } 268 SCHED_UNLOCK(s); 269 } 270 uvm_meter(); 271 wakeup(&lbolt); 272 timeout_add_sec(to, 1); 273 } 274 275 /* 276 * Recalculate the priority of a process after it has slept for a while. 277 * For all load averages >= 1 and max p_estcpu of 255, sleeping for at 278 * least six times the loadfactor will decay p_estcpu to zero. 279 */ 280 void 281 updatepri(struct proc *p) 282 { 283 unsigned int newcpu = p->p_estcpu; 284 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 285 286 SCHED_ASSERT_LOCKED(); 287 288 if (p->p_slptime > 5 * loadfac) 289 p->p_estcpu = 0; 290 else { 291 p->p_slptime--; /* the first time was done in schedcpu */ 292 while (newcpu && --p->p_slptime) 293 newcpu = (int) decay_cpu(loadfac, newcpu); 294 p->p_estcpu = newcpu; 295 } 296 resetpriority(p); 297 } 298 299 /* 300 * General yield call. Puts the current process back on its run queue and 301 * performs a voluntary context switch. 302 */ 303 void 304 yield(void) 305 { 306 struct proc *p = curproc; 307 int s; 308 309 SCHED_LOCK(s); 310 p->p_priority = p->p_usrpri; 311 p->p_stat = SRUN; 312 setrunqueue(p); 313 p->p_stats->p_ru.ru_nvcsw++; 314 mi_switch(); 315 SCHED_UNLOCK(s); 316 } 317 318 /* 319 * General preemption call. Puts the current process back on its run queue 320 * and performs an involuntary context switch. If a process is supplied, 321 * we switch to that process. Otherwise, we use the normal process selection 322 * criteria. 323 */ 324 void 325 preempt(struct proc *newp) 326 { 327 struct proc *p = curproc; 328 int s; 329 330 /* 331 * XXX Switching to a specific process is not supported yet. 332 */ 333 if (newp != NULL) 334 panic("preempt: cpu_preempt not yet implemented"); 335 336 SCHED_LOCK(s); 337 p->p_priority = p->p_usrpri; 338 p->p_stat = SRUN; 339 p->p_cpu = sched_choosecpu(p); 340 setrunqueue(p); 341 p->p_stats->p_ru.ru_nivcsw++; 342 mi_switch(); 343 SCHED_UNLOCK(s); 344 } 345 346 void 347 mi_switch(void) 348 { 349 struct schedstate_percpu *spc = &curcpu()->ci_schedstate; 350 struct proc *p = curproc; 351 struct proc *nextproc; 352 struct rlimit *rlim; 353 struct timeval tv; 354 #ifdef MULTIPROCESSOR 355 int hold_count; 356 int sched_count; 357 #endif 358 359 assertwaitok(); 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 atomic_clearbits_int(&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