Realtime Linux (RTAI) - Radboud University Nijmegen
Exercise #9
RMS & EDF

Note: Excercise a,b,c can be done in a simulated realtime linux os in vmware, but the timing values will not be correct. Exercises d,e,f and g must be done on a real hardware platform.

Introduction

Besides preemptive priority-based FIFO and round robin scheduling, RTAI also supports Rate Monotonic Scheduling (RMS) and Earliest Deadline First (EDF) scheduling.

Objectives

The following are the primary objectives of this exercise:

To get experience with the RMS and EDF possibilities in RTAI.

Description

Rate Monotonic Scheduling (RMS)

Rate Monotonic Scheduling (RMS) is a simple scheduling policy for real time periodic tasks that assigns task priorities in the order of the highest task frequencies, i.e. the shortest periodic task gets the highest priority, then the next with the shortest period get the second highest priority, and so on. So RMS could be easily implemented by yourself simply by assigning appropriate priorities and using the standard prioritized preemptive First In First Out (FIFO) schedulers found in RTAI.

However there are situations, such as dynamic task creation of periodic tasks, that can make it annoying to keep track of all periods and corresponding priorities. Thus some form of minimal support could be of help. RTAI allows you to be sure to comply with MS by calling the function

 void rt_spv_RMS(int cpuid)

This should be done after the operating system knows the timing information of all your tasks. That is, after you have made all of your tasks periodic at the beginning of your application, or after you create a periodic task dynamically, or after changing the period of a task. The cpuid parameter of the function rt_spv_RMS() is only used by the multi uni-processor scheduler.

Note that the function only makes sure that priorities of periodic tasks are assigned accordingly to their periods. The RTAI schedular does not check if this leads to a feasible schedule, where all tasks meet their deadlines. This would also be impossible for the schedular, because it only knows the periods of tasks and not their execution times and deadlines. Hence, the programmer has to ensure schedulability, for instance, by using Rate Monotonic Analysis (RMA) as can be found in any textbook on OSes or scheduling.

Earliest Deadline First (EDF)

Another scheduling policy supported is Earliest Deadline First (EDF). Such a policy schedules always first the task with the earliest deadline. Hence, besides information about when to resume the task (e.g., by defining a period), the scheduler needs to know the deadline of each period. To realize this in RTAI, a task must call at the beginning of every run of one instance of the task, the function

void rt_task_set_resume_end_times(RTIME resume_time, RTIME end_time);

Here resume_time specifies the next release time of the task and end_time the next deadline. Hence, no specific periodicity is assumed. If the arguments are positive they denote absolute times. If the resume_time is negative, it means that it is relative to its previous resume_time and, if negative, also end_time is taken as relative to the previous resume_time, i.e., for negative values we obtain new absolute values as follows:

  rt_task.resume_time -= resume_time;
  rt_task.end_time = rt_task.resume_time - end_time;

It is possible to mix up all the scheduling policies, i.e., the ones above and SCHED_FIFO and RR. It is up to the programmer to insure RMS behaves correctly, e.g., by assigning lower priorities (higher numbers) to non periodic tasks. When EDF tasks come into the game a design choice has to be made for the case they mix up with tasks based on other policies. For instance, once could decide to run EDF tasks as the highest priority ones, i.e., any EDF task will run ahead of any other non-EDF task when its resume time expires.

Example EDF

Since there is little documentation about the use of EDF in RTAI, it is useful to study an example of EDF usage:

/* 

This example features NTASKS realtime tasks running periodically in EDF mode.
The task are given a priority ordered in such a way that low numbered tasks
have the lowest priority. However the tasks execute for a duration proportional 
to their number so that, under EDF, the lowest priority tasks run first.
So if they appear increasingly ordered on the screen EDF should be working.

*/

#include <linux/module.h>

#include <asm/io.h>

#include <asm/rtai.h>
#include <rtai_sched.h>

#define ONE_SHOT

#define TICK_PERIOD 10000000

#define STACK_SIZE 2000

#define LOOPS 3
//#define LOOPS 1000000000

#define NTASKS 8

static RT_TASK thread[NTASKS];

static RTIME tick_period;

static int cpu_used[NR_RT_CPUS];

static void fun(long t)
{
	unsigned int loops = LOOPS;
	while(loops--) {
		cpu_used[hard_cpu_id()]++;
		rt_printk("TASK %d with priority %d in loop %d \n", t, thread[t].priority,loops);
		rt_task_set_resume_end_times(-NTASKS*tick_period, -(t + 1)*tick_period);
	}
        rt_printk("TASK %d with priority %d  ENDS\n", t, thread[t].priority);
}


