2.11BSD#431 - /usr/src/sys/sys/vm_sched.c

   1: /*
   2:  * Copyright (c) 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:  *	@(#)vm_sched.c	1.2 (2.11BSD) 1999/9/10
   7:  */
   8: 
   9: #include "param.h"
  10: #include "user.h"
  11: #include "proc.h"
  12: #include "text.h"
  13: #include "vm.h"
  14: #include "kernel.h"
  15: #include "systm.h"
  16: 
  17: #define MINFINITY   -32767      /* minus infinity */
  18: 
  19: int maxslp = MAXSLP;
  20: 
  21: /*
  22:  * The main loop of the scheduling (swapping) process.
  23:  * The basic idea is:
  24:  *	see if anyone wants to be swapped in
  25:  *	swap out processes until there is room
  26:  *	swap him in
  27:  *	repeat
  28:  * The runout flag is set whenever someone is swapped out.  Sched sleeps on
  29:  * it awaiting work.  Sched sleeps on runin whenever it cannot find enough
  30:  * core (by swapping out or otherwise) to fit the selected swapped process.
  31:  * It is awakened when the core situation changes and in any case once per
  32:  * second.
  33:  */
  34: sched()
  35: {
  36:     register struct proc *rp;
  37:     struct proc *p;
  38:     int inage, maxsize, outpri;
  39: 
  40:     /* Find user to swap in; of users ready, select one out longest. */
  41:     for (;;) {
  42:     (void)_splhigh();
  43:     {
  44:     register int l_outpri, rppri;
  45: 
  46:     l_outpri = -20000;
  47:     for (rp = allproc; rp; rp = rp->p_nxt) {
  48:         if (rp->p_stat != SRUN || rp->p_flag & SLOAD)
  49:             continue;
  50:         rppri = rp->p_time - rp->p_nice * 8;
  51: 
  52:         /*
  53: 		 * Always bring in parents ending a vfork,
  54: 		 * to avoid deadlock
  55: 		 */
  56:         if (rppri > l_outpri || rp->p_flag & SVFPRNT) {
  57:             p = rp;
  58:             l_outpri = rppri;
  59:             if (rp->p_flag & SVFPRNT)
  60:                 break;
  61:         }
  62:     }
  63: 
  64:     /* If there is no one there, wait. */
  65:     if (l_outpri == -20000) {
  66:         ++runout;
  67:         sleep((caddr_t)&runout, PSWP);
  68:         continue;
  69:     }
  70:     outpri = l_outpri;
  71:     }
  72: 
  73:     (void)_spl0();
  74: 
  75:     /* See if there is core for that process, if so, swap it in. */
  76:     if (swapin(p))
  77:         continue;
  78: 
  79:     /*
  80: 	 * None found.  Look around for core: 1) kick out dead wood
  81: 	 * (processes asleep longer than maxslp+10); or 2) select out
  82: 	 * of the processes sleeping interruptibly the process with
  83: 	 * maximum f(size, slptime); or 3) if none, select the oldest.
  84: 	 * If we can find someone to swap out we try to swap someone
  85: 	 * else (hopefully) in, possibly causing someone else to get
  86: 	 * swapped out.
  87: 	 *
  88: 	 * f(size, slptime) = size + (slptime - maxslp) * 16
  89: 	 *
  90: 	 * This weighting is designed to penalize linearly for size
  91: 	 * and excessive slptime, but to reward processes which are
  92: 	 * executing or have executed recently.
  93: 	 */
  94:     {
  95:     register int l_maxsize;
  96: 
  97:     (void)_splhigh();
  98:     l_maxsize = MINFINITY;
  99:     inage = -1;
 100:     for (rp = allproc; rp != NULL; rp = rp->p_nxt) {
 101:         if (rp->p_stat == SZOMB ||
 102:             (rp->p_flag & (SSYS|SLOCK|SULOCK|SLOAD)) != SLOAD)
 103:             continue;
 104:         if (rp->p_textp && rp->p_textp->x_flag & XLOCK)
 105:             continue;
 106:         if (rp->p_stat == SSLEEP &&
 107:             (rp->p_flag & P_SINTR) || rp->p_stat == SSTOP) {
 108:             register int size;
 109: 
 110:             if (rp->p_slptime > maxslp+10) {
 111:                 p = rp;
 112:                 l_maxsize = 1;
 113:                 break;
 114:             }
 115:             size = rp->p_dsize + rp->p_ssize
 116:                 + (rp->p_slptime - maxslp << 4);
 117:             if (l_maxsize < size) {
 118:                 p = rp;
 119:                 l_maxsize = size;
 120:             }
 121:         }
 122:         else if (l_maxsize == MINFINITY &&
 123:             (rp->p_stat == SRUN || rp->p_stat == SSLEEP)) {
 124:             register int rppri;
 125: 
 126:             rppri = rp->p_time + rp->p_nice;
 127:             if (rppri > inage) {
 128:                 p = rp;
 129:                 inage = rppri;
 130:             }
 131:         }
 132:     }
 133:     maxsize = l_maxsize;
 134:     }
 135: 
 136:     (void)_spl0();
 137:     noop();
 138:     (void)_splhigh();
 139:     /*
 140: 	 * Swap found user out if sleeping interruptibly, or if he has spent at
 141: 	 * least 1 second in core and the swapped-out process has spent at
 142: 	 * least 2 seconds out.  Otherwise wait a bit and try again.
 143: 	 */
 144:     if (maxsize != MINFINITY || outpri >= 2 && inage >= 1) {
 145:         p->p_flag &= ~SLOAD;
 146:         if (p->p_stat == SRUN)
 147:             remrq(p);
 148:         (void)_spl0();
 149:         swapout(p, X_FREECORE, X_OLDSIZE, X_OLDSIZE);
 150:     }
 151:     else {
 152:         ++runin;
 153:         sleep((caddr_t)&runin, PSWP);
 154:     }
 155:     }
 156: }
 157: 
 158: /*
 159:  * Count up various things once a second
 160:  */
 161: vmmeter()
 162: {
 163: #ifdef UCB_METER
 164:     register u_short *cp, *rp;
 165:     register long *sp;
 166: 
 167:     ave(avefree, freemem, 5);
 168:     ave(avefree30, freemem, 30);
 169:     cp = &cnt.v_first; rp = &rate.v_first; sp = &sum.v_first;
 170:     while (cp <= &cnt.v_last) {
 171:         ave(*rp, *cp, 5);
 172:         *sp += *cp;
 173:         *cp = 0;
 174:         rp++, cp++, sp++;
 175:     }
 176: #endif
 177: 
 178:     if (time.tv_sec % 5 == 0) {
 179:         vmtotal();
 180: #ifdef UCB_METER
 181:         rate.v_swpin = cnt.v_swpin;
 182:         sum.v_swpin += cnt.v_swpin;
 183:         cnt.v_swpin = 0;
 184:         rate.v_swpout = cnt.v_swpout;
 185:         sum.v_swpout += cnt.v_swpout;
 186:         cnt.v_swpout = 0;
 187: #endif
 188:     }
 189: }
 190: 
 191: vmtotal()
 192: {
 193:     register struct proc *p;
 194:     register nrun = 0;
 195: #ifdef UCB_METER
 196:     char textcounted[100];
 197: 
 198:     total.t_vmtxt = 0;
 199:     total.t_avmtxt = 0;
 200:     total.t_rmtxt = 0;
 201:     total.t_armtxt = 0;
 202: {
 203:     register struct text *xp;
 204: 
 205:     for (xp = text; xp < textNTEXT; xp++)
 206:         if (xp->x_iptr) {
 207:             total.t_vmtxt += xp->x_size;
 208:             if (xp->x_ccount)
 209:                 total.t_rmtxt += xp->x_size;
 210:         }
 211: }
 212:     total.t_vm = 0;
 213:     total.t_avm = 0;
 214:     total.t_rm = 0;
 215:     total.t_arm = 0;
 216:     total.t_rq = 0;
 217:     total.t_dw = 0;
 218:     total.t_sl = 0;
 219:     total.t_sw = 0;
 220:     bzero(textcounted, ntext * sizeof(char));
 221: #endif
 222:     for (p = allproc; p != NULL; p = p->p_nxt) {
 223:         if (p->p_flag & SSYS)
 224:             continue;
 225:         if (p->p_stat) {
 226: #ifdef UCB_METER
 227:             if (p->p_stat != SZOMB) {
 228:                 total.t_vm += p->p_dsize + p->p_ssize + USIZE;
 229:                 if (p->p_flag & SLOAD)
 230:                     total.t_rm += p->p_dsize + p->p_ssize
 231:                         + USIZE;
 232:             }
 233: #endif
 234:             switch (p->p_stat) {
 235: 
 236:             case SSLEEP:
 237:             case SSTOP:
 238:                 if (!(p->p_flag & P_SINTR) && p->p_stat == SSLEEP)
 239:                     nrun++;
 240: #ifdef UCB_METER
 241:                 if (p->p_flag & SLOAD) {
 242:                     if  (!(p->p_flag & P_SINTR))
 243:                         total.t_dw++;
 244:                     else if (p->p_slptime < maxslp)
 245:                         total.t_sl++;
 246:                 } else if (p->p_slptime < maxslp)
 247:                     total.t_sw++;
 248:                 if (p->p_slptime < maxslp)
 249:                     goto active;
 250: #endif
 251:                 break;
 252: 
 253:             case SRUN:
 254:             case SIDL:
 255:                 nrun++;
 256: #ifdef UCB_METER
 257:                 if (p->p_flag & SLOAD)
 258:                     total.t_rq++;
 259:                 else
 260:                     total.t_sw++;
 261: active:
 262:                 total.t_avm += p->p_dsize + p->p_ssize + USIZE;
 263:                 if (p->p_flag & SLOAD)
 264:                     total.t_arm += p->p_dsize + p->p_ssize
 265:                         + USIZE;
 266:                 if (p->p_textp) switch (p->p_stat) {
 267: 
 268:                 case SSTOP:
 269:                 case SSLEEP:
 270:                     if (p->p_slptime >= maxslp)
 271:                         break;
 272:                     /* fall into... */
 273: 
 274:                 case SRUN:
 275:                 case SIDL:
 276:                 {   register int nt;
 277: 
 278:                     total.t_avmtxt += p->p_textp->x_size;
 279:                     nt = p->p_textp - text;
 280:                     if (!textcounted[nt]) {
 281:                         textcounted[nt] = 1;
 282:                         if (p->p_textp->x_ccount)
 283:                             total.t_armtxt +=
 284:                                 p->p_textp->x_size;
 285:                     }
 286:                 }
 287:                 }
 288: #endif
 289:                 break;
 290:             }
 291:         }
 292:     }
 293: #ifdef UCB_METER
 294:     total.t_vm += total.t_vmtxt;
 295:     total.t_avm += total.t_avmtxt;
 296:     total.t_rm += total.t_rmtxt;
 297:     total.t_arm += total.t_armtxt;
 298:     total.t_free = avefree;
 299: #endif
 300:     loadav(avenrun, nrun);
 301: }
 302: 
 303: /*
 304:  * Compute Tenex style load average.  This code is adapted from similar code
 305:  * by Bill Joy on the Vax system.  The major change is that we avoid floating
 306:  * point since not all pdp-11's have it.  This makes the code quite hard to
 307:  * read - it was derived with some algebra.
 308:  *
 309:  * "floating point" numbers here are stored in a 16 bit short, with 8 bits on
 310:  * each side of the decimal point.  Some partial products will have 16 bits to
 311:  * the right.
 312:  *
 313:  * The Vax algorithm is:
 314:  *
 315:  * /*
 316:  *  * Constants for averages over 1, 5, and 15 minutes
 317:  *  * when sampling at 5 second intervals.
 318:  *  * /
 319:  * double	cexp[3] = {
 320:  * 	0.9200444146293232,	/* exp(-1/12) * /
 321:  * 	0.9834714538216174,	/* exp(-1/60) * /
 322:  * 	0.9944598480048967,	/* exp(-1/180) * /
 323:  * };
 324:  *
 325:  * /*
 326:  *  * Compute a tenex style load average of a quantity on
 327:  *  * 1, 5 and 15 minute intervals.
 328:  *  * /
 329:  * loadav(avg, n)
 330:  * 	register double *avg;
 331:  * 	int n;
 332:  * {
 333:  * 	register int i;
 334:  *
 335:  * 	for (i = 0; i < 3; i++)
 336:  * 		avg[i] = cexp[i] * avg[i] + n * (1.0 - cexp[i]);
 337:  * }
 338:  */
 339: 
 340: long cexp[3] = {
 341:     0353,   /* 256 * exp(-1/12)  */
 342:     0373,   /* 256 * exp(-1/60)  */
 343:     0376,   /* 256 * exp(-1/180) */
 344: };
 345: 
 346: loadav(avg, n)
 347:     register short  *avg;
 348:     register int    n;
 349: {
 350:     register int    i;
 351: 
 352:     for (i = 0; i < 3; i++)
 353:         avg[i] = (cexp[i] * (avg[i]-(n<<8)) + (((long)n)<<16)) >> 8;
 354: }

Defined functions

Defined variables

Defined macros