os · 18

우선순위 역전

스케줄링실시간우선순위

우선순위 스케줄링에서는 우선순위가 높은 작업이 낮은 작업보다 먼저 CPU를 받습니다. 그런데 두 작업이 락(자물쇠)으로 보호된 같은 자원을 함께 쓰면 이 질서가 뒤집힐 수 있습니다. 낮은 우선순위 작업이 락을 쥔 채 실행되고 있을 때 높은 우선순위 작업이 같은 락을 기다리게 되면, 높은 작업은 낮은 작업이 락을 풀 때까지 진행하지 못합니다. 여기에 락과 상관없는 중간 우선순위 작업이 끼어들어 낮은 작업을 계속 밀어내면, 낮은 작업은 락을 풀지 못하고 높은 작업은 중간 작업이 끝날 때까지 기다리게 됩니다. 우선순위가 가장 높은 작업이 가장 늦게 진행하는 이 현상을 우선순위 역전(priority inversion)이라고 부릅니다.

우선순위 역전은 제때 끝나야 하는 실시간 시스템에서 특히 위험합니다. 대표적인 해결책은 우선순위 상속(priority inheritance)으로, 락을 쥔 낮은 작업이 그 락을 기다리는 높은 작업의 우선순위를 임시로 물려받아 중간 작업에 밀리지 않고 빨리 락을 풀게 합니다. 이 토픽에서는 역전이 생기는 과정, 상속이 이를 막는 과정, 두 경우 높은 작업의 응답 시간 차이를 봅니다.

핵심 개념

우선순위 스케줄링

실행 가능한 작업 가운데 우선순위가 가장 높은 것을 먼저 실행합니다. 선점형이면 더 높은 작업이 도착하는 순간 낮은 작업은 CPU를 빼앗깁니다.

핵심 개념

락과 임계 구역

공유 자원을 한 번에 한 작업만 쓰게 하려고 락을 잡고 임계 구역을 실행합니다. 락을 쥔 작업이 CPU를 얻지 못하면 락이 풀리지 않아 기다리는 작업도 진행하지 못합니다.

핵심 개념

우선순위 역전

높은 우선순위 작업이 낮은 우선순위 작업이 쥔 락을 기다리는 동안, 락과 무관한 중간 우선순위 작업이 낮은 작업을 선점해 높은 작업이 더 오래 지연되는 현상입니다.

핵심 개념

우선순위 상속

락을 쥔 작업이 그 락을 기다리는 가장 높은 우선순위를 임시로 물려받는 프로토콜입니다. 락을 풀면 원래 우선순위로 돌아가고, 중간 작업이 끼어들지 못하게 막습니다.

핵심 개념

우선순위 상한 프로토콜

락마다 상한을 정해 두고 락을 쥔 동안 소유자를 그 상한 우선순위로 실행하는 방식입니다(즉시 상한 방식, POSIX PTHREAD_PRIO_PROTECT). 상한은 그 락을 쓸 작업 중 가장 높은 우선순위로 정합니다.

핵심 개념

제한된 역전과 제한 없는 역전

낮은 작업의 임계 구역이 끝나기만 기다리는 정도는 길이가 정해진 지연입니다. 중간 작업이 끼어들면 그 작업이 끝날 때까지 지연이 늘어 상한을 알기 어려워지고, 이것이 문제의 핵심입니다.

셋이 모여야 생깁니다 — 낮은 작업이 쥔 락, 그 락을 기다리는 높은 작업, 락과 무관하게 실행 가능한 중간 작업이 함께 있어야 합니다.

중간 작업이 지연을 키웁니다 — 높은 작업은 락을 쥔 낮은 작업을 기다리는 것이 원래의 대기이고, 중간 작업이 낮은 작업을 막아 이 대기가 늘어나는 것이 문제입니다.

