Assignment updates

12/11/21 The assignment was restructuralized. However, the goal is still the same. Older version can be found here.

04/11/21 Feel free to reduce the do_work_for_some_time constant to 10.000.000 when running on the board, as it is not necessary to wait that long for the results. Note that you will have to increase the work constants MID_PRIORITY_WORK and LOW_PRIORITY_WORK.

01/11/21 The entry point function has to end after spawning and activating all the tasks. This is important for Downloadable Kernel Module as it produces extra output when the function returns.

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 at least 1000 (better 10000) measurements. 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 or Real-Time Process, as it is not important which one you select. See following sections for instructions.

  • Test your application in the simulator. However to be awarded by points, your solution has to be both checked by the upload system and also demonstrated on real hardware.

  • Since Real hardware (MicroZed) used in this task has 2 CPU cores, it may happen that the High and Low priority tasks run on different core than the Middle priority task.

    To change the affinity of the task (assign the task to the specific CPU core), please see the following page in the Wind River Documentation > VxWorks, 6.9 > VxWorks Kernel Programmer's Guide, 6.9 > Multiprocessing Technologies > VxWorks SMP > CPU Affinity pages of the documentation. Short example is also available in a section below.

2.1   Common guidelines

These instructions hold for both Downloadable Kernel Module and Real-Time Process.

  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. 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.
  3. The tasks have to be spawned (or activated) in the following order: tLPrio, tMPrio, tHPrio. This way, the measurement won't be affected by the values obtained when there is no competing task.

  4. Report start of the measurement by printing measurement started and end of the measurement by printing measurement finished. As measurement finishes, all created tasks should end as well.

    • This behaviour is controlled by the high priority task. When the target number of the measurements is reached, a global variable (e.g. end) should be set to a certain value, that allows the other tasks to end.
  5. Measured worst-case mutex blocking time is printed to standard output each time it changes as integer number of milliseconds (without units) followed by a newline character.

  6. Example of application output is shown below:

    Measurement started
    0
    440
    500
    Measurement finished
    

Note: Don't use ARMARCH7gnu_SMP build spec as it is not supported on the simulator. Use it only when uploading to the real hardware.

2.2   Downloadable Kernel Module guidelines

  1. Entry point function is called CreateTasks. It takes two arguments.
  • First argument of the entry point function selects the mode of operation:
    • passing value 1 runs the tasks without priority inheritance,
    • passing value 2 runs the tasks with priority inheritance, and
    • passing other values terminates the application.
  • The second argument configures the number of measurements.
  1. Use sysClkRateSet(CLOCK_RATE) at the beginning of your program to achieve higher clock precision.
  2. Proper termination of Downloadable Kernel Module is to call return within the entry point function (or proceed to the end of it). Don't use exit() in this case.
  3. Entry point function has to end right after starting the measurement (i.e., after spawning all the tasks).

2.3   Real-Time Process guidelines

  1. Entry point function is called main. It takes two arguments.
  • First argument of the entry point function selects the mode of operation:
    • passing value 1 runs the tasks without priority inheritance,
    • passing value 2 runs the tasks with priority inheritance, and
    • passing other values terminates the application.
  • The second argument configures the number of measurements.
  1. Entry point function has to remain active during the whole measurement (as when it ends, all spawned tasks are deleted).

    Use a semaphore to send a signal from the high priority task.

2.4   Lab submission guidelines

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

  1. Run CreateTasks(1, 200) / main(1, 200) on board.
    • Show output of the function.
  2. Run CreateTasks(2, 200) / main(2, 200) on board.
    • Show output of the function.
    • Run System Viewer and record your application. Show segment with priority inheritance.

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;
}

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.2.1   Older version of do_something_*()

In previous runs of this subject students used a different function, which is shown below:

/*
 * Deprecated
 * Use function 'do_work_for_some_time()' instead.
 */
void do_work_for_x_milliseconds(int x)
{
    struct timespec begin, end, result;
    int milliseconds = 0;
    clock_gettime(CLOCK_MONOTONIC,&begin);
    while (milliseconds < x)
    {
        clock_gettime(CLOCK_MONOTONIC,&end);
        timespec_subtract(&result, &end, &begin);
        milliseconds = result.tv_sec*1000 + result.tv_nsec/1000000;
    }
}

What is the downside of using this function, and, therefore, what is the reason that it is not used anymore?

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 receive one integer parameter as shown below:

    void CreateTasks(int i) {};
    
  2. In case of a real-time process, parameters are passed as arguments to a regular C application, therefore main function receive parameters as shown below:

    int main(int argc, char** argv) {};
    

3.4   Setting a CPU affinity for a task (example)

cpuset_t affinity;
int tid;

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

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

/* Clear the affinity CPU set and set index for CPU 1 */
CPUSET_ZERO (affinity);
CPUSET_SET (affinity, 1);

if (taskCpuAffinitySet (tid, affinity) == ERROR)
{
    /* Either CPUs are not enabled or we are in UP mode */
    taskDelete (tid);
    return (ERROR);
}

/* Now let the task run on CPU 1 */
taskActivate (tid);

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