[unix-history] / usr / src / sys / kern / kern_synch.c

/*
 * Copyright (c) 1982 Regents of the University of California.
 * All rights reserved.  The Berkeley software License Agreement
 * specifies the terms and conditions for redistribution.
 *
 *	@(#)kern_synch.c	6.10 (Berkeley) %G%
 */

#include "../machine/pte.h"

#include "param.h"
#include "systm.h"
#include "dir.h"
#include "user.h"
#include "proc.h"
#include "file.h"
#include "inode.h"
#include "vm.h"
#include "kernel.h"
#include "buf.h"

#ifdef vax
#include "../vax/mtpr.h"	/* XXX */
#endif
/*
 * Force switch among equal priority processes every 100ms.
 */
roundrobin()
{

	runrun++;
	aston();
	timeout(roundrobin, (caddr_t)0, hz / 10);
}

/* fraction for digital decay to forget 90% of usage in 5*loadav sec */
#define	filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1))

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 */;
	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 slpque {
	struct proc *sq_head;
	struct proc **sq_tailp;
} slpque[SQSIZE];

/*
 * Give up the processor till a wakeup occurs
 * on chan, at which time the process
 * enters the scheduling queue at priority pri.
 * The most important effect of pri is that when
 * pri<=PZERO a signal cannot disturb the sleep;
 * if pri>PZERO signals will be processed.
 * Callers of this routine must be prepared for
 * premature return, and check that the reason for
 * sleeping has gone away.
 */
sleep(chan, pri)
	caddr_t chan;
	int pri;
{
	register struct proc *rp;
	register struct slpque *qp;
	register s;

	rp = u.u_procp;
	s = splhigh();
	if (panicstr) {
		/*
		 * After a panic, 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;
	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;
			(void) spl0();
			goto psig;
		}
		if (rp->p_wchan == 0)
			goto out;
		rp->p_stat = SSLEEP;
		(void) spl0();
		u.u_ru.ru_nvcsw++;
		swtch();
		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 through
	 * u.u_qsave, aborting the system call in progress (see trap.c)
	 */
psig:
	longjmp(&u.u_qsave);
	/*NOTREACHED*/
}

/*
 * Remove a process from its wait queue
 */
unsleep(p)
	register struct proc *p;
{
	register struct slpque *qp;
	register struct proc **hp;
	int s;

	s = splhigh();
	if (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);
}

/*
 * Wake up all processes sleeping on chan.
 */
wakeup(chan)
	register caddr_t chan;
{
	register struct slpque *qp;
	register struct proc *p, **q;
	int s;

	s = splhigh();
	qp = &slpque[HASH(chan)];
restart:
	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_wchan = 0;
			*q = p->p_link;
			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_slptime = 0;
				p->p_stat = SRUN;
				if (p->p_flag & SLOAD)
					setrq(p);
				/*
				 * 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;
			}
			p->p_slptime = 0;
		} else
			q = &p->p_link;
	}
	splx(s);
}

/*
 * Initialize the (doubly-linked) run queues
 * to be empty.
 */
rqinit()
{
	register int i;

	for (i = 0; i < NQS; i++)
		qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i];
}

/*
 * Set the process running;
 * arrange for it to be swapped in if necessary.
 */
setrun(p)
	register struct proc *p;
{
	register int s;

	s = splhigh();
	switch (p->p_stat) {

	case 0:
	case SWAIT:
	case SRUN:
	case SZOMB:
	default:
		panic("setrun");

	case SSTOP:
	case SSLEEP:
		unsleep(p);		/* e.g. when sending signals */
		break;

	case SIDL:
		break;
	}
	if (p->p_slptime > 1)
		updatepri(p);
	p->p_stat = SRUN;
	if (p->p_flag & SLOAD)
		setrq(p);
	splx(s);
	if (p->p_pri < curpri) {
		runrun++;
		aston();
	}
	if ((p->p_flag&SLOAD) == 0) {
		if (runout != 0) {
			runout = 0;
			wakeup((caddr_t)&runout);
		}
		wantin++;
	}
}

/*
 * Set user priority.
 * The rescheduling flag (runrun)
 * is set if the priority is better
 * than the currently running process.
 */
setpri(pp)
	register struct proc *pp;
{
	register int p;

	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) {
		runrun++;
		aston();
	}
	pp->p_usrpri = p;
	return (p);
}
Commit	Line	Data
da7c5cc6 KM	1	/*
	2	* Copyright (c) 1982 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	* @(#)kern_synch.c 6.10 (Berkeley) %G%
	7	*/