상속은 락을 쥔 작업을 서둘러 끝나게 합니다 — 락을 쥔 동안만 우선순위를 올려 높은 작업의 지연을 임계 구역 길이 정도로 줄입니다.

실시간 시스템에서 중요합니다 — 마감 시간을 지켜야 하는 시스템에서는 높은 작업의 지연이 정해진 범위 안에 있어야 합니다.

이 시각화에서 확인할 것 — "우선순위 역전" 탭에서 중간 작업이 끼어들어 높은 작업이 늦어지는 과정을, "우선순위 상속" 탭에서 낮은 작업이 우선순위를 물려받는 과정을, "비교" 탭에서 응답 시간의 차이를 STEP으로 확인하세요.

우선순위 역전의 배경

우선순위 역전은 락을 쓰는 우선순위 기반 스케줄링에서 오래전부터 알려진 문제입니다. 1990년 Sha, Rajkumar, Lehoczky가 IEEE Transactions on Computers 논문에서 우선순위 상속 프로토콜과 우선순위 상한 프로토콜을 분석·정리했고, 1997년 화성 탐사선 패스파인더에서 이 문제로 시스템이 반복해서 재설정된 사례가 널리 알려지면서 실시간 시스템 설계의 대표 교훈이 되었습니다.

숫자로 확인하기

시간 단위 예시 — 낮은 작업 L이 t=0에 시작해 t=1에 락을 잡고, 높은 작업 H가 t=2에 도착해 t=3에 같은 락을 기다리고, 중간 작업 M이 t=3에 도착합니다(시간 단위는 예시이고, 칸 번호 t에서 실행한 작업은 t+1 시점에 끝납니다).

상속이 없을 때 — M이 t=3부터 6까지 4단위 동안 CPU를 차지하고, L이 t=7~8에 락을 풀어 H가 t=9에 락을 얻어 t=11에 끝납니다. H의 응답 시간은 11 − 2 = 9입니다.

상속이 있을 때 — L이 H의 우선순위를 물려받아 t=3~4에 락을 풀고 H가 t=5에 락을 얻어 t=7에 끝납니다. H의 응답 시간은 7 − 2 = 5로 줄어듭니다.

자주 하는 오해

락만 있으면 우선순위 역전이 생긴다 — 락을 기다리는 동안 낮은 작업 때문에 느려지는 것은 길이가 정해진 대기(제한된 역전)라 피할 수 없고, 중간 작업이 끼어 지연이 제한 없이 늘어날 때 심각한 문제가 됩니다.

우선순위 상속은 영구히 우선순위를 올린다 — 락을 쥔 동안, 더 높은 작업이 기다리는 동안만 임시로 올리고 락을 풀면 원래로 돌아갑니다.

우선순위 역전은 실시간 시스템에서만 생긴다 — 우선순위를 쓰는 스케줄러와 락이 있는 환경이면 일반 운영체제에서도 일어날 수 있습니다. 다만 영향이 가장 크게 드러나는 곳이 실시간 시스템입니다.

우선순위를 더 높이면 해결된다 — 모든 작업의 우선순위를 올리면 상대적인 순서는 그대로여서 역전이 사라지지 않습니다.

면접에서 이렇게 물어요

면접 질문

우선순위 역전이 무엇인가요?

낮은 우선순위 작업이 쥔 락을 높은 우선순위 작업이 기다리는 동안, 중간 우선순위 작업이 CPU를 차지해 높은 작업이 중간 작업보다도 늦게 실행되는 현상입니다.

면접 질문

어떻게 해결하나요?

우선순위 상속으로 락을 쥔 낮은 작업이 기다리는 높은 작업의 우선순위를 임시로 받게 하거나, 우선순위 상한 프로토콜로 락을 쥔 작업의 우선순위를 상한으로 올립니다.

면접 질문

패스파인더에서 무슨 일이 있었나요?

