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. a 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 the priority inheritance mechanism influence the length of waiting for the mutex.
Goals:
- Create an application that measures 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 (specified below as Count).
- Compare the results when the priority inheritance mechanism is switched on and off of the given mutex. The goal is to find such a combination of various timing constants (see below) that leads to big 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 the priority inversion actually occurs. It might happen that the task execution is accidentally synchronized in a way not leading to priority inversion. If you think that this might be your case, you can use the 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 will 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.
The functions on this page use several macros. Accompany your source code with their definition in 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 values as you like and observe the behavior of the system. Stick to the values mentioned here only when submitting the assignment to BRUTE and when showing the application to the teacher.
The entry function should receive two parameters prio_inh and count. Passing them differs between DKM and RTP. See below for details. Their meaning is as follows:
- prio_inh 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.
- prio_inh selects whether the mutex uses priority inheritance or not:
Created tasks should be named as follows:
- low priority task is named tLPrio,
- middle priority task is named tMPrio, and
- high priority task is named tHPrio.
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 too in short time. We suggest to use the end variable for this, as shown in the examples below.
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.
Example of application output is shown below:
Measurement started 0 440 500 Measurement finished
2.2 Downloadable Kernel Module guidelines
Entry point function has this prototype (the meaning of arguments is described above):
void start(char* prio_inh, int count);
Use sysClkRateSet(CLOCK_RATE) at the beginning of your program to achieve higher clock resolution.
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).
The start function must end right after starting the measurement (i.e., after spawning all the tasks).
2.3 Real-Time Process guidelines
The main function should receive the prio_inh argument via argv[1] and count via argv[2].
The main task should remain active during the whole measurement. When it ends, all spawned tasks should be terminated.
Use a semaphore to synchronize the termination of the main thread after completion of 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:
- Run start("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 the interval where priority inversion occurs.
- Run start("Y", 200) / main("Y", 200) on the board.
- Show output of the function.
- Run System Viewer and record a trace of your application. Show interval 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 forgot how to do it, see the 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.
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 start(char* prio_inh, int count);
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)

Priority inheritance switched off

Priority inheritance switched on