![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to vm_sched.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / sys / kern|
Return to vm_sched.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / sys / kern |
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.