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