1997년 화성 탐사선에서 높은 우선순위 작업이 낮은 작업이 쥔 뮤텍스를 기다리는 사이 중간 우선순위 작업들이 낮은 작업을 계속 선점했고, 높은 작업이 제때 끝나지 않은 것을 감지한 소프트웨어가 시스템을 재설정했습니다. 해당 뮤텍스 세마포어의 우선순위 상속 옵션을 켜는 패치로 해결했습니다.

면접 질문

락 없이 피할 수 있나요?

락을 쓰지 않는 자료 구조를 쓰거나 임계 구역을 짧게 하고, 락을 공유하는 작업의 우선순위 차이를 줄이는 설계로 위험을 줄일 수 있습니다. 락이 필요하다면 우선순위 상속을 지원하는 뮤텍스를 씁니다.

실제 시스템에서는

POSIX 스레드 — pthread_mutexattr_setprotocol로 뮤텍스의 프로토콜을 PTHREAD_PRIO_INHERIT(우선순위 상속)나 PTHREAD_PRIO_PROTECT(우선순위 상한)로 정할 수 있습니다.

리눅스 — 리눅스 커널의 퓨텍스는 우선순위 상속을 지원하는 연산(FUTEX_LOCK_PI)을 제공하고, PTHREAD_PRIO_INHERIT 뮤텍스는 이런 PI 퓨텍스를 기반으로 구현됩니다.

패스파인더의 VxWorks — 탐사선의 실시간 운영체제 VxWorks는 뮤텍스 세마포어를 만들 때 우선순위 상속 옵션(SEM_INVERSION_SAFE)을 줄 수 있고, 패스파인더는 이를 켜서 해결했다고 알려져 있으며, 문제의 세마포어는 select 라이브러리 내부의 것이었다고 합니다.

일반 운영체제 — 일반적인 시분할 스케줄러(리눅스 SCHED_OTHER)는 우선순위가 낮은 작업에도 CPU 시간을 나눠 주므로 락 소유자가 오래 굶는 상황은 실시간 정책보다 드뭅니다.

함께 보면 좋은 토픽

CPU 스케줄링 — 우선순위 스케줄링과 선점의 기본을 봅니다.

프로세스 동기화 — 락과 뮤텍스, 임계 구역이 무엇인지 봅니다.

교착 상태 — 락을 둘러싼 또 다른 문제인 교착 상태와 비교해 봅니다.

스레드 — 락을 공유하는 스레드의 동작을 봅니다.

참고 자료

논문 — Sha, Rajkumar, Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization", IEEE Transactions on Computers 39(9), 1990

패스파인더 — Mike Jones, What really happened on Mars?, Glenn Reeves의 설명 (RISKS Digest 19.54)

POSIX·리눅스 — pthread_mutexattr_setprotocol, futex(2)

교재 — Silberschatz 외, "Operating System Concepts"의 우선순위 역전 절

C (POSIX) — 우선순위 상속 뮤텍스

#include <pthread.h>

pthread_mutex_t lock;
pthread_mutexattr_t attr;

pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);   /* 우선순위 상속 */
pthread_mutex_init(&lock, &attr);

/* 이제 이 뮤텍스를 쥔 낮은 우선순위 스레드는,
   기다리는 높은 우선순위 스레드의 우선순위를 임시로 물려받는다 */
pthread_mutex_lock(&lock);
/* 임계 구역 */
pthread_mutex_unlock(&lock);

뮤텍스 속성의 프로토콜을 PTHREAD_PRIO_INHERIT로 정하면, 이 뮤텍스를 쥔 스레드가 그 뮤텍스를 기다리는 더 높은 우선순위 스레드의 우선순위를 임시로 물려받습니다. 뮤텍스를 풀면 원래 우선순위로 돌아갑니다. 기본 프로토콜은 PTHREAD_PRIO_NONE이라 상속이 일어나지 않습니다. 우선순위 상한 방식을 쓰려면 PTHREAD_PRIO_PROTECT와 pthread_mutexattr_setprioceiling으로 상한을 정합니다. 주로 SCHED_FIFO 같은 실시간 우선순위를 쓰는 스레드에 쓰며, 지원 여부는 시스템마다 다릅니다(POSIX 선택 옵션).