961945a8 SL	8
961945a8 SL	9	#include "../machine/pte.h"
a379cce8	10
94368568 JB	11	#include "param.h"
	12	#include "systm.h"
	13	#include "dir.h"
	14	#include "user.h"
	15	#include "proc.h"
	16	#include "file.h"
	17	#include "inode.h"
	18	#include "vm.h"
	19	#include "kernel.h"
	20	#include "buf.h"
1edb1cf8	21
961945a8 SL	22	#ifdef vax
	23	#include "../vax/mtpr.h" /* XXX */
	24	#endif
1edb1cf8 BJ	25	/*
	26	* Force switch among equal priority processes every 100ms.
	27	*/
	28	roundrobin()
	29	{
	30
	31	runrun++;
	32	aston();
b32450f4	33	timeout(roundrobin, (caddr_t)0, hz / 10);
1edb1cf8 BJ	34	}
1edb1cf8 BJ	35
1e35e051 MK	36	/* fraction for digital decay to forget 90% of usage in 5loadav sec /
	37	#define filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1))
	38
1edb1cf8 BJ	39	double ccpu = 0.95122942450071400909; /* exp(-1/20) */
1edb1cf8 BJ	40
1edb1cf8 BJ	41	/*
	42	* Recompute process priorities, once a second
	43	*/
	44	schedcpu()
	45	{
fab25db3	46	register double ccpu1 = (1.0 - ccpu) / (double)hz;
1edb1cf8 BJ	47	register struct proc *p;
1edb1cf8 BJ	48	register int s, a;
1e35e051	49	float scale = filter(avenrun[0]);
1edb1cf8	50
1edb1cf8	51	wakeup((caddr_t)&lbolt);
1d348849	52	for (p = allproc; p != NULL; p = p->p_nxt) {
1edb1cf8 BJ	53	if (p->p_time != 127)
1edb1cf8 BJ	54	p->p_time++;
1edb1cf8 BJ	55	if (p->p_stat==SSLEEP \|\| p->p_stat==SSTOP)
	56	if (p->p_slptime != 127)
	57	p->p_slptime++;
1e35e051 MK	58	/*
	59	* If the process has slept the entire second,
	60	* stop recalculating its priority until it wakes up.
	61	*/
	62	if (p->p_slptime > 1) {
	63	p->p_pctcpu *= ccpu;
	64	continue;
	65	}
	66	/*
	67	* p_pctcpu is only for ps.
	68	*/
	69	p->p_pctcpu = ccpu * p->p_pctcpu + ccpu1 * p->p_cpticks;
1edb1cf8	70	p->p_cpticks = 0;
1e35e051	71	a = (int) (scale * (p->p_cpu & 0377)) + p->p_nice;
1edb1cf8 BJ	72	if (a < 0)
	73	a = 0;
	74	if (a > 255)
	75	a = 255;
	76	p->p_cpu = a;
	77	(void) setpri(p);
1e35e051	78	s = splhigh(); /* prevent state changes */
1edb1cf8	79	if (p->p_pri >= PUSER) {
fab25db3	80	#define PPQ (128 / NQS)
1edb1cf8 BJ	81	if ((p != u.u_procp \|\| noproc) &&
	82	p->p_stat == SRUN &&
	83	(p->p_flag & SLOAD) &&
fab25db3	84	(p->p_pri / PPQ) != (p->p_usrpri / PPQ)) {
1edb1cf8 BJ	85	remrq(p);
	86	p->p_pri = p->p_usrpri;
	87	setrq(p);
	88	} else
	89	p->p_pri = p->p_usrpri;
	90	}
	91	splx(s);
	92	}
	93	vmmeter();
	94	if (runin!=0) {
	95	runin = 0;
	96	wakeup((caddr_t)&runin);
	97	}
	98	if (bclnlist != NULL)
	99	wakeup((caddr_t)&proc[2]);
b32450f4	100	timeout(schedcpu, (caddr_t)0, hz);
1edb1cf8	101	}
a379cce8	102
1e35e051 MK	103	/*
	104	* Recalculate the priority of a process after it has slept for a while.
	105	*/
	106	updatepri(p)
	107	register struct proc *p;
	108	{
	109	register int a = p->p_cpu & 0377;
	110	float scale = filter(avenrun[0]);
	111
	112	p->p_slptime--; /* the first time was done in schedcpu */
	113	while (a && --p->p_slptime)
	114	a = (int) (scale * a) /* + p->p_nice */;
	115	if (a < 0)
	116	a = 0;
	117	if (a > 255)
	118	a = 255;
	119	p->p_cpu = a;
	120	(void) setpri(p);
	121	}
	122
