1 /* 2 * Copyright (c) 1982, 1986 Regents of the University of California. 3 * All rights reserved. The Berkeley software License Agreement 4 * specifies the terms and conditions for redistribution. 5 * 6 * @(#)kern_synch.c 7.9 (Berkeley) 05/29/89 7 */ 8 9 #include "machine/pte.h" 10 #include "machine/psl.h" 11 #include "machine/mtpr.h" 12 13 #include "param.h" 14 #include "systm.h" 15 #include "user.h" 16 #include "proc.h" 17 #include "vm.h" 18 #include "kernel.h" 19 #include "buf.h" 20 21 /* 22 * Force switch among equal priority processes every 100ms. 23 */ 24 roundrobin() 25 { 26 27 runrun++; 28 aston(); 29 timeout(roundrobin, (caddr_t)0, hz / 10); 30 } 31 32 /* 33 * constants for digital decay and forget 34 * 90% of (p_cpu) usage in 5*loadav time 35 * 95% of (p_pctcpu) usage in 60 seconds (load insensitive) 36 * Note that, as ps(1) mentions, this can let percentages 37 * total over 100% (I've seen 137.9% for 3 processes). 38 * 39 * Note that hardclock updates p_cpu and p_cpticks independently. 40 * 41 * We wish to decay away 90% of p_cpu in (5 * loadavg) seconds. 42 * That is, the system wants to compute a value of decay such 43 * that the following for loop: 44 * for (i = 0; i < (5 * loadavg); i++) 45 * p_cpu *= decay; 46 * will compute 47 * p_cpu *= 0.1; 48 * for all values of loadavg: 49 * 50 * Mathematically this loop can be expressed by saying: 51 * decay ** (5 * loadavg) ~= .1 52 * 53 * The system computes decay as: 54 * decay = (2 * loadavg) / (2 * loadavg + 1) 55 * 56 * We wish to prove that the system's computation of decay 57 * will always fulfill the equation: 58 * decay ** (5 * loadavg) ~= .1 59 * 60 * If we compute b as: 61 * b = 2 * loadavg 62 * then 63 * decay = b / (b + 1) 64 * 65 * We now need to prove two things: 66 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1) 67 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg) 68 * 69 * Facts: 70 * For x close to zero, exp(x) =~ 1 + x, since 71 * exp(x) = 0! + x**1/1! + x**2/2! + ... . 72 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b. 73 * For x close to zero, ln(1+x) =~ x, since 74 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1 75 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1). 76 * ln(.1) =~ -2.30 77 * 78 * Proof of (1): 79 * Solve (factor)**(power) =~ .1 given power (5*loadav): 80 * solving for factor, 81 * ln(factor) =~ (-2.30/5*loadav), or 82 * factor =~ exp(-1/((5/2.30)*loadav) =~ exp(-1/(2*loadav)) = 83 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED 84 * 85 * Proof of (2): 86 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)): 87 * solving for power, 88 * power*ln(b/(b+1)) =~ -2.30, or 89 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED 90 * 91 * Actual power values for the implemented algorithm are as follows: 92 * loadav: 1 2 3 4 93 * power: 5.68 10.32 14.94 19.55 94 */ 95 96 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */ 97 #define get_b(loadav) (2 * (loadav)) 98 #define get_pcpu(b, cpu) (((b) * ((cpu) & 0377)) / ((b) + FSCALE)) 99 100 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 101 fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 102 103 /* 104 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the 105 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below 106 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT). 107 * 108 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used: 109 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits). 110 * 111 * If you dont want to bother with the faster/more-accurate formula, you 112 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate 113 * (more general) method of calculating the %age of CPU used by a process. 114 */ 115 #define CCPU_SHIFT 11 116 117 /* 118 * Recompute process priorities, once a second 119 */ 120 schedcpu() 121 { 122 register fixpt_t b = get_b(averunnable[0]); 123 register struct proc *p; 124 register int s, a; 125 126 wakeup((caddr_t)&lbolt); 127 for (p = allproc; p != NULL; p = p->p_nxt) { 128 if (p->p_time != 127) 129 p->p_time++; 130 if (p->p_stat==SSLEEP || p->p_stat==SSTOP) 131 if (p->p_slptime != 127) 132 p->p_slptime++; 133 p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT; 134 /* 135 * If the process has slept the entire second, 136 * stop recalculating its priority until it wakes up. 137 */ 138 if (p->p_slptime > 1) 139 continue; 140 /* 141 * p_pctcpu is only for ps. 142 */ 143 #if (FSHIFT >= CCPU_SHIFT) 144 p->p_pctcpu += (hz == 100)? 145 ((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT): 146 100 * (((fixpt_t) p->p_cpticks) 147 << (FSHIFT - CCPU_SHIFT)) / hz; 148 #else 149 p->p_pctcpu += ((FSCALE - ccpu) * 150 (p->p_cpticks * FSCALE / hz)) >> FSHIFT; 151 #endif 152 p->p_cpticks = 0; 153 a = (int) get_pcpu(b, p->p_cpu) + p->p_nice; 154 if (a < 0) 155 a = 0; 156 if (a > 255) 157 a = 255; 158 p->p_cpu = a; 159 (void) setpri(p); 160 s = splhigh(); /* prevent state changes */ 161 if (p->p_pri >= PUSER) { 162 #define PPQ (128 / NQS) 163 if ((p != u.u_procp || noproc) && 164 p->p_stat == SRUN && 165 (p->p_flag & SLOAD) && 166 (p->p_pri / PPQ) != (p->p_usrpri / PPQ)) { 167 remrq(p); 168 p->p_pri = p->p_usrpri; 169 setrq(p); 170 } else 171 p->p_pri = p->p_usrpri; 172 } 173 splx(s); 174 } 175 vmmeter(); 176 if (runin!=0) { 177 runin = 0; 178 wakeup((caddr_t)&runin); 179 } 180 if (bclnlist != NULL) 181 wakeup((caddr_t)&proc[2]); 182 timeout(schedcpu, (caddr_t)0, hz); 183 } 184 185 /* 186 * Recalculate the priority of a process after it has slept for a while. 187 */ 188 updatepri(p) 189 register struct proc *p; 190 { 191 register int a = p->p_cpu & 0377; 192 register fixpt_t b = get_b(averunnable[0]); 193 194 p->p_slptime--; /* the first time was done in schedcpu */ 195 while (a && --p->p_slptime) 196 a = (int) get_pcpu(b, a) /* + p->p_nice */; 197 p->p_slptime = 0; 198 if (a < 0) 199 a = 0; 200 if (a > 255) 201 a = 255; 202 p->p_cpu = a; 203 (void) setpri(p); 204 } 205 206 #define SQSIZE 0100 /* Must be power of 2 */ 207 #define HASH(x) (( (int) x >> 5) & (SQSIZE-1)) 208 struct slpque { 209 struct proc *sq_head; 210 struct proc **sq_tailp; 211 } slpque[SQSIZE]; 212 213 /* 214 * Give up the processor till a wakeup occurs 215 * on chan, at which time the process 216 * enters the scheduling queue at priority pri. 217 * The most important effect of pri is that when 218 * pri<=PZERO a signal cannot disturb the sleep; 219 * if pri>PZERO signals will be processed. 220 * Callers of this routine must be prepared for 221 * premature return, and check that the reason for 222 * sleeping has gone away. 223 */ 224 sleep(chan, pri) 225 caddr_t chan; 226 int pri; 227 { 228 register struct proc *rp; 229 register struct slpque *qp; 230 register s; 231 extern int cold; 232 233 rp = u.u_procp; 234 s = splhigh(); 235 if (cold || panicstr) { 236 /* 237 * After a panic, or during autoconfiguration, 238 * just give interrupts a chance, then just return; 239 * don't run any other procs or panic below, 240 * in case this is the idle process and already asleep. 241 * The splnet should be spl0 if the network was being used 242 * by the filesystem, but for now avoid network interrupts 243 * that might cause another panic. 244 */ 245 (void) splnet(); 246 splx(s); 247 return; 248 } 249 if (chan==0 || rp->p_stat != SRUN || rp->p_rlink) 250 panic("sleep"); 251 rp->p_wchan = chan; 252 rp->p_slptime = 0; 253 rp->p_pri = pri; 254 qp = &slpque[HASH(chan)]; 255 if (qp->sq_head == 0) 256 qp->sq_head = rp; 257 else 258 *qp->sq_tailp = rp; 259 *(qp->sq_tailp = &rp->p_link) = 0; 260 if (pri > PZERO) { 261 /* 262 * If we stop in issig(), wakeup may already have happened 263 * when we return (rp->p_wchan will then be 0). 264 */ 265 if (ISSIG(rp)) { 266 if (rp->p_wchan) 267 unsleep(rp); 268 rp->p_stat = SRUN; 269 (void) spl0(); 270 goto psig; 271 } 272 if (rp->p_wchan == 0) 273 goto out; 274 rp->p_stat = SSLEEP; 275 (void) spl0(); 276 u.u_ru.ru_nvcsw++; 277 swtch(); 278 if (ISSIG(rp)) 279 goto psig; 280 } else { 281 rp->p_stat = SSLEEP; 282 (void) spl0(); 283 u.u_ru.ru_nvcsw++; 284 swtch(); 285 } 286 curpri = rp->p_usrpri; 287 out: 288 splx(s); 289 return; 290 291 /* 292 * If priority was low (>PZERO) and 293 * there has been a signal, execute non-local goto through 294 * u.u_qsave, aborting the system call in progress (see trap.c) 295 */ 296 psig: 297 longjmp(&u.u_qsave); 298 /*NOTREACHED*/ 299 } 300 301 /* 302 * Remove a process from its wait queue 303 */ 304 unsleep(p) 305 register struct proc *p; 306 { 307 register struct slpque *qp; 308 register struct proc **hp; 309 int s; 310 311 s = splhigh(); 312 if (p->p_wchan) { 313 hp = &(qp = &slpque[HASH(p->p_wchan)])->sq_head; 314 while (*hp != p) 315 hp = &(*hp)->p_link; 316 *hp = p->p_link; 317 if (qp->sq_tailp == &p->p_link) 318 qp->sq_tailp = hp; 319 p->p_wchan = 0; 320 } 321 splx(s); 322 } 323 324 /* 325 * Wake up all processes sleeping on chan. 326 */ 327 wakeup(chan) 328 register caddr_t chan; 329 { 330 register struct slpque *qp; 331 register struct proc *p, **q; 332 int s; 333 334 s = splhigh(); 335 qp = &slpque[HASH(chan)]; 336 restart: 337 for (q = &qp->sq_head; p = *q; ) { 338 if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP) 339 panic("wakeup"); 340 if (p->p_wchan==chan) { 341 p->p_wchan = 0; 342 *q = p->p_link; 343 if (qp->sq_tailp == &p->p_link) 344 qp->sq_tailp = q; 345 if (p->p_stat == SSLEEP) { 346 /* OPTIMIZED INLINE EXPANSION OF setrun(p) */ 347 if (p->p_slptime > 1) 348 updatepri(p); 349 p->p_stat = SRUN; 350 if (p->p_flag & SLOAD) 351 setrq(p); 352 /* 353 * Since curpri is a usrpri, 354 * p->p_pri is always better than curpri. 355 */ 356 runrun++; 357 aston(); 358 if ((p->p_flag&SLOAD) == 0) { 359 if (runout != 0) { 360 runout = 0; 361 wakeup((caddr_t)&runout); 362 } 363 wantin++; 364 } 365 /* END INLINE EXPANSION */ 366 goto restart; 367 } 368 } else 369 q = &p->p_link; 370 } 371 splx(s); 372 } 373 374 /* 375 * Initialize the (doubly-linked) run queues 376 * to be empty. 377 */ 378 rqinit() 379 { 380 register int i; 381 382 for (i = 0; i < NQS; i++) 383 qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i]; 384 } 385 386 /* 387 * Set the process running; 388 * arrange for it to be swapped in if necessary. 389 */ 390 setrun(p) 391 register struct proc *p; 392 { 393 register int s; 394 395 s = splhigh(); 396 switch (p->p_stat) { 397 398 case 0: 399 case SWAIT: 400 case SRUN: 401 case SZOMB: 402 default: 403 panic("setrun"); 404 405 case SSTOP: 406 case SSLEEP: 407 unsleep(p); /* e.g. when sending signals */ 408 break; 409 410 case SIDL: 411 break; 412 } 413 p->p_stat = SRUN; 414 if (p->p_flag & SLOAD) 415 setrq(p); 416 splx(s); 417 if (p->p_slptime > 1) 418 updatepri(p); 419 if (p->p_pri < curpri) { 420 runrun++; 421 aston(); 422 } 423 if ((p->p_flag&SLOAD) == 0) { 424 if (runout != 0) { 425 runout = 0; 426 wakeup((caddr_t)&runout); 427 } 428 wantin++; 429 } 430 } 431 432 /* 433 * Set user priority. 434 * The rescheduling flag (runrun) 435 * is set if the priority is better 436 * than the currently running process. 437 */ 438 setpri(pp) 439 register struct proc *pp; 440 { 441 register int p; 442 443 p = (pp->p_cpu & 0377)/4; 444 p += PUSER + 2 * pp->p_nice; 445 if (pp->p_rssize > pp->p_maxrss && freemem < desfree) 446 p += 2*4; /* effectively, nice(4) */ 447 if (p > 127) 448 p = 127; 449 if (p < curpri) { 450 runrun++; 451 aston(); 452 } 453 pp->p_usrpri = p; 454 return (p); 455 } 456