edf.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /* EDF scheduling */
    2 #include        <u.h>
    3 #include        "../port/lib.h"
    4 #include        "mem.h"
    5 #include        "dat.h"
    6 #include        "fns.h"
    7 #include        "../port/error.h"
    8 #include        "../port/edf.h"
    9 #include        <trace.h>
   10 
   11 /* debugging */
   12 enum {
   13         Dontprint = 1,
   14 };
   15 
   16 #define DPRINT  if(Dontprint){}else print
   17 
   18 static long     now;    /* Low order 32 bits of time in µs */
   19 extern ulong    delayedscheds;
   20 extern Schedq   runq[Nrq];
   21 extern int      nrdy;
   22 extern ulong    runvec;
   23 
   24 /* Statistics stuff */
   25 ulong           nilcount;
   26 ulong           scheds;
   27 ulong           edfnrun;
   28 int             misseddeadlines;
   29 
   30 /* Edfschedlock protects modification of admission params */
   31 int             edfinited;
   32 QLock           edfschedlock;
   33 static Lock     thelock;
   34 
   35 enum{
   36         Dl,     /* Invariant for schedulability test: Dl < Rl */
   37         Rl,
   38 };
   39 
   40 static char *testschedulability(Proc*);
   41 static Proc *qschedulability;
   42 
   43 enum {
   44         Onemicrosecond =        1,
   45         Onemillisecond =        1000,
   46         Onesecond =             1000000,
   47         OneRound =              Onemillisecond/2,
   48 };
   49 
   50 static int
   51 timeconv(Fmt *f)
   52 {
   53         char buf[128], *sign;
   54         vlong t;
   55 
   56         buf[0] = 0;
   57         switch(f->r) {
   58         case 'U':
   59                 t = va_arg(f->args, uvlong);
   60                 break;
   61         case 't':                       /* vlong in nanoseconds */
   62                 t = va_arg(f->args, long);
   63                 break;
   64         default:
   65                 return fmtstrcpy(f, "(timeconv)");
   66         }
   67         if (t < 0) {
   68                 sign = "-";
   69                 t = -t;
   70         }
   71         else
   72                 sign = "";
   73         if (t > Onesecond){
   74                 t += OneRound;
   75                 sprint(buf, "%s%d.%.3ds", sign, (int)(t / Onesecond),
   76                         (int)(t % Onesecond)/Onemillisecond);
   77         }else if (t > Onemillisecond)
   78                 sprint(buf, "%s%d.%.3dms", sign, (int)(t / Onemillisecond),
   79                         (int)(t % Onemillisecond));
   80         else
   81                 sprint(buf, "%s%dµs", sign, (int)t);
   82         return fmtstrcpy(f, buf);
   83 }
   84 
   85 long edfcycles;
   86 
   87 Edf*
   88 edflock(Proc *p)
   89 {
   90         Edf *e;
   91 
   92         if (p->edf == nil)
   93                 return nil;
   94         ilock(&thelock);
   95         if((e = p->edf) && (e->flags & Admitted)){
   96                 thelock.pc = getcallerpc(&p);
   97 #ifdef EDFCYCLES
   98                 edfcycles -= lcycles();
   99 #endif
  100                 now = µs();
  101                 return e;
  102         }
  103         iunlock(&thelock);
  104         return nil;
  105 }
  106 
  107 void
  108 edfunlock(void)
  109 {
  110 
  111 #ifdef EDFCYCLES
  112         edfcycles += lcycles();
  113 #endif
  114         edfnrun++;
  115         iunlock(&thelock);
  116 }
  117 
  118 void
  119 edfinit(Proc*p)
  120 {
  121         if(!edfinited){
  122                 fmtinstall('t', timeconv);
  123                 edfinited++;
  124         }
  125         now = µs();
  126         DPRINT("%lud edfinit %lud[%s]\n", now, p->pid, statename[p->state]);
  127         p->edf = malloc(sizeof(Edf));
  128         if(p->edf == nil)
  129                 error(Enomem);
  130         return;
  131 }
  132 
  133 static void
  134 deadlineintr(Ureg*, Timer *t)
  135 {
  136         /* Proc reached deadline */
  137         extern int panicking;
  138         Proc *p;
  139         void (*pt)(Proc*, int, vlong);
  140 
  141         if(panicking || active.exiting)
  142                 return;
  143 
  144         p = t->ta;
  145         now = µs();
  146         DPRINT("%lud deadlineintr %lud[%s]\n", now, p->pid, statename[p->state]);
  147         /* If we're interrupting something other than the proc pointed to by t->a,
  148          * we've already achieved recheduling, so we need not do anything
  149          * Otherwise, we must cause a reschedule, but if we call sched()
  150          * here directly, the timer interrupt routine will not finish its business
  151          * Instead, we cause the resched to happen when the interrupted proc
  152          * returns to user space
  153          */
  154         if(p == up){
  155                 if(up->trace && (pt = proctrace))
  156                         pt(up, SInts, 0);
  157                 up->delaysched++;
  158                 delayedscheds++;
  159         }
  160 }
  161 
  162 static void
  163 release(Proc *p)
  164 {
  165         /* Called with edflock held */
  166         Edf *e;
  167         void (*pt)(Proc*, int, vlong);
  168         long n;
  169         vlong nowns;
  170 
  171         e = p->edf;
  172         e->flags &= ~Yield;
  173         if(e->d - now < 0){
  174                 e->periods++;
  175                 e->r = now;
  176                 if((e->flags & Sporadic) == 0){
  177                         /*
  178                          * Non sporadic processes stay true to their period;
  179                          * calculate next release time.
  180                          * Second test limits duration of while loop.
  181                          */
  182                         if((n = now - e->t) > 0){
  183                                 if(n < e->T)
  184                                         e->t += e->T;
  185                                 else
  186                                         e->t = now + e->T - (n % e->T);
  187                         }
  188                 }else{
  189                         /* Sporadic processes may not be released earlier than
  190                          * one period after this release
  191                          */
  192                         e->t = e->r + e->T;
  193                 }
  194                 e->d = e->r + e->D;
  195                 e->S = e->C;
  196                 DPRINT("%lud release %lud[%s], r=%lud, d=%lud, t=%lud, S=%lud\n",
  197                         now, p->pid, statename[p->state], e->r, e->d, e->t, e->S);
  198                 if(pt = proctrace){
  199                         nowns = todget(nil);
  200                         pt(p, SRelease, nowns);
  201                         pt(p, SDeadline, nowns + 1000LL*e->D);
  202                 }
  203         }else{
  204                 DPRINT("%lud release %lud[%s], too late t=%lud, called from %#p\n",
  205                         now, p->pid, statename[p->state], e->t, getcallerpc(&p));
  206         }
  207 }
  208 
  209 static void
  210 releaseintr(Ureg*, Timer *t)
  211 {
  212         Proc *p;
  213         extern int panicking;
  214         Schedq *rq;
  215 
  216         if(panicking || active.exiting)
  217                 return;
  218 
  219         p = t->ta;
  220         if((edflock(p)) == nil)
  221                 return;
  222         DPRINT("%lud releaseintr %lud[%s]\n", now, p->pid, statename[p->state]);
  223         switch(p->state){
  224         default:
  225                 edfunlock();
  226                 return;
  227         case Ready:
  228                 /* remove proc from current runq */
  229                 rq = &runq[p->priority];
  230                 if(dequeueproc(rq, p) != p){
  231                         DPRINT("releaseintr: can't find proc or lock race\n");
  232                         release(p);     /* It'll start best effort */
  233                         edfunlock();
  234                         return;
  235                 }
  236                 p->state = Waitrelease;
  237                 /* fall through */
  238         case Waitrelease:
  239                 release(p);
  240                 edfunlock();
  241                 if(p->state == Wakeme){
  242                         iprint("releaseintr: wakeme\n");
  243                 }
  244                 ready(p);
  245                 if(up){
  246                         up->delaysched++;
  247                         delayedscheds++;
  248                 }
  249                 return;
  250         case Running:
  251                 release(p);
  252                 edfrun(p, 1);
  253                 break;
  254         case Wakeme:
  255                 release(p);
  256                 edfunlock();
  257                 if(p->trend)
  258                         wakeup(p->trend);
  259                 p->trend = nil;
  260                 if(up){
  261                         up->delaysched++;
  262                         delayedscheds++;
  263                 }
  264                 return;
  265         }
  266         edfunlock();
  267 }
  268 
  269 void
  270 edfrecord(Proc *p)
  271 {
  272         long used;
  273         Edf *e;
  274         void (*pt)(Proc*, int, vlong);
  275 
  276         if((e = edflock(p)) == nil)
  277                 return;
  278         used = now - e->s;
  279         if(e->d - now <= 0)
  280                 e->edfused += used;
  281         else
  282                 e->extraused += used;
  283         if(e->S > 0){
  284                 if(e->S <= used){
  285                         if(pt = proctrace)
  286                                 pt(p, SSlice, 0);
  287                         DPRINT("%lud edfrecord slice used up\n", now);
  288                         e->d = now;
  289                         e->S = 0;
  290                 }else
  291                         e->S -= used;
  292         }
  293         e->s = now;
  294         edfunlock();
  295 }
  296 
  297 void
  298 edfrun(Proc *p, int edfpri)
  299 {
  300         Edf *e;
  301         void (*pt)(Proc*, int, vlong);
  302         long tns;
  303 
  304         e = p->edf;
  305         /* Called with edflock held */
  306         if(edfpri){
  307                 tns = e->d - now;
  308                 if(tns <= 0 || e->S == 0){
  309                         /* Deadline reached or resources exhausted,
  310                          * deschedule forthwith
  311                          */
  312                         p->delaysched++;
  313                         delayedscheds++;
  314                         e->s = now;
  315                         return;
  316                 }
  317                 if(e->S < tns)
  318                         tns = e->S;
  319                 if(tns < 20)
  320                         tns = 20;
  321                 e->tns = 1000LL * tns;  /* µs to ns */
  322                 if(e->tt == nil || e->tf != deadlineintr){
  323                         DPRINT("%lud edfrun, deadline=%lud\n", now, tns);
  324                 }else{
  325                         DPRINT("v");
  326                 }
  327                 if(p->trace && (pt = proctrace))
  328                         pt(p, SInte, todget(nil) + e->tns);
  329                 e->tmode = Trelative;
  330                 e->tf = deadlineintr;
  331                 e->ta = p;
  332                 timeradd(e);
  333         }else{
  334                 DPRINT("<");
  335         }
  336         e->s = now;
  337 }
  338 
  339 char *
  340 edfadmit(Proc *p)
  341 {
  342         char *err;
  343         Edf *e;
  344         int i;
  345         Proc *r;
  346         void (*pt)(Proc*, int, vlong);
  347         long tns;
  348 
  349         e = p->edf;
  350         if (e->flags & Admitted)
  351                 return "task state";    /* should never happen */
  352 
  353         /* simple sanity checks */
  354         if (e->T == 0)
  355                 return "T not set";
  356         if (e->C == 0)
  357                 return "C not set";
  358         if (e->D > e->T)
  359                 return "D > T";
  360         if (e->D == 0)  /* if D is not set, set it to T */
  361                 e->D = e->T;
  362         if (e->C > e->D)
  363                 return "C > D";
  364 
  365         qlock(&edfschedlock);
  366         if (err = testschedulability(p)){
  367                 qunlock(&edfschedlock);
  368                 return err;
  369         }
  370         e->flags |= Admitted;
  371 
  372         edflock(p);
  373 
  374         if(p->trace && (pt = proctrace))
  375                 pt(p, SAdmit, 0);
  376 
  377         /* Look for another proc with the same period to synchronize to */
  378         SET(r);
  379         for(i=0; i<conf.nproc; i++) {
  380                 r = proctab(i);
  381                 if(r->state == Dead || r == p)
  382                         continue;
  383                 if (r->edf == nil || (r->edf->flags & Admitted) == 0)
  384                         continue;
  385                 if (r->edf->T == e->T)
  386                                 break;
  387         }
  388         if (i == conf.nproc){
  389                 /* Can't synchronize to another proc, release now */
  390                 e->t = now;
  391                 e->d = 0;
  392                 release(p);
  393                 if (p == up){
  394                         DPRINT("%lud edfadmit self %lud[%s], release now: r=%lud d=%lud t=%lud\n",
  395                                 now, p->pid, statename[p->state], e->r, e->d, e->t);
  396                         /* We're already running */
  397                         edfrun(p, 1);
  398                 }else{
  399                         /* We're releasing another proc */
  400                         DPRINT("%lud edfadmit other %lud[%s], release now: r=%lud d=%lud t=%lud\n",
  401                                 now, p->pid, statename[p->state], e->r, e->d, e->t);
  402                         p->ta = p;
  403                         edfunlock();
  404                         qunlock(&edfschedlock);
  405                         releaseintr(nil, p);
  406                         return nil;
  407                 }
  408         }else{
  409                 /* Release in synch to something else */
  410                 e->t = r->edf->t;
  411                 if (p == up){
  412                         DPRINT("%lud edfadmit self %lud[%s], release at %lud\n",
  413                                 now, p->pid, statename[p->state], e->t);
  414                         edfunlock();
  415                         qunlock(&edfschedlock);
  416                         return nil;
  417                 }else{
  418                         DPRINT("%lud edfadmit other %lud[%s], release at %lud\n",
  419                                 now, p->pid, statename[p->state], e->t);
  420                         if(e->tt == nil){
  421                                 e->tf = releaseintr;
  422                                 e->ta = p;
  423                                 tns = e->t - now;
  424                                 if(tns < 20)
  425                                         tns = 20;
  426                                 e->tns = 1000LL * tns;
  427                                 e->tmode = Trelative;
  428                                 timeradd(e);
  429                         }
  430                 }
  431         }
  432         edfunlock();
  433         qunlock(&edfschedlock);
  434         return nil;
  435 }
  436 
  437 void
  438 edfstop(Proc *p)
  439 {
  440         Edf *e;
  441         void (*pt)(Proc*, int, vlong);
  442 
  443         if(e = edflock(p)){
  444                 DPRINT("%lud edfstop %lud[%s]\n", now, p->pid, statename[p->state]);
  445                 if(p->trace && (pt = proctrace))
  446                         pt(p, SExpel, 0);
  447                 e->flags &= ~Admitted;
  448                 if(e->tt)
  449                         timerdel(e);
  450                 edfunlock();
  451         }
  452 }
  453 
  454 static int
  455 yfn(void *)
  456 {
  457         now = µs();
  458         return up->trend == nil || now - up->edf->r >= 0;
  459 }
  460 
  461 void
  462 edfyield(void)
  463 {
  464         /* sleep until next release */
  465         Edf *e;
  466         void (*pt)(Proc*, int, vlong);
  467         long n;
  468 
  469         if((e = edflock(up)) == nil)
  470                 return;
  471         if(up->trace && (pt = proctrace))
  472                 pt(up, SYield, 0);
  473         if((n = now - e->t) > 0){
  474                 if(n < e->T)
  475                         e->t += e->T;
  476                 else
  477                         e->t = now + e->T - (n % e->T);
  478         }
  479         e->r = e->t;
  480         e->flags |= Yield;
  481         e->d = now;
  482         if (up->tt == nil){
  483                 n = e->t - now;
  484                 if(n < 20)
  485                         n = 20;
  486                 up->tns = 1000LL * n;
  487                 up->tf = releaseintr;
  488                 up->tmode = Trelative;
  489                 up->ta = up;
  490                 up->trend = &up->sleep;
  491                 timeradd(up);
  492         }else if(up->tf != releaseintr)
  493                 print("edfyield: surprise! %#p\n", up->tf);
  494         edfunlock();
  495         sleep(&up->sleep, yfn, nil);
  496 }
  497 
  498 int
  499 edfready(Proc *p)
  500 {
  501         Edf *e;
  502         Schedq *rq;
  503         Proc *l, *pp;
  504         void (*pt)(Proc*, int, vlong);
  505         long n;
  506 
  507         if((e = edflock(p)) == nil)
  508                 return 0;
  509 
  510         if(p->state == Wakeme && p->r){
  511                 iprint("edfready: wakeme\n");
  512         }
  513         if(e->d - now <= 0){
  514                 /* past deadline, arrange for next release */
  515                 if((e->flags & Sporadic) == 0){
  516                         /*
  517                          * Non sporadic processes stay true to their period;
  518                          * calculate next release time.
  519                          */
  520                         if((n = now - e->t) > 0){
  521                                 if(n < e->T)
  522                                         e->t += e->T;
  523                                 else
  524                                         e->t = now + e->T - (n % e->T);
  525                         }
  526                 }
  527                 if(now - e->t < 0){
  528                         /* Next release is in the future, schedule it */
  529                         if(e->tt == nil || e->tf != releaseintr){
  530                                 n = e->t - now;
  531                                 if(n < 20)
  532                                         n = 20;
  533                                 e->tns = 1000LL * n;
  534                                 e->tmode = Trelative;
  535                                 e->tf = releaseintr;
  536                                 e->ta = p;
  537                                 timeradd(e);
  538                                 DPRINT("%lud edfready %lud[%s], release=%lud\n",
  539                                         now, p->pid, statename[p->state], e->t);
  540                         }
  541                         if(p->state == Running && (e->flags & (Yield|Yieldonblock)) == 0 && (e->flags & Extratime)){
  542                                 /* If we were running, we've overrun our CPU allocation
  543                                  * or missed the deadline, continue running best-effort at low priority
  544                                  * Otherwise we were blocked.  If we don't yield on block, we continue
  545                                  * best effort
  546                                  */
  547                                 DPRINT(">");
  548                                 p->basepri = PriExtra;
  549                                 p->fixedpri = 1;
  550                                 edfunlock();
  551                                 return 0;       /* Stick on runq[PriExtra] */
  552                         }
  553                         DPRINT("%lud edfready %lud[%s] wait release at %lud\n",
  554                                 now, p->pid, statename[p->state], e->t);
  555                         p->state = Waitrelease;
  556                         edfunlock();
  557                         return 1;       /* Make runnable later */
  558                 }
  559                 DPRINT("%lud edfready %lud %s release now\n", now, p->pid, statename[p->state]);
  560                 /* release now */
  561                 release(p);
  562         }
  563         edfunlock();
  564         DPRINT("^");
  565         rq = &runq[PriEdf];
  566         /* insert in queue in earliest deadline order */
  567         lock(runq);
  568         l = nil;
  569         for(pp = rq->head; pp; pp = pp->rnext){
  570                 if(pp->edf->d > e->d)
  571                         break;
  572                 l = pp;
  573         }
  574         p->rnext = pp;
  575         if (l == nil)
  576                 rq->head = p;
  577         else
  578                 l->rnext = p;
  579         if(pp == nil)
  580                 rq->tail = p;
  581         rq->n++;
  582         nrdy++;
  583         runvec |= 1 << PriEdf;
  584         p->priority = PriEdf;
  585         p->readytime = m->ticks;
  586         p->state = Ready;
  587         unlock(runq);
  588         if(p->trace && (pt = proctrace))
  589                 pt(p, SReady, 0);
  590         return 1;
  591 }
  592 
  593 
  594 static void
  595 testenq(Proc *p)
  596 {
  597         Proc *xp, **xpp;
  598         Edf *e;
  599 
  600         e = p->edf;
  601         e->testnext = nil;
  602         if (qschedulability == nil) {
  603                 qschedulability = p;
  604                 return;
  605         }
  606         SET(xp);
  607         for (xpp = &qschedulability; *xpp; xpp = &xp->edf->testnext) {
  608                 xp = *xpp;
  609                 if (e->testtime - xp->edf->testtime < 0
  610                 || (e->testtime == xp->edf->testtime && e->testtype < xp->edf->testtype)){
  611                         e->testnext = xp;
  612                         *xpp = p;
  613                         return;
  614                 }
  615         }
  616         assert(xp->edf->testnext == nil);
  617         xp->edf->testnext = p;
  618 }
  619 
  620 static char *
  621 testschedulability(Proc *theproc)
  622 {
  623         Proc *p;
  624         long H, G, Cb, ticks;
  625         int steps, i;
  626 
  627         /* initialize */
  628         DPRINT("schedulability test %lud\n", theproc->pid);
  629         qschedulability = nil;
  630         for(i=0; i<conf.nproc; i++) {
  631                 p = proctab(i);
  632                 if(p->state == Dead)
  633                         continue;
  634                 if ((p->edf == nil || (p->edf->flags & Admitted) == 0) && p != theproc)
  635                         continue;
  636                 p->edf->testtype = Rl;
  637                 p->edf->testtime = 0;
  638                 DPRINT("\tInit: edfenqueue %lud\n", p->pid);
  639                 testenq(p);
  640         }
  641         H=0;
  642         G=0;
  643         for(steps = 0; steps < Maxsteps; steps++){
  644                 p = qschedulability;
  645                 qschedulability = p->edf->testnext;
  646                 ticks = p->edf->testtime;
  647                 switch (p->edf->testtype){
  648                 case Dl:
  649                         H += p->edf->C;
  650                         Cb = 0;
  651                         DPRINT("\tStep %3d, Ticks %lud, pid %lud, deadline, H += %lud → %lud, Cb = %lud\n",
  652                                 steps, ticks, p->pid, p->edf->C, H, Cb);
  653                         if (H+Cb>ticks){
  654                                 DPRINT("not schedulable\n");
  655                                 return "not schedulable";
  656                         }
  657                         p->edf->testtime += p->edf->T - p->edf->D;
  658                         p->edf->testtype = Rl;
  659                         testenq(p);
  660                         break;
  661                 case Rl:
  662                         DPRINT("\tStep %3d, Ticks %lud, pid %lud, release, G  %lud, C%lud\n",
  663                                 steps, ticks, p->pid, p->edf->C, G);
  664                         if(ticks && G <= ticks){
  665                                 DPRINT("schedulable\n");
  666                                 return nil;
  667                         }
  668                         G += p->edf->C;
  669                         p->edf->testtime += p->edf->D;
  670                         p->edf->testtype = Dl;
  671                         testenq(p);
  672                         break;
  673                 default:
  674                         assert(0);
  675                 }
  676         }
  677         DPRINT("probably not schedulable\n");
  678         return "probably not schedulable";
  679 }
Cache object: f904be0ecd815cceb4e5e47c38141836
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/port/edf.c

FreeBSD/Linux Kernel Cross Reference
sys/port/edf.c
