git.barrelfish.org Git - barrelfish/blob - kernel/schedule_rbed.c

   1 /**
   2  * \file
   3  * \brief Kernel scheduling policy: Rate-Based Earliest Deadline (RBED)
   4  *
   5  * The algorithm is described in the paper "Dynamic Integrated
   6  * Scheduling of Hard Real-Time, Soft Real-Time and Non-Real-Time
   7  * Processes" by Scott A. Brandt of UC Santa Cruz.
   8  *
   9  * Note that while in the paper real number arithmetic is used on some
  10  * variables, we employ fixed-point integer arithmetic within #SPECTRUM
  11  * in these cases.
  12  */
  13
  14 /*
  15  * Copyright (c) 2007, 2008, 2009, 2010, 2013, ETH Zurich.
  16  * All rights reserved.
  17  *
  18  * This file is distributed under the terms in the attached LICENSE file.
  19  * If you do not find this file, copies can be found by writing to:
  20  * ETH Zurich D-INFK, Universitaetstr. 6, CH-8092 Zurich. Attn: Systems Group.
  21  */
  22
  23 /**
  24  * Implementation Notes
  25  *
  26  * real-time tasks:
  27  *  the behaviour of real-time tasks is characterized by four parameters: wcet
  28  *  (worst case execution time), period, (relative) deadline, and
  29  *  release_time.  Besides release_time, the values of these parameters are
  30  *  not changed by the scheduler. RT tasks are considered to be periodic. Note
  31  *  that the interpretation of the parameters is a little different than the
  32  *  original RBED paper.
  33  *
  34  *  ->release_time is the time that the task is ready to be scheduled. RT tasks
  35  *  with ->release_time in the future are not effectively considered to be on
  36  *  the runqueue and are ignored by the scheduler.  In order to meet its
  37  *  deadline the task needs to be scheduled no later than ->release_time +
  38  *  deadline - wcet. EDF guarantees this property, as long as the utilization
  39  *  rate is <= 1.
  40  *
  41  *  The execution of an rt task for a particular period ends either when: (a)
  42  *  the task runs outs of budget (->etime >= ->wcet), or (b) the task yields
  43  *  using scheduler_yield(). When this happens the task's ->etime is reset to
  44  *  0, while ->release_time is increased by ->period. Note that
  45  *  scheduler_remove() does not finalize the current period of the task. Also,
  46  *  note that depending on ->period, there might be a case that an rt task is
  47  *  not executed, even if the CPU is idle.
  48  *
  49  * best-effort tasks:
  50  *  for best-effort tasks the scheduler is responsible to assigns proper values
  51  *  the RT parameters. Also, To prioritize between BE tasks, the scheduler uses
  52  *  ->weight.
  53  */
  54
  55 #include <limits.h>
  56 #ifndef SCHEDULER_SIMULATOR
  57 #       include <kernel.h>
  58 #       include <dispatch.h>
  59 #       include <trace/trace.h>
  60 #       include <trace_definitions/trace_defs.h>
  61 #       include <timer.h> // update_sched_timer
  62 #       include <kcb.h>
  63 #include <systime.h>
  64 #endif
  65
  66 #define SPECTRUM        1000000
  67
  68 /**
  69  * Minimum resource rate reserved for best-effort processes, in #SPECTRUM.
  70  * We set this to 10%.
  71  */
  72 #define BETA            (SPECTRUM / 10)
  73
  74 #define MAX(a, b)       ((a) > (b) ? (a) : (b))
  75 #define MIN(a, b)       ((a) < (b) ? (a) : (b))
  76
  77
  78 // queue_tail has to be global, as its used from assembly
  79 // this is always kept in sync with kcb_current->queue_tail
  80 struct dcb *queue_tail = NULL;
  81
  82 /// Last (currently) scheduled task, for accounting purposes
  83 static struct dcb *lastdisp = NULL;
  84
  85 /**
  86  * \brief Returns whether dcb is in scheduling queue.
  87  * \param dcb   Pointer to DCB to check.
  88  * \return True if in queue, false otherwise.
  89  */
  90 static inline bool in_queue(struct dcb *dcb)
  91 {
  92     return dcb->next != NULL || kcb_current->queue_tail == dcb;
  93 }
  94
  95 static inline unsigned int u_target(struct dcb *dcb)
  96 {
  97     return (dcb->wcet * SPECTRUM) / dcb->period;
  98 }
  99
 100 static inline unsigned int u_actual_srt(struct dcb *dcb)
 101 {
 102     if(u_target(dcb) != 0) {
 103         return MIN(u_target(dcb), (1 - BETA - kcb_current->u_hrt) / (kcb_current->u_srt / u_target(dcb)));
 104     } else {
 105         return 0;
 106     }
 107 }
 108
 109 static inline systime_t deadline(struct dcb *dcb)
 110 {
 111     return dcb->release_time + dcb->deadline;
 112 }
 113
 114 static void queue_insert(struct dcb *dcb)
 115 {
 116     // Empty queue case
 117     if(kcb_current->queue_head == NULL) {
 118         assert(kcb_current->queue_tail == NULL);
 119         kcb_current->queue_head = kcb_current->queue_tail = queue_tail = dcb;
 120         return;
 121     }
 122
 123     /* Insert into priority queue (this is doing EDF). We insert at
 124      * the tail of a train of tasks with equal deadlines, as well as
 125      * equal release times for best-effort tasks, so that trains of
 126      * best-effort tasks with equal deadlines (and those released at
 127      * the same time) get scheduled in a round-robin fashion. The
 128      * release time equality check is important, as best-effort tasks
 129      * have lazily allocated deadlines. In some circumstances (like
 130      * when another task blocks), this might otherwise cause a wrong
 131      * yielding behavior when old deadlines are encountered.
 132      */
 133     struct dcb *prev = NULL;
 134     for(struct dcb *i = kcb_current->queue_head; i != NULL; prev = i, i = i->next) {
 135         // Skip over equal, smaller release times if best-effort
 136         if(dcb->type == TASK_TYPE_BEST_EFFORT &&
 137            dcb->release_time >= i->release_time) {
 138             continue;
 139         }
 140
 141         // Skip over equal deadlines
 142         if(deadline(dcb) >= deadline(i)) {
 143             continue;
 144         }
 145
 146         dcb->next = i;
 147         if(prev == NULL) {      // Insert before head
 148             kcb_current->queue_head = dcb;
 149         } else {                // Insert inside queue
 150             prev->next = dcb;
 151         }
 152
 153         return;
 154     }
 155
 156     // Insert after queue tail
 157     kcb_current->queue_tail->next = dcb;
 158     kcb_current->queue_tail = queue_tail = dcb;
 159 }
 160
 161 /**
 162  * \brief Remove 'dcb' from scheduler ring.
 163  *
 164  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
 165  * the ring, this function is a no-op. The postcondition for this
 166  * function is that dcb is not in the ring.
 167  *
 168  * \param dcb   Pointer to DCB to remove.
 169  */
 170 static void queue_remove(struct dcb *dcb)
 171 {
 172     // No-op if not in scheduler ring
 173     if(!in_queue(dcb)) {
 174         return;
 175     }
 176
 177     if(dcb == kcb_current->queue_head) {
 178         kcb_current->queue_head = dcb->next;
 179         if(kcb_current->queue_head == NULL) {
 180             kcb_current->queue_tail = queue_tail =  NULL;
 181         }
 182
 183         goto out;
 184     }
 185
 186     for(struct dcb *i = kcb_current->queue_head; i != NULL; i = i->next) {
 187         if(i->next == dcb) {
 188             i->next = i->next->next;
 189             if(kcb_current->queue_tail == dcb) {
 190                 kcb_current->queue_tail = queue_tail = i;
 191             }
 192             break;
 193         }
 194     }
 195
 196  out:
 197     dcb->next = NULL;
 198 }
 199
 200 #if 0
 201 /**
 202  * \brief (Re-)Sort the scheduler priority queue.
 203  */
 204 static void queue_sort(void)
 205 {
 206  start_over:
 207     for(struct dcb *i = queue_head; i != NULL && i->next != NULL; i = i->next) {
 208         if(deadline(i) > deadline(i->next)) {
 209             // Gotta re-sort
 210             queue_remove(i);
 211             queue_insert(i);
 212             goto start_over;
 213         }
 214     }
 215 }
 216
 217 static void queue_reset(void)
 218 {
 219     for(struct dcb *i = queue_head; i != NULL; i = i->next) {
 220         if(i->type == TASK_TYPE_BEST_EFFORT) {
 221             i->release_time = kernel_now;
 222         }
 223     }
 224 }
 225 #endif
 226
 227 /**
 228  * \brief Allocates resources for tasks.
 229  *
 230  * \param dcb   Pointer to dcb to allocate resources for.
 231  *
 232  * \return u_actual for 'dcb' in percent.
 233  */
 234 static unsigned int do_resource_allocation(struct dcb *dcb)
 235 {
 236     unsigned int u_actual;
 237
 238     switch(dcb->type) {
 239     case TASK_TYPE_HARD_REALTIME:
 240         u_actual = u_target(dcb);
 241         break;
 242
 243     case TASK_TYPE_SOFT_REALTIME:
 244         u_actual = u_actual_srt(dcb);
 245         break;
 246
 247     case TASK_TYPE_BEST_EFFORT:
 248         assert(kcb_current->w_be > 0 && kcb_current->n_be > 0);
 249         assert(dcb->weight < UINT_MAX / SPECTRUM);
 250         u_actual = (MAX(BETA, SPECTRUM - kcb_current->u_hrt - kcb_current->u_srt) * dcb->weight) / kcb_current->w_be;
 251         dcb->deadline = dcb->period = kcb_current->n_be * kernel_timeslice;
 252         break;
 253
 254     default:
 255         panic("Unknown task type %d!", dcb->type);
 256         break;
 257     }
 258
 259     return u_actual;
 260 }
 261
 262 #if 0
 263 // XXX: Don't understand this yet
 264 static void adjust_weights(void)
 265 {
 266     // No runnable best-effort tasks have a positive weight
 267     if(w_be == 0) {
 268         // Re-assign weights
 269         for(struct dcb *i = queue_head; i != NULL; i = i->next) {
 270             if(i->type != TASK_TYPE_BEST_EFFORT) {
 271                 continue;
 272             }
 273
 274             i->weight = 1;
 275             w_be++;
 276         }
 277     }
 278 }
 279 #endif
 280
 281 static void set_best_effort_wcet(struct dcb *dcb)
 282 {
 283     unsigned int u_actual = do_resource_allocation(dcb);
 284     systime_t wcet_undiv = (kcb_current->n_be * kernel_timeslice * u_actual);
 285
 286     // Assert we are never overloaded
 287     assert(kcb_current->u_hrt + kcb_current->u_srt + u_actual <= SPECTRUM);
 288
 289     // Divide with proper rounding
 290     dcb->wcet = (wcet_undiv + SPECTRUM / 2) / SPECTRUM;
 291 }
 292
 293 /**
 294  * \brief Scheduler policy.
 295  *
 296  * \return Next DCB to schedule or NULL if wait for interrupts.
 297  */
 298 struct dcb *schedule(void)
 299 {
 300     struct dcb *todisp;
 301     systime_t now = systime_now();
 302
 303     // Assert we are never overloaded
 304     assert(kcb_current->u_hrt + kcb_current->u_srt + BETA <= SPECTRUM);
 305
 306     // Update executed time of last dispatched task
 307     if(lastdisp != NULL) {
 308         assert(lastdisp->last_dispatch <= now);
 309         if(lastdisp->release_time <= now) {
 310             lastdisp->etime += now -
 311                 MAX(lastdisp->last_dispatch, lastdisp->release_time);
 312         }
 313     }
 314
 315  start_over:
 316     todisp = kcb_current->queue_head;
 317
 318 #ifndef SCHEDULER_SIMULATOR
 319 #define PRINT_NAME(d) \
 320     do { \
 321         if (!(d) || !(d)->disp) { \
 322             debug(SUBSYS_DISPATCH, "todisp == NULL\n"); \
 323             break; \
 324         } \
 325         struct dispatcher_shared_generic *dst = \
 326             get_dispatcher_shared_generic(d->disp); \
 327         debug(SUBSYS_DISPATCH, "looking at '%s', release_time=%lu, kernel_now=%zu\n", \
 328                 dst->name, d->release_time, now); \
 329     }while(0)
 330 #else
 331 #define PRINT_NAME(d) do{}while(0)
 332 #endif
 333
 334     // Skip over all tasks released in the future, they're technically not
 335     // in the schedule yet. We just have them to reduce book-keeping.
 336     while(todisp != NULL && todisp->release_time > now) {
 337         PRINT_NAME(todisp);
 338         todisp = todisp->next;
 339     }
 340 #undef PRINT_NAME
 341
 342     // nothing to dispatch
 343     if(todisp == NULL) {
 344 #ifndef SCHEDULER_SIMULATOR
 345         debug(SUBSYS_DISPATCH, "schedule: no dcb runnable\n");
 346 #endif
 347         lastdisp = NULL;
 348         return NULL;
 349     }
 350
 351     // Lazy resource allocation for best-effort processes
 352     if(todisp->type == TASK_TYPE_BEST_EFFORT) {
 353         set_best_effort_wcet(todisp);
 354
 355         /* We might've shortened the deadline into the past (eg. when
 356          * another BE task was removed while we already ran well into
 357          * our timeslice). In that case we need to re-release.
 358          */
 359         if(deadline(todisp) < now) {
 360             todisp->release_time = now;
 361         }
 362     }
 363
 364     // Assert we never miss a hard deadline
 365     if(todisp->type == TASK_TYPE_HARD_REALTIME && now > deadline(todisp)) {
 366         panic("Missed hard deadline: now = %zu, deadline = %lu", now,
 367               deadline(todisp));
 368         assert(false && "HRT task missed a dead line!");
 369     }
 370
 371     // Deadline's can't be in the past (or EDF wouldn't work properly)
 372     assert(deadline(todisp) >= now);
 373
 374     // Dispatch first guy in schedule if not over budget
 375     if(todisp->etime < todisp->wcet) {
 376         todisp->last_dispatch = now;
 377
 378         // If nothing changed, run whatever ran last (task might have
 379         // yielded to another), unless it is blocked
 380         if(lastdisp == todisp && dcb_current != NULL && in_queue(dcb_current)) {
 381             /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_CURRENT, */
 382             /*             (uint32_t)(lvaddr_t)dcb_current & 0xFFFFFFFF); */
 383             return dcb_current;
 384         }
 385
 386         /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_SCHEDULE, */
 387         /*             (uint32_t)(lvaddr_t)todisp & 0xFFFFFFFF); */
 388
 389         // Remember who we run next
 390         lastdisp = todisp;
 391         #ifdef CONFIG_ONESHOT_TIMER
 392         // we might be able to do better than that...
 393         // (e.g., check if there is only one task in the queue)
 394         update_sched_timer(now + (todisp->wcet - todisp->etime));
 395         #endif
 396         return todisp;
 397     }
 398
 399     /* we selected a task that is over budget. do the necessary bookkeeping, put
 400      * it back on the queue and re-select a task */
 401
 402     // Best-effort task consumed WCET
 403     // XXX: Don't understand this yet
 404 #if 0
 405     if(todisp->type == TASK_TYPE_BEST_EFFORT) {
 406         w_be -= todisp->weight;
 407         todisp->weight = 0;
 408         adjust_weights();
 409     }
 410 #endif
 411
 412     // Update periodic task and re-sort into run-queue
 413     struct dcb *dcb = todisp;
 414     queue_remove(todisp);
 415     if(dcb->type != TASK_TYPE_BEST_EFFORT) {
 416         if(now > dcb->release_time) {
 417             dcb->release_time += dcb->period;
 418         }
 419     } else {
 420         dcb->release_time = now;
 421     }
 422     dcb->etime = 0;
 423     queue_insert(dcb);
 424     lastdisp = NULL;
 425
 426     goto start_over;
 427 }
 428
 429 void schedule_now(struct dcb *dcb)
 430 {
 431     systime_t now = systime_now();
 432     if (dcb->release_time >= now) {
 433         dcb->release_time = now;
 434     }
 435     dcb->deadline = 1;
 436 }
 437
 438 void make_runnable(struct dcb *dcb)
 439 {
 440     systime_t now = systime_now();
 441
 442     // No-Op if already in schedule
 443     if(in_queue(dcb)) {
 444         return;
 445     }
 446
 447     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_MAKE_RUNNABLE,
 448                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
 449
 450     // Keep counters up to date
 451     switch(dcb->type) {
 452     case TASK_TYPE_BEST_EFFORT:
 453         if(dcb->weight == 0) {
 454             dcb->weight = 1;
 455         } else {
 456             // XXX: Don't understand this yet
 457 #if 0
 458             // Give blocked processes a boost
 459             dcb->weight = dcb->weight / 2 + 6;
 460 #endif
 461         }
 462         kcb_current->w_be += dcb->weight;
 463         kcb_current->n_be++;
 464         dcb->deadline = dcb->period = kcb_current->n_be * kernel_timeslice;
 465         dcb->release_time = now;
 466         /* queue_sort(); */
 467         break;
 468
 469     case TASK_TYPE_SOFT_REALTIME:
 470         panic("Unimplemented!");
 471         break;
 472
 473     case TASK_TYPE_HARD_REALTIME:
 474         kcb_current->u_hrt += u_target(dcb);
 475         break;
 476
 477     default:
 478         panic("Unknown task type %d", dcb->type);
 479         break;
 480     }
 481
 482     // Never overload the scheduler
 483     if(kcb_current->u_hrt + kcb_current->u_srt + BETA > SPECTRUM) {
 484         panic("RBED scheduler overload (loaded %d%%)!",
 485               (kcb_current->u_hrt + kcb_current->u_srt + BETA) / (SPECTRUM / 100));
 486     }
 487
 488     if(dcb->release_time < now) {
 489         panic("Released in the past! now = %zu, release_time = %lu\n",
 490               now, dcb->release_time);
 491     }
 492     /* assert(dcb->release_time >= kernel_now); */
 493     dcb->etime = 0;
 494     queue_insert(dcb);
 495 }
 496
 497 /**
 498  * \brief Remove 'dcb' from scheduler ring.
 499  *
 500  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
 501  * the ring, this function is a no-op. The postcondition for this
 502  * function is that dcb is not in the ring.
 503  *
 504  * \param dcb   Pointer to DCB to remove.
 505  */
 506 void scheduler_remove(struct dcb *dcb)
 507 {
 508     // No-Op if not in schedule
 509     if(!in_queue(dcb)) {
 510         return;
 511     }
 512
 513     queue_remove(dcb);
 514
 515     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_REMOVE,
 516                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
 517
 518     // Update counters
 519     switch(dcb->type) {
 520     case TASK_TYPE_BEST_EFFORT:
 521         kcb_current->w_be -= dcb->weight;
 522         kcb_current->n_be--;
 523         /* queue_sort(); */
 524         /* adjust_weights(); */
 525         break;
 526
 527     case TASK_TYPE_SOFT_REALTIME:
 528         panic("Unimplemented!");
 529         break;
 530
 531     case TASK_TYPE_HARD_REALTIME:
 532         kcb_current->u_hrt -= u_target(dcb);
 533         break;
 534     }
 535 }
 536
 537 /**
 538  * \brief Yield 'dcb' for the rest of the current timeslice.
 539  *
 540  * Re-sorts 'dcb' into the scheduler queue with its release time increased by
 541  * the timeslice period. It is an error to yield a dispatcher not in the
 542  * scheduler queue.
 543  *
 544  * \param dcb   Pointer to DCB to remove.
 545  */
 546 void scheduler_yield(struct dcb *dcb)
 547 {
 548     systime_t now = systime_now();
 549     // For tasks not running yet, yield is a no-op
 550     if(!in_queue(dcb) || dcb->release_time > now) {
 551         return;
 552     }
 553
 554     /* trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_SCHED_YIELD, */
 555     /*             (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF); */
 556
 557     queue_remove(dcb);
 558     switch(dcb->type) {
 559     case TASK_TYPE_HARD_REALTIME:
 560     case TASK_TYPE_SOFT_REALTIME:
 561         dcb->release_time += dcb->period;
 562         break;
 563
 564     case TASK_TYPE_BEST_EFFORT:
 565         // Shuffle us around one time
 566         dcb->release_time = now;
 567         break;
 568     }
 569     dcb->etime = 0;
 570     lastdisp = NULL;    // Don't account for us anymore
 571     queue_insert(dcb);
 572 }
 573
 574 #ifndef SCHEDULER_SIMULATOR
 575 void scheduler_reset_time(void)
 576 {
 577     trace_event(TRACE_SUBSYS_KERNEL, TRACE_EVENT_KERNEL_TIMER_SYNC, 0);
 578
 579     // XXX: Currently, we just re-release everything now
 580     struct kcb *k = kcb_current;
 581     do {
 582         printk(LOG_NOTE, "clearing kcb %p\n", k);
 583         for(struct dcb *i = k->queue_head; i != NULL; i = i->next) {
 584             i->release_time = 0;
 585             i->etime = 0;
 586             i->last_dispatch = 0;
 587         }
 588         k = k->next;
 589     }while(k && k!=kcb_current);
 590
 591     // Forget all accounting information
 592     lastdisp = NULL;
 593 }
 594
 595 void scheduler_convert(void)
 596 {
 597     enum sched_state from = kcb_current->sched;
 598     switch (from) {
 599         case SCHED_RBED:
 600             // do nothing
 601             break;
 602         case SCHED_RR:
 603         {
 604             // initialize RBED fields
 605             // make all tasks best effort
 606             struct dcb *tmp = NULL;
 607             printf("kcb_current: %p\n", kcb_current);
 608             printf("kcb_current->ring_current: %p\n", kcb_current->ring_current);
 609             printf("kcb_current->ring_current->prev: %p\n", kcb_current->ring_current->prev);
 610             struct dcb *i = kcb_current->ring_current;
 611             do {
 612                 printf("converting %p\n", i);
 613                 i->type = TASK_TYPE_BEST_EFFORT;
 614                 tmp = i->next;
 615                 i->next = i->prev = NULL;
 616                 make_runnable(i);
 617                 i = tmp;
 618             } while (i != kcb_current->ring_current);
 619             for (i = kcb_current->queue_head; i; i=i->next) {
 620                 printf("%p (-> %p)\n", i, i->next);
 621             }
 622             break;
 623         }
 624         default:
 625             printf("don't know how to convert %d to RBED state\n", from);
 626             break;
 627     }
 628 }
 629
 630 void scheduler_restore_state(void)
 631 {
 632     // clear time slices
 633     scheduler_reset_time();
 634 }
 635 #endif