int init_module(void)
{
	RTIME now;
	int i;

#ifdef ONE_SHOT
	rt_set_oneshot_mode();
#endif
	for (i = 0; i < NTASKS; i++) {
		rt_task_init(&thread[i], fun, i, STACK_SIZE, NTASKS - i - 1, 0, 0);
	}
	tick_period = start_rt_timer(nano2count(TICK_PERIOD));
	now = rt_get_time() + NTASKS*tick_period;
	for (i = 0; i < NTASKS; i++) {
		rt_task_make_periodic(&thread[NTASKS - i - 1], now, NTASKS*tick_period);
	}
	return 0;
}


void cleanup_module(void)
{
	int i, cpuid;

	stop_rt_timer();
	for (i = 0; i < NTASKS; i++) {
		rt_task_delete(&thread[i]);
	}
	printk("\n\nCPU USE SUMMARY\n");
	for (cpuid = 0; cpuid < NR_RT_CPUS; cpuid++) {
		printk("# %d -> %d\n", cpuid, cpu_used[cpuid]);
	}
	printk("END OF CPU USE SUMMARY\n\n");
}

In fact, part of the information given above is derived by looking into the source of RTAI in /usr/src/, such as the definition of
rt_task_set_resume_end_times:

void rt_task_set_resume_end_times(RTIME resume, RTIME end)
{
    RT_TASK *rt_current;
    long flags;

    flags = rt_global_save_flags_and_cli();
    rt_current = RT_CURRENT;
    rt_current->policy   = -1;
    rt_current->priority =  0;
    if (resume > 0) {
        rt_current->resume_time = resume;
    } else {
        rt_current->resume_time -= resume;
    }
    if (end > 0) {
        rt_current->period = end;
    } else {
        rt_current->period = rt_current->resume_time - end;
    }
    rt_current->state |= RT_SCHED_DELAYED;
    rem_ready_current(rt_current);
    enq_timed_task(rt_current);
    rt_schedule();
    rt_global_restore_flags(flags);
}

Example Task Definition

In this exercise we want to schedule sets of tasks, each with some computation time C and period P. Instead of using real tasks, we simulate task timing by a means of a dummy task which runs periodically with period P and keeps the processor busy during time C, we call this a busy sleep for time C.

How to do a busy sleep?

In the API of RTAI linux we have the function

	void rt_busy_sleep(int ns)

with the following specification: Delay/suspend execution for a while. rt_busy_sleep delays the execution of the caller task without giving back the control to the scheduler. This function burns away CPU cycles in a busy wait loop so it should be used only for very short synchronization delays.

With this function we can easily make a dummy task which runs this rt_busy_sleep for a certain number of nanoseconds for each time it is called.
However, after some testing, it turns out that it does a busy sleep till some time is reached. When another task interrupts it for some time, it will still finish at the same moment as when it was not interrupted. So it is not suitable for our task simulation.

Hence, we decide to implement the busy sleep by running an empty for loop for some counter value loop_size:

for (i = 0; i < loop_size ; i++) {}

The main point is to determine the value of loop_size, e.g., such that it occupies the processor for 1 microsecond. This is done by running the for loop for some initial counter value and record the time it takes. Using this measured time we can calculate the counter value for 1 microsecond. The following code implements this :

    loop_size=1e9;
    rt_printk("Do counter loop from 0 to %lld.\n",countersleep);
    starttime = rt_get_time_ns();
    for (i = 0; i < loop_size ; i++) {}
    sleeptime_ns=rt_get_time_ns()-starttime;
    rt_printk("TIME PASSED in ns %lld.\n",sleeptime_ns);

    sleeptime_in_us = sleeptime_ns/1000; 
    loop_size_need_for_one_us_busysleep=loop_size/sleeptime_in_us;
    rt_printk("loop size needed for 1 us : %lld.\n",loop_size_need_for_one_us_busysleep);

With the calculated loop_size_needed_for_one_us_busysleep value we can implement our desired busysleep function. In the busysleep.c example below we implemented a busysleep function and we use it to make a dummy task witch uses the processor for 200 microseconds :

/*
    busysleep.c
         runs in a dummy_task a busy_sleep for 200 microseconds
*/


