_REAL-TIME SCHEDULING ALGORITHMS_
by Alberto Daniel Ferrari

Listing One

configuration file: TASK DESCRIPTION FILE
; Task set descriptions, from which tasks are instantiated. Keywords are at the
; line's beginning, and end with ':'. Everything in the line after the keywords
; or values is ignored. Lines beginning with '*' are also ignored. No line can
; be longer than MAX_STRING characters, and no name longer than 
; MAX_NAME_LENGTH. Please, maintain the order of the parameters in the task 
; descriptions.
; start:

test set: Article's Example

MAXTIME= 27    /* timeline's upper limit (starting at 0) */
Number of Application Tasks=3

APPLICATION TASKS DESCRIPTION:
Name       Criticality  Period      Execution_time    
Task A,       HIGH,        6,           2.
Task B,       HIGH,        8,           2.
Task C,        LOW,       12,           3.
end.





Listing Two

/***** RTALGS.C -- Algorithms for Real-Time Scheduling  *****
 ***** Alberto Ferrari -- alberto@lcmi.ufsc.br          *****/
/* Simulates the execution of a task set in a multitasking environment, under 
several real-time scheduling algorithms. The objective is to obtain a timeline
of the execution, and to show if tasks meet their deadlines or not. Tasks are
assumed to be hard real-time, preemptive, periodic, with deadline equal to the
next instance's arrival time, and independent (they do not need to syncronize 
with others in order to execute). They also do not suspend its execution 
voluntarily. All tasks start execution at the same time in the simulation.
Available algorithms for scheduling are Rate Monotonic (RM), Earliest-Deadline-
First (EDF), Least-Laxity-First (LLF), and Maximum-Urgency-First (MUF), 
selected in command line. Also selected in command line is the configuration 
file, containing the task set description and the system parameters.
Usage:  rtalgs -[e|E|l|L|m|M|r|R] <testvect.name> where: e, Earliest-Deadline-
First (EDF); l, Least-Laxity-First (LLF); m, Maximum-Urgency-First (MUF), 
r, Rate Monotonic (RM) *****/
void main( int argc, char *argv[]) 
{ 
      node n; 
      task_t *task, *new;
    init( argc, argv);
    printf( "\nSelected Scheduling Algorithm: %s,\n", labels[ alg]);
    (sched_alg_init)();
    /* select which task to run next */
    for( sys_time=0;
        /* the first condition is 'merit_list not empty' */
        (merit_list->header->forward[0]!=NIL || request_list->
                                                       header->forward[0]!=NIL)
            &&  sys_time <= max_time;
        sys_time++){

              /* and if current task emptied its allocated time... */
              if( current!= idle_task  &&  -- current->remaining == 0){
               current->state=DEAD;
               current->cycles++;
               delete_task( deadline_list, current->deadline, 
                                                                      current);
               current= idle_task;
            }
            /* Look out for deadline failures */
            while(  key_of( n=first_node_of( deadline_list))
                                                                  <= sys_time){
                if( (task= n->v)->state != DEAD){
                    printf( "At %d: task %c (\"%s\"), 
                                            instance %d, Deadline Failure%s\n",
                        sys_time, task->sys_id, task->name,
                                            task->instance, bell);
                }
                delete( deadline_list, n->key);
            }
            /* if it is time to launch a task... */
            while(  key_of( n=first_node_of( request_list))  
                                                                 <= sys_time){
                task_init( (task= n->v) );
                delete( request_list, n->key);
                insert_task( deadline_list, task->deadline,task);
                insert_task(  request_list, task->deadline, task);
            }
            new = (sched_alg)();
            /* swap and register who's using the processor */
            if( current!=new){
                context_switches++;
                current->state=READY;
                current=new;
                current->state=RUNNING;
            }
            timeline.history[ sys_time]= current->sys_id;
            #ifdef DEBUG
            printf( "%d: %s\n", sys_time, timeline.history);
            #endif
    }
    (sched_alg_end)();

    draw_timeline();
}
  ......
task_t *default_dispatcher( void)
{
    task_t *task;
    if(  (task=first_ready( merit_list))==NULL)
        return( idle_task);
    else if( current== idle_task)
        return( task);
    else /* current task prevails other tasks with same merit */
        return(  (*task->merit == *current->merit)? current : task);
}


