우선순위 역전과 실시간 시스템의 블로킹 제어

락을 기다리는 높은 우선순위 태스크

우선순위 기반 선점 스케줄러에서 높은 우선순위 태스크가 항상 먼저 끝나는 것은 아니다. 낮은 우선순위 태스크가 락이나 세마포어 같은 공유 리소스를 보유하고 있으면, 높은 우선순위 태스크도 그 리소스가 풀릴 때까지 멈춘다. 이 현상이 우선순위 역전(Priority Inversion)이다.

실시간 시스템에서는 이 대기가 데드라인 위반으로 이어질 수 있다. 우선순위 기반 선점형 스케줄링, 공유 리소스의 상호 배제, 그리고 서로 다른 우선순위 태스크의 같은 리소스 접근이 겹칠 때 문제가 나타난다.

⤢✕

낮은 우선순위 태스크의 임계 구역 시간만큼만 기다리는 경우는 제한된 우선순위 역전(Bounded Priority Inversion)이다. 임계 구역이 짧다면 지연을 예측하고 제한할 수 있다.

반면 중간 우선순위 태스크가 끼어들면 낮은 우선순위 태스크는 리소스를 해제할 기회를 얻지 못한다. 높은 우선순위 태스크의 대기 시간이 무한정 늘어날 수 있는 무한 우선순위 역전(Unbounded Priority Inversion)이며, 실시간 제약에서는 심각한 상황이 된다.

H, M, L 태스크가 만드는 지연

태스크 H(High), M(Medium), L(Low)와 공유 리소스 R을 가정하자. L이 R을 획득한 뒤 H가 R을 요청하면 H는 대기한다. 이때 R이 필요 없는 M이 도착하면 M은 L을 선점할 수 있고, H는 M이 끝날 때까지도 계속 기다린다.

시간	이벤트	실행 태스크	리소스 R
t0	L 시작	L	-
t1	L이 R 획득	L	L 보유
t2	H 도착, R 요청	L	L 보유 (H 대기)
t3	M 도착 (R 불필요)	M	L 보유 (H 대기)
t4	M 완료	L	L 보유 (H 대기)
t5	L이 R 해제	H	H 획득
t6	H 완료	L	-

⤢✕

리소스가 여럿이면 블로킹은 연쇄될 수 있다.

Task H: R1 요청 → 대기 (Task M이 R1 보유)
Task M: R2 요청 → 대기 (Task L이 R2 보유)
Task L: R2 보유 중 실행

중첩된 임계 구역에서는 데드락도 발생할 수 있다. 이때 우선순위 역전과 데드락은 별개 문제가 아니라 서로 영향을 주는 조건이 된다.

상속과 천장으로 블로킹을 제한한다

우선순위 상속 프로토콜(Priority Inheritance Protocol, PIP)은 낮은 우선순위 태스크가 높은 우선순위 태스크를 블로킹할 때, 블로킹한 태스크가 높은 우선순위를 일시적으로 상속하도록 한다. L이 R을 보유한 상태에서 H가 R을 요청하면 L은 H의 우선순위를 상속하고, R을 해제한 뒤 원래 우선순위로 돌아간다.

⤢✕

PIP는 무한 우선순위 역전을 방지하고 구현도 비교적 간단하다. 다만 연쇄 블로킹은 가능하며, 교착 상태를 막지는 못한다.

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);

pthread_mutex_t mutex;
pthread_mutex_init(&mutex, &attr);

우선순위 천장 프로토콜(Priority Ceiling Protocol, PCP)은 각 리소스에 천장 우선순위를 지정해 우선순위 역전과 교착 상태를 함께 다룬다.

리소스 R의 우선순위 천장 = R을 사용하는 모든 태스크 중 최고 우선순위

태스크는 리소스를 얻을 때 해당 리소스의 천장 우선순위로 올라가고, 해제하면 원래 우선순위로 복귀한다. 현재 시스템 천장보다 높은 우선순위 태스크만 리소스를 획득할 수 있다.

⤢✕

PCP는 최대 한 번의 블로킹을 보장하고 교착 상태를 방지해 분석이 쉽다. 대신 오버헤드는 높다.

즉시 우선순위 천장 프로토콜(Immediate Priority Ceiling Protocol, IPCP)은 PCP를 단순화한 방식이다. 리소스를 획득하는 즉시 천장 우선순위로 올라가므로 블로킹 검사가 필요 없고 구현은 단순하다. 반대로 불필요한 우선순위 상승은 발생할 수 있다.

항목	PCP	IPCP
우선순위 상승 시점	블로킹 발생 시	리소스 획득 즉시
블로킹 검사	필요	불필요
구현 복잡도	높음	낮음
불필요한 우선순위 상승	없음	가능

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_PROTECT);
pthread_mutexattr_setprioceiling(&attr, 99);  // 천장 우선순위

pthread_mutex_t mutex;
pthread_mutex_init(&mutex, &attr);