#include <linux/kernel.h>    /* decls needed for kernel modules */
#include <linux/module.h>    /* decls needed for kernel modules */
#include <linux/version.h>    /* LINUX_VERSION_CODE, KERNEL_VERSION() */
#include <linux/errno.h>    /* EINVAL, ENOMEM */

/*
  Specific header files for RTAI, our flavor of RT Linux
 */
#include "rtai.h"
#include "rtai_sched.h"
#include <rtai_sem.h>

MODULE_LICENSE("GPL");


/* globals */

#define CALIBRATION_PERCENTAGE  100
#define CALIBRATION_LOOP_SIZE  1e5
                            // or 1000000000LL

#define STACK_SIZE 2000
#define NTASKS 1
#define HIGH 100
#define MID 101
#define LOW 102

static RTIME count_need_for_one_us_busysleep;
static SEM sync;
static RT_TASK tasks[NTASKS];
static int switchesCount[NTASKS];

static RT_TASK init_task_str;

// executes a loop from 0 till count
//  returns : time in ns to execute the loop
inline RTIME loop(RTIME count) {
//RTIME loop(RTIME count) {
    //RTIME i;
    unsigned long int i;
    RTIME starttime;
    RTIME sleeptime_ns;

    //rt_printk("Do counter loop from 0 to %lld.\n",count);
    starttime = rt_get_time_ns();
    for (i = 0; i < count ; i++) {}
    sleeptime_ns=rt_get_time_ns()-starttime;

    return sleeptime_ns;
}    

/* function to callibrate busysleep function */
void calibrate_busysleep(void)
{
    RTIME sleeptime_ns;
    RTIME x;
    

    volatile RTIME loop_size=CALIBRATION_LOOP_SIZE;
    //RTIME loop_size=CALIBRATION_LOOP_SIZE;
    
    // loop with global CALIBRATION_LOOP_SIZE
    sleeptime_ns=loop(loop_size);   
    //sleeptime_ns=loop(CALIBRATION_LOOP_SIZE);   
    rt_printk("sleeptime_ns=%lld\n",sleeptime_ns);
    
    // EXPLANATION CALCULATION :
    //    sleeptime_in_us = sleeptime_ns/1000 
    //    count_need_for_one_us_busysleep=calibration_loop_size/sleeptime_in_us;
    //     -> add calibration factor to sleeptime_in_us :
    //           sleeptime_in_us -> sleeptime_in_us *  calibrationpercentage/100
    //     -> combine everything 
    //        counterbusysleepns= calibration_loop_size*10*calibrationpercentage/sleeptime_ns
    x=CALIBRATION_LOOP_SIZE*10*CALIBRATION_PERCENTAGE;
    do_div(x,sleeptime_ns);

   
    // set global calibration value
    count_need_for_one_us_busysleep =x;
}


/*
    RTIME busysleep(RTIME sleeptime_us ) 

      usage :    
          sleeptime_ns busysleep(sleeptime_us) 
    
      description :    
          keep the processor busy in a loop for a sleeptime_us amount 
          of microseconds

      returns :       
          the real time passed during this loop  (if other tasks get
          scheduled during this function this time can become much larger than
          the time this function keeps the cpu busy)
*/          
RTIME busysleep(RTIME sleeptime_us ) {
    RTIME sleeptime_ns;

    //volatile RTIME sleep_count;
    RTIME sleep_count;

    sleep_count= count_need_for_one_us_busysleep*sleeptime_us;
    sleeptime_ns=loop(sleep_count);   
    return sleeptime_ns;
}

// calibrate busy sleep
static void init(long arg)
{
    rt_printk("------------------------------------------ init task  started\n",arg);

    // first calibrate busysleep for the speed of the current machine
    // no other tasks are allowed to run to garantee optimal calibration
    calibrate_busysleep();
    rt_printk("count_need_for_one_us_busysleep=%lld\n", count_need_for_one_us_busysleep); 
     
    rt_printk("------------------------------------------ init task  ended\n",arg);
    return;
}


