X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/e5df4be8ac82c3497cf3ede28c37df163c7c087c..6a79e262ebff67defcc88ba77f6eea5894a6b695:/usr/src/sys/kern/kern_synch.c

diff --git a/usr/src/sys/kern/kern_synch.c b/usr/src/sys/kern/kern_synch.c
index 2b1ea134e2..d6110aa59a 100644
--- a/usr/src/sys/kern/kern_synch.c
+++ b/usr/src/sys/kern/kern_synch.c
@@ -1,20 +1,191 @@
-/*	kern_synch.c	3.9	%H%	*/
+/*
+ * Copyright (c) 1982, 1986 Regents of the University of California.
+ * All rights reserved.  The Berkeley software License Agreement
+ * specifies the terms and conditions for redistribution.
+ *
+ *	@(#)kern_synch.c	7.6 (Berkeley) %G%
+ */
+
+#include "../machine/pte.h"
+#include "../machine/psl.h"
+#include "../machine/mtpr.h"
+
+#include "param.h"
+#include "systm.h"
+#include "dir.h"
+#include "user.h"
+#include "proc.h"
+#include "vm.h"
+#include "kernel.h"
+#include "buf.h"
+
+/*
+ * Force switch among equal priority processes every 100ms.
+ */
+roundrobin()
+{
+
+	runrun++;
+	aston();
+	timeout(roundrobin, (caddr_t)0, hz / 10);
+}
+
+/*
+ * constants for digital decay and forget
+ *	90% of (p_cpu) usage in 5*loadav time
+ *	95% of (p_pctcpu) usage in 60 seconds (load insensitive)
+ *          Note that, as ps(1) mentions, this can let percentages
+ *          total over 100% (I've seen 137.9% for 3 processes).
+ *
+ * Note that hardclock updates p_cpu and p_cpticks independently.
+ *
+ * We wish to decay away 90% of p_cpu in (5 * loadavg) seconds.
+ * That is, the system wants to compute a value of decay such
+ * that the following for loop:
+ * 	for (i = 0; i < (5 * loadavg); i++)
+ * 		p_cpu *= decay;
+ * will compute
+ * 	p_cpu *= 0.1;
+ * for all values of loadavg:
+ *
+ * Mathematically this loop can be expressed by saying:
+ * 	decay ** (5 * loadavg) ~= .1
+ *
+ * The system computes decay as:
+ * 	decay = (2 * loadavg) / (2 * loadavg + 1)
+ *
+ * We wish to prove that the system's computation of decay
+ * will always fulfill the equation:
+ * 	decay ** (5 * loadavg) ~= .1
+ *
+ * If we compute b as:
+ * 	b = 2 * loadavg
+ * then
+ * 	decay = b / (b + 1)
+ *
+ * We now need to prove two things:
+ *	1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
+ *	2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
+ *	
+ * Facts:
+ *         For x close to zero, exp(x) =~ 1 + x, since
+ *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
+ *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
+ *         For x close to zero, ln(1+x) =~ x, since
+ *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
+ *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
+ *         ln(.1) =~ -2.30
+ *
+ * Proof of (1):
+ *    Solve (factor)**(power) =~ .1 given power (5*loadav):
+ *	solving for factor,
+ *      ln(factor) =~ (-2.30/5*loadav), or
+ *      factor =~ exp(-1/((5/2.30)*loadav) =~ exp(-1/(2*loadav)) =
+ *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
+ *
+ * Proof of (2):
+ *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
+ *	solving for power,
+ *      power*ln(b/(b+1)) =~ -2.30, or
+ *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
+ *
+ * Actual power values for the implemented algorithm are as follows:
+ *      loadav: 1       2       3       4
+ *      power:  5.68    10.32   14.94   19.55
+ */
+#define	filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1))
 
-#include "../h/param.h"
-#include "../h/systm.h"
-#include "../h/dir.h"
-#include "../h/user.h"
-#include "../h/proc.h"
-#include "../h/file.h"
-#include "../h/inode.h"
-#include "../h/vm.h"
-#include "../h/pte.h"
-#include "../h/inline.h"
+double	ccpu = 0.95122942450071400909;		/* exp(-1/20) */
 
