2003/0228/port/proc.c (diff list | history)

2003/0226/sys/src/9/port/proc.c:20,26 – 2003/0228/sys/src/9/port/proc.c:20,41 (short | long | prev | next)
New many-run-queue scheduler. rsc Mon Mar 20 20:49:41 2006
1997/0327		Proc* free;
2001/0527		} procalloc;
1990/0227
2003/0228		enum { Q=(HZ/20)*4, DQ=((HZ-Q)/40)*2, };
2001/0527		static Schedq runq[Nrq];
2003/0228		static ulong runvec; static int quanta[Nrq] = { Q+19*DQ, Q+18*DQ, Q+17*DQ, Q+16*DQ, Q+15*DQ, Q+14*DQ, Q+13*DQ, Q+12*DQ, Q+11*DQ, Q+10*DQ, Q+ 9*DQ, Q+ 8*DQ, Q+ 7*DQ, Q+ 6*DQ, Q+ 5*DQ, Q+ 4*DQ, Q+ 3*DQ, Q+ 2*DQ, Q+ 1*DQ, Q+ 0*DQ, };
1994/0728
2002/0704		extern Edfinterface nulledf;
2003/0226/sys/src/9/port/proc.c:128,155 – 2003/0228/sys/src/9/port/proc.c:143,196
1994/0321		int anyready(void) {
2002/0704		return nrdy || edf->edfanyready();
2003/0228		return runvec || edf->edfanyready();
1990/1227		}
1994/0809		int
1994/0817		anyhigher(void)
1994/0809		{
1999/0326		Schedq *rq;
2003/0228		return runvec & ~((1<<(up->priority+1))-1); }
1994/0817
1999/0326		if(nrdy == 0) return 0;
2003/0228		/* * here once per clock tick to see if we should resched */ void hzsched(void) { /* another cycle, another quantum */ up->quanta--;
1999/0326		for(rq = &runq[Nrq-1]; rq > &runq[up->priority]; rq--) if(rq->head != nil) return 1;
2003/0228		/* edf scheduler always gets first chance */ if(edf->isedf(up)) return;
2002/0315
1999/0326		return 0;
2003/0228		/* don't bother unless someone is elegible */ if(anyhigher() || (!up->fixedpri && anyready())){ sched(); splhi(); }
1994/0809		}
1995/0110		enum
2003/0228		/* * here at the end of non-clock interrupts to see if we should preempt the * current process. Returns 1 if preempted, 0 otherwise. */ int preempted(void)
1995/0110		{
2002/0228		Squantum = 1,
1995/0110		};
2003/0228		if(up && up->state == Running) if(up->preempted == 0) if(anyhigher()) if(!active.exiting){ up->preempted = 1; sched(); splhi(); up->preempted = 0; return 1; } return 0; }
1995/0110
1990/0227		void ready(Proc *p)
2003/0226/sys/src/9/port/proc.c:164,197 – 2003/0228/sys/src/9/port/proc.c:205,241
2002/0404		splx(s); return; }
2003/0228		pri = p->priority;
2001/0315		if(p->fixedpri){ pri = p->basepri;
2003/0228		p->quanta = HZ; } else if(p->state == Running){ if(p->quanta <= 0){ /* degrade priority of anyone that used their whole quanta */ /* processes > PriNormal and those below don't mix */ if(p->basepri > PriNormal){ if(pri > PriNormal) pri--; } else { if(pri > 0) pri--; } p->quanta = quanta[pri]; }
1995/0110		} else {
2001/0315		/* history counts */ if(p->state == Running){ p->rt++;
2002/0228		pri = (p->art + p->rt)/2;
2001/0315		} else {
2002/0228		p->art = (p->art + p->rt + 2)/2; pri = (p->art + p->rt)/2;
2001/0315		p->rt = 0;
2003/0228		if(p->quanta > quanta[pri]/2){ /* blocked before using half its quanta, go up */ if(++pri > p->basepri) pri = p->basepri;
2001/0315		}
2002/0228		pri = p->basepri - (pri/Squantum);
2001/0315		if(pri < 0) pri = 0;
2002/0315
2001/0315		/* the only intersection between the classes is at PriNormal */ if(pri < PriNormal && p->basepri > PriNormal) pri = PriNormal;
1995/0110
2001/0315		/* stick at low priority any process waiting for a lock */ if(p->lockwait) pri = PriLock;
2003/0228		p->quanta = quanta[pri];
2001/0315		}
1998/0606
2003/0228		rq = &runq[pri];
1996/0523		p->priority = pri;
1995/0110		rq = &runq[p->priority];                  lock(runq);
1990/0227		p->rnext = 0;
1995/0110		if(rq->tail)
2003/0226/sys/src/9/port/proc.c:201,206 – 2003/0228/sys/src/9/port/proc.c:245,251
1995/0110		rq->tail = p; rq->n++; nrdy++;
2003/0228		runvec |= 1<<pri;
1995/0110		p->readytime = m->ticks;
1990/0227		p->state = Ready;
1995/0110		unlock(runq);
2003/0226/sys/src/9/port/proc.c:210,219 – 2003/0228/sys/src/9/port/proc.c:255,264
1990/0227		Proc* runproc(void) {
1998/0901		Schedq *rq, *xrq;
2003/0228		Schedq *rq;
1995/0110		Proc *p, *l;
1998/0901		ulong rt;
2002/0822		ulong start, now;
2003/0228		int i;
1990/0227
2002/0822		start = perfticks();
2002/0821
2003/0226/sys/src/9/port/proc.c:221,275 – 2003/0228/sys/src/9/port/proc.c:266,295
2002/0404		return p;
1990/0227		loop:
1995/0110		/* * find a process that last ran on this processor (affinity), * or one that hasn't moved in a while (load balancing).
2003/0228		* or one that hasn't moved in a while (load balancing). Every * time around the loop affinity goes down.
1995/0110		*/
1992/0603		spllo();
1995/0912		for(;;){
2003/0226		if((++(m->fairness) & 0x3) == 0){
1998/0901		/* * once in a while, run process that's been waiting longest * regardless of movetime */ rt = 0xffffffff; xrq = nil;
1995/0110		for(rq = runq; rq < &runq[Nrq]; rq++){ p = rq->head;
1996/0315		if(p == 0)
1995/0110		continue;
1998/0901		if(p->readytime < rt){ xrq = rq; rt = p->readytime; }
2003/0228		for(i = 0;; i++){ /* * 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->wired && i > 0)) goto found;
1998/0901		} if(xrq != nil){ rq = xrq; p = rq->head;
1999/0711		if(p != nil && p->wired == nil)
1998/0901		p->movetime = 0;
1998/0923		goto found;
1998/0901		} } 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;
1996/0315		for(; p; p = p->rnext){
1998/0901		if(p->mp == MACHP(m->machno)
1999/0811		|| p->movetime < MACHP(0)->ticks)
1996/0315		goto found; }
1995/0110		} }
2002/0822		/* remember how much time we're here */
2000/1130		idlehands();
2003/0228		/* remember how much time we're here */
2002/0822		now = perfticks(); m->perf.inidle += now-start; start = now;
2003/0226/sys/src/9/port/proc.c:282,288 – 2003/0228/sys/src/9/port/proc.c:302,308
1991/0420
1995/0110		l = 0; for(p = rq->head; p; p = p->rnext){
2002/0415		if(p->mp == MACHP(m->machno) || p->movetime <= MACHP(0)->ticks)
2003/0228		if(p->mp == MACHP(m->machno) || (!p->wired && i > 0))
1995/0110		break; l = p;
1994/0728		}
2003/0226/sys/src/9/port/proc.c:300,305 – 2003/0228/sys/src/9/port/proc.c:320,327
1995/0110		l->rnext = p->rnext;
1994/0728		else
1995/0110		rq->head = p->rnext;
2003/0228		if(rq->head == nil) runvec &= ~(1<<(rq-runq));
1995/0110		rq->n--; nrdy--; if(p->state != Ready)
2003/0226/sys/src/9/port/proc.c:307,314 – 2003/0228/sys/src/9/port/proc.c:329,334
1995/0110		unlock(runq);
1995/0102
1995/0110		p->state = Scheding;
1995/0811		if(p->mp != MACHP(m->machno))
1999/0811		p->movetime = MACHP(0)->ticks + HZ/10;
1995/0811		p->mp = MACHP(m->machno);
2002/0315
1995/0110		return p;
2003/0226/sys/src/9/port/proc.c:366,378 – 2003/0228/sys/src/9/port/proc.c:386,394
1993/0501		p->kp = 0; p->procctl = 0; p->notepending = 0;
1995/0110		p->mp = 0; p->movetime = 0;
1995/0102		p->wired = 0;
1995/0115		p->ureg = 0;
2001/1117		p->privatemem = 0;
2002/0502		p->noswap = 0;
2002/0328		p->lockwait = nil;
2001/0924		p->errstr = p->errbuf0; p->syserrstr = p->errbuf1; p->errbuf0[0] = '\0';
2003/0226/sys/src/9/port/proc.c:379,385 – 2003/0228/sys/src/9/port/proc.c:395,400
2001/0924		p->errbuf1[0] = '\0';
2002/0404		p->nlocks = 0; p->delaysched = 0;
2002/0415		p->movetime = 0;
2001/0527		kstrdup(&p->user, "*nouser"); kstrdup(&p->text, "*notext"); kstrdup(&p->args, "");
2003/0226/sys/src/9/port/proc.c:394,399 – 2003/0228/sys/src/9/port/proc.c:409,419
1993/0501		if(p->kstack == 0) p->kstack = smalloc(KSTACK);
2003/0228		/* sched params */ p->mp = 0; p->wired = 0; procpriority(p, PriNormal, 0);
2002/0315		p->task = nil;
1993/0501		return p;
2003/0226/sys/src/9/port/proc.c:430,440 – 2003/0228/sys/src/9/port/proc.c:450,477
1999/0711		}
1995/0102		p->wired = MACHP(bm);
1995/0110		p->movetime = 0xffffffff; p->mp = p->wired;
1995/0102		} void
2003/0228		procpriority(Proc *p, int pri, int fixed) { if(pri >= Nrq) pri = Nrq - 1; else if(pri < 0) pri = 0; p->basepri = pri; p->priority = pri; if(fixed){ p->quanta = 0xfffff; p->fixedpri = 1; } else { p->quanta = quanta[pri]; p->fixedpri = 0; } } void
1990/0227		procinit0(void) /* bad planning - clashes with devproc.c */ { Proc *p;
2003/0226/sys/src/9/port/proc.c:967,975 – 2003/0228/sys/src/9/port/proc.c:1004,1012
1995/1030		s = p->psstate; if(s == 0)
2001/0217		s = statename[p->state];
2002/0404		print("%3lud:%10s pc %8lux dbgpc %8lux %8s (%s) ut %ld st %ld bss %lux qpc %lux nl %lud nd %lud lpc %lux\n",
2003/0228		print("%3lud:%10s pc %8lux dbgpc %8lux %8s (%s) ut %ld st %ld bss %lux qpc %lux nl %lud nd %lud lpc %lux pri %lud\n",
1995/1030		p->pid, p->text, p->pc, dbgpc(p), s, statename[p->state],
2002/0404		p->time[0], p->time[1], bss, p->qpc, p->nlocks, p->delaysched, p->lastlock ? p->lastlock->pc : 0);
2003/0228		p->time[0], p->time[1], bss, p->qpc, p->nlocks, p->delaysched, p->lastlock ? p->lastlock->pc : 0, p->priority);
1995/1030		} void
2003/0226/sys/src/9/port/proc.c:1047,1054 – 2003/0228/sys/src/9/port/proc.c:1084,1090
1995/0110		continue;
1998/0825		print("rq%ld:", rq-runq);
1995/0110		for(p = rq->head; p; p = p->rnext)
1998/0825		print(" %lud(%lud, %lud)", p->pid, m->ticks - p->readytime,
1999/0811		MACHP(0)->ticks - p->movetime);
2003/0228		print(" %lud(%lud)", p->pid, m->ticks - p->readytime);
1994/0728		print("\n");
1995/1030		delay(150);
1990/0227		}
2003/0226/sys/src/9/port/proc.c:1083,1090 – 2003/0228/sys/src/9/port/proc.c:1119,1125
1993/0501		p->ureg = 0; p->dbgreg = 0;
1994/0920
1995/0110		p->basepri = PriKproc; p->priority = p->basepri;
2003/0228		procpriority(p, PriKproc, 0);
1990/0227
1993/0501		kprocchild(p, func, arg);
1991/0705