2002/0330/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 char *edf_statename[] = { [EdfUnused] = "Unused", [EdfExpelled] = "Expelled", [EdfAdmitted] = "Admitted", [EdfIdle] = "Idle", [EdfAwaitrelease] = "Awaitrelease", [EdfReleased] = "Released", [EdfRunning] = "Running", [EdfExtra] = "Extra", [EdfPreempted] = "Preempted", [EdfBlocked] = "Blocked", [EdfDeadline] = "Deadline", };
2002/0327		static Cycintr cycdeadline; /* Time of next deadline */ static Cycintr cycrelease; /* Time of next release */
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; int edf_stateupdate; 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; /* Tasks admitted waiting for first release */ Taskq qadmit; /* Running/Preempted EDF tasks, head running, one stack per processor */ Taskq edfstack[MAXMACH];
2002/0316		void (*devrt)(Task*, Ticks, int);
2002/0315		static void edf_resched(Task *t);
2002/0320		static void setdelta(void); static void testdelta(Task *thetask);
2002/0315		static char * edf_testschedulability(Task *thetask);
2002/0328		static void edfreleaseintr(Ureg *, Cycintr *cy); static void edfdeadlineintr(Ureg*, Cycintr*);
2002/0315		void edf_init(void) { if (initialized) return; ilock(&edflock); if (initialized){ iunlock(&edflock); return; } fastticks(&fasthz);
2002/0327		cycdeadline.f = edfdeadlineintr; cycdeadline.a = &cycdeadline; cycdeadline.when = 0; cycrelease.f = edfreleaseintr; cycrelease.a = &cycrelease; cycrelease.when = 0;
2002/0315		initialized = 1; iunlock(&edflock); } int isedf(Proc *p) { return p && p->task && p->task->state >= EdfIdle; } int edf_anyready(void) { /* If any edf tasks (with runnable procs in them) are released, * at least one of them must be on the stack */ return edfstack[m->machno].head != nil; } static void edfpush(Task *t) { Taskq *q;
2002/0322		DPRINT("%d edfpush, %s, %d\n", m->machno, edf_statename[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/0322		DPRINT("%d edfenqueue, %s, %d\n", m->machno, edf_statename[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/0322		DPRINT("%d edfqremove, %s, %d\n", m->machno, edf_statename[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"); if (cycrelease.when)
2002/0327		cycintrdel(&cycrelease); cycrelease.when = t->r;
2002/0328		if (cycrelease.when <= now)
2002/0327		cycrelease.when = now; cycintradd(&cycrelease); clockintrsched(); } void
2002/0315		edf_block(Proc *p) { 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/0322		DPRINT("%d edf_block, %s, %d\n", m->machno, edf_statename[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 edfdeadline(Proc *p, SEvent why) { Task *t, *nt; /* Task has reached its deadline, lock must be held */
2002/0322		DPRINT("%d edfdeadline, %s, %d\n", m->machno, edf_statename[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/0320		iprint("edfdeadline, %s, %d\n", edf_statename[p->task->state], p->task->runq.n);
2002/0315		iunlock(&edflock); assert(0 && p == nil || nt == t); }
2002/0327		if (cycdeadline.when){ cycintrdel(&cycdeadline); cycdeadline.when = 0; clockintrsched(); }
2002/0315		t->d = now; t->state = EdfDeadline;
2002/0316		if(devrt) devrt(t, now, why);
2002/0315		edf_resched(t); } void edf_deadline(Proc *p) {
2002/0322		DPRINT("%d edf_deadline\n", m->machno);
2002/0315		/* Task has reached its deadline */ ilock(&edflock); now = fastticks(nil); edfdeadline(p, SYield); iunlock(&edflock); } char * edf_admit(Task *t) { 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); if (err = edf_testschedulability(t)){ qunlock(&edfschedlock); return err; } ilock(&edflock);
2002/0322		DPRINT("%d edf_admit, %s, %d\n", m->machno, edf_statename[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/0322		DPRINT("%d edf_admitting 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); }else{ if (t->runq.n){ if (edfstack[m->machno].head == nil){ t->state = EdfAdmitted; t->r = now; edf_release(t);
2002/0320		setdelta();
2002/0315		edf_resched(t); }else{ edfenqueue(&qadmit, t); } } } iunlock(&edflock); qunlock(&edfschedlock); return nil; } void edf_expel(Task *t) { Task *tt; qlock(&edfschedlock); ilock(&edflock);
2002/0322		DPRINT("%d edf_expel, %s, %d\n", m->machno, edf_statename[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/0328		edfreleaseintr(Ureg*, Cycintr*)
2002/0315		{
2002/0327		Task *t;
2002/0328		DPRINT("%d edfreleaseintr\n", m->machno);
2002/0327
2002/0330		cycintrdel(&cycrelease);
2002/0328		cycrelease.when = 0;
2002/0330		clockintrsched();
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/0327		edf_release(t); } iunlock(&edflock); sched(); splhi(); } static void
2002/0328		edfdeadlineintr(Ureg*, Cycintr*)
2002/0327		{
2002/0328		/* Task reached deadline */
2002/0315		Ticks used; Task *t;
2002/0327		DPRINT("%d edfdeadlineintr\n", m->machno);
2002/0330		cycintrdel(&cycdeadline);
2002/0328		cycdeadline.when = 0;
2002/0330		clockintrsched();
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 */ edfdeadline(up, SSlice); while (t = edfstack[m->machno].head){ if (now < t->d) break; edfdeadline(nil, SSlice); } } }
2002/0329		if (up->nlocks) iprint("have %lud locks at deadline\n", up->nlocks);
2002/0315		} iunlock(&edflock); sched(); splhi(); } void edf_bury(Proc *p) { Task *t; Proc **pp;
2002/0322		DPRINT("%d edf_bury\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 edf_ready(Proc *p) { Task *t; ilock(&edflock);
2002/0322		DPRINT("%d edf_ready, %s, %d\n", m->machno, edf_statename[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); edf_resched(t); } iunlock(&edflock); } static void edf_resched(Task *t) { Task *xt;
2002/0322		DPRINT("%d edf_resched, %s, %d\n", m->machno, edf_statename[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/0322		DPRINT("%d edf_resched, 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; } edf_release(t); 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/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; xt = edfpop(); assert(xt == t); edf_release(t); return; } if (now < t->d){ if (t->S > 0){
2002/0322		DPRINT("%d edf_resched, 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/0322		DPRINT("%d edf_resched, rerelease\n", m->machno);
2002/0315		/* Period passed, rerelease */ t->r = now; edf_release(t); return; } if (now < t->d && (t->flags & Useblocking) == 0){ if (t->S > 0){
2002/0322		DPRINT("%d edf_resched, 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 edf_release(Task *t) {
2002/0322		DPRINT("%d edf_release, %s, %d\n", m->machno, edf_statename[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 * edf_runproc(void) { /* Return an edf proc to run or nil */ Task *t, *nt; Proc *p;
2002/0327		Ticks when;
2002/0315		static ulong nilcount; /* 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/0322		DPRINT("edf_runproc %lud\n", nilcount);
2002/0320		if (nt && (t == nil || (nt->d < t->d && nt->D < t->Delta))){
2002/0315		/* released task is better than current */
2002/0322		DPRINT("%d edf_runproc: 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/0322		DPRINT("%d edf_runproc: current\n", m->machno);
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){ DPRINT("%d edf_timer: %T too late\n", m->machno, ticks2time(now-when)); when = now; }
2002/0327		if (cycdeadline.when){ if(cycdeadline.when == when){ iunlock(&edflock); return p; } cycintrdel(&cycdeadline); } cycdeadline.when = when; cycintradd(&cycdeadline); clockintrsched();
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 * edf_testschedulability(Task *thetask) { 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; ticks = 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); }