a379cce8 BJ	123	#define SQSIZE 0100 /* Must be power of 2 */
a379cce8 BJ	124	#define HASH(x) (( (int) x >> 5) & (SQSIZE-1))
3abb418a KM	125	struct slpque {
	126	struct proc *sq_head;
	127	struct proc **sq_tailp;
	128	} slpque[SQSIZE];
a379cce8 BJ	129
	130	/*
	131	* Give up the processor till a wakeup occurs
	132	* on chan, at which time the process
	133	* enters the scheduling queue at priority pri.
	134	* The most important effect of pri is that when
	135	* pri<=PZERO a signal cannot disturb the sleep;
	136	* if pri>PZERO signals will be processed.
	137	* Callers of this routine must be prepared for
	138	* premature return, and check that the reason for
	139	* sleeping has gone away.
	140	*/
	141	sleep(chan, pri)
bd76c595 BJ	142	caddr_t chan;
bd76c595 BJ	143	int pri;
a379cce8	144	{
3abb418a KM	145	register struct proc *rp;
3abb418a KM	146	register struct slpque *qp;
6fdc0335	147	register s;
a379cce8 BJ	148
a379cce8 BJ	149	rp = u.u_procp;
1e35e051	150	s = splhigh();
76acd871 MK	151	if (panicstr) {
	152	/*
	153	* After a panic, just give interrupts a chance,
	154	* then just return; don't run any other procs
	155	* or panic below, in case this is the idle process
	156	* and already asleep.
	157	* The splnet should be spl0 if the network was being used
	158	* by the filesystem, but for now avoid network interrupts
	159	* that might cause another panic.
	160	*/
	161	(void) splnet();
	162	splx(s);
	163	return;
	164	}
	165	if (chan==0 \|\| rp->p_stat != SRUN \|\| rp->p_rlink)
a379cce8	166	panic("sleep");
a379cce8 BJ	167	rp->p_wchan = chan;
	168	rp->p_slptime = 0;
	169	rp->p_pri = pri;
3abb418a KM	170	qp = &slpque[HASH(chan)];
	171	if (qp->sq_head == 0)
	172	qp->sq_head = rp;
	173	else
	174	*qp->sq_tailp = rp;
	175	*(qp->sq_tailp = &rp->p_link) = 0;
18a4549b	176	if (pri > PZERO) {
6f414c22 MK	177	/*
	178	* If we stop in issig(), wakeup may already have happened
	179	* when we return (rp->p_wchan will then be 0).
	180	*/
18a4549b	181	if (ISSIG(rp)) {
e5df4be8 BJ	182	if (rp->p_wchan)
e5df4be8 BJ	183	unsleep(rp);
a379cce8	184	rp->p_stat = SRUN;
81263dba	185	(void) spl0();
a379cce8 BJ	186	goto psig;
a379cce8 BJ	187	}
e5df4be8 BJ	188	if (rp->p_wchan == 0)
	189	goto out;
	190	rp->p_stat = SSLEEP;
81263dba	191	(void) spl0();
bd76c595	192	u.u_ru.ru_nvcsw++;
a379cce8	193	swtch();
18a4549b	194	if (ISSIG(rp))
a379cce8 BJ	195	goto psig;
a379cce8 BJ	196	} else {
6fdc0335	197	rp->p_stat = SSLEEP;
81263dba	198	(void) spl0();
bd76c595	199	u.u_ru.ru_nvcsw++;
a379cce8 BJ	200	swtch();
a379cce8 BJ	201	}
fab25db3	202	curpri = rp->p_usrpri;
e5df4be8	203	out:
a379cce8 BJ	204	splx(s);
	205	return;
	206
	207	/*
	208	* If priority was low (>PZERO) and
18a4549b	209	* there has been a signal, execute non-local goto through
d01b68d6	210	* u.u_qsave, aborting the system call in progress (see trap.c)
a379cce8 BJ	211	*/
a379cce8 BJ	212	psig:
d01b68d6	213	longjmp(&u.u_qsave);
a379cce8 BJ	214	/NOTREACHED/
	215	}
	216
