123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679 |
- /* EDF scheduling */
- #include <u.h>
- #include "../port/lib.h"
- #include "mem.h"
- #include "dat.h"
- #include "fns.h"
- #include "../port/error.h"
- #include "../port/edf.h"
- #include <trace.h>
- /* debugging */
- int edfprint = 0;
- #define DPRINT if(edfprint)print
- static long now; /* Low order 32 bits of time in µs */
- extern ulong delayedscheds;
- extern Schedq runq[Nrq];
- extern int nrdy;
- extern ulong runvec;
- /* Statistics stuff */
- ulong nilcount;
- ulong scheds;
- long edfruntime;
- ulong edfnrun;
- int misseddeadlines;
- /* Edfschedlock protects modification of admission params */
- int edfinited;
- QLock edfschedlock;
- static Lock thelock;
- enum{
- Dl, /* Invariant for schedulability test: Dl < Rl */
- Rl,
- };
- static char *testschedulability(Proc*);
- static Proc *qschedulability;
- enum {
- Onemicrosecond = 1,
- Onemillisecond = 1000,
- Onesecond = 1000000,
- OneRound = Onemillisecond/2,
- };
- static int
- timeconv(Fmt *f)
- {
- char buf[128], *sign;
- vlong t;
- buf[0] = 0;
- switch(f->r) {
- case 'U':
- t = va_arg(f->args, uvlong);
- break;
- case 't': // vlong in nanoseconds
- t = va_arg(f->args, long);
- break;
- default:
- return fmtstrcpy(f, "(timeconv)");
- }
- if (t < 0) {
- sign = "-";
- t = -t;
- }
- else
- sign = "";
- if (t > Onesecond){
- t += OneRound;
- sprint(buf, "%s%d.%.3ds", sign, (int)(t / Onesecond), (int)(t % Onesecond)/Onemillisecond);
- }else if (t > Onemillisecond)
- sprint(buf, "%s%d.%.3dms", sign, (int)(t / Onemillisecond), (int)(t % Onemillisecond));
- else
- sprint(buf, "%s%dµs", sign, (int)t);
- return fmtstrcpy(f, buf);
- }
- /*
- uvlong x;
- ulong xpc;
- */
- Edf*
- edflock(Proc *p)
- {
- Edf *e;
- if (p->edf == nil)
- return nil;
- ilock(&thelock);
- if ((e = p->edf) && (e->flags & Admitted)){
- /*
- cycles(&x);
- xpc = getcallerpc(&p);
- */
- now = fastticks2us(fastticks(nil));
- return e;
- }
- iunlock(&thelock);
- return nil;
- }
- void
- edfunlock(void)
- {
- /*
- uvlong y;
- ulong n, upc;
- cycles(&y);
- upc = 0;
- if((n = y - x) > 500000) upc = xpc;
- */
- edfruntime += todget(nil) - now;
- edfnrun++;
- iunlock(&thelock);
- /*
- if(upc)
- print("edfunlock %ld 0x%lux\n", n, upc);
- */
- }
- void
- edfinit(Proc*p)
- {
- if(!edfinited){
- fmtinstall('t', timeconv);
- edfinited++;
- }
- now = fastticks2us(fastticks(nil));
- DPRINT("%t edfinit %lud[%s]\n", now, p->pid, statename[p->state]);
- p->edf = malloc(sizeof(Edf));
- if(p->edf == nil)
- error(Enomem);
- return;
- }
- static void
- deadlineintr(Ureg*, Timer *t)
- {
- /* Proc reached deadline */
- extern int panicking;
- Proc *p;
- void (*pt)(Proc*, int, vlong);
- if(panicking || active.exiting)
- return;
- p = t->ta;
- now = fastticks2us(fastticks(nil));
- DPRINT("%t deadlineintr %lud[%s]\n", now, p->pid, statename[p->state]);
- /* If we're interrupting something other than the proc pointed to by t->a,
- * we've already achieved recheduling, so we need not do anything
- * Otherwise, we must cause a reschedule, but if we call sched()
- * here directly, the timer interrupt routine will not finish its business
- * Instead, we cause the resched to happen when the interrupted proc
- * returns to user space
- */
- if (p == up){
- pt = proctrace;
- if(up->trace && pt)
- pt(up, SInts, 0);
- up->delaysched++;
- delayedscheds++;
- }
- }
- static void
- release(Proc *p)
- {
- /* Called with edflock held */
- Edf *e;
- void (*pt)(Proc*, int, vlong);
- long n;
- vlong nowns;
- e = p->edf;
- e->flags &= ~Yield;
- if (e->d - now < 0){
- e->periods++;
- e->r = now;
- if ((e->flags & Sporadic) == 0){
- /*
- * Non sporadic processes stay true to their period;
- * calculate next release time.
- * Second test limits duration of while loop.
- */
- if((n = now - e->t) > 0){
- if(n < e->T)
- e->t += e->T;
- else
- e->t = now + e->T - (n % e->T);
- }
- }else{
- /* Sporadic processes may not be released earlier than
- * one period after this release
- */
- e->t = e->r + e->T;
- }
- e->d = e->r + e->D;
- e->S = e->C;
- DPRINT("%t release %lud[%s], r=%t, d=%t, t=%t, S=%t\n",
- now, p->pid, statename[p->state], e->r, e->d, e->t, e->S);
- if (pt = proctrace){
- nowns = todget(nil);
- pt(p, SRelease, nowns);
- pt(p, SDeadline, nowns + 1000LL*e->D);
- }
- }else{
- DPRINT("%t release %lud[%s], too late t=%t, called from 0x%lux\n",
- now, p->pid, statename[p->state], e->t, getcallerpc(&p));
- }
- }
- static void
- releaseintr(Ureg*, Timer *t)
- {
- Proc *p;
- extern int panicking;
- Schedq *rq;
- if(panicking || active.exiting)
- return;
- p = t->ta;
- if((edflock(p)) == nil)
- return;
- DPRINT("%t releaseintr %lud[%s]\n", now, p->pid, statename[p->state]);
- switch(p->state){
- default:
- edfunlock();
- return;
- case Ready:
- /* remove proc from current runq */
- rq = &runq[p->priority];
- if (dequeueproc(rq, p) != p){
- DPRINT("releaseintr: can't find proc or lock race\n");
- release(p); /* It'll start best effort */
- edfunlock();
- return;
- }
- p->state = Waitrelease;
- /* fall through */
- case Waitrelease:
- release(p);
- edfunlock();
- ready(p);
- if (up){
- up->delaysched++;
- delayedscheds++;
- }
- return;
- case Running:
- release(p);
- edfrun(p, 1);
- break;
- case Wakeme:
- release(p);
- edfunlock();
- if (p->trend)
- wakeup(p->trend);
- p->trend = nil;
- if (up){
- up->delaysched++;
- delayedscheds++;
- }
- return;
- }
- edfunlock();
- }
- void
- edfrecord(Proc *p)
- {
- long used;
- Edf *e;
- void (*pt)(Proc*, int, vlong);
- if((e = edflock(p)) == nil)
- return;
- used = now - e->s;
- if (e->d - now <= 0)
- e->edfused += used;
- else
- e->extraused += used;
- if (e->S > 0){
- if(e->S <= used){
- if(pt = proctrace)
- pt(p, SSlice, 0);
- DPRINT("%t edfrecord slice used up\n", now);
- e->d = now;
- e->S = 0;
- }else
- e->S -= used;
- }
- e->s = now;
- edfunlock();
- }
- void
- edfrun(Proc *p, int edfpri)
- {
- Edf *e;
- void (*pt)(Proc*, int, vlong);
- long tns;
- e = p->edf;
- /* Called with edflock held */
- if(edfpri){
- tns = e->d - now;
- if (tns <= 0 || e->S == 0){
- /* Deadline reached or resources exhausted,
- * deschedule forthwith
- */
- p->delaysched++;
- delayedscheds++;
- e->s = now;
- return;
- }
- if(e->S < tns)
- tns = e->S;
- e->tns = 1000LL * tns;
- if(e->tt == nil || e->tf != deadlineintr){
- DPRINT("%t edfrun, deadline=%t\n", now, tns);
- }else{
- DPRINT("v");
- }
- if(p->trace && (pt = proctrace))
- pt(p, SInte, todget(nil) + e->tns);
- e->tmode = Trelative;
- e->tf = deadlineintr;
- e->ta = p;
- timeradd(e);
- }else{
- DPRINT("<");
- }
- e->s = now;
- }
- char *
- edfadmit(Proc *p)
- {
- char *err;
- Edf *e;
- int i;
- Proc *r;
- void (*pt)(Proc*, int, vlong);
- long tns;
- e = p->edf;
- if (e->flags & Admitted)
- return "task state"; /* should never happen */
- /* simple sanity checks */
- if (e->T == 0)
- return "T not set";
- if (e->C == 0)
- return "C not set";
- if (e->D > e->T)
- return "D > T";
- if (e->D == 0) /* if D is not set, set it to T */
- e->D = e->T;
- if (e->C > e->D)
- return "C > D";
- qlock(&edfschedlock);
- if (err = testschedulability(p)){
- qunlock(&edfschedlock);
- return err;
- }
- e->flags |= Admitted;
- edflock(p);
- if(pt = proctrace)
- pt(p, SAdmit, 0);
- /* Look for another proc with the same period to synchronize to */
- SET(r);
- for(i=0; i<conf.nproc; i++) {
- r = proctab(i);
- if(r->state == Dead || r == p)
- continue;
- if (r->edf == nil || (r->edf->flags & Admitted) == 0)
- continue;
- if (r->edf->T == e->T)
- break;
- }
- if (i == conf.nproc){
- /* Can't synchronize to another proc, release now */
- e->t = now;
- e->d = 0;
- release(p);
- if (p == up){
- DPRINT("%t edfadmit self %lud[%s], release now: r=%t d=%t t=%t\n",
- now, p->pid, statename[p->state], e->r, e->d, e->t);
- /* We're already running */
- edfrun(p, 1);
- }else{
- /* We're releasing another proc */
- DPRINT("%t edfadmit other %lud[%s], release now: r=%t d=%t t=%t\n",
- now, p->pid, statename[p->state], e->r, e->d, e->t);
- p->ta = p;
- edfunlock();
- qunlock(&edfschedlock);
- releaseintr(nil, p);
- return nil;
- }
- }else{
- /* Release in synch to something else */
- e->t = r->edf->t;
- if (p == up){
- DPRINT("%t edfadmit self %lud[%s], release at %t\n",
- now, p->pid, statename[p->state], e->t);
- edfunlock();
- qunlock(&edfschedlock);
- return nil;
- }else{
- DPRINT("%t edfadmit other %lud[%s], release at %t\n",
- now, p->pid, statename[p->state], e->t);
- if(e->tt == nil){
- e->tf = releaseintr;
- e->ta = p;
- tns = e->t - now;
- if(tns < 20)
- tns = 20;
- e->tns = 1000LL * tns;
- e->tmode = Trelative;
- timeradd(e);
- }
- }
- }
- edfunlock();
- qunlock(&edfschedlock);
- return nil;
- }
- void
- edfstop(Proc *p)
- {
- Edf *e;
- void (*pt)(Proc*, int, vlong);
- if (e = edflock(p)){
- DPRINT("%t edfstop %lud[%s]\n", now, p->pid, statename[p->state]);
- if(pt = proctrace)
- pt(p, SExpel, 0);
- e->flags &= ~Admitted;
- if(e->tt)
- timerdel(e);
- edfunlock();
- }
- }
- static int
- yfn(void *)
- {
- now = fastticks2us(fastticks(nil));
- return up->trend == nil || now - up->edf->r >= 0;
- }
- void
- edfyield(void)
- {
- /* sleep until next release */
- Edf *e;
- void (*pt)(Proc*, int, vlong);
- long n;
- if((e = edflock(up)) == nil)
- return;
- if(pt = proctrace)
- pt(up, SYield, 0);
- if((n = now - e->t) > 0){
- if(n < e->T)
- e->t += e->T;
- else
- e->t = now + e->T - (n % e->T);
- }
- e->r = e->t;
- e->flags |= Yield;
- e->d = now;
- if (up->tt == nil){
- n = e->t - now;
- if(n < 20)
- n = 20;
- up->tns = 1000LL * n;
- up->tf = releaseintr;
- up->tmode = Trelative;
- up->ta = up;
- up->trend = &up->sleep;
- timeradd(up);
- }else if(up->tf != releaseintr)
- print("edfyield: surprise! 0x%lux\n", up->tf);
- edfunlock();
- sleep(&up->sleep, yfn, nil);
- }
- int
- edfready(Proc *p)
- {
- Edf *e;
- Schedq *rq;
- Proc *l, *pp;
- void (*pt)(Proc*, int, vlong);
- long n;
- if((e = edflock(p)) == nil)
- return 0;
- if(e->d - now <= 0){
- /* past deadline, arrange for next release */
- if((e->flags & Sporadic) == 0){
- /*
- * Non sporadic processes stay true to their period;
- * calculate next release time.
- */
- if((n = now - e->t) > 0){
- if(n < e->T)
- e->t += e->T;
- else
- e->t = now + e->T - (n % e->T);
- }
- }
- if(now - e->t < 0){
- /* Next release is in the future, schedule it */
- if(e->tt == nil || e->tf != releaseintr){
- n = e->t - now;
- if(n < 20)
- n = 20;
- e->tns = 1000LL * n;
- e->tmode = Trelative;
- e->tf = releaseintr;
- e->ta = p;
- timeradd(e);
- DPRINT("%t edfready %lud[%s], release=%t\n",
- now, p->pid, statename[p->state], e->t);
- }
- if(p->state == Running && (e->flags & (Yield|Yieldonblock)) == 0 && (e->flags & Extratime)){
- /* If we were running, we've overrun our CPU allocation
- * or missed the deadline, continue running best-effort at low priority
- * Otherwise we were blocked. If we don't yield on block, we continue
- * best effort
- */
- DPRINT(">");
- p->basepri = PriExtra;
- p->fixedpri = 1;
- edfunlock();
- return 0; /* Stick on runq[PriExtra] */
- }
- DPRINT("%t edfready %lud[%s] wait release at %t\n",
- now, p->pid, statename[p->state], e->t);
- p->state = Waitrelease;
- edfunlock();
- return 1; /* Make runnable later */
- }
- DPRINT("%t edfready %lud %s release now\n", now, p->pid, statename[p->state]);
- /* release now */
- release(p);
- }
- edfunlock();
- DPRINT("^");
- rq = &runq[PriEdf];
- /* insert in queue in earliest deadline order */
- lock(runq);
- l = nil;
- for(pp = rq->head; pp; pp = pp->rnext){
- if(pp->edf->d > e->d)
- break;
- l = pp;
- }
- p->rnext = pp;
- if (l == nil)
- rq->head = p;
- else
- l->rnext = p;
- if(pp == nil)
- rq->tail = p;
- rq->n++;
- nrdy++;
- runvec |= 1 << PriEdf;
- p->priority = PriEdf;
- p->readytime = m->ticks;
- p->state = Ready;
- unlock(runq);
- if(pt = proctrace)
- pt(p, SReady, 0);
- return 1;
- }
- static void
- testenq(Proc *p)
- {
- Proc *xp, **xpp;
- Edf *e;
- e = p->edf;
- e->testnext = nil;
- if (qschedulability == nil) {
- qschedulability = p;
- return;
- }
- SET(xp);
- for (xpp = &qschedulability; *xpp; xpp = &xp->edf->testnext) {
- xp = *xpp;
- if (e->testtime - xp->edf->testtime < 0
- || (e->testtime == xp->edf->testtime && e->testtype < xp->edf->testtype)){
- e->testnext = xp;
- *xpp = p;
- return;
- }
- }
- assert(xp->edf->testnext == nil);
- xp->edf->testnext = p;
- }
- static char *
- testschedulability(Proc *theproc)
- {
- Proc *p;
- long H, G, Cb, ticks;
- int steps, i;
- /* initialize */
- DPRINT("schedulability test %lud\n", theproc->pid);
- qschedulability = nil;
- for(i=0; i<conf.nproc; i++) {
- p = proctab(i);
- if(p->state == Dead)
- continue;
- if ((p->edf == nil || (p->edf->flags & Admitted) == 0) && p != theproc)
- continue;
- p->edf->testtype = Rl;
- p->edf->testtime = 0;
- DPRINT("\tInit: edfenqueue %lud\n", p->pid);
- testenq(p);
- }
- H=0;
- G=0;
- for(steps = 0; steps < Maxsteps; steps++){
- p = qschedulability;
- qschedulability = p->edf->testnext;
- ticks = p->edf->testtime;
- switch (p->edf->testtype){
- case Dl:
- H += p->edf->C;
- Cb = 0;
- DPRINT("\tStep %3d, Ticks %t, pid %lud, deadline, H += %t → %t, Cb = %t\n",
- steps, ticks, p->pid, p->edf->C, H, Cb);
- if (H+Cb>ticks){
- DPRINT("not schedulable\n");
- return "not schedulable";
- }
- p->edf->testtime += p->edf->T - p->edf->D;
- p->edf->testtype = Rl;
- testenq(p);
- break;
- case Rl:
- DPRINT("\tStep %3d, Ticks %t, pid %lud, release, G %t, C%t\n",
- steps, ticks, p->pid, p->edf->C, G);
- if(ticks && G <= ticks){
- DPRINT("schedulable\n");
- return nil;
- }
- G += p->edf->C;
- p->edf->testtime += p->edf->D;
- p->edf->testtype = Dl;
- testenq(p);
- break;
- default:
- assert(0);
- }
- }
- DPRINT("probably not schedulable\n");
- return "probably not schedulable";
- }
|