edf.h File Reference

#include "libos/os.h"
#include "libos/thread_structures.h"
#include "priority_schedule_structures.h"

Include dependency graph for edf.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	SCHEDULER_MAX_THREADS   16

Functions
void	edf_init ()
void	edf_insert (sched_task *)
tcb_t *	edf_pop ()

Macro Definition Documentation

#define SCHEDULER_MAX_THREADS   16

Definition at line 16 of file edf.h.

Function Documentation

void edf_init

(

)

Initialize the Earliest Deadline First task queue

Precondition

ensure at least one task has been scheduled prior to invoking this function

Definition at line 475 of file os.c.

References DL_EDF_INSERT, edf_insert(), sched_task_pool::next, sched_task_pool::queue, and SCHEDULER_QUEUES.

Referenced by os_launch().

                {

    sched_task_pool *start = SCHEDULER_QUEUES;
    sched_task_pool *next = start->next;

    /* avoid the NULL EDF_QUEUE to allow optimized form of `edf_insert' */
    DL_EDF_INSERT(EDF_QUEUE, start->queue);

    /* Create the rest of the EDF */
    while(next && next != start) {
        /* DL_EDF_INSERT(EDF_QUEUE, next->queue); */
        edf_insert(next->queue);
        next = next->next;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void edf_insert

(

sched_task *

)

Add by insertion sort the specified task into the EDF queue

Definition at line 491 of file os.c.

References sched_task::absolute_deadline, DL_EDF_INSERT, DL_EDF_PREPEND, EDF_QUEUE, and sched_task::pri_next.

Referenced by edf_init(), edf_pop(), and scheduler_reschedule().

                                  {

    sched_task *elt = EDF_QUEUE;

    while(elt && task->absolute_deadline > elt->absolute_deadline) {
        elt = elt->pri_next;
    }
    /* inject task at point -- if elt is null, this is the new end*/
    if (elt) {
        if (elt == EDF_QUEUE) {
            DL_EDF_PREPEND(elt, task);
            EDF_QUEUE = elt;
        } else {
            DL_EDF_PREPEND(elt, task);
        }
    } else {
        /* TODO: this incurs the O(n) again, optimize */
        DL_EDF_INSERT(EDF_QUEUE, task);
    }
}

Here is the caller graph for this function:

tcb_t* edf_pop

(

)

Definition at line 512 of file os.c.

References sched_task::absolute_deadline, sched_task_pool::deadline, edf_insert(), EDF_QUEUE, sched_task::next, sched_task_pool::next, sched_task::pri_next, sched_task_pool::queue, SCHEDULER_QUEUES, SYSTICKS_PER_HZ, and sched_task::tcb.

                 {

    volatile sched_task *executing = EDF_QUEUE;
    volatile sched_task_pool *pool = SCHEDULER_QUEUES;

    /* DL_EDF_DELETE(EDF_QUEUE, elt); */
    /* TODO: CHECKME: should we use pri_next or pri_prev?? */
    EDF_QUEUE = EDF_QUEUE->pri_next;

    /* KLUDGE: fix this for production */
    while (pool->queue != executing) {
        pool = pool->next;
    }
    /* will drop out with pool->queue = executing */

    executing->absolute_deadline = pool->deadline * SYSTICKS_PER_HZ;

    /* do the recycling, change the pool's head */
    /* TODO: CHECKME: should we use next or prev?? */
    pool->queue = executing->next;
    edf_insert(pool->queue);

    /* TODO: after use, put the command back in the appropriate pool */
    return executing->tcb;
}

Here is the call graph for this function: