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.8 (Berkeley) 05/05/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 #define filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1)) 96 97 double ccpu = 0.95122942450071400909; /* exp(-1/20) */ 98 99 /* 100 * Recompute process priorities, once a second 101 */ 102 schedcpu() 103 { 104 register double ccpu1 = (1.0 - ccpu) / (double)hz; 105 register struct proc *p; 106 register int s, a; 107 float scale = filter(avenrun[0]); 108 109 wakeup((caddr_t)&lbolt); 110 for (p = allproc; p != NULL; p = p->p_nxt) { 111 if (p->p_time != 127) 112 p->p_time++; 113 if (p->p_stat==SSLEEP || p->p_stat==SSTOP) 114 if (p->p_slptime != 127) 115 p->p_slptime++; 116 /* 117 * If the process has slept the entire second, 118 * stop recalculating its priority until it wakes up. 119 */ 120 if (p->p_slptime > 1) { 121 p->p_pctcpu *= ccpu; 122 continue; 123 } 124 /* 125 * p_pctcpu is only for ps. 126 */ 127 p->p_pctcpu = ccpu * p->p_pctcpu + ccpu1 * p->p_cpticks; 128 p->p_cpticks = 0; 129 a = (int) (scale * (p->p_cpu & 0377)) + p->p_nice; 130 if (a < 0) 131 a = 0; 132 if (a > 255) 133 a = 255; 134 p->p_cpu = a; 135 (void) setpri(p); 136 s = splhigh(); /* prevent state changes */ 137 if (p->p_pri >= PUSER) { 138 #define PPQ (128 / NQS) 139 if ((p != u.u_procp || noproc) && 140 p->p_stat == SRUN && 141 (p->p_flag & SLOAD) && 142 (p->p_pri / PPQ) != (p->p_usrpri / PPQ)) { 143 remrq(p); 144 p->p_pri = p->p_usrpri; 145 setrq(p); 146 } else 147 p->p_pri = p->p_usrpri; 148 } 149 splx(s); 150 } 151 vmmeter(); 152 if (runin!=0) { 153 runin = 0; 154 wakeup((caddr_t)&runin); 155 } 156 if (bclnlist != NULL) 157 wakeup((caddr_t)&proc[2]); 158 timeout(schedcpu, (caddr_t)0, hz); 159 } 160 161 /* 162 * Recalculate the priority of a process after it has slept for a while. 163 */ 164 updatepri(p) 165 register struct proc *p; 166 { 167 register int a = p->p_cpu & 0377; 168 float scale = filter(avenrun[0]); 169 170 p->p_slptime--; /* the first time was done in schedcpu */ 171 while (a && --p->p_slptime) 172 a = (int) (scale * a) /* + p->p_nice */; 173 p->p_slptime = 0; 174 if (a < 0) 175 a = 0; 176 if (a > 255) 177 a = 255; 178 p->p_cpu = a; 179 (void) setpri(p); 180 } 181 182 #define SQSIZE 0100 /* Must be power of 2 */ 183 #define HASH(x) (( (int) x >> 5) & (SQSIZE-1)) 184 struct slpque { 185 struct proc *sq_head; 186 struct proc **sq_tailp; 187 } slpque[SQSIZE]; 188 189 /* 190 * Give up the processor till a wakeup occurs 191 * on chan, at which time the process 192 * enters the scheduling queue at priority pri. 193 * The most important effect of pri is that when 194 * pri<=PZERO a signal cannot disturb the sleep; 195 * if pri>PZERO signals will be processed. 196 * Callers of this routine must be prepared for 197 * premature return, and check that the reason for 198 * sleeping has gone away. 199 */ 200 sleep(chan, pri) 201 caddr_t chan; 202 int pri; 203 { 204 register struct proc *rp; 205 register struct slpque *qp; 206 register s; 207 extern int cold; 208 209 rp = u.u_procp; 210 s = splhigh(); 211 if (cold || panicstr) { 212 /* 213 * After a panic, or during autoconfiguration, 214 * just give interrupts a chance, then just return; 215 * don't run any other procs or panic below, 216 * in case this is the idle process and already asleep. 217 * The splnet should be spl0 if the network was being used 218 * by the filesystem, but for now avoid network interrupts 219 * that might cause another panic. 220 */ 221 (void) splnet(); 222 splx(s); 223 return; 224 } 225 if (chan==0 || rp->p_stat != SRUN || rp->p_rlink) 226 panic("sleep"); 227 rp->p_wchan = chan; 228 rp->p_slptime = 0; 229 rp->p_pri = pri; 230 qp = &slpque[HASH(chan)]; 231 if (qp->sq_head == 0) 232 qp->sq_head = rp; 233 else 234 *qp->sq_tailp = rp; 235 *(qp->sq_tailp = &rp->p_link) = 0; 236 if (pri > PZERO) { 237 /* 238 * If we stop in issig(), wakeup may already have happened 239 * when we return (rp->p_wchan will then be 0). 240 */ 241 if (ISSIG(rp)) { 242 if (rp->p_wchan) 243 unsleep(rp); 244 rp->p_stat = SRUN; 245 (void) spl0(); 246 goto psig; 247 } 248 if (rp->p_wchan == 0) 249 goto out; 250 rp->p_stat = SSLEEP; 251 (void) spl0(); 252 u.u_ru.ru_nvcsw++; 253 swtch(); 254 if (ISSIG(rp)) 255 goto psig; 256 } else { 257 rp->p_stat = SSLEEP; 258 (void) spl0(); 259 u.u_ru.ru_nvcsw++; 260 swtch(); 261 } 262 curpri = rp->p_usrpri; 263 out: 264 splx(s); 265 return; 266 267 /* 268 * If priority was low (>PZERO) and 269 * there has been a signal, execute non-local goto through 270 * u.u_qsave, aborting the system call in progress (see trap.c) 271 */ 272 psig: 273 longjmp(&u.u_qsave); 274 /*NOTREACHED*/ 275 } 276 277 /* 278 * Remove a process from its wait queue 279 */ 280 unsleep(p) 281 register struct proc *p; 282 { 283 register struct slpque *qp; 284 register struct proc **hp; 285 int s; 286 287 s = splhigh(); 288 if (p->p_wchan) { 289 hp = &(qp = &slpque[HASH(p->p_wchan)])->sq_head; 290 while (*hp != p) 291 hp = &(*hp)->p_link; 292 *hp = p->p_link; 293 if (qp->sq_tailp == &p->p_link) 294 qp->sq_tailp = hp; 295 p->p_wchan = 0; 296 } 297 splx(s); 298 } 299 300 /* 301 * Wake up all processes sleeping on chan. 302 */ 303 wakeup(chan) 304 register caddr_t chan; 305 { 306 register struct slpque *qp; 307 register struct proc *p, **q; 308 int s; 309 310 s = splhigh(); 311 qp = &slpque[HASH(chan)]; 312 restart: 313 for (q = &qp->sq_head; p = *q; ) { 314 if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP) 315 panic("wakeup"); 316 if (p->p_wchan==chan) { 317 p->p_wchan = 0; 318 *q = p->p_link; 319 if (qp->sq_tailp == &p->p_link) 320 qp->sq_tailp = q; 321 if (p->p_stat == SSLEEP) { 322 /* OPTIMIZED INLINE EXPANSION OF setrun(p) */ 323 if (p->p_slptime > 1) 324 updatepri(p); 325 p->p_stat = SRUN; 326 if (p->p_flag & SLOAD) 327 setrq(p); 328 /* 329 * Since curpri is a usrpri, 330 * p->p_pri is always better than curpri. 331 */ 332 runrun++; 333 aston(); 334 if ((p->p_flag&SLOAD) == 0) { 335 if (runout != 0) { 336 runout = 0; 337 wakeup((caddr_t)&runout); 338 } 339 wantin++; 340 } 341 /* END INLINE EXPANSION */ 342 goto restart; 343 } 344 } else 345 q = &p->p_link; 346 } 347 splx(s); 348 } 349 350 /* 351 * Initialize the (doubly-linked) run queues 352 * to be empty. 353 */ 354 rqinit() 355 { 356 register int i; 357 358 for (i = 0; i < NQS; i++) 359 qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i]; 360 } 361 362 /* 363 * Set the process running; 364 * arrange for it to be swapped in if necessary. 365 */ 366 setrun(p) 367 register struct proc *p; 368 { 369 register int s; 370 371 s = splhigh(); 372 switch (p->p_stat) { 373 374 case 0: 375 case SWAIT: 376 case SRUN: 377 case SZOMB: 378 default: 379 panic("setrun"); 380 381 case SSTOP: 382 case SSLEEP: 383 unsleep(p); /* e.g. when sending signals */ 384 break; 385 386 case SIDL: 387 break; 388 } 389 p->p_stat = SRUN; 390 if (p->p_flag & SLOAD) 391 setrq(p); 392 splx(s); 393 if (p->p_slptime > 1) 394 updatepri(p); 395 if (p->p_pri < curpri) { 396 runrun++; 397 aston(); 398 } 399 if ((p->p_flag&SLOAD) == 0) { 400 if (runout != 0) { 401 runout = 0; 402 wakeup((caddr_t)&runout); 403 } 404 wantin++; 405 } 406 } 407 408 /* 409 * Set user priority. 410 * The rescheduling flag (runrun) 411 * is set if the priority is better 412 * than the currently running process. 413 */ 414 setpri(pp) 415 register struct proc *pp; 416 { 417 register int p; 418 419 p = (pp->p_cpu & 0377)/4; 420 p += PUSER + 2 * pp->p_nice; 421 if (pp->p_rssize > pp->p_maxrss && freemem < desfree) 422 p += 2*4; /* effectively, nice(4) */ 423 if (p > 127) 424 p = 127; 425 if (p < curpri) { 426 runrun++; 427 aston(); 428 } 429 pp->p_usrpri = p; 430 return (p); 431 } 432