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 *u, 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                 twakeup(u, t);
 258                 if(up){
 259                         up->delaysched++;
 260                         delayedscheds++;
 261                 }
 262                 return;
 263         }
 264         edfunlock();
 265 }
 266
 267 void
 268 edfrecord(Proc *p)
 269 {
 270         long used;
 271         Edf *e;
 272         void (*pt)(Proc*, int, vlong);
 273
 274         if((e = edflock(p)) == nil)
 275                 return;
 276         used = now - e->s;
 277         if(e->d - now <= 0)
 278                 e->edfused += used;
 279         else
 280                 e->extraused += used;
 281         if(e->S > 0){
 282                 if(e->S <= used){
 283                         if(pt = proctrace)
 284                                 pt(p, SSlice, 0);
 285                         DPRINT("%lud edfrecord slice used up\n", now);
 286                         e->d = now;
 287                         e->S = 0;
 288                 }else
 289                         e->S -= used;
 290         }
 291         e->s = now;
 292         edfunlock();
 293 }
 294
 295 void
 296 edfrun(Proc *p, int edfpri)
 297 {
 298         Edf *e;
 299         void (*pt)(Proc*, int, vlong);
 300         long tns;
 301
 302         e = p->edf;
 303         /* Called with edflock held */
 304         if(edfpri){
 305                 tns = e->d - now;
 306                 if(tns <= 0 || e->S == 0){
 307                         /* Deadline reached or resources exhausted,
 308                          * deschedule forthwith
 309                          */
 310                         p->delaysched++;
 311                         delayedscheds++;
 312                         e->s = now;
 313                         return;
 314                 }
 315                 if(e->S < tns)
 316                         tns = e->S;
 317                 if(tns < 20)
 318                         tns = 20;
 319                 e->tns = 1000LL * tns;  /* µs to ns */
 320                 if(e->tt == nil || e->tf != deadlineintr){
 321                         DPRINT("%lud edfrun, deadline=%lud\n", now, tns);
 322                 }else{
 323                         DPRINT("v");
 324                 }
 325                 if(p->trace && (pt = proctrace))
 326                         pt(p, SInte, todget(nil) + e->tns);
 327                 e->tmode = Trelative;
 328                 e->tf = deadlineintr;
 329                 e->ta = p;
 330                 timeradd(e);
 331         }else{
 332                 DPRINT("<");
 333         }
 334         e->s = now;
 335 }
 336
 337 char *
 338 edfadmit(Proc *p)
 339 {
 340         char *err;
 341         Edf *e;
 342         int i;
 343         Proc *r;
 344         void (*pt)(Proc*, int, vlong);
 345         long tns;
 346
 347         e = p->edf;
 348         if (e->flags & Admitted)
 349                 return "task state";    /* should never happen */
 350
 351         /* simple sanity checks */
 352         if (e->T == 0)
 353                 return "T not set";
 354         if (e->C == 0)
 355                 return "C not set";
 356         if (e->D > e->T)
 357                 return "D > T";
 358         if (e->D == 0)  /* if D is not set, set it to T */
 359                 e->D = e->T;
 360         if (e->C > e->D)
 361                 return "C > D";
 362
 363         qlock(&edfschedlock);
 364         if (err = testschedulability(p)){
 365                 qunlock(&edfschedlock);
 366                 return err;
 367         }
 368         e->flags |= Admitted;
 369
 370         edflock(p);
 371
 372         if(p->trace && (pt = proctrace))
 373                 pt(p, SAdmit, 0);
 374
 375         /* Look for another proc with the same period to synchronize to */
 376         SET(r);
 377         for(i=0; i<conf.nproc; i++) {
 378                 r = proctab(i);
 379                 if(r->state == Dead || r == p)
 380                         continue;
 381                 if (r->edf == nil || (r->edf->flags & Admitted) == 0)
 382                         continue;
 383                 if (r->edf->T == e->T)
 384                                 break;
 385         }
 386         if (i == conf.nproc){
 387                 /* Can't synchronize to another proc, release now */
 388                 e->t = now;
 389                 e->d = 0;
 390                 release(p);
 391                 if (p == up){
 392                         DPRINT("%lud edfadmit self %lud[%s], release now: r=%lud d=%lud t=%lud\n",
 393                                 now, p->pid, statename[p->state], e->r, e->d, e->t);
 394                         /* We're already running */
 395                         edfrun(p, 1);
 396                 }else{
 397                         /* We're releasing another proc */
 398                         DPRINT("%lud edfadmit other %lud[%s], release now: r=%lud d=%lud t=%lud\n",
 399                                 now, p->pid, statename[p->state], e->r, e->d, e->t);
 400                         p->ta = p;
 401                         edfunlock();
 402                         qunlock(&edfschedlock);
 403                         releaseintr(nil, p);
 404                         return nil;
 405                 }
 406         }else{
 407                 /* Release in synch to something else */
 408                 e->t = r->edf->t;
 409                 if (p == up){
 410                         DPRINT("%lud edfadmit self %lud[%s], release at %lud\n",
 411                                 now, p->pid, statename[p->state], e->t);
 412                         edfunlock();
 413                         qunlock(&edfschedlock);
 414                         return nil;
 415                 }else{
 416                         DPRINT("%lud edfadmit other %lud[%s], release at %lud\n",
 417                                 now, p->pid, statename[p->state], e->t);
 418                         if(e->tt == nil){
 419                                 e->tf = releaseintr;
 420                                 e->ta = p;
 421                                 tns = e->t - now;
 422                                 if(tns < 20)
 423                                         tns = 20;
 424                                 e->tns = 1000LL * tns;
 425                                 e->tmode = Trelative;
 426                                 timeradd(e);
 427                         }
 428                 }
 429         }
 430         edfunlock();
 431         qunlock(&edfschedlock);
 432         return nil;
 433 }
 434
 435 void
 436 edfstop(Proc *p)
 437 {
 438         Edf *e;
 439         void (*pt)(Proc*, int, vlong);
 440
 441         if(e = edflock(p)){
 442                 DPRINT("%lud edfstop %lud[%s]\n", now, p->pid, statename[p->state]);
 443                 if(p->trace && (pt = proctrace))
 444                         pt(p, SExpel, 0);
 445                 e->flags &= ~Admitted;
 446                 timerdel(e);
 447                 edfunlock();
 448         }
 449 }
 450
 451 static int
 452 yfn(void *)
 453 {
 454         now = µs();
 455         return up->trend == nil || now - up->edf->r >= 0;
 456 }
 457
 458 void
 459 edfyield(void)
 460 {
 461         /* sleep until next release */
 462         Edf *e;
 463         void (*pt)(Proc*, int, vlong);
 464         long n;
 465
 466         if((e = edflock(up)) == nil)
 467                 return;
 468         if(up->trace && (pt = proctrace))
 469                 pt(up, SYield, 0);
 470         if((n = now - e->t) > 0){
 471                 if(n < e->T)
 472                         e->t += e->T;
 473                 else
 474                         e->t = now + e->T - (n % e->T);
 475         }
 476         e->r = e->t;
 477         e->flags |= Yield;
 478         e->d = now;
 479         n = e->t - now;
 480         if(n < 20)
 481                 n = 20;
 482         up->tns = 1000LL * n;
 483         up->tf = releaseintr;
 484         up->tmode = Trelative;
 485         up->ta = up;
 486         up->trend = &up->sleep;
 487         timeradd(up);
 488         edfunlock();
 489         if(waserror()){
 490                 up->trend = nil;
 491                 timerdel(up);
 492                 nexterror();
 493         }
 494         sleep(&up->sleep, yfn, nil);
 495         poperror();
 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 }