스택 리소스 정책(Stack Resource Policy, SRP)은 다중 유닛 리소스와 동적 우선순위 스케줄링을 지원한다. 각 태스크에 선점 수준을 할당하고, 현재 시스템 천장보다 높은 선점 수준을 가진 태스크만 실행할 수 있게 한다. EDF 스케줄링과 호환되며 다중 유닛 리소스를 지원하고 단일 스택을 사용할 수 있다.

Mars Pathfinder가 보여준 실패 경로

1997년 화성 탐사선 패스파인더는 우선순위 역전이 실제 시스템 장애로 이어진 사례다. 이 시스템은 VxWorks RTOS, 우선순위 기반 선점형 스케줄링, 공유 Information Bus를 사용했다.

⤢✕

저우선순위 버스 관리 태스크가 버스 뮤텍스를 획득한 상태에서 고우선순위 데이터 수집 태스크가 버스 접근을 시도해 블로킹됐다. 이어 중간 우선순위 통신 태스크가 선점하면서 고우선순위 태스크는 데드라인을 넘겼고, 워치독 타이머가 시스템을 리셋했다.

해결은 지상에서 원격으로 우선순위 상속을 활성화하고 VxWorks 뮤텍스 옵션을 변경하는 방식이었다. 공유 리소스를 줄이고 임계 구역 길이를 짧게 유지하며, 상황에 맞는 프로토콜을 선택하고 충분히 테스트·시뮬레이션해야 하는 이유가 이 사례에 드러난다.

응답 시간 분석에 블로킹을 포함한다

PIP에서 낮은 우선순위 태스크가 n개일 때 최대 블로킹 시간은 각 임계 구역 시간의 합으로 표현된다.

n개의 낮은 우선순위 태스크가 있을 때:
최대 블로킹 시간 = Σ(임계 구역 시간)

PCP에서는 가장 긴 임계 구역 시간이 최대 블로킹 시간이 되며, 단일 블로킹이 보장된다.

최대 블로킹 시간 = max(임계 구역 시간)
단일 블로킹 보장

응답 시간 분석에는 태스크 i의 최대 블로킹 시간 Bi를 포함한다.

Ri = Ci + Bi + Σ(⌈Ri/Tj⌉ × Cj)

Bi: 태스크 i의 최대 블로킹 시간

WCET 분석에는 RapiTime, 시간 분석에는 aiT, 스케줄 분석에는 Chronos를 사용할 수 있다. 시간 오토마타 검증에는 UPPAAL, 확률적 모델 체킹에는 PRISM이 있다.

운영체제가 제공하는 동기화 수단

POSIX 스레드는 뮤텍스 속성으로 프로토콜을 지정할 수 있다.

// 뮤텍스 프로토콜 설정
int pthread_mutexattr_setprotocol(
    pthread_mutexattr_t *attr,
    int protocol
);

// protocol 옵션
PTHREAD_PRIO_NONE      // 프로토콜 없음
PTHREAD_PRIO_INHERIT   // 우선순위 상속
PTHREAD_PRIO_PROTECT   // 우선순위 천장

Linux 커널의 RT-Mutex는 우선순위 상속을 지원하는 커널 내부 동기화 프리미티브이며, PREEMPT_RT 패치에서 확장된다.

// 커널 내부 RT-mutex
struct rt_mutex lock;
rt_mutex_init(&lock);
rt_mutex_lock(&lock);
rt_mutex_unlock(&lock);

VxWorks에서는 뮤텍스 생성 시 우선순위 상속 옵션을 활성화할 수 있다.

// 우선순위 상속 활성화
semMCreate(SEM_Q_PRIORITY | SEM_INVERSION_SAFE);

FreeRTOS의 뮤텍스도 우선순위 상속을 적용한다.

// 뮤텍스 생성 (우선순위 상속 자동 적용)
SemaphoreHandle_t mutex = xSemaphoreCreateMutex();

// 뮤텍스 획득
xSemaphoreTake(mutex, portMAX_DELAY);

// 뮤텍스 해제
xSemaphoreGive(mutex);

공유 상태를 줄이는 설계

락프리 데이터 구조에서 Compare-And-Swap(CAS)를 사용하면 블로킹 없는 동기화를 통해 우선순위 역전의 원인을 제거할 수 있다. 리소스 파티셔닝으로 우선순위별 전용 리소스를 할당하는 방식도 공유 리소스를 줄이는 방법이다.

공유 메모리 대신 메시지 큐를 두는 아키텍처는 비동기 통신으로 블로킹을 피하는 선택지다.

⤢✕

우선순위 역전은 스케줄러만의 문제가 아니다. 락의 보유 시간, 자원 접근 순서, 동기화 프로토콜, 응답 시간 분석이 함께 맞물린다. PIP는 무한 우선순위 역전을 방지하고 PCP는 교착 상태까지 예방한다.