sys/src/9/port/edf.c

   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 }