2002/1218/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/1119		#include "realtime.h" #include "../port/edf.h"
2002/0315		/* 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 Ticks now;
2002/0831		/* Edfschedlock protects modification of sched params, including resources */
2002/0328		QLock edfschedlock;
2002/0315		Lock edflock;
2002/0831		Head tasks; Head resources;
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;}
2002/0704		static void edfrelease(Task *t);
2002/0315		/* 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/0927		static Task *qschedulability;
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315
2002/1001		static void edfresched(Task*);
2002/0320		static void setdelta(void);
2002/1001		static void testdelta(Task*); static void edfreleaseintr(Ureg*, Timer*);
2002/0405		static void edfdeadlineintr(Ureg*, Timer*);
2002/1001		static char * edftestschedulability(Task*); static void resrelease(Task*);
2002/0315
2002/0704		static void
2002/0410		edfinit(void)
2002/0315		{
2002/0410		int i;
2002/0315		if (initialized) return; ilock(&edflock); if (initialized){ iunlock(&edflock); return; }
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); }
2002/0704		static int
2002/0315		isedf(Proc *p) { return p && p->task && p->task->state >= EdfIdle; }
2002/0704		static 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		releasetimer[m->machno].when = t->r; if (releasetimer[m->machno].when <= now) releasetimer[m->machno].when = now; timeradd(&releasetimer[m->machno]);
2002/0327		}
2002/0704		static 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;
2002/0503		Ticks used;
2002/0315		/* 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/0503		used = now - t->scheduled; t->S -= used; t->scheduled = now; t->total += used; t->aged = (t->aged*31 + t->C - t->S) >> 5;
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0410		edfresched(t);
2002/0315		}
2002/0704		static 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); }
2002/0704		static char *
2002/0410		edfadmit(Task *t)
2002/0315		{
2002/0927		char *err, *p; static char csndump[512]; CSN *c;
2002/0315
2002/0831		/* Called with edfschedlock held */
2002/0315		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/0927		resourcetimes(t, &t->csns); DEBUG("task %d: T %T, C %T, D %T, tΔ %T\n", t->taskno, ticks2time(t->T), ticks2time(t->C), ticks2time(t->D), ticks2time(t->testDelta)); p = seprintresources(csndump, csndump+sizeof csndump); seprintcsn(p, csndump+sizeof csndump, &t->csns); DEBUG("%s\n", csndump);
2002/0410		if (err = edftestschedulability(t)){
2002/0315		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/0503		t->periods++;
2002/0316		if(devrt) devrt(t, now, SRun);
2002/0320		setdelta();
2002/0927		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ DEBUG("admit csn: C=%T\n", ticks2time(c->C)); c->S = c->C; }
2002/0315		assert(t->runq.n > 0 || (up && up->task == t)); edfpush(t);
2002/0410		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); return nil; }
2002/0704		static void
2002/0410		edfexpel(Task *t)
2002/0315		{ Task *tt;
2002/0831		/* Called with edfschedlock held */
2002/0315		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); 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); return; } static void
2002/0405		edfreleaseintr(Ureg*, Timer*)
2002/0315		{
2002/0327		Task *t;
2002/0927		extern int panicking;
2002/0327
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0410		timerdel(&releasetimer[m->machno]); releasetimer[m->machno].when = 0;
2002/0328
2002/0927		if(panicking || active.exiting)
2002/0327		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/1001		edfdeadlineintr(Ureg*, Timer *timer)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0315		Ticks used; Task *t;
2002/0927		Resource *r; char buf[128]; int noted; extern int panicking;
2002/0315
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/1001		if (timer) timer->when = 0;
2002/0328
2002/0927		if(panicking || active.exiting)
2002/0327		return; ilock(&edflock);
2002/0315		// If up is not set, we're running inside the scheduler
2002/0927		// for non-real-time processes. noted = 0;
2002/0315		if (up && isedf(up)) {
2002/0328		now = fastticks(nil);
2002/0315		t = up->task;
2002/1218		assert(t->state == EdfRunning);
2002/0315		assert(t->scheduled > 0); used = now - t->scheduled; t->scheduled = now;
2002/0503		t->total += used;
2002/0315		if (t->r < now){
2002/0927		if (t->curcsn){ if (t->curcsn->S <= used){ t->curcsn->S = 0LL;
2002/1001		resrelease(t);
2002/0927		r = t->curcsn->i; noted++; snprint(buf, sizeof buf, "sys: deadline miss: resource %s", r->name); }else t->curcsn->S -= used; } if (t->S <= used){
2002/0315		t->S = 0LL;
2002/0927		if (!noted){ noted++; snprint(buf, sizeof buf, "sys: deadline miss: runtime"); } }else
2002/0315		t->S -= used;
2002/0927		if (t->d <= now || t->S == 0LL || t->curcsn == 0LL){
2002/0315		/* Task has reached its deadline/slice, remove from queue */
2002/0503		if (t->d <= now){ t->missed++;
2002/0420		misseddeadlines++;
2002/0503		}
2002/0410		deadline(up, SSlice);
2002/0927
2002/0315		while (t = edfstack[m->machno].head){ if (now < t->d) break;
2002/0410		deadline(nil, SSlice);
2002/0315		} } } } iunlock(&edflock);
2002/0927		if (noted) postnote(up, 1, buf, NUser);
2002/0315		sched(); splhi(); }
2002/0704		static void
2002/0410		edfbury(Proc *p)
2002/0315		{ Task *t;
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);
2002/0831		delist(&t->procs, p);
2002/0315		if (t->runq.head == nil){ edfpop(); t->state = EdfBlocked; }
2002/0831		if (t->procs.n == 0){
2002/0315		assert(t->runq.head == nil); t->state = EdfIdle; }
2002/0316		if(devrt) devrt(t, now, SBlock);
2002/0315		p->task = nil; iunlock(&edflock); }
2002/0704		static 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/0831		if (t->procs.n == 0){
2002/0315		/* 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; } }
2002/0704		static void
2002/0410		edfrelease(Task *t)
2002/0315		{
2002/0927		CSN *c;
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;
2002/0927		for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ DEBUG("release csn: C=%T\n", ticks2time(c->C)); c->S = c->C; }
2002/0315		t->state = EdfReleased; edfenqueue(&qreleased, t);
2002/0316		if(devrt) devrt(t, now, SRelease);
2002/0315		}
2002/0704		static 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/1217
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);
2002/1217		assert(nt->runq.n >= 1 || (up && up->task == nt));
2002/0315		edfpush(nt); 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;
2002/0503		t->periods++;
2002/0315		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/1218		if(deadlinetimer[m->machno].when == when){ iunlock(&edflock); return p;
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		{
2002/0831		Resource *r; Task *t;
2002/0927		int R; List *lr, *l; TaskLink *lt; CSN *c;
2002/0315
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0927		r->Delta = Infinity; R = 1; for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
2002/0831		t = lt->i; assert(t);
2002/0927		if (t->D < r->Delta){
2002/0831		r->Delta = t->D;
2002/0927		} if (lt->R == 0){ R = 0; }
2002/0831		}
2002/0927		if (R) r->Delta = Infinity; /* Read-only resource, no exclusion */
2002/0315		}
2002/0927		/* Enumerate the critical sections */ for (l = tasks.next; l ; l = l->next){ t = l->i;
2002/0831		assert(t);
2002/0927		if (t->state <= EdfExpelled)
2002/0315		continue;
2002/0927		t->Delta = Infinity; for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ r = c->i;
2002/0831		assert(r);
2002/0927		c->Delta = r->Delta; if (c->p && c->p->Delta < c->Delta) c->Delta = c->p->Delta; if (c->C == t->C && r->Delta < t->Delta)
2002/0831		t->Delta = r->Delta; }
2002/0315		} } static void
2002/0320		testdelta(Task *thetask)
2002/0315		{
2002/0831		Resource *r; Task *t;
2002/0927		int R; List *lr, *l; TaskLink *lt; CSN *c;
2002/0315
2002/0831		for (lr = resources.next; lr; lr = lr->next){ r = lr->i; assert(r);
2002/0927		DEBUG("Resource %s: ", r->name); r->testDelta = Infinity; R = 1; for (lt = (TaskLink*)r->tasks.next; lt; lt = (TaskLink*)lt->next){
2002/0831		t = lt->i; assert(t);
2002/0927		if (t->D < r->testDelta){
2002/0831		r->testDelta = t->D;
2002/0927		DEBUG("%d→%T ", t->taskno, ticks2time(t->D)); } if (lt->R == 0){ DEBUG("%d→X ", t->taskno); R = 0; }
2002/0831		}
2002/0927		if (R) r->testDelta = Infinity; /* Read-only resource, no exclusion */ DEBUG("tΔ = %T\n", ticks2time(r->testDelta));
2002/0315		}
2002/0927		/* Enumerate the critical sections */ for (l = tasks.next; l ; l = l->next){ t = l->i;
2002/0831		assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue;
2002/0927		t->testDelta = Infinity; for (c = (CSN*)t->csns.next; c; c = (CSN*)c->next){ r = c->i;
2002/0831		assert(r);
2002/0927		c->testDelta = r->testDelta; if (c->p && c->p->testDelta < c->testDelta) c->testDelta = c->p->testDelta; if (c->C == t->C && r->testDelta < t->testDelta)
2002/0831		t->testDelta = r->testDelta;
2002/0927		DEBUG("Task %d Resource %s: tΔ = %T\n", t->taskno, r->name, ticks2time(r->testDelta));
2002/0831		}
2002/0315		} } static Ticks
2002/0927		blockcost(Ticks ticks, Task *task, Task *thetask)
2002/0315		{
2002/0927		Ticks Cb, Cbt; List *l; Resource *r; CSN *c, *lc; int R;
2002/0315		Task *t; Cb = 0;
2002/0927		/* for each resource in task t, find all CSNs that refer to the * resource. If their Δ <= ticks < D and c->C > current CB * Cb = c->C */ DEBUG("blockcost task %d: ", task->taskno); for (c = (CSN*)task->csns.next; c; c = (CSN*)c->next){ r = c->i; assert(r); DEBUG("%s ", r->name); Cbt = Cb; R = 1; /* R == 1: resource is only used in read-only mode */ for (l = tasks.next; l; l = l->next){ t = l->i; if (t->state <= EdfExpelled && t != thetask) continue; /* csn belongs to an irrelevant task */ for (lc = (CSN*)t->csns.next; lc; lc = (CSN*)lc->next){ if (lc->i != r) continue; /* wrong resource */ if (lc->R == 0) R = 0; /* Resource is used in exclusive mode */ DEBUG("(%T≤%T<%T: %T) ", ticks2time(lc->testDelta), ticks2time(ticks), ticks2time(t->D), ticks2time(lc->C)); if (lc->testDelta <= ticks && ticks < t->D && Cbt < lc->C) Cbt = lc->C; } } if (R == 0){ DEBUG("%T, ", ticks2time(Cbt)); Cb = Cbt; } DEBUG("ro, ");
2002/0315		}
2002/0927		DEBUG("Cb = %T\n", ticks2time(Cb));
2002/0315		return Cb; } 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;
2002/0831		List *l;
2002/0315		/* initialize */
2002/0320		testdelta(thetask);
2002/0315		if (thetask && (thetask->flags & Verbose))
2002/0927		pprint("schedulability test for task %d\n", thetask->taskno);
2002/0315		qschedulability = nil;
2002/0831		for (l = tasks.next; l; l = l->next){ t = l->i; assert(t);
2002/0315		if (t->state <= EdfExpelled && t != thetask) continue; t->testtype = Release; t->testtime = 0; if (thetask && (thetask->flags & Verbose))
2002/0927		pprint("\tInit: enqueue task %d\n", t->taskno);
2002/0315		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;
2002/0927		Cb = blockcost(ticks, t, thetask);
2002/0315		if (thetask && (thetask->flags & Verbose))
2002/0927		pprint("\tStep %3d, Ticks %T, task %d, deadline, H += %T → %T, Cb = %T\n",
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(H), ticks2time(Cb));
2002/0927		if (H+Cb>ticks){ if (thetask && (thetask->flags & Verbose)) pprint("task %d not schedulable: H=%T + Cb=%T > ticks=%T\n", thetask->taskno, ticks2time(H), ticks2time(Cb), ticks2time(ticks));
2002/0315		return "not schedulable";
2002/0927		}
2002/0315		t->testtime += t->T - t->D; t->testtype = Release; testenq(t); break; case Release: if (thetask && (thetask->flags & Verbose))
2002/0927		pprint("\tStep %3d, Ticks %T, task %d, release, G %T, C%T\n",
2002/0831		steps, ticks2time(ticks), t->taskno,
2002/0315		ticks2time(t->C), ticks2time(G));
2002/0927		if(ticks && G <= ticks){ if (thetask && (thetask->flags & Verbose)) pprint("task %d schedulable: G=%T <= ticks=%T\n", thetask->taskno, ticks2time(G), ticks2time(ticks));
2002/0315		return nil;
2002/0927		}
2002/0315		G += t->C; t->testtime += t->D; t->testtype = Deadline; testenq(t); break; default: assert(0); } } return "probably not schedulable"; }
2002/0927		static void resacquire(Task *t, CSN *c)
2002/0315		{
2002/0927		Ticks now, when, used;
2002/0315
2002/0927		now = fastticks(nil); used = now - t->scheduled; t->scheduled = now; t->total += used; t->S -= used; if (t->curcsn) t->curcsn->S -= used; when = now + c->S; if (when < deadlinetimer[m->machno].when){ deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]); } t->Delta = c->Delta; t->curcsn = c;
2002/1001		if(devrt) devrt(t, now, SResacq);
2002/0927		/* priority is going up, no need to reschedule */
2002/0315		}
2002/0927		static void resrelease(Task *t)
2002/0315		{
2002/0927		Ticks now, when, used; CSN *c;
2002/0315
2002/0927		c = t->curcsn; assert(c); t->curcsn = c->p; now = fastticks(nil); used = now - t->scheduled; t->scheduled = now; t->total += used; t->S -= used; c->S -= used; if (now + t->S > t->d) when = t->d; else when = now + t->S; if (t->curcsn){ t->curcsn->S -= c->S; /* the sins of the fathers shall be visited upon the children */ t->Delta = t->curcsn->Delta; if (when > now + t->curcsn->S) when = now + t->curcsn->S; }else t->Delta = Infinity; c->S = 0LL; /* don't allow reuse */
2002/1001		if(devrt) devrt(t, now, SResrel);
2002/0927		deadlinetimer[m->machno].when = when; timeradd(&deadlinetimer[m->machno]); qunlock(&edfschedlock); sched(); /* reschedule */ qlock(&edfschedlock);
2002/0315		}
2002/0704		Edfinterface realedf = { .isedf = isedf, .edfbury = edfbury, .edfanyready = edfanyready, .edfready = edfready, .edfrunproc = edfrunproc, .edfblock = edfblock, .edfinit = edfinit, .edfexpel = edfexpel, .edfadmit = edfadmit, .edfdeadline = edfdeadline,
2002/0927		.resacquire = resacquire, .resrelease = resrelease,
2002/0704		};