Is priority inheritance applied "retroactively"

[hkengblom (1048576)]

Hi,

I’ve tried to find the answer to this question both here and by reading the code, but still I’m not sure.

Consider the following theoretical scenario,

We have three tasks t1, t2 and t3, t3 being the one with highest prio, t1 lowest.

1. t1 executes and successfully takes a mutex

2. t2 executes and blocks waiting on a semaphore that will at some point be “given” from an ISR.

3. t1 executes and blocks waiting on the same semaphore as t2. At this point t2 with its higher priority would get the semaphore when the ISR gives it. This is, as far as I understand, due to a queue/list both t1 and t2 are put on, a queue/list “owned” by the semaphore.

4. t3 executes and tries to get the same mutex t1 took in step 1 above. t3 blocks, and t1 will get hoisted priority due to priority inheritance, but is still blocked since it waits for the semaphore.

5. The ISR gives the semaphore both t1 and t2 is waiting for.

Who will get the semaphore t1 or t2 ? At this point t1 has highest priority, but at the time t1 started waiting for the semaphore t2 had the highest priority.

As far as I can see, priority inheritance is not applied “retroactively”, meaning, t2 would get the semaphore even though t1 at the point of time the semaphore is given from ISR has higher prio.

I do not consider this a bug, I just want to know. My gut-feeling is that it would be very cumbersome to look for other resources t1 is holding at the time t3 wants to acquire the mutex, and re-calculate the priority list in the semaphore.

Do I understand it correctly, or is there some kind of mechanism that will apply priority inheritance “retroactively” ?

br H

[richard-damon]

I believe that since a task can only be blocked on ONE resource when its priority is upgraded, that FreeRTOS could (and likely SHOULD) apply that priority to that list when the task has its priority upgraded. I am pretty sure the TCB contains the information needed to directly locate that task list.

[RAc]

From what I understand, Richard Barry’s explanations from here still hold:

Nested Mutexes and Priority Inheritance

rtel wrote on Tuesday, March 23, 2010: Whether or not it will cause problems depends on the the priorities of the tasks holding the mutexes. The priority inheritance assumes that only one mutex will be held at a time.  If two mutexes are held then the priority will be inherited to that of the highest task priority that is attempting to access the same mutex, but will be dropped back to the base priority when either mutex is returned.  This could result in some priority inversion, but this won’…

[hkengblom (1048576)]

@RAc

From what I understand, Richard Barry’s explanations from here still hold:

Not exactly the same scenario, but definitely related and interesting.

Regarding the TCB and if it contains information about held resources, yes it does, via the xEventListItem, but so far I have not found any code that would access that item and via that TCB member modify the order in queue held by the semaphore in the above example

(sorry for double posting and deleting, not used to the GUI)

[hkengblom (1048576)]

Did a small test to verify what the behavior is, for anyone coming across this later.

It seems, in the above given example, the semaphore is indeed given to task 2, even though task 1 at the time the semaphore is given has higher priority.

Here is my test-code, the semaphore is not given from an ISR but from another task, but I don’t think it should matter:

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"

#include "_memmap.h"

StaticTask_t t1TaskTCB;
StackType_t t1TaskStack[100];
StaticTask_t t2TaskTCB;
StackType_t t2TaskStack[100];
StaticTask_t t3TaskTCB;
StackType_t t3TaskStack[100];
StaticTask_t t4TaskTCB;
StackType_t t4TaskStack[100];

SemaphoreHandle_t            sem;
StaticSemaphore_t            semBuf;

SemaphoreHandle_t mutex;
StaticSemaphore_t mutexBuf;

void t1(void *arg) {
    (void)arg;
    mmDebug.t1 = 1;
    xSemaphoreTake(mutex, 0);
    mmDebug.t1 = 2;
    vTaskDelay(2000);
    mmDebug.t1 = 3;
    xSemaphoreTake(sem, 100000);
    mmDebug.t1 = 4;
    for(;;) {
        vTaskDelay(2000);
    }
}

void t2(void *arg) {
    (void)arg;
    mmDebug.t2 = 1;
    vTaskDelay(1000);
    mmDebug.t2 = 2;
    xSemaphoreTake(sem, 100000);
    mmDebug.t2 = 3;
    for(;;) {
        vTaskDelay(2000);
    }
}

void t3(void *arg) {
    (void)arg;
    mmDebug.t3 = 1;
    vTaskDelay(3000);
    mmDebug.t3 = 2;
    xSemaphoreTake(mutex, 100000);
    mmDebug.t3 = 3;
    for(;;) {
        vTaskDelay(2000);
    }
}

void t4(void *arg) {
    (void)arg;
    mmDebug.t4 = 1;
    vTaskDelay(4000);
    mmDebug.t4 = 2;
    xSemaphoreGive(sem);
    mmDebug.t4 = 3;
    for(;;) {
        vTaskDelay(2000);
    }
}

void tests(void) {
    mutex = xSemaphoreCreateMutexStatic(&mutexBuf);

    sem =  xSemaphoreCreateBinaryStatic(&semBuf);

    xTaskCreateStatic(t1,
                      "t1",
                      100,
                      NULL,
                      tskIDLE_PRIORITY + 1,
                      t1TaskStack,
                      &t1TaskTCB);

    xTaskCreateStatic(t2,
                      "t2",
                      100,
                      NULL,
                      tskIDLE_PRIORITY + 2,
                      t2TaskStack,
                      &t2TaskTCB);
    xTaskCreateStatic(t3,
                      "t3",
                      100,
                      NULL,
                      tskIDLE_PRIORITY + 3,
                      t3TaskStack,
                      &t3TaskTCB);
    xTaskCreateStatic(t4,
                      "t4",
                      100,
                      NULL,
                      tskIDLE_PRIORITY + 1,
                      t4TaskStack,
                      &t4TaskTCB);
}

The state of the debug variables after lets say 10 seconds are:
t1: 3
t2: 3
t3: 2
t4: 3

The test is run on an old FreeRTOS version 9.0.0, tick is 1 kHz

[RAc]

Actually, this here may be of interest to you as well:

ARM(R) Cortex(R) M Blog (ruediger-asche.de)

scroll down to the entry from Feb 4, 2017 entitled “On priority inversion and priority inheritance”. I wrote that entry after a private conversation with Segger first (who do implement aggregate priority inheritance in their OS) and then Richard Barry. Sorry I did not mention that before, didn’t have access to the site when I responded first.

[hkengblom (1048576)]

@RAc

Actually, this here may be of interest to you as well:

Thanks, that was food for thought. This is more or less exactly what I mean, there is a limit in complex situations when one has to stop perpetuate priority inheritance, it would just make the RTOS extremely complex and the penalty would be execution time.

[rtel (Richard Barry)]

@RAc

From what I understand, Richard Barry’s explanations from here still hold:

I don’t think that is still the case. The priority inheritance mechanism has been enhanced a couple of times since 2010. For example: https://github.com/FreeRTOS/FreeRTOS-Kernel/blob/main/History.txt#L968 - but it remains a simplified implementation (otherwise it would take too much code and memory).

A task can now have its priority raised more than once if it takes multiple mutexes, but the priority is only disinherited after releasing all the mutexes. In other words, it does not maintain a stack of priorities or associate different inherited values with each mutex, but instead counts the number of mutexes it holds, then only disinherits when the count unwinds to zero.