+/*
+ * Recompute process priorities, once a second
+ */
+schedcpu()
+{
+	register double ccpu1 = (1.0 - ccpu) / (double)hz;
+	register struct proc *p;
+	register int s, a;
+	float scale = filter(avenrun[0]);
+
+	wakeup((caddr_t)&lbolt);
+	for (p = allproc; p != NULL; p = p->p_nxt) {
+		if (p->p_time != 127)
+			p->p_time++;
+		if (p->p_stat==SSLEEP || p->p_stat==SSTOP)
+			if (p->p_slptime != 127)
+				p->p_slptime++;
+		/*
+		 * If the process has slept the entire second,
+		 * stop recalculating its priority until it wakes up.
+		 */
+		if (p->p_slptime > 1) {
+			p->p_pctcpu *= ccpu;
+			continue;
+		}
+		/*
+		 * p_pctcpu is only for ps.
+		 */
+		p->p_pctcpu = ccpu * p->p_pctcpu + ccpu1 * p->p_cpticks;
+		p->p_cpticks = 0;
+		a = (int) (scale * (p->p_cpu & 0377)) + p->p_nice;
+		if (a < 0)
+			a = 0;
+		if (a > 255)
+			a = 255;
+		p->p_cpu = a;
+		(void) setpri(p);
+		s = splhigh();	/* prevent state changes */
+		if (p->p_pri >= PUSER) {
+#define	PPQ	(128 / NQS)
+			if ((p != u.u_procp || noproc) &&
+			    p->p_stat == SRUN &&
+			    (p->p_flag & SLOAD) &&
+			    (p->p_pri / PPQ) != (p->p_usrpri / PPQ)) {
+				remrq(p);
+				p->p_pri = p->p_usrpri;
+				setrq(p);
+			} else
+				p->p_pri = p->p_usrpri;
+		}
+		splx(s);
+	}
+	vmmeter();
+	if (runin!=0) {
+		runin = 0;
+		wakeup((caddr_t)&runin);
+	}
+	if (bclnlist != NULL)
+		wakeup((caddr_t)&proc[2]);
+	timeout(schedcpu, (caddr_t)0, hz);
+}
+
+/*
+ * Recalculate the priority of a process after it has slept for a while.
+ */
+updatepri(p)
+	register struct proc *p;
+{
+	register int a = p->p_cpu & 0377;
+	float scale = filter(avenrun[0]);
+
+	p->p_slptime--;		/* the first time was done in schedcpu */
+	while (a && --p->p_slptime)
+		a = (int) (scale * a) /* + p->p_nice */;
+	p->p_slptime = 0;
+	if (a < 0)
+		a = 0;
+	if (a > 255)
+		a = 255;
+	p->p_cpu = a;
+	(void) setpri(p);
+}
 
 #define SQSIZE 0100	/* Must be power of 2 */
 #define HASH(x)	(( (int) x >> 5) & (SQSIZE-1))
-struct proc *slpque[SQSIZE];
+struct slpque {
+	struct proc *sq_head;
+	struct proc **sq_tailp;
+} slpque[SQSIZE];
 
 /*
  * Give up the processor till a wakeup occurs
@@ -28,23 +199,47 @@ struct proc *slpque[SQSIZE];
  * sleeping has gone away.
  */
 sleep(chan, pri)
