#define	WANT_M#include	"u.h"#include	"lib.h"#include	"mem.h"#include	"dat.h"#include	"fns.h"#include	"error.h"#include	"trace.h" int	schedgain = 30;	/* units in seconds */int	nrdy;Ref	noteidalloc; void updatecpu(Proc*);int reprioritize(Proc*); ulong	delayedscheds;	/* statistics */long skipscheds;long preempts;ulong load; static Ref	pidalloc; static struct Procalloc{	Lock lk;	Proc*	ht[128];	Proc*	arena;	Proc*	free;} procalloc; enum{	Q=10,	DQ=4,	Scaling=2,}; Schedq	runq[Nrq];ulong	runvec; char *statename[] ={	/* BUG: generate automatically */	"Dead",	"Moribund",	"Ready",	"Scheding",	"Running",	"Queueing",	"QueueingR",	"QueueingW",	"Wakeme",	"Broken",	"Stopped",	"Rendez",	"Waitrelease",}; static void pidhash(Proc*);static void pidunhash(Proc*);static void rebalance(void); /* * Always splhi()'ed. */voidschedinit(void)		/* never returns */{ 	setlabel(&m->sched);	if(traceprocs)	// Plan 9 VX		print("schedinit %p %p %s\n", m, up, up ? up->text : "");	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.lk);			unlock(&procalloc.lk);			break;		}		up->mach = nil;		updatecpu(up);		up = nil;	}	sched();} /* *  If changing this routine, look also at sleep().  It *  contains a copy of the guts of sched(). */voidsched(void){	Proc *p; 	if(traceprocs)	// Plan 9 VX		print("sched %p %p [%s]\n", m, up, up ? up->text : "");	if(m->ilockdepth)		panic("cpu%d: ilockdepth %d, last lock %#p at %#p, sched called from %#p",			m->machno,			m->ilockdepth,			up? up->lastilock: nil,			(up && up->lastilock)? up->lastilock->pc: 0,			getcallerpc(&p+2));	if(up){		/*		 * Delay the sched until the process gives up the locks		 * it is holding.  This avoids dumb lock loops.		 * Don't delay if the process is Moribund.		 * It called sched to die.		 * But do sched eventually.  This avoids a missing unlock		 * from hanging the entire kernel. 		 * But don't reschedule procs holding palloc or procalloc.		 * Those are far too important to be holding while asleep.		 *		 * This test is not exact.  There can still be a few instructions		 * in the middle of taslock when a process holds a lock		 * but Lock.p has not yet been initialized.		 */		if(up->nlocks.ref)		if(up->state != Moribund)		if(up->delaysched < 20		|| palloc.lk.p == up		|| procalloc.lk.p == up){			up->delaysched++; 			delayedscheds++;			return;		}		up->delaysched = 0; 		splhi(); 		/* statistics */		m->cs++; 		procsave(up);		if(setlabel(&up->sched)){			if(traceprocs)				print("sched %p %p: awake\n", m, up);			procrestore(up);			spllo();			return;		}		if(traceprocs)			print("sched %p %p: entering scheduler\n", m, up);		gotolabel(&m->sched);	}	if(traceprocs)		print("sched %p %p: runproc", m, up);	p = runproc();	if(1){		updatecpu(p);		p->priority = reprioritize(p);	}	if(p != m->readied)		m->schedticks = msec() + HZ/10;	m->readied = 0;	up = p;	up->state = Running;	up->mach = MACHP(m->machno);	m->proc = up;	if(traceprocs)		print("run %p %p [%s]\n", m, up, up->text);	mmuswitch(up);	gotolabel(&up->sched);} intanyready(void){	return runvec;} intanyhigher(void){	return runvec & ~((1<<(up->priority+1))-1);} /* *  here once per clock tick to see if we should resched */voidhzsched(void){	/* once a second, rebalance will reprioritize ready procs */	if(m->machno == 0)		rebalance(); 	/* unless preempted, get to run for at least 100ms */	if(anyhigher()	|| (!up->fixedpri && msec() > m->schedticks && anyready())){		m->readied = nil;	/* avoid cooperative scheduling */		up->delaysched++;	}} /* *  here at the end of non-clock interrupts to see if we should preempt the *  current process.  Returns 1 if preempted, 0 otherwise. */intpreempted(void){	if(up && up->state == Running)	if(up->preempted == 0)	if(anyhigher())	if(!active.exiting){		m->readied = nil;	/* avoid cooperative scheduling */		up->preempted = 1;		sched();		splhi();		up->preempted = 0;		return 1;	}	return 0;} /* * Update the cpu time average for this particular process, * which is about to change from up -> not up or vice versa. * p->lastupdate is the last time an updatecpu happened. * * The cpu time average is a decaying average that lasts * about D clock ticks.  D is chosen to be approximately * the cpu time of a cpu-intensive "quick job".  A job has to run * for approximately D clock ticks before we home in on its  * actual cpu usage.  Thus if you manage to get in and get out * quickly, you won't be penalized during your burst.  Once you * start using your share of the cpu for more than about D * clock ticks though, your p->cpu hits 1000 (1.0) and you end up  * below all the other quick jobs.  Interactive tasks, because * they basically always use less than their fair share of cpu, * will be rewarded. * * If the process has not been running, then we want to * apply the filter * *	cpu = cpu * (D-1)/D * * n times, yielding  *  *	cpu = cpu * ((D-1)/D)^n * * but D is big enough that this is approximately  * * 	cpu = cpu * (D-n)/D * * so we use that instead. *  * If the process has been running, we apply the filter to * 1 - cpu, yielding a similar equation.  Note that cpu is  * stored in fixed point (* 1000). * * Updatecpu must be called before changing up, in order * to maintain accurate cpu usage statistics.  It can be called * at any time to bring the stats for a given proc up-to-date. */voidupdatecpu(Proc *p){	int n, t, ocpu;	int D = schedgain*HZ*Scaling; 	if(p->edf)		return; 	t = msec()*Scaling + Scaling/2;	n = t - p->lastupdate;	p->lastupdate = t; 	if(n == 0)		return;	if(n > D)		n = D; 	ocpu = p->cpu;	if(p != up)		p->cpu = (ocpu*(D-n))/D;	else{		t = 1000 - ocpu;		t = (t*(D-n))/D;		p->cpu = 1000 - t;	} //iprint("pid %d %s for %d cpu %d -> %d\n", p->pid,p==up?"active":"inactive",n, ocpu,p->cpu);} /* * On average, p has used p->cpu of a cpu recently. * Its fair share is conf.nmach/m->load of a cpu.  If it has been getting * too much, penalize it.  If it has been getting not enough, reward it. * I don't think you can get much more than your fair share that  * often, so most of the queues are for using less.  Having a priority * of 3 means you're just right.  Having a higher priority (up to p->basepri)  * means you're not using as much as you could. */intreprioritize(Proc *p){	int fairshare, n, load, ratio; 	load = MACHP(0)->load;	if(load == 0)		return p->basepri; 	/*	 *  fairshare = 1.000 * conf.nproc * 1.000/load,	 * except the decimal point is moved three places	 * on both load and fairshare.	 */	fairshare = (conf.nmach*1000*1000)/load;	n = p->cpu;	if(n == 0)		n = 1;	ratio = (fairshare+n/2) / n;	if(ratio > p->basepri)		ratio = p->basepri;	if(ratio < 0)		panic("reprioritize");//iprint("pid %d cpu %d load %d fair %d pri %d\n", p->pid, p->cpu, load, fairshare, ratio);	return ratio;} /* * add a process to a scheduling queue */voidqueueproc(Schedq *rq, Proc *p){	int pri; 	pri = rq - runq;	lock(&runq->lk);	p->priority = pri;	p->rnext = 0;	if(rq->tail)		rq->tail->rnext = p;	else		rq->head = p;	rq->tail = p;	rq->n++;	nrdy++;	runvec |= 1<<pri;	unlock(&runq->lk);} /* *  try to remove a process from a scheduling queue (called splhi) */Proc*dequeueproc(Schedq *rq, Proc *tp){	Proc *l, *p; 	if(!canlock(&runq->lk))		return nil; 	/*	 *  the queue may have changed before we locked runq,	 *  refind the target process.	 */	l = 0;	for(p = rq->head; p; p = p->rnext){		if(p == tp)			break;		l = p;	} 	/*	 *  p->mach==0 only when process state is saved	 */	if(p == 0 || p->mach){		unlock(&runq->lk);		return nil;	}	if(p->rnext == 0)		rq->tail = l;	if(l)		l->rnext = p->rnext;	else		rq->head = p->rnext;	if(rq->head == nil)		runvec &= ~(1<<(rq-runq));	rq->n--;	nrdy--;	if(p->state != Ready)		print("dequeueproc %s %lud %s\n", p->text, p->pid, statename[p->state]); 	unlock(&runq->lk);	return p;} /* *  ready(p) picks a new priority for a process and sticks it in the *  runq for that priority. */void_ready(Proc *p){	int s, pri;	Schedq *rq;	void (*pt)(Proc*, int, vlong); 	s = splhi();	if(0){		splx(s);		return;	} 	if(up != p)		m->readied = p;	/* group scheduling */ 	updatecpu(p);	pri = reprioritize(p);	p->priority = pri;	rq = &runq[pri];	p->state = Ready;	queueproc(rq, p);	pt = proctrace;	if(pt)		pt(p, SReady, 0);	splx(s);} /* *  yield the processor and drop our priority */voidyield(void){	if(anyready()){		/* pretend we just used 1/2 tick */		up->lastupdate -= Scaling/2;  		sched();	}} /* *  recalculate priorities once a second.  We need to do this *  since priorities will otherwise only be recalculated when *  the running process blocks. */ulong balancetime; static voidrebalance(void){	int pri, npri, t, x;	Schedq *rq;	Proc *p; 	t = msec();	if(t - balancetime < HZ)		return;	balancetime = t; 	for(pri=0, rq=runq; pri<Npriq; pri++, rq++){another:		p = rq->head;		if(p == nil)			continue;		if(p->mp != MACHP(m->machno))			continue;		if(pri == p->basepri)			continue;		updatecpu(p);		npri = reprioritize(p);		if(npri != pri){			x = splhi();			p = dequeueproc(rq, p);			if(p)				queueproc(&runq[npri], p);			splx(x);			goto another;		}	}}	 /* *  pick a process to run */Proc*

Lines 1–500 of 1622. Load more