Listing Three

/***** Rate Monotonic (RM) Algorithm *****/
void monotonic_rate_init( void)
{
    int i;
    node n;
    task_t *task;      /* 'task' is the task with 'lesser' period */
    float task_load=0.0, critical_task_load=0.0, schedulability_bound;
    /* in RM case, 'deadline_list' is different from the 'merit_list' */
    deadline_list= newList(); deadline_list ->sys_id= 'D';
    /* calculate n*(2^1/n - 1) */
    schedulability_bound= num_tasks * ( pow( 2.0, 1.0/num_tasks) -1.0);
    printf( "which has a schedulability bound of %.1f%% for %d tasks.\n",
            100.0 * schedulability_bound, num_tasks);
    /* insert tasks in merit_list by increasing periods */
    /* If two tasks with equal period, order them by original sequence */
    for( i=1; i<=num_tasks; i++){
        task->merit= &(task=task_set+i)->period;
        insert_task( merit_list, *task->merit, task);
        insert_task( request_list, 0, task);
    }
    puts( "Critical set is composed of");
    for( task= (n= merit_list->header->forward[0])->v; n!=NIL; 
         task= (n= n->forward[0])->v){
        task_load+= (float )task->cpu_time / (float )task->period;
        if( task_load <schedulability_bound){
            critical_task_load= task_load;
            printf( "\t%s,\n", task->name);
        }
    }
    printf( "which accounts for a critical load of %.1f%%, over a total 
      system load of %.1f%%\n", 100.0 * critical_task_load, 100.0 * task_load);

    if( task_load<=schedulability_bound) printf( "So, the whole task set IS");
    else if( task_load>1.0) printf( "WARNING: the whole task set IS NOT");
    else printf( "WARNING: the whole task set MAY NOT be");
    printf( " schedulable under RM\n\n");
}
void monotonic_rate_end( void){}
/***** Earliest-Deadline-First (EDF) algorithm *****/
void earliest_deadline_init( void)
{
    task_t *task;
    float task_load=0.0;
    int i;
    printf( "which has a schedulability bound of 100%%\n");
    /* in the EDF case, 'deadline_list' is the same as 'merit_list' */
    deadline_list= merit_list;
    /* insert tasks in merit_list by increasing deadlines */
    for( i=1; i<=num_tasks; i++){
        task->merit= &(task=task_set+i)->deadline;
        task_load+= (float )task->cpu_time / (float )task->period;
        insert_task( request_list, 0, task);
    }
    printf( "Total system task load = %.1f%%\n", 100.0 * task_load);
    if( task_load<=1.0) printf( "So, the whole task set IS");
    else printf( "WARNING: the whole task set IS NOT");
    printf( " schedulable under EDF\n\n");
}
void earliest_deadline_end( void) {}
/***** Least Laxity Algorithm (LLA)  *****/
void least_laxity_init( void)
{
    task_t *task;
    float task_load=0.0;
    int i;
    printf( "which has a schedulability bound of 100%%\n");
    /* in the LLF case, 'deadline_list' is not the same as 'merit_list' */
    deadline_list= newList(); deadline_list ->sys_id= 'D';
    for( i=1; i<=num_tasks; i++){
        task->merit= &(task=task_set+i)->laxity;
        task_load+= (float )task->cpu_time / (float )task->period;
        insert_task( merit_list, *task->merit, task);
        insert_task( request_list, 0, task);
    }
    printf( "Total system task load = %.1f%%\n", 100.0 * task_load);
    if( task_load<=1.0) printf( "So, the whole task set IS");
    else printf( "WARNING: the whole task set IS NOT");
    printf( " schedulable under LLF\n\n");
}
task_t *least_laxity( void)
{
    task_t *least;
    /* all tasks (except 'current') now have one less 'laxity' unit */
    if(  (least=update_laxity_and_get_least( merit_list)) ==idle_task)
        return( idle_task);
    else if( current== idle_task)
        return( least);
    else /* current task prevails other tasks with same merit */
        return( (*least->merit == *current->merit)? current : least);
}
void least_laxity_end( void){}
/* returns idle_task if 'l' is empty */
task_t *update_laxity_and_get_least( list l)
{
    task_t *task, *least;
    node n;
    least= idle_task;
    for( task= (n= l->header->forward[0])->v; n!=NIL; 
         task= (n= n->forward[0])->v){
        /* task->laxity(t) = task->deadline - t - task->remaining(t);
         * but now(t)= now(t-1)+1,
         * and task->remaining(t)=  task->remaining(t-1), if task!=current,
         * ==> task->laxity(t) = task->laxity(t-1) -1;
         *****************************************************************/
        /* look out! task->laxity is decremented only if its state is 
                                                        READY, because of && */
        if( task->state ==READY  &&  -- task->laxity<0){ 
                                                      /* if it's eligible... */
            printf( "At %d: task %c (\"%s\"), instance %d, will 
                            lose its deadline at %d%s\n", 
                sys_time, task->sys_id, task->name, 
                            task->instance, task->deadline, bell);
            task->state=BLOCKED;
        }
        if( (task->state ==READY  ||  task->state ==RUNNING)  
         &&  task->laxity < least->laxity)
                   least=task;
    }
    return( least);
}


Listing Four

/***** Maximum-Urgency-First (MUF) Algorithm *****/
list high_crit_l, low_crit_l;
task_t *first;
void maximum_urgency_first_init( void)
{
    node n;
    list temp_list;
    task_t *task;
    float critical_task_load=0.0, task_load=0.0, temp=0.0, load;
    int i, critical_set=TRUE;
    printf( "which has a schedulability bound of 100%%\n");
    /* in the MUF case, 'deadline_list' is not the same as 'merit_list' */
    deadline_list= newList(); deadline_list->sys_id= 'D';
    temp_list= newList(); temp_list->sys_id= 'T';
    high_crit_l= merit_list; high_crit_l->sys_id= 'H';
    low_crit_l= newList(); low_crit_l->sys_id= 'L';
    for( i=1; i<=num_tasks; i++){
        task=task_set+i;
        task->merit= &task->laxity;
        /* use temp_list to order tasks by increasing periods */
        insert_task( temp_list, task->period, task);
        insert_task( request_list, 0, task);
    }
    /* insert tasks in both (high_crit_l and low_crit_l) lists */
    puts( "Critical set is composed of"); /* the first 'n' tasks in 
                             'high_crit_l' with combined load less than 100% */
    for( task= (n= temp_list->header->forward[0])->v; n!=NIL; 
                                                  task= (n=n->forward[0])->v){
        task_load+=(load=(float )task->cpu_time/(float )task->period);
        if( task->criticality ==HIGH){
            if(  (temp+=load)<=1.0  &&  critical_set==TRUE){
                critical_task_load= temp;
                printf( "\t%s,\n", task->name);
                insert_task( high_crit_l, task->period, task);
            }else{
                critical_set= FALSE;
                printf( "WARNING at %d: Highly critical task 
                                    %c (\"%s\"),\ found NOT Schedulable!!%s", 
                                    now(), task->sys_id, task->name, bell);
                printf( "\nContinue anyway? (y/[N]) ");
                if( (i=getchar()) == '\n' || i=='n' || i=='N') 
                                                                      exit(0);
                else insert_task(low_crit_l,task->period,task);
            }
        }else{    /* task->criticality ==LOW */
            insert_task( low_crit_l, task->period, task);
        }
    }
    freeList( temp_list);
    printf( "which accounts for a critical load of %.1f%%, over a total 
                        system load of %.1f%%\n", 
                        100.0 * critical_task_load, 
                        100.0 * task_load);
    if( task_load<=1.0) printf( "So, the whole task set MAY BE");
    else printf( "WARNING: the whole task set IS NOT");
    printf( " schedulable under MUF\n\n");
}
task_t *maximum_urgency_first( void)
{
    task_t *least, *leasth, *leastl;
    /* all tasks (except 'current') now have one less 'laxity' unit */
    leasth= update_laxity_and_get_least( high_crit_l);
    leastl= update_laxity_and_get_least( low_crit_l);
    least= (leasth==idle_task)? leastl : leasth;
    /* all tasks (except 'current') have one less 'laxity' time unit */
    if( least==idle_task)
        return( idle_task);
    else if( current== idle_task)
        return( least);
    else /* current task prevails other tasks with same merit */
        return( (*least->merit == *current->merit)? current : least);
}
void maximum_urgency_first_end( void){}