Transitive Priority Inheritance on Mutexes

The Priority Inheritance protocol can be defined by a single invariant: At any instant, a task assumes the highest priority amongst the tasks it is blocking.

Note that a task might own more than one mutex, but blocks on a single one. So, the dynamics of the waiting tasks must be observed to avoid breaking the protocol.

This post demonstrates RK0 fully transitive priority inheritance mechanism for mutexes. Specifically, it shows correct behaviour on an edge case: donor switching while mutexes are locked and nested. This is a known case in which ‘incomplete’ protocol implementations fail, allowing a real-time kernel to do what it shouldn’t: dispatch a less-urgent task and allow unbounded waiting for a more-urgent one.

This is one case that supports the rationale for an RK0 design choice: ‘(the decision of) allowing only static tasks is rooted in real-time correctness’.

Test case

A dependency chain with 2 mutexes and 4 contenders:

Task	Priority	Behaviour
TL	3 (lowest)	Starts first (because higher tasks are delayed) and acquires (owns) mutex A and B
TM	2	Blocks on A
TH	1	Blocks on B
TH0	0 (highest)	Blocks on B with timeout
T4	2	‘Noise’ task

We will see donor switching while the owner still holds locks, in a very tricky scenario, to demonstrate that RK0 correctly handles the priority inheritance ‘graph’ when it changes in unusual ways.

The intricate scenario (which exposes some cases that must be handled to avoid breaking the protocol invariant)

While lowest priority TL holds mutexes A + B:

Highest priority tasks TH0 + TH are also waiting on B, we expect that:
→ TL effective priority must be 0
If TH0 times out (removed from wait set!)
→ TL effective priority must drop to 1 (while still holding B)
If TL unlocks A first (wrong order)
→ TL must remain at priority 1 (TH still waits on B)
TL returns to its nominal priority when it is not blocking any higher-priority task.

Anything different from that is incorrect.

The code:

			
#include <kapi.h>
#include <application.h>
#include <logger.h>
#define STACKSIZE 128 /* words */
/* TH0: waits on B (prio 0) with timeout */
RK_DECLARE_TASK(task0Handle, Task0, stack0, STACKSIZE) 
/* TH : waits on B (prio 1) forever */
RK_DECLARE_TASK(task1Handle, Task1, stack1, STACKSIZE) 
/* TM : waits on A (prio 2) */
RK_DECLARE_TASK(task2Handle, Task2, stack2, STACKSIZE) 
 /* TL : higher priority tasks are delayed, so TL kicks off and
 owns A+B (prio 3) */
RK_DECLARE_TASK(task3Handle, Task3, stack3, STACKSIZE)
 /* X or T4  : middle priority poke (prio 2) */
RK_DECLARE_TASK(task4Handle, Task4, stack4, STACKSIZE)
RK_MUTEX mutexA;
RK_MUTEX mutexB;
VOID kApplicationInit(VOID)
{
    K_ASSERT(!kCreateTask(&task0Handle, Task0, RK_NO_ARGS, "TH0", stack0,
                          STACKSIZE, 0, RK_PREEMPT));
    K_ASSERT(!kCreateTask(&task1Handle, Task1, RK_NO_ARGS, "TH", stack1,
                          STACKSIZE, 1, RK_PREEMPT));
    K_ASSERT(!kCreateTask(&task2Handle, Task2, RK_NO_ARGS, "TM", stack2,
                          STACKSIZE, 2, RK_PREEMPT));
    K_ASSERT(!kCreateTask(&task3Handle, Task3, RK_NO_ARGS, "TL", stack3,
                          STACKSIZE, 3, RK_PREEMPT));
    K_ASSERT(!kCreateTask(&task4Handle, Task4, RK_NO_ARGS, "X", stack4,
                          STACKSIZE, 2, RK_PREEMPT));
    logInit(5); /* initialise log facility - 
    active object on lowest priority */
    /* the mutexes with prio inh enabled */
    kMutexInit(&mutexA, RK_INHERIT);
    kMutexInit(&mutexB, RK_INHERIT);
}
/**
 * It goes like this:
 * TL holds BOTH A and B, then blocks.
 * While TL blocked:
 *  - TM waits on A
 *  - TH waits on B forever (prio 1)
 *  - TH0 waits on B but times out (prio 0)
 *
 *  - TL wakes boosted to 0 
 *  - after TH0 times out, while TL still holds B, 
 * TL must drop to 1 (TH still waiting)
 *  - TL unlocks A first and must stay at 1
 *  - TL unlocks B and drops to 3
 */
