proc.c

著名操作系统Plan 9的第三版的部分核心源代码。现在很难找到了。Plan 9是bell实验室开发的Unix后继者。

#include	"u.h"
#include	"../port/lib.h"
#include	"mem.h"
#include	"dat.h"
#include	"fns.h"
#include	"../port/error.h"

Ref	pidalloc;
Ref	noteidalloc;

struct
{
	Lock;
	Proc*	arena;
	Proc*	free;
}procalloc;

struct
{
	Lock;
	Waitq*	free;
}waitqalloc;

typedef struct
{
	Lock;
	Proc*	head;
	Proc*	tail;
	int	n;
} Schedq;

int	nrdy;
Schedq	runq[Nrq];

char *statename[] =
{			/* BUG: generate automatically */
	"Dead",
	"Moribund",
	"Ready",
	"Scheding",
	"Running",
	"Queueing",
	"QueueingR",
	"QueueingW",
	"Wakeme",
	"Broken",
	"Stopped",
	"Rendez",
};

/*
 * Always splhi()'ed.
 */
void
schedinit(void)		/* never returns */
{
	setlabel(&m->sched);
	if(up) {
		m->proc = 0;
		switch(up->state) {
		case Running:
			ready(up);
			break;
		case Moribund:
			up->state = Dead;
			/*
			 * Holding locks from pexit:
			 * 	procalloc
			 *	palloc
			 */
			mmurelease(up);

			up->qnext = procalloc.free;
			procalloc.free = up;

			unlock(&palloc);
			unlock(&procalloc);
			break;
		}
		up->mach = 0;
		up = 0;
	}
	sched();
}

/*
 *  If changing this routine, look also at sleep().  It
 *  contains a copy of the guts of sched().
 */
void
sched(void)
{
	if(up) {
		splhi();

		/* statistics */
		m->cs++;

		procsave(up);
		if(setlabel(&up->sched)) {
			procrestore(up);
			spllo();
			return;
		}
		gotolabel(&m->sched);
	}
	up = runproc();
	up->state = Running;
	up->mach = MACHP(m->machno);
	m->proc = up;
	mmuswitch(up);
	gotolabel(&up->sched);
}

int
anyready(void)
{
	return nrdy;
}

int
anyhigher(void)
{
	Schedq *rq;

	if(nrdy == 0)
		return 0;

	for(rq = &runq[Nrq-1]; rq > &runq[up->priority]; rq--)
		if(rq->head != nil)
			return 1;
	
	return 0;
}

enum
{
	Squantum = (HZ+Nrq-1)/Nrq,
};

void
ready(Proc *p)
{
	int s, pri;
	Schedq *rq;

	s = splhi();

	/* history counts */
	if(p->state == Running){
		p->rt++;
		pri = ((p->art + (p->rt<<1))>>2)/Squantum;
	} else {
		p->art = (p->art + (p->rt<<1))>>2;
		p->rt = 0;
		pri = p->art/Squantum;
	}
	pri = p->basepri - pri;
	if(pri < 0)
		pri = 0;

	/* the only intersection between the classes is at PriNormal */
	if(pri < PriNormal && p->basepri > PriNormal)
		pri = PriNormal;

	/* stick at low priority any process waiting for a lock */
	if(p->lockwait)
		pri = PriLock;

	p->priority = pri;
	rq = &runq[p->priority];

	lock(runq);
	p->rnext = 0;
	if(rq->tail)
		rq->tail->rnext = p;
	else
		rq->head = p;
	rq->tail = p;
	rq->n++;
	nrdy++;
	p->readytime = m->ticks;
	p->state = Ready;
	unlock(runq);
	splx(s);
}

