Return to vm_sched.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / sys / kern

Annotation of 43BSDReno/sys/kern/vm_sched.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.