The user nicked Tom from mikrocontroller.net brought an interesting issue to my attention: How do different RTOSs handle priority inheritance on muteces in complex waiting situations?

Let's look at the following code. We omit initialization for readability's sake:

// this hogs CPU cycles for p_Delay OS ticks
unsigned long TaskUseTime(unsigned long p_Delay)
{
TickType_t a_Future = xTaskGetTickCount() + p_Delay;
// won't work well on architectures where
// portTICK_TYPE_IS_ATOMIC is not defined
while (xTaskGetTickCount() < a_Future) {};
}


void Task1(void *p_Unused) // this runs at lowest pri (tskIDLE_PRIORITY+1)
{
/* obtain the mutex, then hog some CPU time. */
xSemaphoreTake(g_Mutex,portMAX_DELAY);
TaskUseTime(5); // hog cpu time
xSemaphoreGive(g_ReaderMutex);
vTaskDelete( NULL );
}

void Task2(void *p_Unused) // this runs at 2nd lowest pri (tskIDLE_PRIORITY+2)
{
vTaskDelay(1); // to make sure task1 has a chance to obtain the mutex
TaskUseTime((unsigned long)0xffff0000);
}

void Task3(void *p_Unused) // this runs at medium pri (tskIDLE_PRIORITY+3)
{
vTaskDelay(2); // to make sure task1 has a chance to obtain the mutex
/* obtain the mutex, then hog some CPU time. */
xSemaphoreTake(g_Mutex,portMAX_DELAY);
TaskUseTime(2); // hog CPU time
xSemaphoreGive(g_Mutex);
}

void Task4(void *p_Unused) // this runs at 2nd highest pri (tskIDLE_PRIORITY+4)
{
vTaskDelay(3); // to make sure task1 has a chance to obtain the
// mutex AND task 3 can start up
while (1)
{
TaskUseTime((unsigned long)5);
vTaskDelay(1); // to make sure task2 gets a chance to do
//something for demo purposes
};
}

void Task5(void *p_Unused) // this runs at highest pri (tskIDLE_PRIORITY+5)
{
vTaskDelay(4); // to make sure tasks 1 and 2 get the mutex first
/* obtain the mutex, then hog some CPU time. */
xSemaphoreTake(g_Mutex,portMAX_DELAY);
TaskUseTime(2); // hog CPU time
xSemaphoreGive(g_Mutex);
}

In short, all tasks hog CPU time in a CPU bound loop. According to the rules of RTOS, this means that task 5, having the highest priority, will starve out all lower priority tasks. Pretty boring appliction that is.

Now. To make things more interesting, tasks 1,3 and 5 all attempt to access a mutex: task 1 will claim the mutex immediately, then attempt to hog 10 OS ticks worth of time. While it does that, task 3 and 5 will attempt to claim the mutex as well.

The percepio visualization trace below shows immediately what happens. As task1 has claimed the mutex, task2 starts starving out out task1. At timer tick 2, however, task3 attempts to claim the mutex, which causes FreeRTOS to bump task1's priority to 3, thus relieving the priority inversion situation. However, at tick 3, task 4 comes in and would thus starve out everything below it...

wouldn't there be task5 also attempting to claim the mutex at tick 4. The priority inheritance mechanism kicks in again, bumping task1's priority to 5 such that task1 now has a chance to complete its computation at the highest priority of another task waiting for the mutex (which is 5).





The interesting question here is this: Once task1 has completed its computation, who is next in line to get the mutex? According to the rules of FIFO, it would be task2; however, that's undesirable because task5 has the highest priority of those waiting (3 and 5). And lo and behold, that's what's happening: Task5 gets the mutex next even though Task3 was first to become suspended on the mutex. The place FreeRTOS does this is in the guts on xSemaphoreTake() which is really just a wrapper around xQueueGenericReceive(). Here, tasks susupended on the object are sorted in priority order automatically such that the next call to xSemaphoreGive() will without any further action select the task of the highest waiting priority to obtain the semaphore or mutex (please remember that the nomenclature of FreeRTOS freely mixes mutexes and semaphores which is unfortunate because a lot of people also believe erratically that semaphores and muteces were the same. They aren't).

Now there is one nasty situation in which priority inheritance isn't realized all the way through. For this scenario to study, let us briefly assume that task4 performs an infinite CPU bound computation:

void Task4(void *p_Unused) // this runs at 2nd highest pri (tskIDLE_PRIORITY+4)
{
vTaskDelay(3); // to make sure task1 has a chance to obtain the
//mutex AND task 3 can start up
while (1)
{
};
}

Assume Task2 claims another mutex g_NestedMutex which tas1k attempts to claim after having claimed g_Mutex but BEFORE task3 attempts to claim g_Mutex (this is the area shaded grey in the second visualization below). At this point, task1 still runs at base priority 1; thus, task2's priority is NOT bumped to 3. Thus, task4 can now starve out the entire shebang even though task5's claim to g_Mutex has raised task1's priority to 1 - which doesn't help, though, because task1 can not propagate its new Priority to task2, and task2 is starved out by task4. This is a classical priority inversion problem.

The problem here is that Task2 is not dynamically informed about changes to task1's priority; as task3 and then subsequently task5 causes task1 to inherit their respective priorities, task2 is not affected but should also inherit the higher priorities.