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