1 /* kern_synch.c 4.20 82/09/06 */ 2 3 #include "../h/param.h" 4 #include "../h/systm.h" 5 #include "../h/dir.h" 6 #include "../h/user.h" 7 #include "../h/proc.h" 8 #include "../h/file.h" 9 #include "../h/inode.h" 10 #include "../h/vm.h" 11 #include "../h/pte.h" 12 #include "../h/inline.h" 13 #include "../h/mtpr.h" 14 #ifdef MUSH 15 #include "../h/quota.h" 16 #include "../h/share.h" 17 #endif 18 #include "../h/kernel.h" 19 #include "../h/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, 0, hz / 10); 30 } 31 32 /* 33 * The digital decay cpu usage priority assignment is scaled to run in 34 * time as expanded by the 1 minute load average. Each second we 35 * multiply the the previous cpu usage estimate by 36 * nrscale*avenrun[0] 37 * The following relates the load average to the period over which 38 * cpu usage is 90% forgotten: 39 * loadav 1 5 seconds 40 * loadav 5 24 seconds 41 * loadav 10 47 seconds 42 * loadav 20 93 seconds 43 * This is a great improvement on the previous algorithm which 44 * decayed the priorities by a constant, and decayed away all knowledge 45 * of previous activity in about 20 seconds. Under heavy load, 46 * the previous algorithm degenerated to round-robin with poor response 47 * time when there was a high load average. 48 */ 49 #undef ave 50 #define ave(a,b) ((int)(((int)(a*b))/(b+1))) 51 int nrscale = 2; 52 double avenrun[]; 53 54 /* 55 * Constant for decay filter for cpu usage field 56 * in process table (used by ps au). 57 */ 58 double ccpu = 0.95122942450071400909; /* exp(-1/20) */ 59 60 #ifdef MELB 61 /* 62 * Automatic niceness rate & max constants 63 */ 64 #define MAXNICE (8 + NZERO) /* maximum auto nice value */ 65 #define NFACT (40 * hz) /* nice++ every 40 secs cpu+sys time */ 66 #endif 67 68 /* 69 * Recompute process priorities, once a second 70 */ 71 schedcpu() 72 { 73 register struct proc *p; 74 register int s, a; 75 76 s = spl6(); time.tv_sec += lbolt / hz; lbolt %= hz; splx(s); 77 wakeup((caddr_t)&lbolt); 78 79 for (p = proc; p < procNPROC; p++) if (p->p_stat && p->p_stat!=SZOMB) { 80 #ifdef MUSH 81 /* 82 * Charge process for memory in use 83 */ 84 if (p->p_quota->q_uid) 85 p->p_quota->q_cost += 86 shconsts.sc_click * p->p_rssize; 87 #endif 88 if (p->p_time != 127) 89 p->p_time++; 90 if (timerisset(&p->p_seltimer) && 91 --p->p_seltimer.tv_sec <= 0) { 92 timerclear(&p->p_seltimer); 93 s = spl6(); 94 switch (p->p_stat) { 95 96 case SSLEEP: 97 setrun(p); 98 break; 99 100 case SSTOP: 101 unsleep(p); 102 break; 103 } 104 splx(s); 105 } 106 if (timerisset(&p->p_realtimer.it_value) && 107 itimerdecr(&p->p_realtimer, 1000000) == 0) 108 psignal(p, SIGALRM); 109 if (p->p_stat==SSLEEP || p->p_stat==SSTOP) 110 if (p->p_slptime != 127) 111 p->p_slptime++; 112 if (p->p_flag&SLOAD) 113 p->p_pctcpu = ccpu * p->p_pctcpu + 114 (1.0 - ccpu) * (p->p_cpticks/(float)hz); 115 p->p_cpticks = 0; 116 #ifdef MUSH 117 a = ave((p->p_cpu & 0377), avenrun[0]*nrscale) + 118 p->p_nice - NZERO + p->p_quota->q_nice; 119 #else 120 a = ave((p->p_cpu & 0377), avenrun[0]*nrscale) + 121 p->p_nice - NZERO; 122 #endif 123 if (a < 0) 124 a = 0; 125 if (a > 255) 126 a = 255; 127 p->p_cpu = a; 128 (void) setpri(p); 129 s = spl6(); /* prevent state changes */ 130 if (p->p_pri >= PUSER) { 131 if ((p != u.u_procp || noproc) && 132 p->p_stat == SRUN && 133 (p->p_flag & SLOAD) && 134 p->p_pri != p->p_usrpri) { 135 remrq(p); 136 p->p_pri = p->p_usrpri; 137 setrq(p); 138 } else 139 p->p_pri = p->p_usrpri; 140 } 141 splx(s); 142 } 143 vmmeter(); 144 if (runin!=0) { 145 runin = 0; 146 wakeup((caddr_t)&runin); 147 } 148 if (bclnlist != NULL) 149 wakeup((caddr_t)&proc[2]); 150 timeout(schedcpu, 0, hz); 151 } 152 153 #define SQSIZE 0100 /* Must be power of 2 */ 154 #define HASH(x) (( (int) x >> 5) & (SQSIZE-1)) 155 struct proc *slpque[SQSIZE]; 156 157 /* 158 * Give up the processor till a wakeup occurs 159 * on chan, at which time the process 160 * enters the scheduling queue at priority pri. 161 * The most important effect of pri is that when 162 * pri<=PZERO a signal cannot disturb the sleep; 163 * if pri>PZERO signals will be processed. 164 * Callers of this routine must be prepared for 165 * premature return, and check that the reason for 166 * sleeping has gone away. 167 */ 168 sleep(chan, pri) 169 caddr_t chan; 170 int pri; 171 { 172 register struct proc *rp, **hp; 173 register s; 174 175 rp = u.u_procp; 176 s = spl6(); 177 if (chan==0 || rp->p_stat != SRUN || rp->p_rlink) 178 panic("sleep"); 179 rp->p_wchan = chan; 180 rp->p_slptime = 0; 181 rp->p_pri = pri; 182 hp = &slpque[HASH(chan)]; 183 rp->p_link = *hp; 184 *hp = rp; 185 if (pri > PZERO) { 186 if (ISSIG(rp)) { 187 if (rp->p_wchan) 188 unsleep(rp); 189 rp->p_stat = SRUN; 190 (void) spl0(); 191 goto psig; 192 } 193 if (rp->p_wchan == 0) 194 goto out; 195 rp->p_stat = SSLEEP; 196 (void) spl0(); 197 u.u_ru.ru_nvcsw++; 198 swtch(); 199 if (ISSIG(rp)) 200 goto psig; 201 } else { 202 rp->p_stat = SSLEEP; 203 (void) spl0(); 204 u.u_ru.ru_nvcsw++; 205 swtch(); 206 } 207 out: 208 splx(s); 209 return; 210 211 /* 212 * If priority was low (>PZERO) and 213 * there has been a signal, execute non-local goto through 214 * u.u_qsav, aborting the system call in progress (see trap.c) 215 * (or finishing a tsleep, see below) 216 */ 217 psig: 218 longjmp(u.u_qsav); 219 /*NOTREACHED*/ 220 } 221 222 /* 223 * Sleep on chan at pri for at most a specified amount of time. 224 * Return (TS_OK,TS_TIME,TS_SIG) on (normal,timeout,signal) condition. 225 */ 226 tsleep(chan, pri, tvp) 227 caddr_t chan; 228 int pri; 229 struct timeval *tvp; 230 { 231 register struct proc *p = u.u_procp; 232 int s, rval; 233 234 s = spl7(); 235 if (timercmp(tvp, &p->p_realtimer.it_value, >)) { 236 /* alarm will occur first! */ 237 sleep(chan, pri); 238 rval = TS_OK; /* almost NOTREACHED modulo fuzz */ 239 } else { 240 label_t lqsav; 241 242 bcopy((caddr_t)u.u_qsav, (caddr_t)lqsav, sizeof (label_t)); 243 p->p_seltimer = *tvp; 244 if (setjmp(u.u_qsav)) 245 rval = TS_SIG; 246 else { 247 sleep(chan, pri); 248 rval = TS_OK; 249 } 250 timerclear(&p->p_seltimer); 251 bcopy((caddr_t)lqsav, (caddr_t)u.u_qsav, sizeof (label_t)); 252 } 253 splx(s); 254 return (rval); 255 } 256 257 /* 258 * Remove a process from its wait queue 259 */ 260 unsleep(p) 261 register struct proc *p; 262 { 263 register struct proc **hp; 264 register s; 265 266 s = spl6(); 267 if (p->p_wchan) { 268 hp = &slpque[HASH(p->p_wchan)]; 269 while (*hp != p) 270 hp = &(*hp)->p_link; 271 *hp = p->p_link; 272 p->p_wchan = 0; 273 } 274 splx(s); 275 } 276 277 /* 278 * Wake up all processes sleeping on chan. 279 */ 280 wakeup(chan) 281 register caddr_t chan; 282 { 283 register struct proc *p, **q, **h; 284 int s; 285 286 s = spl6(); 287 h = &slpque[HASH(chan)]; 288 restart: 289 for (q = h; p = *q; ) { 290 if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP) 291 panic("wakeup"); 292 if (p->p_wchan==chan) { 293 p->p_wchan = 0; 294 *q = p->p_link; 295 p->p_slptime = 0; 296 if (p->p_stat == SSLEEP) { 297 /* OPTIMIZED INLINE EXPANSION OF setrun(p) */ 298 p->p_stat = SRUN; 299 if (p->p_flag & SLOAD) 300 setrq(p); 301 if (p->p_pri < curpri) { 302 runrun++; 303 aston(); 304 } 305 if ((p->p_flag&SLOAD) == 0) { 306 if (runout != 0) { 307 runout = 0; 308 wakeup((caddr_t)&runout); 309 } 310 wantin++; 311 } 312 /* END INLINE EXPANSION */ 313 goto restart; 314 } 315 } else 316 q = &p->p_link; 317 } 318 splx(s); 319 } 320 321 /* 322 * Initialize the (doubly-linked) run queues 323 * to be empty. 324 */ 325 rqinit() 326 { 327 register int i; 328 329 for (i = 0; i < NQS; i++) 330 qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i]; 331 } 332 333 /* 334 * Set the process running; 335 * arrange for it to be swapped in if necessary. 336 */ 337 setrun(p) 338 register struct proc *p; 339 { 340 register int s; 341 342 s = spl6(); 343 switch (p->p_stat) { 344 345 case 0: 346 case SWAIT: 347 case SRUN: 348 case SZOMB: 349 default: 350 panic("setrun"); 351 352 case SSTOP: 353 case SSLEEP: 354 unsleep(p); /* e.g. when sending signals */ 355 break; 356 357 case SIDL: 358 break; 359 } 360 p->p_stat = SRUN; 361 if (p->p_flag & SLOAD) 362 setrq(p); 363 splx(s); 364 if (p->p_pri < curpri) { 365 runrun++; 366 aston(); 367 } 368 if ((p->p_flag&SLOAD) == 0) { 369 if (runout != 0) { 370 runout = 0; 371 wakeup((caddr_t)&runout); 372 } 373 wantin++; 374 } 375 } 376 377 /* 378 * Set user priority. 379 * The rescheduling flag (runrun) 380 * is set if the priority is better 381 * than the currently running process. 382 */ 383 setpri(pp) 384 register struct proc *pp; 385 { 386 register int p; 387 388 p = (pp->p_cpu & 0377)/4; 389 p += PUSER + 2*(pp->p_nice - NZERO); 390 if (pp->p_rssize > pp->p_maxrss && freemem < desfree) 391 p += 2*4; /* effectively, nice(4) */ 392 if (p > 127) 393 p = 127; 394 if (p < curpri) { 395 runrun++; 396 aston(); 397 } 398 pp->p_usrpri = p; 399 return (p); 400 } 401