4.3BSD - /usr/src/sys/sys/vm_sched.c

   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:  *	@(#)vm_sched.c	7.1 (Berkeley) 6/5/86
   7:  */
   8: 
   9: #include "param.h"
  10: #include "systm.h"
  11: #include "seg.h"
  12: #include "dir.h"
  13: #include "user.h"
  14: #include "proc.h"
  15: #include "text.h"
  16: #include "vm.h"
  17: #include "cmap.h"
  18: #include "kernel.h"
  19: 
  20: 
  21: 
  22: int maxslp = MAXSLP;
  23: int saferss = SAFERSS;
  24: 
  25: /*
  26:  * The following parameters control operation of the page replacement
  27:  * algorithm.  They are initialized to 0, and then computed at boot time
  28:  * based on the size of the system.  If they are patched non-zero in
  29:  * a loaded vmunix they are left alone and may thus be changed per system
  30:  * using adb on the loaded system.
  31:  */
  32: int maxpgio = 0;
  33: int minfree = 0;
  34: int desfree = 0;
  35: int lotsfree = 0;
  36: int slowscan = 0;
  37: int fastscan = 0;
  38: int klin = KLIN;
  39: int klseql = KLSEQL;
  40: int klsdist = KLSDIST;
  41: int kltxt = KLTXT;
  42: int klout = KLOUT;
  43: int multprog = -1;      /* so we don't count process 2 */
  44: 
  45: double  avenrun[3];     /* load average, of runnable procs */
  46: 
  47: /*
  48:  * The main loop of the scheduling (swapping) process.
  49:  *
  50:  * The basic idea is:
  51:  *	see if anyone wants to be swapped in;
  52:  *	swap out processes until there is room;
  53:  *	swap him in;
  54:  *	repeat.
  55:  * If the paging rate is too high, or the average free memory
  56:  * is very low, then we do not consider swapping anyone in,
  57:  * but rather look for someone to swap out.
  58:  *
  59:  * The runout flag is set whenever someone is swapped out.
  60:  * Sched sleeps on it awaiting work.
  61:  *
  62:  * Sched sleeps on runin whenever it cannot find enough
  63:  * core (by swapping out or otherwise) to fit the
  64:  * selected swapped process.  It is awakened when the
  65:  * core situation changes and in any case once per second.
  66:  *
  67:  * sched DOESN'T ACCOUNT FOR PAGE TABLE SIZE IN CALCULATIONS.
  68:  */
  69: 
  70: #define swappable(p) \
  71:     (((p)->p_flag&(SSYS|SLOCK|SULOCK|SLOAD|SPAGE|SKEEP|SWEXIT|SPHYSIO))==SLOAD)
  72: 
  73: /* insure non-zero */
  74: #define nz(x)   (x != 0 ? x : 1)
  75: 
  76: #define NBIG    4
  77: #define MAXNBIG 10
  78: int nbig = NBIG;
  79: 
  80: struct bigp {
  81:     struct  proc *bp_proc;
  82:     int bp_pri;
  83:     struct  bigp *bp_link;
  84: } bigp[MAXNBIG], bplist;
  85: 
  86: sched()
  87: {
  88:     register struct proc *rp, *p, *inp;
  89:     int outpri, inpri, rppri;
  90:     int sleeper, desperate, deservin, needs, divisor;
  91:     register struct bigp *bp, *nbp;
  92:     int biggot, gives;
  93: 
  94: loop:
  95:     wantin = 0;
  96:     deservin = 0;
  97:     sleeper = 0;
  98:     p = 0;
  99:     /*
 100: 	 * See if paging system is overloaded; if so swap someone out.
 101: 	 * Conditions for hard outswap are:
 102: 	 *	if need kernel map (mix it up).
 103: 	 * or
 104: 	 *	1. if there are at least 2 runnable processes (on the average)
 105: 	 * and	2. the paging rate is excessive or memory is now VERY low.
 106: 	 * and	3. the short (5-second) and longer (30-second) average
 107: 	 *	   memory is less than desirable.
 108: 	 */
 109:     if (kmapwnt ||
 110:         (avenrun[0] >= 2 && imax(avefree, avefree30) < desfree &&
 111:         (rate.v_pgin + rate.v_pgout > maxpgio || avefree < minfree))) {
 112:         desperate = 1;
 113:         goto hardswap;
 114:     }
 115:     desperate = 0;
 116:     /*
 117: 	 * Not desperate for core,
 118: 	 * look for someone who deserves to be brought in.
 119: 	 */
 120:     outpri = -20000;
 121:     for (rp = allproc; rp != NULL; rp = rp->p_nxt) switch(rp->p_stat) {
 122: 
 123:     case SRUN:
 124:         if ((rp->p_flag&SLOAD) == 0) {
 125:             rppri = rp->p_time -
 126:                 rp->p_swrss / nz((maxpgio/2) * (klin * CLSIZE)) +
 127:                 rp->p_slptime - (rp->p_nice-NZERO)*8;
 128:             if (rppri > outpri) {
 129:                 if (rp->p_poip)
 130:                     continue;
 131:                 if (rp->p_textp && rp->p_textp->x_poip)
 132:                     continue;
 133:                 p = rp;
 134:                 outpri = rppri;
 135:             }
 136:         }
 137:         continue;
 138: 
 139:     case SSLEEP:
 140:     case SSTOP:
 141:         if ((freemem < desfree || rp->p_rssize == 0) &&
 142:             rp->p_slptime > maxslp &&
 143:             (!rp->p_textp || (rp->p_textp->x_flag&XLOCK)==0) &&
 144:             swappable(rp)) {
 145:             /*
 146: 			 * Kick out deadwood.
 147: 			 */
 148:             rp->p_flag &= ~SLOAD;
 149:             (void) swapout(rp, rp->p_dsize, rp->p_ssize);
 150:         }
 151:         continue;
 152:     }
 153: 
 154:     /*
 155: 	 * No one wants in, so nothing to do.
 156: 	 */
 157:     if (outpri == -20000) {
 158:         (void) splhigh();
 159:         if (wantin) {
 160:             wantin = 0;
 161:             sleep((caddr_t)&lbolt, PSWP);
 162:         } else {
 163:             runout++;
 164:             sleep((caddr_t)&runout, PSWP);
 165:         }
 166:         (void) spl0();
 167:         goto loop;
 168:     }
 169:     /*
 170: 	 * Decide how deserving this guy is.  If he is deserving
 171: 	 * we will be willing to work harder to bring him in.
 172: 	 * Needs is an estimate of how much core he will need.
 173: 	 * If he has been out for a while, then we will
 174: 	 * bring him in with 1/2 the core he will need, otherwise
 175: 	 * we are conservative.
 176: 	 */
 177:     deservin = 0;
 178:     divisor = 1;
 179:     if (outpri > maxslp/2) {
 180:         deservin = 1;
 181:         divisor = 2;
 182:     }
 183:     needs = p->p_swrss;
 184:     if (p->p_textp && p->p_textp->x_ccount == 0)
 185:         needs += p->p_textp->x_swrss;
 186:     needs = imin(needs, lotsfree);
 187:     if (freemem - deficit > needs / divisor) {
 188:         deficit += needs;
 189:         if (swapin(p))
 190:             goto loop;
 191:         deficit -= imin(needs, deficit);
 192:     }
 193: 
 194: hardswap:
 195:     /*
 196: 	 * Need resources (kernel map or memory), swap someone out.
 197: 	 * Select the nbig largest jobs, then the oldest of these
 198: 	 * is ``most likely to get booted.''
 199: 	 */
 200:     inp = p;
 201:     sleeper = 0;
 202:     if (nbig > MAXNBIG)
 203:         nbig = MAXNBIG;
 204:     if (nbig < 1)
 205:         nbig = 1;
 206:     biggot = 0;
 207:     bplist.bp_link = 0;
 208:     for (rp = allproc; rp != NULL; rp = rp->p_nxt) {
 209:         if (!swappable(rp))
 210:             continue;
 211:         if (rp == inp)
 212:             continue;
 213:         if (rp->p_textp && rp->p_textp->x_flag&XLOCK)
 214:             continue;
 215:         if (rp->p_slptime > maxslp &&
 216:             (rp->p_stat==SSLEEP&&rp->p_pri>PZERO||rp->p_stat==SSTOP)) {
 217:             if (sleeper < rp->p_slptime) {
 218:                 p = rp;
 219:                 sleeper = rp->p_slptime;
 220:             }
 221:         } else if (!sleeper && (rp->p_stat==SRUN||rp->p_stat==SSLEEP)) {
 222:             rppri = rp->p_rssize;
 223:             if (rp->p_textp)
 224:                 rppri += rp->p_textp->x_rssize/rp->p_textp->x_ccount;
 225:             if (biggot < nbig)
 226:                 nbp = &bigp[biggot++];
 227:             else {
 228:                 nbp = bplist.bp_link;
 229:                 if (nbp->bp_pri > rppri)
 230:                     continue;
 231:                 bplist.bp_link = nbp->bp_link;
 232:             }
 233:             for (bp = &bplist; bp->bp_link; bp = bp->bp_link)
 234:                 if (rppri < bp->bp_link->bp_pri)
 235:                     break;
 236:             nbp->bp_link = bp->bp_link;
 237:             bp->bp_link = nbp;
 238:             nbp->bp_pri = rppri;
 239:             nbp->bp_proc = rp;
 240:         }
 241:     }
 242:     if (!sleeper) {
 243:         p = NULL;
 244:         inpri = -1000;
 245:         for (bp = bplist.bp_link; bp; bp = bp->bp_link) {
 246:             rp = bp->bp_proc;
 247:             rppri = rp->p_time+rp->p_nice-NZERO;
 248:             if (rppri >= inpri) {
 249:                 p = rp;
 250:                 inpri = rppri;
 251:             }
 252:         }
 253:     }
 254:     /*
 255: 	 * If we found a long-time sleeper, or we are desperate and
 256: 	 * found anyone to swap out, or if someone deserves to come
 257: 	 * in and we didn't find a sleeper, but found someone who
 258: 	 * has been in core for a reasonable length of time, then
 259: 	 * we kick the poor luser out.
 260: 	 */
 261:     if (sleeper || desperate && p || deservin && inpri > maxslp) {
 262:         (void) splhigh();
 263:         p->p_flag &= ~SLOAD;
 264:         if (p->p_stat == SRUN)
 265:             remrq(p);
 266:         (void) spl0();
 267:         if (desperate) {
 268:             /*
 269: 			 * Want to give this space to the rest of
 270: 			 * the processes in core so give them a chance
 271: 			 * by increasing the deficit.
 272: 			 */
 273:             gives = p->p_rssize;
 274:             if (p->p_textp)
 275:                 gives += p->p_textp->x_rssize / p->p_textp->x_ccount;
 276:             gives = imin(gives, lotsfree);
 277:             deficit += gives;
 278:         } else
 279:             gives = 0;  /* someone else taketh away */
 280:         if (swapout(p, p->p_dsize, p->p_ssize) == 0)
 281:             deficit -= imin(gives, deficit);
 282:         else
 283:             goto loop;
 284:     }
 285:     /*
 286: 	 * Want to swap someone in, but can't
 287: 	 * so wait on runin.
 288: 	 */
 289:     (void) splhigh();
 290:     runin++;
 291:     sleep((caddr_t)&runin, PSWP);
 292:     (void) spl0();
 293:     goto loop;
 294: }
 295: 
 296: vmmeter()
 297: {
 298:     register unsigned *cp, *rp, *sp;
 299: 
 300:     deficit -= imin(deficit,
 301:         imax(deficit / 10, ((klin * CLSIZE) / 2) * maxpgio / 2));
 302:     ave(avefree, freemem, 5);
 303:     ave(avefree30, freemem, 30);
 304:     /* v_pgin is maintained by clock.c */
 305:     cp = &cnt.v_first; rp = &rate.v_first; sp = &sum.v_first;
 306:     while (cp <= &cnt.v_last) {
 307:         ave(*rp, *cp, 5);
 308:         *sp += *cp;
 309:         *cp = 0;
 310:         rp++, cp++, sp++;
 311:     }
 312:     if (time.tv_sec % 5 == 0) {
 313:         vmtotal();
 314:         rate.v_swpin = cnt.v_swpin;
 315:         sum.v_swpin += cnt.v_swpin;
 316:         cnt.v_swpin = 0;
 317:         rate.v_swpout = cnt.v_swpout;
 318:         sum.v_swpout += cnt.v_swpout;
 319:         cnt.v_swpout = 0;
 320:     }
 321:     if (avefree < minfree && runout || proc[0].p_slptime > maxslp/2) {
 322:         runout = 0;
 323:         runin = 0;
 324:         wakeup((caddr_t)&runin);
 325:         wakeup((caddr_t)&runout);
 326:     }
 327: }
 328: 
 329: /*
 330:  * Schedule rate for paging.
 331:  * Rate is linear interpolation between
 332:  * slowscan with lotsfree and fastscan when out of memory.
 333:  */
 334: schedpaging()
 335: {
 336:     register int vavail;
 337: 
 338:     nscan = desscan = 0;
 339:     vavail = freemem - deficit;
 340:     if (vavail < 0)
 341:         vavail = 0;
 342:     if (freemem < lotsfree) {
 343:         desscan = (slowscan * vavail + fastscan * (lotsfree - vavail)) /
 344:             nz(lotsfree) / RATETOSCHEDPAGING;
 345:         wakeup((caddr_t)&proc[2]);
 346:     }
 347:     timeout(schedpaging, (caddr_t)0, hz / RATETOSCHEDPAGING);
 348: }
 349: 
 350: vmtotal()
 351: {
 352:     register struct proc *p;
 353:     register struct text *xp;
 354:     int nrun = 0;
 355: 
 356:     total.t_vmtxt = 0;
 357:     total.t_avmtxt = 0;
 358:     total.t_rmtxt = 0;
 359:     total.t_armtxt = 0;
 360:     for (xp = text; xp < textNTEXT; xp++)
 361:         if (xp->x_iptr) {
 362:             total.t_vmtxt += xp->x_size;
 363:             total.t_rmtxt += xp->x_rssize;
 364:             for (p = xp->x_caddr; p; p = p->p_xlink)
 365:             switch (p->p_stat) {
 366: 
 367:             case SSTOP:
 368:             case SSLEEP:
 369:                 if (p->p_slptime >= maxslp)
 370:                     continue;
 371:                 /* fall into... */
 372: 
 373:             case SRUN:
 374:             case SIDL:
 375:                 total.t_avmtxt += xp->x_size;
 376:                 total.t_armtxt += xp->x_rssize;
 377:                 goto next;
 378:             }
 379: next:
 380:             ;
 381:         }
 382:     total.t_vm = 0;
 383:     total.t_avm = 0;
 384:     total.t_rm = 0;
 385:     total.t_arm = 0;
 386:     total.t_rq = 0;
 387:     total.t_dw = 0;
 388:     total.t_pw = 0;
 389:     total.t_sl = 0;
 390:     total.t_sw = 0;
 391:     for (p = allproc; p != NULL; p = p->p_nxt) {
 392:         if (p->p_flag & SSYS)
 393:             continue;
 394:         if (p->p_stat) {
 395:             total.t_vm += p->p_dsize + p->p_ssize;
 396:             total.t_rm += p->p_rssize;
 397:             switch (p->p_stat) {
 398: 
 399:             case SSLEEP:
 400:             case SSTOP:
 401:                 if (p->p_pri <= PZERO)
 402:                     nrun++;
 403:                 if (p->p_flag & SPAGE)
 404:                     total.t_pw++;
 405:                 else if (p->p_flag & SLOAD) {
 406:                     if (p->p_pri <= PZERO)
 407:                         total.t_dw++;
 408:                     else if (p->p_slptime < maxslp)
 409:                         total.t_sl++;
 410:                 } else if (p->p_slptime < maxslp)
 411:                     total.t_sw++;
 412:                 if (p->p_slptime < maxslp)
 413:                     goto active;
 414:                 break;
 415: 
 416:             case SRUN:
 417:             case SIDL:
 418:                 nrun++;
 419:                 if (p->p_flag & SLOAD)
 420:                     total.t_rq++;
 421:                 else
 422:                     total.t_sw++;
 423: active:
 424:                 total.t_avm += p->p_dsize + p->p_ssize;
 425:                 total.t_arm += p->p_rssize;
 426:                 break;
 427:             }
 428:         }
 429:     }
 430:     total.t_vm += total.t_vmtxt;
 431:     total.t_avm += total.t_avmtxt;
 432:     total.t_rm += total.t_rmtxt;
 433:     total.t_arm += total.t_armtxt;
 434:     total.t_free = avefree;
 435:     loadav(avenrun, nrun);
 436: }
 437: 
 438: /*
 439:  * Constants for averages over 1, 5, and 15 minutes
 440:  * when sampling at 5 second intervals.
 441:  */
 442: double  cexp[3] = {
 443:     0.9200444146293232, /* exp(-1/12) */
 444:     0.9834714538216174, /* exp(-1/60) */
 445:     0.9944598480048967, /* exp(-1/180) */
 446: };
 447: 
 448: /*
 449:  * Compute a tenex style load average of a quantity on
 450:  * 1, 5 and 15 minute intervals.
 451:  */
 452: loadav(avg, n)
 453:     register double *avg;
 454:     int n;
 455: {
 456:     register int i;
 457: 
 458:     for (i = 0; i < 3; i++)
 459:         avg[i] = cexp[i] * avg[i] + n * (1.0 - cexp[i]);
 460: }

Defined functions

Defined variables

Defined struct's

Defined macros