Priority Inversion 진단·예방 — Mars Pathfinder Lesson 추적

#한 줄 요약

“Priority Inversion = High task가 Low 잠금 자원 대기 + Medium에 차단됨” 1997년 Mars Pathfinder를 정지시켰던 bug입니다.

#시나리오

세 task가 시간축에서 어떻게 얽히는지 timeline으로 보면 한눈에 들어옵니다.

1
Task H (high) — periodic, 10 ms deadline
2
Task M (medium) — 일반 작업
3
Task L (low) — log writer, mutex 보유
4

5
t=0:  L take(mtx) → 시작
6
t=1:  H runnable → preempt L, H 실행
7
t=2:  H take(mtx) → block (L 보유 중)
8
t=2:  L ready, but M now CPU 점유 (L 못 가짐)
9
t=10: M 계속 진행 → H deadline miss

Medium task는 lock과 무관한데도 결과적으로 high task를 블록합니다.

#Mars Pathfinder (1997)

NASA의 Sojourner rover 시스템:

• Bus management task (high)
• Comm task (medium) — frequent
• Weather task (low) — info_bus mutex 보유

순환:

• Weather 작업 중 → bus mgmt preempt
• Bus mgmt → mutex 시도 → block
• Comm 빈번 → CPU 점유
• Weather 미실행 → mutex 못 풀음
• Bus mgmt deadline miss → watchdog reset

매 며칠마다 system reset이 일어났습니다. 지구에서 원격으로 debug를 진행했고, priority inheritance를 활성화해 문제를 해결했습니다.

#Tony Hoare의 회상

1
"Priority Inheritance was implemented in VxWorks but disabled by default
2
 because of overhead concerns. We had to push the update."

VxWorks의 selectPriorityInherit를 활성화해 문제를 해결했습니다.

#해결 1: Priority Inheritance (PI)

Low task가 mutex 보유 중 High task가 same mutex 대기:

• → Low task의 priority가 High 수준으로 boost
• → Medium이 preempt 못 함
• → Low 빨리 완료 → mutex give → High 진행

FreeRTOS PI mutex (xSemaphoreCreateMutex):

1
SemaphoreHandle_t mtx = xSemaphoreCreateMutex();   /* PI 자동 활성 */
2

3
xSemaphoreTake(mtx, portMAX_DELAY);   /* High waiting → Low boost */
4
critical();
5
xSemaphoreGive(mtx);   /* boost 복원 */

POSIX:

1
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
2
pthread_mutex_init(&mtx, &attr);

#Chain Inheritance

1
L1 보유 mtx_A, L2 보유 mtx_B
2
L1 mtx_B 대기 → L2 boost
3
H mtx_A 대기 → L1·L2 둘 다 boost

체인 길이가 N이면 boost propagation과 ready-list 처리가 추가됩니다. 비용은 RTOS·port·체인 구조에 따라 측정해야 합니다.

자동차 ASIL-D에서는 chain depth를 제한합니다(보통 3 이하).

#해결 2: Priority Ceiling Protocol (PCP)

각 mutex에 ceiling priority를 미리 지정한다. ceiling = mutex를 사용할 가능성 있는 모든 task 중 최고 priority.

• Take 시 — task priority가 ceiling 수준으로 즉시 boost
• Give 시 — 원래 priority 복원

VxWorks와 INTEGRITY, 일부 µC/OS는 PCP를 지원합니다. 덕분에 WCET 분석이 훨씬 쉬워집니다.

#Immediate vs Original PCP

Immediate PCP (Sha 1990):

• Take 즉시 ceiling boost — 다른 mutex 대기 안 함

Original PCP:

• Ceiling만큼 boost되어 다른 lower priority task만 preempt 가능

Immediate와 Original 방식의 선택과 지원 여부는 RTOS 구현마다 다릅니다. 둘의 차이와 실제 지원 범위를 문서와 소스로 확인합니다.

#해결 3: Priority Ceiling Emulation (PCE)

Linux PREEMPT_RT의 mutex/priority protocol 지원은 kernel API와 설정에 따라 확인해야 하며, robust mutex와 priority ceiling을 같은 기능으로 간주하면 안 됩니다.

1
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_PROTECT);
2
pthread_mutexattr_setprioceiling(&attr, 90);
3
pthread_mutex_init(&mtx, &attr);

Take 시점에 ceiling인 90으로 boost되어 우선순위가 자동으로 통제됩니다.

#진단 — Tracealyzer / SystemView

