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