Proc*
runproc(void)
{
	Schedq *rq, *xrq;
	Proc *p, *l;
	ulong rt;

loop:

	/*
	 *  find a process that last ran on this processor (affinity),
	 *  or one that hasn't moved in a while (load balancing).
	 */
	spllo();
	for(;;){
		idlehands();
		if((++(m->fairness) & 0x3) == 0){
			/*
			 *  once in a while, run process that's been waiting longest
			 *  regardless of movetime
			 */
			rt = 0xffffffff;
			xrq = nil;
			for(rq = runq; rq < &runq[Nrq]; rq++){
				p = rq->head;
				if(p == 0)
					continue;
				if(p->readytime < rt){
					xrq = rq;
					rt = p->readytime;
				}
			}
			if(xrq != nil){
				rq = xrq;
				p = rq->head;
				if(p != nil && p->wired == nil)
					p->movetime = 0;
				goto found;
			}
		} else {
			/*
			 *  get highest priority process that this
			 *  processor can run given affinity constraints
			 */
			for(rq = &runq[Nrq-1]; rq >= runq; rq--){
				p = rq->head;
				if(p == 0)
					continue;
				for(; p; p = p->rnext){
					if(p->mp == MACHP(m->machno)
					|| p->movetime < MACHP(0)->ticks)
						goto found;
				}
			}
		}
	}

found:
	splhi();
	if(!canlock(runq))
		goto loop;

	l = 0;
	for(p = rq->head; p; p = p->rnext){
		if(p->mp == MACHP(m->machno) || p->movetime < MACHP(0)->ticks)
			break;
		l = p;
	}

	/*
	 *  p->mach==0 only when process state is saved
	 */
	if(p == 0 || p->mach){
		unlock(runq);
		goto loop;
	}
	if(p->rnext == 0)
		rq->tail = l;
	if(l)
		l->rnext = p->rnext;
	else
		rq->head = p->rnext;
	rq->n--;
	nrdy--;
	if(p->state != Ready)
		print("runproc %s %lud %s\n", p->text, p->pid, statename[p->state]);
	unlock(runq);

	p->state = Scheding;
	if(p->mp != MACHP(m->machno))
		p->movetime = MACHP(0)->ticks + HZ/10;
	p->mp = MACHP(m->machno);
	return p;
}

int
canpage(Proc *p)
{
	int ok = 0;

	splhi();
	lock(runq);
	/* Only reliable way to see if we are Running */
	if(p->mach == 0) {
		p->newtlb = 1;
		ok = 1;
	}
	unlock(runq);
	spllo();

	return ok;
}

Proc*
newproc(void)
{
	Proc *p;

	lock(&procalloc);
	for(;;) {
		if(p = procalloc.free)
			break;

		unlock(&procalloc);
		resrcwait("no procs");
		lock(&procalloc);
	}
	procalloc.free = p->qnext;
	unlock(&procalloc);

	p->state = Scheding;
	p->psstate = "New";
	p->mach = 0;
	p->qnext = 0;
	p->nchild = 0;
	p->nwait = 0;
	p->waitq = 0;
	p->pgrp = 0;
	p->egrp = 0;
	p->fgrp = 0;
	p->rgrp = 0;
	p->pdbg = 0;
	p->fpstate = FPinit;
	p->kp = 0;
	p->procctl = 0;
	p->notepending = 0;
	p->mp = 0;
	p->movetime = 0;
	p->wired = 0;
	p->ureg = 0;
	p->error[0] = '\0';
	memset(p->seg, 0, sizeof p->seg);
	p->pid = incref(&pidalloc);
	p->noteid = incref(&noteidalloc);
	if(p->pid==0 || p->noteid==0)
		panic("pidalloc");
	if(p->kstack == 0)
		p->kstack = smalloc(KSTACK);

	return p;
}

/*
 * wire this proc to a machine
 */
void
procwired(Proc *p, int bm)
{
	Proc *pp;
	int i;
	char nwired[MAXMACH];
	Mach *wm;

	if(bm < 0){
		/* pick a machine to wire to */
		memset(nwired, 0, sizeof(nwired));
		p->wired = 0;
		pp = proctab(0);
		for(i=0; i<conf.nproc; i++, pp++){
			wm = pp->wired;
			if(wm && pp->pid)
				nwired[wm->machno]++;
		}
		bm = 0;
		for(i=0; i<conf.nmach; i++)
			if(nwired[i] < nwired[bm])
				bm = i;
	} else {
		/* use the virtual machine requested */
		bm = bm % conf.nmach;
	}

	p->wired = MACHP(bm);
	p->movetime = 0xffffffff;
	p->mp = p->wired;
}

void
procinit0(void)		/* bad planning - clashes with devproc.c */
{
	Proc *p;
	int i;

	procalloc.free = xalloc(conf.nproc*sizeof(Proc));
	if(procalloc.free == nil)
		panic("cannot allocate %d procs\n", conf.nproc);
	procalloc.arena = procalloc.free;

	p = procalloc.free;
	for(i=0; i<conf.nproc-1; i++,p++)
		p->qnext = p+1;
	p->qnext = 0;
}