87d0f32e BJ	217	/*
	218	* Remove a process from its wait queue
	219	*/
	220	unsleep(p)
18a4549b	221	register struct proc *p;
87d0f32e	222	{
3abb418a	223	register struct slpque *qp;
87d0f32e	224	register struct proc **hp;
3abb418a	225	int s;
87d0f32e	226
1e35e051	227	s = splhigh();
87d0f32e	228	if (p->p_wchan) {
3abb418a	229	hp = &(qp = &slpque[HASH(p->p_wchan)])->sq_head;
87d0f32e BJ	230	while (*hp != p)
	231	hp = &(*hp)->p_link;
	232	*hp = p->p_link;
3abb418a KM	233	if (qp->sq_tailp == &p->p_link)
3abb418a KM	234	qp->sq_tailp = hp;
87d0f32e BJ	235	p->p_wchan = 0;
	236	}
	237	splx(s);
	238	}
	239
a379cce8 BJ	240	/*
	241	* Wake up all processes sleeping on chan.
	242	*/
	243	wakeup(chan)
18a4549b	244	register caddr_t chan;
a379cce8	245	{
3abb418a KM	246	register struct slpque *qp;
3abb418a KM	247	register struct proc p, *q;
a379cce8 BJ	248	int s;
a379cce8 BJ	249
1e35e051	250	s = splhigh();
3abb418a	251	qp = &slpque[HASH(chan)];
a379cce8	252	restart:
3abb418a	253	for (q = &qp->sq_head; p = *q; ) {
87d0f32e	254	if (p->p_rlink \|\| p->p_stat != SSLEEP && p->p_stat != SSTOP)
a379cce8	255	panic("wakeup");
6fdc0335	256	if (p->p_wchan==chan) {
a379cce8	257	p->p_wchan = 0;
e5df4be8	258	*q = p->p_link;
3abb418a KM	259	if (qp->sq_tailp == &p->p_link)
3abb418a KM	260	qp->sq_tailp = q;
87d0f32e BJ	261	if (p->p_stat == SSLEEP) {
87d0f32e BJ	262	/* OPTIMIZED INLINE EXPANSION OF setrun(p) */
6f414c22 MK	263	if (p->p_slptime > 1)
6f414c22 MK	264	updatepri(p);
cd8d1b96	265	p->p_slptime = 0;
87d0f32e	266	p->p_stat = SRUN;
c74c8a79	267	if (p->p_flag & SLOAD)
87d0f32e	268	setrq(p);
fab25db3 MK	269	/*
	270	* Since curpri is a usrpri,
	271	* p->p_pri is always better than curpri.
	272	*/
	273	runrun++;
	274	aston();
7eb2e67e BJ	275	if ((p->p_flag&SLOAD) == 0) {
	276	if (runout != 0) {
	277	runout = 0;
	278	wakeup((caddr_t)&runout);
	279	}
	280	wantin++;
87d0f32e BJ	281	}
87d0f32e BJ	282	/* END INLINE EXPANSION */
e5df4be8	283	goto restart;
a379cce8	284	}
cd8d1b96	285	p->p_slptime = 0;
e5df4be8 BJ	286	} else
e5df4be8 BJ	287	q = &p->p_link;
a379cce8 BJ	288	}
	289	splx(s);
	290	}
	291