Trace 화면에서는 다음과 같이 확인할 수 있습니다.

• Task L이 “running” 상태로 priority boost와 함께 표시됩니다.
• Mutex가 L에 의해 잡혀 있다고 보입니다.
• Task H는 “blocked on mutex” 상태로 표시됩니다.

이렇게 하면 priority inversion을 직접 시각적으로 확인할 수 있습니다.

1
/* Debug — boost 횟수 측정 */
2
struct mutex_stats {
3
    uint32_t boost_count;
4
    uint32_t max_boost_ms;
5
};

#ISR과 Priority Inversion

ISR이 H가 잡고 있는 mutex를 만나면 ISR에는 priority 개념이 없으므로 단순 block이 아니라 ISR-blocked-task 상황이 된다. 일반적으로 ISR은 mutex를 잡지 않는다.

ISR과 task 사이에는 semaphore(signaling)를 씁니다. Mutex는 task 간에만 사용합니다.

#예방 — Design Rule

1. Short critical section을 μs 단위로 유지합니다.
2. Sleep이나 IO 중에는 mutex를 잡지 않습니다.
3. Lock ordering으로 deadlock과 chain inheritance를 제한합니다.
4. PI mutex를 사용합니다(해당 RTOS의 mutex 구현과 설정 확인).

1
/* 회피 */
2
xSemaphoreTake(&mtx, portMAX_DELAY);
3
read_file();   /* ← seconds */
4
xSemaphoreGive(&mtx);
5

6
/* Good */
7
read_file();
8
xSemaphoreTake(&mtx, portMAX_DELAY);
9
update_var();
10
xSemaphoreGive(&mtx);

#Automotive — Lock 사용 자제

ASIL-D ECU:

• Mutex 자제, double buffer 또는 lock-free
• 사용 시 Immediate PCP + WCET 분석
• 일부 코드는 mutex 자체 금지

자동차에서는 예측 가능성이 throughput보다 우선합니다.

#Boeing 787 Bug

2015 — 787 시스템:

• 248일 후 RTOS counter overflow
• → priority inversion-like 상태로 fail

테스트되지 않은 long-run path는 WCET 분석에 반드시 포함해야 합니다. 단기 테스트만으로는 잡히지 않습니다.

#WCET 분석

1
Task H budget: 예시값 — 시스템 요구사항으로 산정
2
Mutex hold worst case (Low): 측정·분석 필요
3
Inheritance chain depth: 실제 lock graph로 산정
4
Total worst case wait: WCET·스케줄링 분석 필요
5

6
H의 deadline 충족 여부는 측정된 WCET와 모든 blocking 항을 합산해 판단

aiT와 Bound-T 같은 정적 WCET 도구를 활용합니다. 자동차와 항공 분야의 표준입니다.

#자주 하는 실수

⚠️ Non-PI mutex 사용

1
SemaphoreHandle_t mtx = xSemaphoreCreateBinary();   /* ← PI 없음 — semaphore */

대신 xSemaphoreCreateMutex를 써야 PI가 자동으로 동작합니다.

⚠️ Long task in mutex

1
xSemaphoreTake(mtx, ...);
2
http_request();   /* seconds — high task block */
3
xSemaphoreGive(mtx);

이때는 데이터를 미리 fetch해 두고 critical section을 짧게 유지해야 합니다.

⚠️ ISR이 mutex 사용

1
ISR: xSemaphoreTake(mtx, 0);   /* ✗ */

ISR에서는 mutex 대신 semaphore를 써야 합니다.

⚠️ Priority 계층 잘못 설계

1
Task H priority 5
2
Task M priority 5    /* ← same priority → preempt 없음, FIFO */

이런 경우에는 priority를 명확히 다르게 지정해야 합니다.

#정리

• Priority Inversion은 Low가 보유 + Medium이 preempt = High가 block되는 상황입니다.
• Mars Pathfinder는 1997년에 원격 patch로 해결했습니다.
• PI mutex는 보유자 priority를 동적으로 boost합니다.
• PCP는 컴파일 타임 ceiling을 활용해 더 단순한 분석이 가능합니다.
• Chain inheritance는 depth 제한이 필요합니다.
• ASIL-D에서는 lock 자체를 자제하고 double buffer를 선호합니다.

다음 편은 Memory Barrier입니다.

#관련 항목

• 2-02: Lock-Free Ring
• 2-04: Memory Barrier
• RTOS 3-04: Priority Inversion