/**
 * NOTE:
 * kSleep(t): suspends for t ticks on every call.
 * kSleepPeriod(p): suspends assuming a period 'p' defined on the 
 * first call. For every other call, any time drift is compensated
 * to keep overall phase as constant as possible (see the docbook)
 * kDelay(t): spins - runs doing nothing for t ticks (busy delay,
 * work load emulation)
 *
**/
volatile UINT gCycle = 0;
VOID Task3(VOID *args)
{
    RK_UNUSEARGS
    while (1)
    {
        kMutexLock(&mutexA, RK_WAIT_FOREVER);
        kMutexLock(&mutexB, RK_WAIT_FOREVER);
        UINT cycle = ++gCycle;
        logPost(": [TL] cycle=%u HOLDING A+B, BLOCK#1 | Eff:%d Nom:%d\r\n",
                cycle, RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        /* Let TM block on A and TH/TH0 block on B */
        kSleep(10);
        logPost(": [TL] WOKE#1 (expect Eff=0) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        /*
         * Keep  A+B, let TH0 timeout
         * while TH remains blocked on B.
         */
        logPost(": [TL] HOLDING A+B, BLOCK#2 (wait H0 timeout) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kSleep(30); 
        logPost(": [TL] WOKE#2 (Eff=1 after TH0 timemout) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        /*
         * Wrong release order so TL 
         * keeps boosted at 1, since TH still wants B.
         */
        logPost(": [TL] UNLOCK A FIRST (should Eff=1) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kMutexUnlock(&mutexA);
        /* Give TM time to run/ */
        kSleep(5);
        logPost(": [TL] AFTER UNLOCK A (expect Eff=1) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        
        kMutexUnlock(&mutexB);
        logPost(": [TL] UNLOCK B (restore prio) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        logPost(" [TL] EXIT | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kSleepPeriod(50);
    }
}
/* TM: blocks on A while TL holds it */
VOID Task2(VOID *args)
{
    RK_UNUSEARGS
    while (1)
    {
        kSleep(3);
        logPost(": [TM] Attempt LOCK A (should block) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kMutexLock(&mutexA, RK_WAIT_FOREVER);
        logPost(": [TM] GOT A | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kMutexUnlock(&mutexA);
        logPost(": [TM] EXIT | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kSleepPeriod(50);
    }
}
/* TH (prio 1) */
VOID Task1(VOID *args)
{
    RK_UNUSEARGS
    while (1)
    {
        kSleep(4);
        logPost("[TH ] Tries LOCK B (shall block) | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kMutexLock(&mutexB, RK_WAIT_FOREVER);
        logPost(" [TH ] GOT B | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kMutexUnlock(&mutexB);
        logPost(" [TH ] EXIT | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        kSleepPeriod(50);
    }
}
/*
 * TH0: blocks on B  with a timeout.
 * This forces donor switching while TL still holds B.
 * */
VOID Task0(VOID *args)
{
    RK_UNUSEARGS
    UINT seen = 0;
    while (1)
    {
        while (gCycle == seen)
        {
            kSleep(1);
        } 
        seen = gCycle;
        logPost(": [TH0] cycle=%u Try LOCK B (timeout) | Eff:%d Nom:%d\r\n",
                seen, RK_gRunPtr->priority, RK_gRunPtr->prioReal);
        RK_ERR err = kMutexLock(&mutexB, 15);
        if (err != 0)
            logPost(": [TH0] cycle=%u TIMEOUT on B (donor removed)\r\n", seen);
        else
        {
            logPost(": [TH0] cycle=%u GOT B (TL released early)\r\n", seen);
            kMutexUnlock(&mutexB);
        }
    }
}
/* bothers periodically */
VOID Task4(VOID *args)
{
    RK_UNUSEARGS
    while (1)
    {
        kSleep(5); 
        kDelay(3); /* spins */
        kSleepPeriod(2);
        logPost(": [T4  ] ran | Eff:%d Nom:%d\r\n",
                RK_gRunPtr->priority, RK_gRunPtr->prioReal);
    }
}

		

			
/* REPLICATING THE PASS CRITERIA HERE FOR CONVENIENCE */
/* 
While lowest priority  TL holds mutexes A + B:
If Highest priority tasks TH0 + TH are also waiting on B, 
EXPECTED: TL effective priority must be 0 
If  TH0 times out (removed from wait set!)
EXPECTED: TL effective priority must drop to 1 (while still holding B) 
If TL unlocks A first (wrong order)
EXPTECTED: TL must remain at priority 1 (TH still waits on B)
EXPECTED: TL returns to its nominal priority when it is not blocking 
any higher-priority task.      
 */
       0 ms :: : [TL] cycle=1 HOLDING A+B, BLOCK#1 | Eff:3 Nom:3
ms :: : [TH0] cycle=1 Try LOCK B (timeout) | Eff:0 Nom:0
 
ms :: : [TM] Attempt LOCK A (should block) | Eff:2 Nom:2
 
ms :: [TH ] Tries LOCK B (shall block) | Eff:1 Nom:1
 
ms :: : [TL] WOKE#1 (expect Eff=0) | Eff:0 Nom:3
 
ms :: : [TL] HOLDING A+B, BLOCK#2 (wait H0 timeout) | Eff:0 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TH0] cycle=1 TIMEOUT on B (donor removed)
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] WOKE#2 (Eff=1 after TH0 timemout) | Eff:1 Nom:3
 
ms :: : [TL] UNLOCK A FIRST (should Eff=1) | Eff:1 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TM] GOT A | Eff:2 Nom:2
 
ms :: : [TM] EXIT | Eff:2 Nom:2
 
ms :: : [TL] AFTER UNLOCK A (expect Eff=1) | Eff:1 Nom:3
 
ms ::  [TH ] GOT B | Eff:1 Nom:1
 
ms ::  [TH ] EXIT | Eff:1 Nom:1
 
ms :: : [TL] UNLOCK B (restore prio) | Eff:3 Nom:3
 
ms ::  [TL] EXIT | Eff:3 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] cycle=2 HOLDING A+B, BLOCK#1 | Eff:3 Nom:3
 
ms :: : [TH0] cycle=2 Try LOCK B (timeout) | Eff:0 Nom:0
 
ms :: : [TM] Attempt LOCK A (should block) | Eff:2 Nom:2
 
ms :: [TH ] Tries LOCK B (shall block) | Eff:1 Nom:1
 
ms :: : [TL] WOKE#1 (expect Eff=0) | Eff:0 Nom:3
 
ms :: : [TL] HOLDING A+B, BLOCK#2 (wait H0 timeout) | Eff:0 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TH0] cycle=2 TIMEOUT on B (donor removed)
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] WOKE#2 (Eff=1 after TH0 timemout) | Eff:1 Nom:3
 
ms :: : [TL] UNLOCK A FIRST (should Eff=1) | Eff:1 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TM] GOT A | Eff:2 Nom:2
 
ms :: : [TM] EXIT | Eff:2 Nom:2
 
ms :: : [TL] AFTER UNLOCK A (expect Eff=1) | Eff:1 Nom:3
 
ms ::  [TH ] GOT B | Eff:1 Nom:1
 
ms ::  [TH ] EXIT | Eff:1 Nom:1
 
ms :: : [TL] UNLOCK B (restore prio) | Eff:3 Nom:3
 
ms ::  [TL] EXIT | Eff:3 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] cycle=3 HOLDING A+B, BLOCK#1 | Eff:3 Nom:3
 
ms :: : [TH0] cycle=3 Try LOCK B (timeout) | Eff:0 Nom:0
 
ms :: : [TM] Attempt LOCK A (should block) | Eff:2 Nom:2
 
ms :: [TH ] Tries LOCK B (shall block) | Eff:1 Nom:1
 
ms :: : [TL] WOKE#1 (expect Eff=0) | Eff:0 Nom:3
 
ms :: : [TL] HOLDING A+B, BLOCK#2 (wait H0 timeout) | Eff:0 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TH0] cycle=3 TIMEOUT on B (donor removed)
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] WOKE#2 (Eff=1 after TH0 timemout) | Eff:1 Nom:3
 
ms :: : [TL] UNLOCK A FIRST (should Eff=1) | Eff:1 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TM] GOT A | Eff:2 Nom:2
 
ms :: : [TM] EXIT | Eff:2 Nom:2
 
ms :: : [TL] AFTER UNLOCK A (expect Eff=1) | Eff:1 Nom:3
 
ms ::  [TH ] GOT B | Eff:1 Nom:1
 
ms ::  [TH ] EXIT | Eff:1 Nom:1
 
ms :: : [TL] UNLOCK B (restore prio) | Eff:3 Nom:3
 
ms ::  [TL] EXIT | Eff:3 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] cycle=4 HOLDING A+B, BLOCK#1 | Eff:3 Nom:3
 
ms :: : [TH0] cycle=4 Try LOCK B (timeout) | Eff:0 Nom:0
 
ms :: : [TM] Attempt LOCK A (should block) | Eff:2 Nom:2
 
ms :: [TH ] Tries LOCK B (shall block) | Eff:1 Nom:1
 
ms :: : [TL] WOKE#1 (expect Eff=0) | Eff:0 Nom:3
 
ms :: : [TL] HOLDING A+B, BLOCK#2 (wait H0 timeout) | Eff:0 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TH0] cycle=4 TIMEOUT on B (donor removed)
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TL] WOKE#2 (Eff=1 after TH0 timemout) | Eff:1 Nom:3
 
ms :: : [TL] UNLOCK A FIRST (should Eff=1) | Eff:1 Nom:3
 
ms :: : [T4  ] ran | Eff:2 Nom:2
 
ms :: : [TM] GOT A | Eff:2 Nom:2
 
ms :: : [TM] EXIT | Eff:2 Nom:2
 
ms :: : [TL] AFTER UNLOCK A (expect Eff=1) | Eff:1 Nom:3
 
ms ::  [TH ] GOT B | Eff:1 Nom:1
 
ms ::  [TH ] EXIT | Eff:1 Nom:1
 
ms :: : [TL] UNLOCK B (restore prio) | Eff:3 Nom:3
 
ms ::  [TL] EXIT | Eff:3 Nom:3

WHY THIS MATTERS

Priority inversion is a dread phenomenon in real-time systems. This post shows that RK0 can avoid it, under a very difficult scenario: timeouts, misordered unlocks, and interference from other tasks.

In the next post, we will discuss how priority-driven message-passing is an RK0 feature. When fully-synchronous (RPCish) communication is required, leading to a not-so-obvious priority inversion case.