scheduler: priority inversion problem #7365
Description
The RIOT scheduler seems to have no protection against the priority inversion problem where a task of medium priority can prevent the execution a higher prioritized task when that waits for a resource allocated by a low prioritized task. The attached code example demonstrated this behavior.
A common solution for this is a for this is priority inheritance mechanism, where owning task temporary inherits the priority of the waiting task. But there might be other solutions too.
Even though this problem can be mostly avoided in the application design, it would be an feature which can avoid critical complications and simplifies the design of complex applications.
An famous example for this problem is the Pathfinder Mission which got stuck in a reboot loop (triggered by the watchdog timer) and exceeded its energy budget. In that case, that could be fixed by remotely enabling the priority inheritance feature.
In the example below, the shared resource represented by the mutex res_mtx which is used by a low and a high priority thread. A medium priority thread starts working after 3 s prevents the low priority thread from freeing the mutex and thus, the high priority thread from being scheduled.
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "thread.h"
#include "mutex.h"
#include "xtimer.h"
mutex_t res_mtx;
char stack_high[THREAD_STACKSIZE_MAIN];
char stack_mid[THREAD_STACKSIZE_MAIN];
char stack_low[THREAD_STACKSIZE_MAIN];
void *t_low_handler(void *arg)
{
/* starting working loop immediately */
while(1){
printf("t_low: allocating resource...\n");
mutex_lock(&res_mtx);
printf("t_low: got resource.\n");
xtimer_sleep(1);
printf("t_low: freeing resource...\n");
mutex_unlock(&res_mtx);
printf("t_low: freed resource.\n");
xtimer_sleep(1);
}
return NULL;
}
void *t_mid_handler(void *arg)
{
/* starting working loop after 3s */
xtimer_sleep(3);
printf("t_mid: doing some stupid stuff...\n");
while(1){
thread_yield_higher();
}
}
void *t_high_handler(void *arg)
{
/* starting working loop after 500 ms */
xtimer_usleep(500);
while(1){
printf("t_high: allocating resource...\n");
mutex_lock(&res_mtx);
printf("t_high: got resource.\n");
xtimer_sleep(1);
printf("t_high: freeing resource...\n");
mutex_unlock(&res_mtx);
printf("t_high: freed resource.\n");
}
return NULL;
}
kernel_pid_t pid_low;
kernel_pid_t pid_mid;
kernel_pid_t pid_high;
int main(void)
{
xtimer_init();
mutex_init(&res_mtx);
puts("This is a scheduling test for Priority Inversion");
pid_low = thread_create(stack_low, sizeof(stack_low),
THREAD_PRIORITY_MAIN - 1,
THREAD_CREATE_STACKTEST,
t_low_handler, NULL,
"t_low");
pid_mid = thread_create(stack_mid, sizeof(stack_mid),
THREAD_PRIORITY_MAIN - 2,
THREAD_CREATE_STACKTEST,
t_mid_handler, NULL,
"t_mid");
pid_high = thread_create(stack_high, sizeof(stack_high),
THREAD_PRIORITY_MAIN - 3,
THREAD_CREATE_STACKTEST,
t_high_handler, NULL,
"t_high");
thread_sleep();
return 0;
}