-caddr_t chan;
+	caddr_t chan;
+	int pri;
 {
-	register struct proc *rp, **hp;
-	register s, h;
+	register struct proc *rp;
+	register struct slpque *qp;
+	register s;
+	extern int cold;
 
 	rp = u.u_procp;
-	s = spl6();
+	s = splhigh();
+	if (cold || panicstr) {
+		/*
+		 * After a panic, or during autoconfiguration,
+		 * just give interrupts a chance, then just return;
+		 * don't run any other procs or panic below,
+		 * in case this is the idle process and already asleep.
+		 * The splnet should be spl0 if the network was being used
+		 * by the filesystem, but for now avoid network interrupts
+		 * that might cause another panic.
+		 */
+		(void) splnet();
+		splx(s);
+		return;
+	}
 	if (chan==0 || rp->p_stat != SRUN || rp->p_rlink)
 		panic("sleep");
 	rp->p_wchan = chan;
 	rp->p_slptime = 0;
 	rp->p_pri = pri;
-	hp = &slpque[HASH(chan)];
-	rp->p_link = *hp;
-	*hp = rp;
-	if(pri > PZERO) {
-		if(ISSIG(rp)) {
+	qp = &slpque[HASH(chan)];
+	if (qp->sq_head == 0)
+		qp->sq_head = rp;
+	else
+		*qp->sq_tailp = rp;
+	*(qp->sq_tailp = &rp->p_link) = 0;
+	if (pri > PZERO) {
+		/*
+		 * If we stop in issig(), wakeup may already have happened
+		 * when we return (rp->p_wchan will then be 0).
+		 */
+		if (ISSIG(rp)) {
 			if (rp->p_wchan)
 				unsleep(rp);
 			rp->p_stat = SRUN;
@@ -55,94 +250,49 @@ caddr_t chan;
 			goto out;
 		rp->p_stat = SSLEEP;
 		(void) spl0();
-		if(runin != 0) {
-			runin = 0;
-			wakeup((caddr_t)&runin);
-		}
+		u.u_ru.ru_nvcsw++;
 		swtch();
-		if(ISSIG(rp))
+		if (ISSIG(rp))
 			goto psig;
 	} else {
+		rp->p_stat = SSLEEP;
 		(void) spl0();
+		u.u_ru.ru_nvcsw++;
 		swtch();
 	}
+	curpri = rp->p_usrpri;
 out:
 	splx(s);
 	return;
 
 	/*
 	 * If priority was low (>PZERO) and
-	 * there has been a signal,
-	 * execute non-local goto to
-	 * the qsav location.
-	 * (see trap1/trap.c)
+	 * there has been a signal, execute non-local goto through
+	 * u.u_qsave, aborting the system call in progress (see trap.c)
 	 */
 psig:
-	longjmp(u.u_qsav);
+	longjmp(&u.u_qsave);
 	/*NOTREACHED*/
 }
 
-/*
- * Sleep on chan at pri.
- * Return in no more than the indicated number of seconds.
- * (If seconds==0, no timeout implied)
- * Return	TS_OK if chan was awakened normally
- *		TS_TIME if timeout occurred
- *		TS_SIG if asynchronous signal occurred
- */
-tsleep(chan, pri, seconds)
-caddr_t chan;
-{
-	label_t lqsav;
-	register struct proc *pp;
-	register sec, n, rval;
-
-	pp = u.u_procp;
-	n = spl7();
-	sec = 0;
-	rval = 0;
-	if (pp->p_clktim && pp->p_clktim<seconds)
-		seconds = 0;
-	if (seconds) {
-		pp->p_flag |= STIMO;
-		sec = pp->p_clktim-seconds;
-		pp->p_clktim = seconds;
-	}
-	bcopy((caddr_t)u.u_qsav, (caddr_t)lqsav, sizeof (label_t));
-	if (setjmp(u.u_qsav))
-		rval = TS_SIG;
-	else {
-		sleep(chan, pri);
-		if ((pp->p_flag&STIMO)==0 && seconds)
-			rval = TS_TIME;
-		else
-			rval = TS_OK;
-	}
-	pp->p_flag &= ~STIMO;
-	bcopy((caddr_t)lqsav, (caddr_t)u.u_qsav, sizeof (label_t));
-	if (sec > 0)
-		pp->p_clktim += sec;
-	else
-		pp->p_clktim = 0;
-	splx(n);
-	return(rval);
-}
-
 /*
  * Remove a process from its wait queue
  */
 unsleep(p)
-register struct proc *p;
+	register struct proc *p;
 {
+	register struct slpque *qp;
 	register struct proc **hp;
-	register s;
+	int s;
 
-	s = spl6();
+	s = splhigh();
 	if (p->p_wchan) {
-		hp = &slpque[HASH(p->p_wchan)];
+		hp = &(qp = &slpque[HASH(p->p_wchan)])->sq_head;
 		while (*hp != p)
 			hp = &(*hp)->p_link;
 		*hp = p->p_link;
+		if (qp->sq_tailp == &p->p_link)
+			qp->sq_tailp = hp;
 		p->p_wchan = 0;
 	}
 	splx(s);
@@ -152,37 +302,42 @@ register struct proc *p;
  * Wake up all processes sleeping on chan.
  */
 wakeup(chan)
-register caddr_t chan;
+	register caddr_t chan;
 {
-	register struct proc *p, **q, **h;
+	register struct slpque *qp;
+	register struct proc *p, **q;
 	int s;
 
-	s = spl6();
-	h = &slpque[HASH(chan)];
+	s = splhigh();
+	qp = &slpque[HASH(chan)];
 restart:
-	for (q = h; p = *q; ) {
+	for (q = &qp->sq_head; p = *q; ) {
 		if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP)
 			panic("wakeup");
-		if (p->p_wchan==chan && p->p_stat!=SZOMB) {
+		if (p->p_wchan==chan) {
 			p->p_wchan = 0;
 			*q = p->p_link;
-			p->p_slptime = 0;
+			if (qp->sq_tailp == &p->p_link)
+				qp->sq_tailp = q;
 			if (p->p_stat == SSLEEP) {
 				/* OPTIMIZED INLINE EXPANSION OF setrun(p) */
+				if (p->p_slptime > 1)
+					updatepri(p);
 				p->p_stat = SRUN;
-				if (p->p_flag & SLOAD) {
-#ifndef FASTVAX
-					p->p_link = runq;
-					runq = p->p_link;
-#else
+				if (p->p_flag & SLOAD)
 					setrq(p);
-#endif
-				}
-				if(p->p_pri < curpri)
-					runrun++;
-				if(runout != 0 && (p->p_flag&SLOAD) == 0) {
-					runout = 0;
-					wakeup((caddr_t)&runout);
+				/*
+				 * Since curpri is a usrpri,
+				 * p->p_pri is always better than curpri.
+				 */
+				runrun++;
+				aston();
+				if ((p->p_flag&SLOAD) == 0) {
+					if (runout != 0) {
+						runout = 0;
+						wakeup((caddr_t)&runout);
+					}
+					wantin++;
 				}
 				/* END INLINE EXPANSION */
 				goto restart;
@@ -193,7 +348,6 @@ restart:
 	splx(s);
 }
 
-#ifdef FASTVAX
 /*
  * Initialize the (doubly-linked) run queues
  * to be empty.
@@ -205,19 +359,17 @@ rqinit()
 	for (i = 0; i < NQS; i++)
 		qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i];
 }
-#endif
 
 /*
  * Set the process running;
  * arrange for it to be swapped in if necessary.
  */
 setrun(p)
-register struct proc *p;
+	register struct proc *p;
 {
-	register caddr_t w;
-	register s;
+	register int s;
 
-	s = spl6();
+	s = splhigh();
 	switch (p->p_stat) {
 
 	case 0:
@@ -227,23 +379,30 @@ register struct proc *p;
 	default:
 		panic("setrun");
 
+	case SSTOP:
 	case SSLEEP:
 		unsleep(p);		/* e.g. when sending signals */
 		break;
 
 	case SIDL:
-	case SSTOP:
 		break;
 	}
 	p->p_stat = SRUN;
 	if (p->p_flag & SLOAD)
 		setrq(p);
 	splx(s);
-	if(p->p_pri < curpri)
+	if (p->p_slptime > 1)
+		updatepri(p);
+	if (p->p_pri < curpri) {
 		runrun++;
-	if(runout != 0 && (p->p_flag&SLOAD) == 0) {
-		runout = 0;
-		wakeup((caddr_t)&runout);
+		aston();
+	}
+	if ((p->p_flag&SLOAD) == 0) {
+		if (runout != 0) {
+			runout = 0;
+			wakeup((caddr_t)&runout);
+		}
+		wantin++;
 	}
 }
 
@@ -254,157 +413,20 @@ register struct proc *p;
  * than the currently running process.
  */
 setpri(pp)
-register struct proc *pp;
+	register struct proc *pp;
 {
-	register p;
+	register int p;
 
-	p = (pp->p_cpu & 0377)/16;
-	p += PUSER + pp->p_nice - NZERO;
-	if(p > 127)
+	p = (pp->p_cpu & 0377)/4;
+	p += PUSER + 2 * pp->p_nice;
+	if (pp->p_rssize > pp->p_maxrss && freemem < desfree)
+		p += 2*4;	/* effectively, nice(4) */
+	if (p > 127)
 		p = 127;
-	if(p < curpri)
+	if (p < curpri) {
 		runrun++;
-	pp->p_usrpri = p;
-	return(p);
-}
-
-/*
- * Create a new process-- the internal version of
- * sys fork.
- * It returns 1 in the new process, 0 in the old.
- */
-newproc(isvfork)
-{
-	register struct proc *p;
-	register struct proc *rpp, *rip;
-	register int n;
-
-	p = NULL;
-	/*
-	 * First, just locate a slot for a process
-	 * and copy the useful info from this process into it.
-	 * The panic "cannot happen" because fork has already
-	 * checked for the existence of a slot.
-	 */
-retry:
-	mpid++;
-	if(mpid >= 30000) {
-		mpid = 0;
-		goto retry;
-	}
-	for(rpp = &proc[0]; rpp < &proc[NPROC]; rpp++) {
-		if(rpp->p_stat == NULL && p==NULL)
-			p = rpp;
-		if (rpp->p_pid==mpid || rpp->p_pgrp==mpid)
-			goto retry;
+		aston();
 	}
-	if ((rpp = p)==NULL)
-		panic("no procs");
-
-	/*
-	 * make proc entry for new proc
-	 */
-
-	rip = u.u_procp;
-	rpp->p_stat = SIDL;
-	rpp->p_clktim = 0;
-	rpp->p_flag = SLOAD | (rip->p_flag & SPAGI);
-	if (isvfork) {
-		rpp->p_flag |= SVFORK;
-		rpp->p_ndx = rip->p_ndx;
-	} else
-		rpp->p_ndx = rpp - proc;
-	rpp->p_uid = rip->p_uid;
-	rpp->p_pgrp = rip->p_pgrp;
-	rpp->p_nice = rip->p_nice;
-	rpp->p_textp = isvfork ? 0 : rip->p_textp;
-	rpp->p_pid = mpid;
-	rpp->p_ppid = rip->p_pid;
-	rpp->p_pptr = rip;
-	rpp->p_time = 0;
-	rpp->p_cpu = 0;
-	rpp->p_siga0 = rip->p_siga0;
-	rpp->p_siga1 = rip->p_siga1;
-	/* take along any pending signals, like stops? */
-	if (isvfork) {
-		rpp->p_tsize = rpp->p_dsize = rpp->p_ssize = 0;
-		rpp->p_szpt = clrnd(ctopt(UPAGES));
-		forkstat.cntvfork++;
-		forkstat.sizvfork += rip->p_dsize + rip->p_ssize;
-	} else {
-		rpp->p_tsize = rip->p_tsize;
-		rpp->p_dsize = rip->p_dsize;
-		rpp->p_ssize = rip->p_ssize;
-		rpp->p_szpt = rip->p_szpt;
-		forkstat.cntfork++;
-		forkstat.sizfork += rip->p_dsize + rip->p_ssize;
-	}
-	rpp->p_rssize = 0;
-	rpp->p_wchan = 0;
-	rpp->p_slptime = 0;
-	rpp->p_aveflt = rip->p_aveflt;
-	rate.v_pgin += rip->p_aveflt;
-	rpp->p_faults = 0;
-	n = PIDHASH(rpp->p_pid);
-	p->p_idhash = pidhash[n];
-	pidhash[n] = rpp - proc;
-
-	/*
-	 * make duplicate entries
-	 * where needed
-	 */
-
-	multprog++;
-
-	for(n=0; n<NOFILE; n++)
-		if(u.u_ofile[n] != NULL) {
-			u.u_ofile[n]->f_count++;
-			if(!isvfork && u.u_vrpages[n])
-				u.u_ofile[n]->f_inode->i_vfdcnt++;
-		}
-
-	u.u_cdir->i_count++;
-	if (u.u_rdir)
-		u.u_rdir->i_count++;
-	/*
-	 * Partially simulate the environment
-	 * of the new process so that when it is actually
-	 * created (by copying) it will look right.
-	 */
-
-	rip->p_flag |= SKEEP;	/* prevent parent from being swapped */
-
-	if (procdup(rpp, isvfork))
-		return (1);
-
-	spl6();
-	rpp->p_stat = SRUN;
-	setrq(rpp);
-	spl0();
-	/* SSWAP NOT NEEDED IN THIS CASE AS u.u_pcb.pcb_sswap SUFFICES */
-	/* rpp->p_flag |= SSWAP; */
-	rip->p_flag &= ~SKEEP;
-	if (isvfork) {
-		u.u_procp->p_xlink = rpp;
-		u.u_procp->p_flag |= SNOVM;
-		while (rpp->p_flag & SVFORK)
-			sleep((caddr_t)rpp, PZERO - 1);
-		if ((rpp->p_flag & SLOAD) == 0)
-			panic("newproc vfork");
-		uaccess(rpp, Vfmap, &vfutl);
-		u.u_procp->p_xlink = 0;
-		vpassvm(rpp, u.u_procp, &vfutl, &u, Vfmap);
-		for (n = 0; n < NOFILE; n++)
-			if (vfutl.u_vrpages[n]) {
-				if ((u.u_vrpages[n] = vfutl.u_vrpages[n] - 1) == 0)
-					if (--u.u_ofile[n]->f_inode->i_vfdcnt < 0)
-						panic("newproc i_vfdcnt");
-				vfutl.u_vrpages[n] = 0;
-			}
-		u.u_procp->p_flag &= ~SNOVM;
-		rpp->p_ndx = rpp - proc;
-		rpp->p_flag |= SVFDONE;
-		wakeup((caddr_t)rpp);
-	}
-	return (0);
+	pp->p_usrpri = p;
+	return (p);
 }