barrelfish-2018-10-04/kernel/schedule_rbed.c

77 struct dcb *queue_tail = NULL;
80 static struct dcb *lastdisp = NULL;
83  * \brief Returns whether dcb is in scheduling queue.
84  * \param dcb   Pointer to DCB to check.
87 static inline bool in_queue(struct dcb *dcb)
89     return dcb->next != NULL || kcb_current->queue_tail == dcb;
92 static inline unsigned int u_target(struct dcb *dcb)
94     return (dcb->wcet * SPECTRUM) / dcb->period;
97 static inline unsigned int u_actual_srt(struct dcb *dcb)
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)));
106 static inline systime_t deadline(struct dcb *dcb)
108     return dcb->release_time + dcb->deadline;
111 static void queue_insert(struct dcb *dcb)
116         kcb_current->queue_head = kcb_current->queue_tail = queue_tail = dcb;
130     struct dcb *prev = NULL;
131     for(struct dcb *i = kcb_current->queue_head; i != NULL; prev = i, i = i->next) {
133         if(dcb->type == TASK_TYPE_BEST_EFFORT &&
134            dcb->release_time >= i->release_time) {
139         if(deadline(dcb) >= deadline(i)) {
143         dcb->next = i;
145             kcb_current->queue_head = dcb;
147             prev->next = dcb;
154     kcb_current->queue_tail->next = dcb;
155     kcb_current->queue_tail = queue_tail = dcb;
159  * \brief Remove 'dcb' from scheduler ring.
161  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
163  * function is that dcb is not in the ring.
165  * \param dcb   Pointer to DCB to remove.
167 static void queue_remove(struct dcb *dcb)
170     if(!in_queue(dcb)) {
174     if(dcb == kcb_current->queue_head) {
175         kcb_current->queue_head = dcb->next;
183     for(struct dcb *i = kcb_current->queue_head; i != NULL; i = i->next) {
184         if(i->next == dcb) {
186             if(kcb_current->queue_tail == dcb) {
194     dcb->next = NULL;
204     for(struct dcb *i = queue_head; i != NULL && i->next != NULL; i = i->next) {
216     for(struct dcb *i = queue_head; i != NULL; i = i->next) {
227  * \param dcb   Pointer to dcb to allocate resources for.
229  * \return u_actual for 'dcb' in percent.
231 static unsigned int do_resource_allocation(struct dcb *dcb)
235     switch(dcb->type) {
237         u_actual = u_target(dcb);
241         u_actual = u_actual_srt(dcb);
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;
252         panic("Unknown task type %d!", dcb->type);
266         for(struct dcb *i = queue_head; i != NULL; i = i->next) {
278 static void set_best_effort_wcet(struct dcb *dcb)
280     unsigned int u_actual = do_resource_allocation(dcb);
287     dcb->wcet = (wcet_undiv + SPECTRUM / 2) / SPECTRUM;
295 struct dcb *schedule(void)
297     struct dcb *todisp;
342         debug(SUBSYS_DISPATCH, "schedule: no dcb runnable\n");
410     struct dcb *dcb = todisp;
412     if(dcb->type != TASK_TYPE_BEST_EFFORT) {
413         if(now > dcb->release_time) {
414             dcb->release_time += dcb->period;
417         dcb->release_time = now;
419     dcb->etime = 0;
420     queue_insert(dcb);
426 void schedule_now(struct dcb *dcb)
429     if (dcb->release_time >= now) {
430         dcb->release_time = now;
432     dcb->deadline = 1;
435 void make_runnable(struct dcb *dcb)
440     if(in_queue(dcb)) {
445                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
448     switch(dcb->type) {
450         if(dcb->weight == 0) {
451             dcb->weight = 1;
456             dcb->weight = dcb->weight / 2 + 6;
459         kcb_current->w_be += dcb->weight;
461         dcb->deadline = dcb->period = kcb_current->n_be * kernel_timeslice;
462         dcb->release_time = now;
471         kcb_current->u_hrt += u_target(dcb);
475         panic("Unknown task type %d", dcb->type);
485     if(dcb->release_time < now) {
487               now, dcb->release_time);
489     /* assert(dcb->release_time >= kernel_now); */
490     dcb->etime = 0;
491     queue_insert(dcb);
495  * \brief Remove 'dcb' from scheduler ring.
497  * Removes dispatcher 'dcb' from the scheduler ring. If it was not in
499  * function is that dcb is not in the ring.
501  * \param dcb   Pointer to DCB to remove.
503 void scheduler_remove(struct dcb *dcb)
506     if(!in_queue(dcb)) {
510     queue_remove(dcb);
513                 (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF);
516     switch(dcb->type) {
518         kcb_current->w_be -= dcb->weight;
529         kcb_current->u_hrt -= u_target(dcb);
535  * \brief Yield 'dcb' for the rest of the current timeslice.
537  * Re-sorts 'dcb' into the scheduler queue with its release time increased by
541  * \param dcb   Pointer to DCB to remove.
543 void scheduler_yield(struct dcb *dcb)
547     if(!in_queue(dcb) || dcb->release_time > now) {
552     /*             (uint32_t)(lvaddr_t)dcb & 0xFFFFFFFF); */
554     queue_remove(dcb);
555     switch(dcb->type) {
558         dcb->release_time += dcb->period;
563         dcb->release_time = now;
566     dcb->etime = 0;
568     queue_insert(dcb);
580         for(struct dcb *i = k->queue_head; i != NULL; i = i->next) {
603             struct dcb *tmp = NULL;
607             struct dcb *i = kcb_current->ring_current;