Design Decisions: Why RK0 chose not to implement PCP

RK0 is a kernel designed for determinism, with priority inversion as a main scheduling concern. Instead of the more common Priority Ceiling used in deterministic profiles, it uses the Priority Inheritance Protocol (with a fully transitive implementation).

I want to explain why I made this choice, even though it is not set in stone.

Why PCP feels RK0ish

PCP solves real problems with a clear approach. It helps designers limit blocking, avoid unbounded priority inversion, and, in its original form, stops circular waits by blocking unsafe resource entries early. In a closed system where all tasks and resource accesses are known ahead of time, this is a strong guarantee. That last point alone could be enough to use PCP in RK0 if it did not conflict with a design principle.

RK0 aims to make scheduler behaviour easy to explain based on the current dependency graph.

PCP requires the system to consider a static map of dependencies that might matter in the future.

What is actually CEILING

There are actually two main ideas behind the ceiling concept.

The first idea is immediate ceiling locking. Each mutex region has a fixed ceiling, and a task is raised to that ceiling as soon as it enters the region. This is how protocols like POSIX PRIO_PROTECT work. A task cannot lock a mutex whose ceiling priority is lower than the effective task priority.

The second idea is the original Priority Ceiling Protocol, which uses a system ceiling. In this case, the scheduler looks at the highest ceiling among resources currently locked by other tasks. So if a task with effective priority K owns a ceiled mutex, other tasks with priority K cannot lock any ceiled mutex, even if it is free. This global check is what gives PCP its strong theoretical guarantees, but it is also where RK0’s goal of having no surprises disappears.

Ceiling values become part of the scheduler. If a user sets a ceiling too high, tasks might be blocked longer than needed. If a ceiling is set too low, the guarantees it should provide can fail. In a small, fully analysed system, this might be fine.

**The deadlock point: release order is not the issue**

One common reason to use PCP is that it prevents deadlocks. We should be fair here: RK0’s priority inheritance can handle nested locks regardless of release order: the effective priority is recalculated from the task’s original priority and the priorities of all waiters on any mutexes it still owns. Unlocking in a non-LIFO order does not leave a stale boost or remove a boost just because the last mutex released was not the right one.

But this is a separate issue from circular acquisition. If task A owns one mutex and waits for another, while task B owns the second mutex and waits for the first, no priority protocol can fix the resource order without adding an admission rule or a lock-order policy. PCP handles this by blocking certain entries from the start: A task is only allowed to acquire a lock if its priority is higher than all priority ceilings of all active mutexes in the system. RK0, on the other hand, does not make this global refusal rule the default behaviour.

The Immediate PCP protocol, on the other hand, will only avoid circular waiting if tasks have different priorities.


T1 priority L
T2 priority H

A ceiling H
B ceiling H

T1: lock A; sleep; lock B;
T2: lock B; sleep; lock A;

//IPCP
T1 runs
T1 locks A
T1 is raised from L to H
T1 sleeps while still owning A

T2 runs
T2 locks B
T2 is already H, so there is no effective change
T2 sleeps while still owning B

T1 wakes
T1 tries B
B is owned by T2
T1 blocks waiting for B

T2 wakes
T2 tries A
A is owned by T1
T2 blocks waiting for A

-- deadlock --

//PCP
Original PCP requires:
Original PCP uses the highest active ceiling owned by OTHER tasks.

T1 runs
T1 locks A
current ceiling = H

T1 sleeps while owning A
T1 is still effective L while sleeping

T2 runs
T2 owns NOTHING and tries B
(scheduler looks at the highest ceiling among 
resources currently locked by OTHER tasks)
T2 priority H, A is owned with ceiling H
T2 is now blocked on A by T1, so T1 inherits from T2.

T1 wakes at effective H
T1 tries B
(scheduler looks at the highest ceiling among 
resources currently locked by OTHER tasks)
T1 acquires B

IPCP prevents the deadlock if boosting to the ceiling prevents other eligible resource users from running while the lock is held.

Conclusion

RK0 did not leave out PCP because it is bad. It left out PCP because a global, hypothetical dependency does not match its ‘no-surprise’ approach.