a379cce8 BJ	292	/*
	293	* Initialize the (doubly-linked) run queues
	294	* to be empty.
	295	*/
	296	rqinit()
	297	{
	298	register int i;
	299
	300	for (i = 0; i < NQS; i++)
	301	qs[i].ph_link = qs[i].ph_rlink = (struct proc *)&qs[i];
	302	}
a379cce8 BJ	303
	304	/*
	305	* Set the process running;
	306	* arrange for it to be swapped in if necessary.
	307	*/
	308	setrun(p)
18a4549b	309	register struct proc *p;
a379cce8	310	{
18a4549b	311	register int s;
a379cce8	312
1e35e051	313	s = splhigh();
a379cce8 BJ	314	switch (p->p_stat) {
	315
	316	case 0:
	317	case SWAIT:
	318	case SRUN:
	319	case SZOMB:
	320	default:
	321	panic("setrun");
	322
6fdc0335	323	case SSTOP:
a379cce8	324	case SSLEEP:
87d0f32e	325	unsleep(p); /* e.g. when sending signals */
a379cce8 BJ	326	break;
	327
	328	case SIDL:
a379cce8 BJ	329	break;
a379cce8 BJ	330	}
1e35e051 MK	331	if (p->p_slptime > 1)
1e35e051 MK	332	updatepri(p);
a379cce8 BJ	333	p->p_stat = SRUN;
	334	if (p->p_flag & SLOAD)
	335	setrq(p);
	336	splx(s);
18a4549b	337	if (p->p_pri < curpri) {
a379cce8	338	runrun++;
534d9295 BJ	339	aston();
534d9295 BJ	340	}
7eb2e67e	341	if ((p->p_flag&SLOAD) == 0) {
18a4549b	342	if (runout != 0) {
7eb2e67e BJ	343	runout = 0;
	344	wakeup((caddr_t)&runout);
	345	}
	346	wantin++;
a379cce8 BJ	347	}
	348	}
	349
	350	/*
	351	* Set user priority.
	352	* The rescheduling flag (runrun)
	353	* is set if the priority is better
	354	* than the currently running process.
	355	*/
	356	setpri(pp)
18a4549b	357	register struct proc *pp;
a379cce8	358	{
18a4549b	359	register int p;
a379cce8	360
16a64baa	361	p = (pp->p_cpu & 0377)/4;
1e35e051	362	p += PUSER + 2 * pp->p_nice;
9afea775 BJ	363	if (pp->p_rssize > pp->p_maxrss && freemem < desfree)
9afea775 BJ	364	p += 24; / effectively, nice(4) */
18a4549b	365	if (p > 127)
a379cce8	366	p = 127;
18a4549b	367	if (p < curpri) {
a379cce8	368	runrun++;
a51a6e74 BJ	369	aston();
a51a6e74 BJ	370	}
a379cce8	371	pp->p_usrpri = p;
18a4549b	372	return (p);
a379cce8	373	}