Priority Inheritance 구현 — Inherit·Disinherit·Chain

#한 줄 요약

“PI는 take 시 boost하고 give 시 복원한다” — uxBasePriority가 원래 값을 보존합니다.

이번 글에서는 FreeRTOS의 PI 구현을 코드 수준에서 살펴봅니다. inherit과 disinherit, 그리고 chained 상황까지 따라가 봅니다.

#TCB의 PI Field

1
typedef struct {
2
    UBaseType_t uxPriority;       // 현재 priority (boost 시 변경)
3
    UBaseType_t uxBasePriority;   // 원래 priority (PI 해제 시 복원)
4
    UBaseType_t uxMutexesHeld;    // 보유 mutex 수
5
    /* ... */
6
} TCB_t;

uxBasePriority가 PI 구현의 핵심입니다. 이 값은 영구적인 우선순위이고, uxPriority는 임시로 변경되는 값입니다.

#Inherit — Boost

1
void vTaskPriorityInherit(TaskHandle_t pxMutexHolder) {
2
    TCB_t *holder = (TCB_t *)pxMutexHolder;
3

4
    /* Caller (current task)가 더 높은 priority면 */
5
    if (holder->uxPriority < pxCurrentTCB->uxPriority) {
6
        /* Ready list에서 제거 */
7
        if (listIS_CONTAINED_WITHIN(
8
            &(pxReadyTasksLists[holder->uxPriority]),
9
            &(holder->xStateListItem))) {
10
            uxListRemove(&(holder->xStateListItem));
11
            /* Bitmap 정리 */
12
            taskRESET_READY_PRIORITY(holder->uxPriority);
13
        }
14

15
        /* Priority boost */
16
        holder->uxPriority = pxCurrentTCB->uxPriority;
17

18
        /* New priority list로 재삽입 */
19
        prvAddTaskToReadyList(holder);
20
    }
21
}

호출 시점은 Mutex take 실패 직후, waiter 추가 시점입니다. Wait list에 들어가기 직전에 boost가 일어납니다.

#Disinherit — 복원

1
BaseType_t xTaskPriorityDisinherit(TaskHandle_t pxMutexHolder) {
2
    TCB_t *holder = (TCB_t *)pxMutexHolder;
3
    BaseType_t xReturn = pdFALSE;
4

5
    /* uxMutexesHeld 감소 */
6
    holder->uxMutexesHeld--;
7

8
    /* 모든 mutex 해제됐는가? */
9
    if (holder->uxMutexesHeld == 0) {
10
        /* 원래 priority 복원 */
11
        if (holder->uxPriority != holder->uxBasePriority) {
12
            uxListRemove(&(holder->xStateListItem));
13
            taskRESET_READY_PRIORITY(holder->uxPriority);
14

15
            holder->uxPriority = holder->uxBasePriority;
16

17
            prvAddTaskToReadyList(holder);
18
            xReturn = pdTRUE;
19
        }
20
    }
21
    return xReturn;
22
}

Mutex give 시점에 호출됩니다. 모든 mutex가 해제된 후에만 priority가 복원된다는 점이 중요합니다. 여러 mutex를 동시에 보유한 경우 단계적으로만 복원됩니다.

시간축 위에서 보면 boost의 의미가 분명해집니다. High가 mutex M을 기다리는 순간 Low의 priority가 일시적으로 High level까지 올라가, 그 사이 Mid가 끼어들지 못합니다.

#Multi-Mutex 시나리오

• T_low가 mutex A와 B를 동시 보유 중.
• T_high1이 A를 대기하면 → T_low의 priority가 high1 level로 boost.
• T_high2가 B를 대기하면 → 이미 boost된 상태이므로 변화 없음.
• T_low가 A를 release하면 uxMutexesHeld = 1이 되어 priority는 B 때문에 유지됩니다.
• T_low가 B를 release하면 uxMutexesHeld = 0이 되어 priority가 복원됩니다.

#Chained Inheritance

• T_high가 mutex X를 대기, T_med가 보유 중.
• T_med는 mutex Y를 대기, T_low가 보유 중.

전파 순서

1. T_high가 X를 대기할 때 T_med의 priority가 high level로 boost.
2. T_med가 Y를 대기할 때 T_low의 priority도 high level로 boost (boost된 T_med의 level).

xTaskCheckForChainedInheritance()가 recursive boost를 담당합니다.

#Disinherit After Timeout

1
void vTaskPriorityDisinheritAfterTimeout(TaskHandle_t pxMutexHolder,
2
                                          UBaseType_t uxHighestPriorityWaitingTask) {
3
    /* Waiter timeout 시 — 더 이상 그 priority로 boost할 이유 없음 */
4
    /* 남은 waiters 중 가장 높은 priority로 *부분 복원* */
5
}

Timeout이 발생하면 해당 waiter의 priority 영향만 제거합니다.

#Time Slicing과 Boost 상호작용

Boost된 task는 원래 같은 priority에 있던 다른 task와 같은 레벨이 되어 round-robin 대상에 포함됩니다. 이는 의도된 동작입니다.

#Implementation Overhead

• Inherit — ~50 cycle (list remove + insert + bitmap update)
• Disinherit — ~50 cycle (역방향)
• Chain — depth × inherit cost

Cortex-M4 @ 168 MHz 기준 0.3 µs/op입니다. 무시 가능한 수준입니다.

#Zephyr — k_mutex의 PI

1
struct k_mutex {
2
    _wait_q_t wait_q;
3
    struct k_thread *owner;
4
    uint32_t lock_count;
5
    int owner_orig_prio;   // ← Zephyr의 base priority
6
};

구조는 비슷합니다. PI 활성/비활성을 옵션으로 고를 수 있습니다.

#Linux PREEMPT_RT rtmutex

1
struct rt_mutex_base {
2
    raw_spinlock_t wait_lock;
3
    struct rb_root_cached waiters;  // RB tree
4
    struct task_struct *owner;
5
};

Waiters를 RB tree로 정렬해 O(log N)으로 priority 조작이 가능합니다. Linux의 다른 sleeping lock(예: futex)보다 한층 정교합니다.

#자주 하는 실수

⚠️ Inherit 후 manual priority 변경

vTaskPrioritySet()로 priority를 바꾸면 uxBasePriority도 함께 갱신해야 합니다. FreeRTOS API가 이 처리를 대신해 줍니다.

⚠️ Multiple mutex deep nesting

3개 이상의 mutex를 동시에 보유하면 chain 깊이가 증가합니다. Lock order와 단순한 설계로 회피하는 것이 정답입니다.

⚠️ ISR에서 PI 가정

ISR은 task가 아니므로 PI 자체가 무의미합니다. ISR과 task 사이 통신은 task notification을 씁니다.

#정리

• PI는 take 시 boost하고 give 시 복원합니다.
• uxBasePriority가 원래 값을 보존합니다.
• Multi-mutex 상황에서는 uxMutexesHeld == 0일 때만 복원됩니다.
• Chained inheritance도 recursive boost로 처리합니다.
• Linux PREEMPT_RT의 rtmutex는 RB tree로 더 정교하게 구현돼 있습니다.

다음 편은 Priority Ceiling Protocol 구현입니다.

#관련 항목

• 3-04: Priority Inversion 문제
• 3-06: Priority Ceiling Protocol