// task which calibrates busysleep and tests it
static void dummy_task(long arg)
{
    RTIME sleeptime_ns;
    RTIME sleeptime_us;

    rt_printk("RESUMED TASK #%d (%p) ON CPU %d.\n", arg, &tasks[arg], hard_cpu_id());
    rt_sem_wait(&sync);
    
    rt_printk("------------------------------------------ task %d started\n",arg);

    //  do a test sleep
    rt_printk("\nTEST SLEEP for 1000 us\n");
    sleeptime_us=1000;
    sleeptime_ns=busysleep(sleeptime_us);
    //  as long nothing else is happening on this machine, the returned
    //  realtime should match the  time the processor is kept busy
    rt_printk("RESULT SLEEPTIME in ns : %lld.\n\n",sleeptime_ns);
     
    rt_printk("END TASK #%d (%p) ON CPU %d.\n", arg, &tasks[arg], hard_cpu_id());
    rt_printk("------------------------------------------ task %d ended\n",arg);
    return;
}


static void signal(void)
/* signal handler, executed when a context switch occurs */
{
    RT_TASK *task;
    int i;
    for (i = 0; i < NTASKS; i++) {
        if ((task = rt_whoami()) == &tasks[i]) {
            switchesCount[i]++;
            rt_printk("Switch to task #%d (%p) on CPU %d.\n", i, task, hard_cpu_id());
            break;
        }
    }
}


// start the realtime tasks with a specific scheduling
int init_module(void)
{
    
    printk("Start of init_module\n");
    
    rt_set_oneshot_mode();
    start_rt_timer(1);
    
    printk("INSMOD on CPU %d.\n", hard_cpu_id());
    rt_sem_init(&sync, 0);

    // calibrate busy sleep
    rt_task_init(&init_task_str, init, 0, STACK_SIZE, LOW, 0, 0);
    rt_task_resume(&init_task_str);
   
    // start busysleep task
    rt_task_init(&tasks[0], dummy_task, 0, STACK_SIZE, LOW, 0, 0);
    rt_task_resume(&tasks[0]);
    rt_sem_broadcast(&sync);
    
    printk("End of init_module\n");
    
    return 0;
}


void cleanup_module(void)
{
    int i;  

    stop_rt_timer();
    rt_sem_delete(&sync);
    for (i = 0; i < NTASKS; i++) {
        printk("number of context switches task # %d -> %d\n", i, switchesCount[i]);
        rt_task_delete(&tasks[i]);
    }
    rt_task_delete(&init_task_str);
}

NOTES :

The CALIBRATION_LOOP_SIZE variable which is used for calibrating the busysleep is set to 1e9, however for slow machine this may be to big. In that case change it to a lower value.

Normal division is not allowed in kernel code, therefore division in the above code is done with the function do_div. From the linux kernel source we get :

   /*
   * do_div(dividend,divisor)  
   * 
   * do_div() is NOT a C function. It wants to return
   * two values (the quotient and the remainder), but
   * since that doesn't work very well in C, what it
   * does is:
   *
   * - modifies the 64-bit dividend _in_place_ with the 
       quotient   
   * - returns the 32-bit remainder
   *
   * This ends up being the most efficient "calling
   * convention" on x86.
   */

Exercises

Exercise 9a.

Implement using the above busysleep.c (see source) a program which runs 3 dummy tasks with priority 1 and which are scheduled with standard FIFO scheduling.

Exercise 9b.

Implement a program which runs 3 dummy tasks with priority 1,2,3 and which are scheduled with standard FIFO scheduling.
(in fact this is already RMS scheduling)

Exercise 9c.

Build and run the edf example given in this exercise (see edf_example.c in source). Explain what is happening.
How could we change we program so that edf scheduling starts immediately?
Do this and test the resulting code.

Exercise 9d.

For the task given below simulate the schedules using RMS.
Use the code given in simulate.c (see source).

Task	Computation time	Period
τ1	C1 = 3	T1 = 6
τ2	C2 = 2	T2 = 9
τ3	C3 = 2	T3 = 11

Exercise 9e.

Rewrite the RMS program of 9d. so you can use it for EDF scheduling.
For the task given in 9d. simulate the schedules using EDF.

Exercise 9f.

For the task given below simulate the schedules using RMS and EDF.

Task	Priority	Computation time	Period
τ1	3	C1 = 2	T1 = 7
τ2	2	C2 = 4	T2 = 16
τ3	1	C3 = 7	T3 = 31

Exercise 9g.

For the tasks given in 9f. how much can you increase C3 theoretically so that EDF scheduling is still possible?
Simulate EDF with these values. Is it also schedable in the simulation? If not, why not?

Last Updated: 26 September 2007 ( Harco Kuppens)
Created by: Harco Kuppens
h.kuppens@cs.ru.nl

Realtime Linux (RTAI) - Radboud University Nijmegen Exercise #9 RMS & EDF