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