2002/0420/port/edf.c (diff list | history)

port/edf.c on 2002/0315
2002/0315		/* EDF scheduling */ #include "u.h" #include "../port/lib.h" #include "mem.h" #include "dat.h" #include "fns.h" #include "../port/error.h"
2002/0316		#include "../port/devrealtime.h"
2002/0315		#include "../port/edf.h" /* debugging */ int edfprint = 0; #define DPRINT if(edfprint)iprint
2002/0410		char *edfstatename[] = {
2002/0315		[EdfUnused] = "Unused", [EdfExpelled] = "Expelled", [EdfAdmitted] = "Admitted", [EdfIdle] = "Idle", [EdfAwaitrelease] = "Awaitrelease", [EdfReleased] = "Released", [EdfRunning] = "Running", [EdfExtra] = "Extra", [EdfPreempted] = "Preempted", [EdfBlocked] = "Blocked", [EdfDeadline] = "Deadline", };
2002/0410		static Timer deadlinetimer[MAXMACH]; /* Time of next deadline */ static Timer releasetimer[MAXMACH]; /* Time of next release */
2002/0327
2002/0315		static int initialized; static uvlong fasthz; static Ticks now;
2002/0328		QLock edfschedlock;
2002/0315		Lock edflock; Task tasks[Maxtasks]; int ntasks; Resource resources[Maxresources]; int nresources;
2002/0410		int edfstateupdate;
2002/0420		int misseddeadlines;
2002/0315		enum{ Deadline, /* Invariant for schedulability test: Deadline < Release */ Release, }; static int earlierrelease(Task *t1, Task *t2) {return t1->r < t2->r;} static int earlierdeadline(Task *t1, Task *t2) {return t1->d < t2->d;} /* Tasks waiting for release, head earliest release time */ Taskq qwaitrelease = {{0}, nil, earlierrelease}; /* Released tasks waiting to run, head earliest deadline */ Taskq qreleased = {{0}, nil, earlierdeadline}; /* Exhausted EDF tasks, append at end */ Taskq qextratime; /* Running/Preempted EDF tasks, head running, one stack per processor */ Taskq edfstack[MAXMACH];
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315
2002/0410		static void edfresched(Task *t);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0405		static void edfreleaseintr(Ureg *, Timer *cy); static void edfdeadlineintr(Ureg*, Timer*);
2002/0410		static char * edftestschedulability(Task *thetask);
2002/0315		void
2002/0410		edfinit(void)
2002/0315		{
2002/0410		int i;
2002/0315		if (initialized) return; ilock(&edflock); if (initialized){ iunlock(&edflock); return; } fastticks(&fasthz);
2002/0410		for (i = 0; i < conf.nmach; i++){ deadlinetimer[i].f = edfdeadlineintr; deadlinetimer[i].a = &deadlinetimer[i]; deadlinetimer[i].when = 0; releasetimer[i].f = edfreleaseintr; releasetimer[i].a = &releasetimer[i]; releasetimer[i].when = 0; }
2002/0315		initialized = 1; iunlock(&edflock); } int isedf(Proc *p) { return p && p->task && p->task->state >= EdfIdle; } int
2002/0410		edfanyready(void)
2002/0315		{
2002/0411		return edfstack[m->machno].head || qreleased.head;
2002/0315		} static void edfpush(Task *t) { Taskq *q;
2002/0410		DPRINT("%d edfpush, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		q = edfstack + m->machno; assert(t->runq.n || (up && up->task == t)); if (q->head){ assert(q->head->state == EdfRunning); q->head->state = EdfPreempted;
2002/0316		if(devrt) devrt(q->head, now, SPreempt);
2002/0315		} t->rnext = q->head;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0315		q->head = t; } static Task* edfpop(void) { Task *t; Taskq *q;
2002/0322		DPRINT("%d edfpop\n", m->machno);
2002/0315		q = edfstack + m->machno; if (t = q->head){ assert(t->state == EdfRunning); q->head = t->rnext; t->rnext = nil; if (q->head){ assert(q->head->state == EdfPreempted); q->head->state = EdfRunning;
2002/0316		if(devrt) devrt(q->head, now, SRun);
2002/0315		} } return t; } static Task* edfenqueue(Taskq *q, Task *t) { Task *tt, **ttp;
2002/0410		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		t->rnext = nil; if (q->head == nil) { q->head = t; return t; } SET(tt); for (ttp = &q->head; *ttp; ttp = &tt->rnext) { tt = *ttp; if (q->before && q->before(t, tt)) { t->rnext = tt; *ttp = t; break; } } if (*ttp == nil) tt->rnext = t; if (t != q->head) t = nil; return t; } static Task* edfdequeue(Taskq *q) { Task *t;
2002/0322		DPRINT("%d edfdequeue\n", m->machno);
2002/0315		if (t = q->head){ q->head = t->rnext; t->rnext = nil; } return t; }
2002/0327		static Task*
2002/0315		edfqremove(Taskq *q, Task *t) { Task **tp;
2002/0410		DPRINT("%d edfqremove, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		for (tp = &q->head; *tp; tp = &(*tp)->rnext){ if (*tp == t){ *tp = t->rnext;
2002/0327		t = (tp == &q->head) ? q->head : nil; return t;
2002/0315		} }
2002/0328		return nil;
2002/0315		}
2002/0327
2002/0315		void
2002/0327		edfreleasetimer(void) { Task *t;
2002/0328		if ((t = qwaitrelease.head) == nil)
2002/0327		return;
2002/0328		DPRINT("edfreleasetimer clock\n");
2002/0410		if (releasetimer[m->machno].when) timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = t->r; if (releasetimer[m->machno].when <= now) releasetimer[m->machno].when = now; timeradd(&releasetimer[m->machno]);
2002/0327		} void
2002/0410		edfblock(Proc *p)
2002/0315		{ Task *t, *pt; /* The current proc has blocked */ ilock(&edflock); t = p->task;
2002/0320		assert(t); if (t->state != EdfRunning){ /* called by a proc just joining the task */ iunlock(&edflock); return; }
2002/0410		DPRINT("%d edfblock, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		if (t->runq.n){ /* There's another runnable proc in the running task, leave task where it is */ iunlock(&edflock); return; } pt = edfpop(); assert(pt == t); t->state = EdfBlocked;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		iunlock(&edflock); } static void
2002/0410		deadline(Proc *p, SEvent why)
2002/0315		{ Task *t, *nt; /* Task has reached its deadline, lock must be held */
2002/0410		DPRINT("%d deadline, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
2002/0315		SET(nt); if (p){ nt = p->task;
2002/0321		if (nt == nil || nt->state != EdfRunning) return;
2002/0315		} t = edfpop(); if(p != nil && nt != t){
2002/0410		iprint("deadline, %s, %d\n", edfstatename[p->task->state], p->task->runq.n);
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0410		if (deadlinetimer[m->machno].when){ timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0327		}
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0410		edfresched(t);
2002/0315		} void
2002/0410		edfdeadline(Proc *p)
2002/0315		{
2002/0410		DPRINT("%d edfdeadline\n", m->machno);
2002/0315		/* Task has reached its deadline */ ilock(&edflock); now = fastticks(nil);
2002/0410		deadline(p, SYield);
2002/0315		iunlock(&edflock); } char *
2002/0410		edfadmit(Task *t)
2002/0315		{ char *err; if (t->state != EdfExpelled) return "task state"; /* should never happen */
2002/0316		/* simple sanity checks */ if (t->T == 0) return "T not set"; if (t->C == 0) return "C not set"; if (t->D > t->T) return "D > T"; if (t->D == 0) /* if D is not set, set it to T */ t->D = t->T; if (t->C > t->D) return "C > D";
2002/0315		qlock(&edfschedlock);
2002/0410		if (err = edftestschedulability(t)){
2002/0315		qunlock(&edfschedlock); return err; } ilock(&edflock);
2002/0410		DPRINT("%d edfadmit, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); t->state = EdfAdmitted;
2002/0316		if(devrt) devrt(t, t->d, SAdmit);
2002/0315		if (up->task == t){
2002/0410		DPRINT("%d edfadmitting self\n", m->machno);
2002/0315		/* Admitting self, fake reaching deadline */ t->r = now; t->t = now + t->T; t->d = now + t->D;
2002/0316		if(devrt) devrt(t, t->d, SDeadline);
2002/0315		t->S = t->C; t->scheduled = now; t->state = EdfRunning;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0320		setdelta();
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0410		if (deadlinetimer[m->machno].when) timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = t->d; timeradd(&deadlinetimer[m->machno]);
2002/0315		}else{ if (t->runq.n){ if (edfstack[m->machno].head == nil){ t->state = EdfAdmitted; t->r = now;
2002/0410		edfrelease(t);
2002/0320		setdelta();
2002/0410		edfresched(t);
2002/0315		} } } iunlock(&edflock); qunlock(&edfschedlock); return nil; } void
2002/0410		edfexpel(Task *t)
2002/0315		{ Task *tt; qlock(&edfschedlock); ilock(&edflock);
2002/0410		DPRINT("%d edfexpel, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		now = fastticks(nil); switch(t->state){ case EdfUnused: case EdfExpelled: /* That was easy */ iunlock(&edflock); qunlock(&edfschedlock); return; case EdfAdmitted: case EdfIdle: /* Just reset state */ break; case EdfAwaitrelease:
2002/0327		if (edfqremove(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; case EdfReleased: edfqremove(&qreleased, t); break; case EdfRunning: /* Task must be expelling itself */ tt = edfpop(); assert(t == tt); break; case EdfExtra: edfqremove(&qextratime, t); break; case EdfPreempted: edfqremove(edfstack + m->machno, t); break; case EdfBlocked: case EdfDeadline: break; } t->state = EdfExpelled;
2002/0316		if(devrt) devrt(t, now, SExpel);
2002/0320		setdelta();
2002/0315		iunlock(&edflock); qunlock(&edfschedlock); return; } static void
2002/0405		edfreleaseintr(Ureg*, Timer*)
2002/0315		{
2002/0327		Task *t;
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0410		timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting) return; ilock(&edflock);
2002/0328		now = fastticks(nil);
2002/0327		while((t = qwaitrelease.head) && t->r <= now){ /* There's something waiting to be released and its time has come */ edfdequeue(&qwaitrelease);
2002/0328		edfreleasetimer();
2002/0410		edfrelease(t);
2002/0327		} iunlock(&edflock); sched(); splhi(); } static void
2002/0405		edfdeadlineintr(Ureg*, Timer*)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0315		Ticks used; Task *t;
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0410		timerdel(&deadlinetimer[m->machno]); deadlinetimer[m->machno].when = 0;
2002/0328
2002/0327		if(active.exiting) return; ilock(&edflock);
2002/0315		// If up is not set, we're running inside the scheduler // for non-real-time processes. if (up && isedf(up)) {
2002/0328		now = fastticks(nil);
2002/0315		t = up->task; assert(t->scheduled > 0); used = now - t->scheduled; t->scheduled = now; if (t->r < now){ if (t->S <= used) t->S = 0LL; else t->S -= used; if (t->d <= now || t->S == 0LL){ /* Task has reached its deadline/slice, remove from queue */
2002/0420		if (t->S > 0LL) misseddeadlines++;
2002/0410		deadline(up, SSlice);
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d) break;
2002/0410		deadline(nil, SSlice);
2002/0315		} } } } iunlock(&edflock); sched(); splhi(); } void
2002/0410		edfbury(Proc *p)
2002/0315		{ Task *t; Proc **pp;
2002/0410		DPRINT("%d edfbury\n", m->machno);
2002/0315		ilock(&edflock); now = fastticks(nil); if ((t = p->task) == nil){ /* race condition? */ iunlock(&edflock);
2002/0322		DPRINT("%d edf bury race, pid %lud\n", m->machno, p->pid);
2002/0315		return; } assert(edfstack[m->machno].head == t); for (pp = t->procs; pp < t->procs + nelem(t->procs); pp++) if (*pp == p){ t->nproc--; *pp = nil; } if (t->runq.head == nil){ edfpop(); t->state = EdfBlocked; } if (t->nproc == 0){ assert(t->runq.head == nil); t->state = EdfIdle; }
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		p->task = nil; iunlock(&edflock); } void
2002/0410		edfready(Proc *p)
2002/0315		{ Task *t; ilock(&edflock);
2002/0410		DPRINT("%d edfready, %s, %d\n", m->machno, edfstatename[p->task->state], p->task->runq.n);
2002/0315		if ((t = p->task) == nil){ /* Must be a race */ iunlock(&edflock);
2002/0322		DPRINT("%d edf ready race, pid %lud\n", m->machno, p->pid);
2002/0315		return; } p->rnext = 0; p->readytime = m->ticks; p->state = Ready; t->runq.n++; if(t->runq.tail){ t->runq.tail->rnext = p; t->runq.tail = p; }else{ t->runq.head = p; t->runq.tail = p; /* first proc to become runnable in this task */ now = fastticks(nil);
2002/0410		edfresched(t);
2002/0315		} iunlock(&edflock); } static void
2002/0410		edfresched(Task *t)
2002/0315		{ Task *xt;
2002/0410		DPRINT("%d edfresched, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		if (t->nproc == 0){ /* No member processes */ if (t->state > EdfIdle){ t->state = EdfIdle;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} return; } if (t->runq.n == 0 && (up == nil || up->task != t)){ /* Member processes but none runnable */
2002/0410		DPRINT("%d edfresched, nothing runnable\n", m->machno);
2002/0315		if (t->state == EdfRunning) edfpop(); if (t->state >= EdfIdle && t->state != EdfBlocked){ t->state = EdfBlocked;
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		} return; } /* There are runnable processes */ switch (t->state){ case EdfUnused:
2002/0322		iprint("%d attempt to schedule unused task\n", m->machno);
2002/0315		case EdfExpelled: return; /* Not admitted */ case EdfIdle: /* task was idle, schedule release now or later */ if (t->r < now){ if (t->t < now) t->t = now + t->T; t->r = t->t; }
2002/0410		edfrelease(t);
2002/0315		break; case EdfAwaitrelease: case EdfReleased: case EdfExtra: case EdfPreempted: /* dealt with by timer */ break; case EdfAdmitted: /* test whether task can be started */ if (edfstack[m->machno].head != nil){ return; } /* fall through */ case EdfRunning: if (t->r <= now){ if (t->t < now){
2002/0410		DPRINT("%d edfresched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; xt = edfpop(); assert(xt == t);
2002/0410		edfrelease(t);
2002/0315		return; } if (now < t->d){ if (t->S > 0){
2002/0410		DPRINT("%d edfresched, resume\n", m->machno);
2002/0315		/* Running, not yet at deadline, leave it */ return; }else t->d = now; } /* Released, but deadline is past, release at t->t */ t->r = t->t; } xt = edfpop(); assert(xt == t);
2002/0328		t->state = EdfAwaitrelease; if (edfenqueue(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; case EdfBlocked: case EdfDeadline: if (t->r <= now){ if (t->t < now){
2002/0410		DPRINT("%d edfresched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now;
2002/0410		edfrelease(t);
2002/0315		return; } if (now < t->d && (t->flags & Useblocking) == 0){ if (t->S > 0){
2002/0410		DPRINT("%d edfresched, resume\n", m->machno);
2002/0315		/* Released, not yet at deadline, release (again) */ t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SResume);
2002/0315		return; }else t->d = now; } /* Released, but deadline is past, release at t->t */ t->r = t->t; }
2002/0328		t->state = EdfAwaitrelease; if (edfenqueue(&qwaitrelease, t)) edfreleasetimer();
2002/0315		break; } } void
2002/0410		edfrelease(Task *t)
2002/0315		{
2002/0410		DPRINT("%d edfrelease, %s, %d\n", m->machno, edfstatename[t->state], t->runq.n);
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); t->t = t->r + t->T; t->d = t->r + t->D;
2002/0316		if(devrt) devrt(t, t->d, SDeadline);
2002/0315		t->S = t->C; t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		} Proc *
2002/0410		edfrunproc(void)
2002/0315		{ /* Return an edf proc to run or nil */
2002/0410		Task *t, *nt, *xt;
2002/0315		Proc *p;
2002/0327		Ticks when;
2002/0315		static ulong nilcount;
2002/0410		int i;
2002/0315
2002/0411		if (edfstack[m->machno].head == nil && qreleased.head== nil){ // quick way out nilcount++; return nil; }
2002/0315		/* Figure out if the current proc should be preempted*/ ilock(&edflock); now = fastticks(nil); /* first candidate is at the top of the stack of running procs */ t = edfstack[m->machno].head; /* check out head of the release queue for a proc with a better deadline */ nt = qreleased.head; if (t == nil && nt == nil){ nilcount++; iunlock(&edflock); return nil; }
2002/0410		DPRINT("edfrunproc %lud\n", nilcount);
2002/0320		if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
2002/0410		if (conf.nmach > 1){ for (i = 0; i < conf.nmach; i++){ if (i == m->machno) continue; xt = edfstack[i].head; if (xt && xt->Delta <= nt->D){ DPRINT("%d edfrunproc: interprocessor conflict, run current\n", m->machno); if (t) goto runt; nilcount++; iunlock(&edflock); return nil; } } }
2002/0315		/* released task is better than current */
2002/0410		DPRINT("%d edfrunproc: released\n", m->machno);
2002/0315		edfdequeue(&qreleased); assert(nt->runq.n >= 1); edfpush(nt); nt->state = EdfRunning; t = nt; t->scheduled = now; }else{
2002/0410		DPRINT("%d edfrunproc: current\n", m->machno);
2002/0315		}
2002/0410		runt:
2002/0315		assert (t->runq.n); /* Get first proc off t's run queue * No need to lock runq, edflock always held to access runq */ t->state = EdfRunning; p = t->runq.head; if ((t->runq.head = p->rnext) == nil) t->runq.tail = nil; t->runq.n--; p->state = Scheding; if(p->mp != MACHP(m->machno)) p->movetime = MACHP(0)->ticks + HZ/10; p->mp = MACHP(m->machno);
2002/0327		when = now + t->S; if (t->d < when) when = t->d;
2002/0328		if (when < now){
2002/0410		DPRINT("%d edftimer: %T too late\n", m->machno, ticks2time(now-when));
2002/0328		when = now; }
2002/0410		if (deadlinetimer[m->machno].when){ if(deadlinetimer[m->machno].when == when){
2002/0327		iunlock(&edflock); return p; }
2002/0410		timerdel(&deadlinetimer[m->machno]);
2002/0327		}
2002/0410		deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]);
2002/0315		iunlock(&edflock); return p; } /* Schedulability testing and its supporting routines */ static void
2002/0320		setdelta(void)
2002/0315		{ Resource *r, **rr; Task **tt, *t; for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue;
2002/0320		r->Delta = ~0LL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
2002/0320		if (*tt && (*tt)->D < r->Delta) r->Delta = (*tt)->D;
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){ if (t->state < EdfIdle) continue;
2002/0320		t->Delta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
2002/0320		if (*rr && (*rr)->Delta < t->Delta) t->Delta = (*rr)->Delta;
2002/0315		} } static void
2002/0320		testdelta(Task *thetask)
2002/0315		{ Resource *r, **rr; Task **tt, *t; for (r = resources; r < resources + nelem(resources); r++){ if (r->name == nil) continue;
2002/0320		r->testDelta = ~0ULL;
2002/0315		for (tt = r->tasks; tt < r->tasks + nelem(r->tasks); tt++)
2002/0320		if (*tt && (*tt)->D < r->testDelta) r->testDelta = (*tt)->D;
2002/0315		} for (t = tasks; t < tasks + nelem(tasks); t++){ if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		t->testDelta = t->D;
2002/0315		for (rr = t->res; rr < t->res + nelem(t->res); rr++)
2002/0320		if (*rr && (*rr)->testDelta < t->testDelta) t->testDelta = (*rr)->testDelta;
2002/0315		} } static Ticks blockcost(Ticks ticks, Task *thetask) { Task *t; Ticks Cb; Cb = 0; for (t = tasks; t < tasks + Maxtasks; t++){ if (t->state <= EdfExpelled && t != thetask) continue;
2002/0320		if (t->testDelta <= ticks && ticks < t->D && Cb < t->C)
2002/0315		Cb = t->C; } return Cb; } static Task *qschedulability; static void testenq(Task *t) { Task *tt, **ttp; t->testnext = nil; if (qschedulability == nil) { qschedulability = t; return; } SET(tt); for (ttp = &qschedulability; *ttp; ttp = &tt->testnext) { tt = *ttp; if (t->testtime < tt->testtime || (t->testtime == tt->testtime && t->testtype < tt->testtype)){ t->testnext = tt; *ttp = t; return; } } assert(tt->testnext == nil); tt->testnext = t; } static char *
2002/0410		edftestschedulability(Task *thetask)
2002/0315		{ Task *t; Ticks H, G, Cb, ticks; int steps; /* initialize */
2002/0320		testdelta(thetask);
2002/0315		if (thetask && (thetask->flags & Verbose)) pprint("schedulability test\n"); qschedulability = nil; for (t = tasks; t < tasks + Maxtasks; t++){ if (t->state <= EdfExpelled && t != thetask) continue; t->testtype = Release; t->testtime = 0; if (thetask && (thetask->flags & Verbose)) pprint("\tInit: enqueue task %lud\n", t - tasks); testenq(t); } H=0; G=0; for(steps = 0; steps < Maxsteps; steps++){ t = qschedulability; qschedulability = t->testnext; ticks = t->testtime; switch (t->testtype){ case Deadline: H += t->C; Cb = blockcost(ticks, thetask); if (thetask && (thetask->flags & Verbose)) pprint("\tStep %3d, Ticks %T, task %lud, deadline, H += %T → %T, Cb = %T\n", steps, ticks2time(ticks), t - tasks, ticks2time(t->C), ticks2time(H), ticks2time(Cb)); if (H+Cb>ticks) return "not schedulable"; t->testtime += t->T - t->D; t->testtype = Release; testenq(t); break; case Release: if (thetask && (thetask->flags & Verbose)) pprint("\tStep %3d, Ticks %T, task %lud, release, G %T, C%T\n", steps, ticks2time(ticks), t - tasks, ticks2time(t->C), ticks2time(G)); if(ticks && G <= ticks) return nil; G += t->C; t->testtime += t->D; t->testtype = Deadline; testenq(t); break; default: assert(0); } } return "probably not schedulable"; } static uvlong uvmuldiv(uvlong x, ulong num, ulong den) { /* multiply, then divide, avoiding overflow */ uvlong hi; hi = (x & 0xffffffff00000000LL) >> 32; x &= 0xffffffffLL; hi *= num; return (x*num + (hi%den << 32)) / den + (hi/den << 32); } Time ticks2time(Ticks ticks) { assert(ticks >= 0);
2002/0320		if (fasthz == 0) fastticks(&fasthz);
2002/0315		return uvmuldiv(ticks, Onesecond, fasthz); } Ticks time2ticks(Time time) { assert(time >= 0); return uvmuldiv(time, fasthz, Onesecond); }