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