Assignment updates

10/11/23 Added note about different data type of timespec tv_sec.

1   Assignment

Under a real-time operating system, when a task with the highest priority needs to run, it should “get the CPU” as soon as possible, without waiting for other tasks to finish. However, if the high-priority task and another tasks share a resource (e.g. critical section protected by a mutex), the high-priority task may have to wait for a lower-priority task to finish the critical section. In this exercise, you will measure how does priority inheritance mechanism influence the wait duration.

  • Create an application that will measure the worst-case mutex blocking time (i.e. one number) of the highest-priority task.
  • Measure the worst-case among a given number of measurements (below specified as Count).
  • Compare the results when the priority inheritance for the mutex is switched on and off. The goal is to find such a combination of various timing constants (see below) that results in high difference between worst-case mutex blocking times with and without priority inheritance.

To create the application you can use the snippets provided below. The challenge is to tune the lengths of delays and do_something...() code in the individual tasks so that priority inversion actually occurs. It might happen that the task execution is accidentally synchronized in a way that priority inversion does not happen. If you think that this might be your case, you can use System Viewer to explore the execution (see the first lab session). You can also change the parameters randomly with the hope that at some point you find the right combination where priority inversion occurs.

2   Submission guidelines

  • Implement the application as either Downloadable Kernel Module (DKM) or Real-Time Process (RTP), as it is not important which one you select. See the following sections for detailed instructions.

2.1   Common guidelines

These instructions hold for both DKM and RTP.

  1. The functions on this page use several macros. Accompany your source code with their definition (inside config.h):

    /* Clock rate for 'sysClkRateSet()' function. */
    #define CLOCK_RATE              1000
    
    /* Priority of three tasks -- lower number = higher priority. */
    #define HIGH_PRIORITY           210
    #define MID_PRIORITY            211
    #define LOW_PRIORITY            222
    
    /* Work factors of the tasks for 'do_work_for_some_time()'. */
    #define MID_PRIORITY_WORK       10
    #define LOW_PRIORITY_WORK       3
    
    /* Delays of the tasks. Fill them with your own values */
    #define HIGH_PRIORITY_DELAY     ?
    #define MID_PRIORITY_DELAY      ?
    #define LOW_PRIORITY_DELAY      ?
    

    Feel free to modify the macros as you like and observe behaviour of the system. Stick to these values only when submitting the assignment to BRUTE and when showing the application to the teacher.

  2. The entry function should receive two parameters mode and count. Passing them differs between DKM and RTP. See below for details. Their meaning is as follows:

    • mode selects whether the mutex uses priority inheritance or not:
      • value "N" means no priority inheritance,
      • value "Y" activates the priority inheritance.
      • Other values should lead to error and termination of the application.
    • count specifies the number of measurements. The program should terminate after performing count measurements. If count is zero or is not specified at all, measurements runs indefinitely.
  3. Created tasks should be named as follows:

    1. low priority task is named tLPrio,
    2. middle priority task is named tMPrio, and
    3. high priority task is named tHPrio.
  1. Report start of the measurement by printing measurement started and end of the measurement by printing measurement finished.

    When the program prints the finish message, all other tasks should finish automatically too. We suggest to use the end variable for this, as shown in the examples below.

  2. Measured worst-case mutex blocking time is printed to standard output each time it changes. It is reported as an integer number of milliseconds (without units) followed by a newline character.

  3. Example of application output is shown below:

    Measurement started
    0
    440
    500
    Measurement finished
    

2.2   Downloadable Kernel Module guidelines

  1. Entry point function has this prototype (the meaning of arguments is described above):

    void CreateTasks(char* mode, int count);
    
  2. Use sysClkRateSet(CLOCK_RATE) at the beginning of your program to achieve higher clock precision.

  3. Don't use exit() in DKM code. To terminate a DKM task, just return from the entry point function (or proceed to the end of it).

  4. The CreateTasks function must end right after starting the measurement (i.e., after spawning all the tasks).

2.3   Real-Time Process guidelines

  1. The main function should receive the mode argument via argv[1] and count via argv[2].

  2. Entry point function has to remain active during the whole measurement. When it ends, all spawned tasks should be deleted.

    Use a semaphore to synchronize the termination of the main thread with the high priority thread, i.e., semTake in main(), semGive at the end of tHPrio.

2.4   Lab submission guidelines

In order to submit this assignment during the lab, please prepare:

  1. Run CreateTasks("N", 200) / main("N", 200) on the board.
    • Show the output of the function.
    • Run System Viewer and record a trace of your application. Show segment where priority inversion occurs.
  2. Run CreateTasks("Y", 200) / main("Y", 200) on the board.
    • Show output of the function.
    • Run System Viewer and record a trace of your application. Show segment where priority inheritance is active.

Note

Do not forget to use Event Logging Level -- Additional Instrumentation. This setting shows where the tasks are taking and releasing the mutex. In case you forget how to do it, see first assignment.

3   Hints

3.1   Pseudo code of tasks in the application

Pseudo-code of the highest priority task can look like this:

while (/* loop NUMBER_OF_MEASUREMENTS times */) {
  struct timespec tstart, tend, result;
  clock_gettime(CLOCK_MONOTONIC, &tstart);
  if (semTake(mutex, WAIT_FOREVER) == ERROR)
    fprintf(stderr, "semTake error\n");
  clock_gettime(CLOCK_MONOTONIC, &tend);
  semGive(mutex);
  timespec_subtract(&result, &tend, &tstart);
  /* Handle measurement and print if necessary */
  taskDelay(HIGH_PRIORITY_DELAY); /* let other tasks run */
  n++;
}

end = 1; /* Signal the other tasks to end */

Note

If you use clock_gettime() to determine the current time, the result is of type struct timespec. You can find documentation about this type and hints how to substract two values of this type in glibc info pages. Run this command from Linux terminal:

info libc "Elapsed Time"

For your convenience, we provide you the function mentioned there, already converted for use with struct timespec:

/* Subtract the `struct timespec' values X and Y,
   storing the result in RESULT (result = x - y).
   Return 1 if the difference is negative, otherwise 0.  */

int
timespec_subtract (struct timespec *result,
           struct timespec *x,
           struct timespec *y)
{
  /* Perform the carry for the later subtraction by updating Y. */
  if (x->tv_nsec < y->tv_nsec) {
    int num_sec = (y->tv_nsec - x->tv_nsec) / 1000000000 + 1;
    y->tv_nsec -= 1000000000 * num_sec;
    y->tv_sec += num_sec;
  }
  if (x->tv_nsec - y->tv_nsec > 1000000000) {
    int num_sec = (x->tv_nsec - y->tv_nsec) / 1000000000;
    y->tv_nsec += 1000000000 * num_sec;
    y->tv_sec -= num_sec;
  }

  /* Compute the time remaining to wait.
     `tv_nsec' is certainly positive. */
  result->tv_sec = x->tv_sec - y->tv_sec;
  result->tv_nsec = x->tv_nsec - y->tv_nsec;

  /* Return 1 if result is negative. */
  return x->tv_sec < y->tv_sec;
}

Warning

Structure struct timespec used in this assignment is defined differently on the simulator and on the MZAPO board (see Year 2038 problem). Be careful when performing arithmetic operations with both timespec fields, as you can get different results due to integer overflows. The differences follow from Usual Arithmetic Conversions and Integer Promotions defined by the C language standard.

Simulator MZAPO
struct timespec
{
    long tv_sec; /* 32 bits */
    long tv_nsec;
};
struct timespec
{
    long long tv_sec; /* 64 bits */
    long tv_nsec;
};

In order for the task to block at some time, there must be another task contending for the same mutex:

while (!end) {
  semTake(mutex, WAIT_FOREVER);
  do_something_while_the_mutex_is_locked();
  semGive(mutex);
  taskDelay(LOW_PRIORITY_DELAY); /* this delay can be even zero - do you know why? */
}

If our application had only the two above tasks, priority inversion would never happen. Therefore, a third middle-priority task has to be added. Note, that this task can be completely independent of the other tasks (doesn't share mutexes with them).

while (!end) {
  do_something_very_long();
  taskDelay(MID_PRIORITY_DELAY); /* wait to let the low priority task run */
}

3.2   do_something_*()

Functions do_something_*() in the above examples are filled with a code with long, but finite-time execution. Example of such a function is given below:

void do_work_for_some_time(int x)
{
    long int len = x * 100000000;
    while (len > 0) len--;
}

3.3   Passing parameters to the functions

Parameters can be passed to your application by filling the appropriate field in Run → Run Configurations... → Launch Context → General → Arguments. This is valid for both Downloadable Kernel Modules and Real-Time Processes.

  1. In case of a kernel module, parameters are passed as arguments to a regular C function, therefore entry point function should have the following prototype:

    void CreateTasks(char* mode, int count);
    
  2. In case of a real-time process, parameters are passed as arguments via standard argc/argv arguments. The main function should have the following prototype:

    int main(int argc, char* argv[]);
    

3.4   Setting a CPU affinity for all tasks

In a multicore system it may happen that the High and Low priority tasks run on a different core than the Middle priority task. To prevent such situations and ensure that you can always observe the problematic priority inversion, set affinity of all tasks to the same CPU as follows:

cpuset_t affinity;
CPUSET_ZERO(affinity);
CPUSET_SET(affinity, 0);
taskCpuAffinitySet(taskIdSelf(), affinity);

/* All tasks created below will inherit the CPU affinity set above. */

/* Create the task but only activate it after setting its affinity */
TASK_ID tid = taskSpawn("myCpu1Task", 100, 0, 5000, printf,
                        (int) "myCpu1Task executed on CPU 1!\n", 0, 0, 0, 0, 0, 0, 0, 0, 0);

if (tid == NULL)
    return (ERROR);

3.5   Traces

Here we show the traces of the program with priority inheritance switched off and on. You can compare them with your application's traces when to tune the delay constants. (Thanks to Ondrej Kucera)

inherit_off.png

Priority inheritance switched off

inherit_on.png

Priority inheritance switched on