VxWorks — 패스파인더가 켠 옵션 (개념 예시)

/* 우선순위 상속을 지원하지 않는 뮤텍스 (역전 가능) */
SEM_ID m1 = semMCreate(SEM_Q_PRIORITY);

/* 우선순위 상속을 켠 뮤텍스 */
SEM_ID m2 = semMCreate(SEM_Q_PRIORITY | SEM_INVERSION_SAFE);

VxWorks의 semMCreate는 뮤텍스 세마포어를 만드는 함수이고, SEM_INVERSION_SAFE 옵션을 주면 우선순위 상속이 켜집니다. 패스파인더 사례는 이 옵션이 꺼진 뮤텍스에서 우선순위 역전이 생겼고 옵션을 켜는 패치로 해결되었다고 알려져 있습니다. SEM_INVERSION_SAFE는 큐의 순서를 우선순위로 정하는 SEM_Q_PRIORITY와 함께 쓰도록 되어 있습니다. 위 코드는 개념을 보이는 최소 예시이며, 실제 사용은 VxWorks 문서의 설명을 따라야 합니다.

리눅스 셸 — 실시간 우선순위 확인

# SCHED_FIFO 우선순위 50으로 프로그램 실행 (root 권한)
sudo chrt -f 50 ./worker

# 프로세스의 스케줄링 정책과 실시간 우선순위 확인
chrt -p 1234

# 정책(cls)과 실시간 우선순위(rtprio) 열로 목록 보기
ps -eo pid,cls,rtprio,ni,comm

chrt는 프로세스의 스케줄링 정책과 우선순위를 설정하고 조회하는 도구입니다. -f는 SCHED_FIFO 정책을 뜻하며, 이 정책의 실시간 프로세스는 같은 우선순위 안에서는 스스로 양보하거나 블록되거나 더 높은 우선순위 작업에 선점되기 전까지 CPU를 쥡니다. ps의 cls 열은 스케줄링 클래스(예: FF는 SCHED_FIFO, TS는 일반 시분할)를, rtprio 열은 실시간 우선순위를 보여 줍니다. 실시간 우선순위를 가진 작업이 락을 두고 경쟁하는 상황에서는 앞의 PTHREAD_PRIO_INHERIT 뮤텍스를 쓰는 것이 우선순위 역전을 막는 대표적인 방법입니다.

우선순위 역전(Priority Inversion)이 발생하는 상황을 가장 잘 설명한 것은?

우선순위가 높은 작업이 낮은 작업 때문에 밀리는 역설입니다.

낮은 우선순위 작업이 락을 쥔 채 중간 우선순위 작업에게 CPU를 빼앗기면, 그 락을 기다리는 높은 우선순위 작업이 중간 작업보다도 늦게 실행되는 현상이 생깁니다.

우선순위 역전을 완화하는 대표적인 방법은?

락을 쥔 작업이 빨리 끝나야 기다리는 작업도 풀립니다.

우선순위 상속은 락을 가진 낮은 우선순위 작업이 대기 중인 높은 우선순위 작업의 우선순위를 임시로 상속해, 중간 우선순위 작업에게 밀리지 않고 빨리 락을 풀도록 만드는 기법입니다.

1997년 화성 탐사선 패스파인더에서 시스템이 반복해서 재부팅된 원인으로 알려진 것은?

실시간 OS의 동기화 문제가 원인이었습니다.

Mars Pathfinder는 우선순위 역전으로 높은 우선순위 작업이 제때 실행되지 못해 워치독 타이머가 시스템을 재부팅시켰습니다. 우선순위 상속 옵션을 켜는 원격 패치로 해결되었습니다.