/*
 *  Sleep, postnote, and wakeup are complicated by the
 *  fact that at least one of them must indirect
 *  through an unlocked structure to find the synchronizing
 *  lock structure.  This is because sleep()
 *  and wakeup() share direct knowledge only of r while
 *  sleep() and postnote() share knowledge only of p.  We've
 *  chosen to put the synchronization lock in p, i.e.,
 *  p->rlock.  Therefore the interaction between sleep()
 *  and postnote() is completely synchronized by keeping
 *  p->rlock locked in sleep until the process has
 *  saved all the information it needs to become dormant.
 *
 *  However, wakeup() can only find what process is sleeping
 *  by looking at r->p.  A wakeup looks like:
 *
 *	1) set condition that sleep checks with (*f)()
 *	2) is p = r->p non zero
 *	3) lock(p->rlock)
 *	4) check r->p == p
 *	5) ...
 *
 *  A sleep looks like
 *
 *	a) lock(p->rlock)
 *	b) r->p = up
 *	c) check condition
 *	d) ...
 *
 *  On a multiprocessor, two processors
 *  may not see writes occur in the same order.  The coherence()
 *  instruction ensures that a processor has flushed all its
 *  writes to memory so that those writes will be seen by other
 *  processors and that the processor will see all writes flushed
 *  by other processors.
 *
 *  To make the above sequence work on a multiprocessor, we need
 *  to put a coherence() call between (1) and (2) and between
 *  (b) and (c).  That way we're guaranteed that if (1) and
 *  (2) occur after (c), the wakeup process will know
 *  which process is about to sleep and will enter its
 *  critical section.  If it doesn't, the sleep could proceed
 *  while the waker returns without doing anything.
 *  Similarly, if (b) and (c) occur after (2),
 *  the sleeper needs coherence to see that the condition was
 *  set.  Otherwise it could sleep even though the wakeup
 *  had already decided there was nothing to do.
 *
 *	jmk & presotto
 */
void
sleep(Rendez *r, int (*f)(void*), void *arg)
{
	int s;

	s = splhi();

	lock(&up->rlock);
	if(r->p){
		print("double sleep %lud %lud\n", r->p->pid, up->pid);
		dumpstack();
	}

	/*
	 *  Wakeup only knows there may be something to do by testing
	 *  r->p in order to get something to lock on.
	 *  Flush that information out to memory in case the sleep is
	 *  committed.
	 */
	r->p = up;
	coherence();

	if((*f)(arg) || up->notepending){
		/*
		 *  if condition happened or a note is pending
		 *  never mind
		 */
		r->p = nil;
		unlock(&up->rlock);
	} else {
		/*
		 *  now we are committed to
		 *  change state and call scheduler
		 */
		up->state = Wakeme;
		up->r = r;

		/* statistics */
		m->cs++;
	
		procsave(up);
		if(setlabel(&up->sched)) {
			/*
			 *  here when the process is awakened
			 */
			procrestore(up);
			spllo();
		} else {
			/*
			 *  here to go to sleep (i.e. stop Running)
			 */
			unlock(&up->rlock);
			gotolabel(&m->sched);
		}
	}

	if(up->notepending) {
		up->notepending = 0;
		splx(s);
		error(Eintr);
	}

	splx(s);
}

int
tfn(void *arg)
{
	return MACHP(0)->ticks >= up->twhen || up->tfn(arg);
}

void
tsleep(Rendez *r, int (*fn)(void*), void *arg, int ms)
{
	ulong when;
	Proc *f, **l;

	/* avoid overflows at the cost of precision */
	if(ms >= 1000000)
		when = ms/(1000/HZ);
	else
		when = MS2TK(ms);
	when += MACHP(0)->ticks;

	lock(&talarm);
	/* take out of list if checkalarm didn't */
	if(up->trend) {
		l = &talarm.list;
		for(f = *l; f; f = f->tlink) {
			if(f == up) {
				*l = up->tlink;
				break;
			}
			l = &f->tlink;
		}
	}
	/* insert in increasing time order */
	l = &talarm.list;
	for(f = *l; f; f = f->tlink) {
		if(f->twhen >= when)
			break;
		l = &f->tlink;
	}
	up->trend = r;
	up->twhen = when;
	up->tfn = fn;
	up->tlink = *l;
	*l = up;
	unlock(&talarm);

	if(waserror()){
		up->twhen = 0;
		nexterror();
	}
	sleep(r, tfn, arg);
	up->twhen = 0;
	poperror();
}

/*
 * Expects that only one process can call wakeup for any given Rendez
 */
int
wakeup(Rendez *r)
{
	Proc *p;
	int s, rv;

	/*
	 *  this makes sure that the condition sleep checks
	 *  with its (*f)(void) is visible to it
	 */
	coherence();

	rv = 0;
	p = r->p;
	if(p == 0)
		return rv;

	s = splhi();
	lock(&p->rlock);

	if(r->p == p && p->r == r){
		r->p = 0;
		if(p->state != Wakeme)
			panic("wakeup: state");
		p->r = 0;
		ready(p);
		rv = 1;
	}

	unlock(&p->rlock);
	splx(s);

	return rv;
}

int
postnote(Proc *p, int dolock, char *n, int flag)
{
	int s, ret;
	Rendez *r;
	Proc *d, **l;

	if(dolock)