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