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

/*
 * 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.2 (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 "file.h"
#include "inode.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);
}

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