우선순위 역전

우선순위 역전은 가장 급한 작업이 덜 급한 작업보다 늦게 도는 고장입니다. 급한 작업에 필요한 락을 가장 덜 급한 작업이 쥐고 있을 때 생깁니다. 그 사이 중간 작업이 락을 쥔 작업을 밀어냅니다. 급한 작업이 중간 작업 뒤로 밀려난 꼴이라 이런 이름이 붙었습니다.

쉽고 빠른 이해

우선순위 역전은 급한 일이 덜 급한 일 뒤로 밀리는 고장입니다. 가장 덜 급한 작업이 쥔 락을 가장 급한 작업이 기다립니다. 그 사이 중간 작업이 락을 쥔 작업을 밀어내고 먼저 돕니다.

이 고장이 문제가 되는 까닭은 「급한 일부터 돌린다」는 약속을 조용히 깨기 때문입니다. 기다림이 얼마나 길어질지는 중간 작업이 얼마나 많고 긴지에 달려 있어서 미리 잴 수 없습니다. 마감 시각을 지켜야 하는 장비에서는 이 늦음이 곧 고장입니다.

어떻게 도나:

1. 가장 덜 급한 작업이 락을 잡고 일을 시작합니다
2. 가장 급한 작업이 같은 락을 잡으려다 막혀 잠듭니다
3. 락과 무관한 중간 작업이 락을 쥔 작업을 밀어내고 돕니다. 그 작업이 못 도니 락도 못 놓습니다

무엇이 나빠지나 — 가장 급한 작업이 중간 작업이 다 끝날 때까지 기다립니다. 드물게 겹칠 때만 터져서 다시 만들어 보기도 어렵습니다.

상세

스레드는 한 프로그램 안에서 따로 나아가는 실행 흐름입니다. 앞에서 작업이라 부른 것이 스레드입니다. 프로세스나 태스크라고 불러도 이야기는 같습니다.

우선순위 역전은 급한 스레드가 덜 급한 스레드 때문에 기다리는 고장입니다. 그 기다림을 중간쯤 급한 스레드들이 길게 늘립니다.

먼저 사무실 이야기 하나로 모양을 잡습니다. 그다음 같은 장면을 스레드 셋으로 옮깁니다.

복사기 앞에서 기다리는 사장

사무실에 복사기가 한 대 있습니다. 신입 사원이 복사기에 자기 카드를 꽂고 긴 문서를 복사하기 시작합니다. 카드가 꽂힌 동안은 다른 사람이 복사기를 못 씁니다.

사장이 급한 서류를 들고 와서 신입이 끝나기를 기다립니다. 신입의 복사는 금방 끝날 참이었습니다.

그때 과장이 신입을 불러 전혀 다른 심부름을 시킵니다. 신입은 윗사람의 말을 먼저 들어야 하므로 카드를 꽂아 둔 채 복사기를 떠납니다. 사장은 과장의 심부름이 다 끝날 때까지 복사기 앞에 서 있습니다.

사장이 과장보다 윗사람입니다. 그런데도 과장의 일이 먼저 끝납니다.

우선순위 스케줄링이 하는 약속

스케줄러는 여러 스레드 가운데 지금 CPU(Central Processing Unit, 중앙처리장치)에서 돌 것을 고르는 운영체제의 한 부분입니다. 스레드는 CPU보다 많은 것이 보통이라 누군가는 차례를 기다려야 합니다. 그 차례를 정하는 것이 스케줄러의 일입니다.

우선순위는 스레드마다 매긴 급한 정도입니다. 우선순위로 고르는 스케줄러는 「돌 준비가 된 스레드 가운데 가장 높은 것을 돌린다」를 약속합니다. 마감 시각이 있는 일을 먼저 끝내려고 이렇게 합니다.

선점은 이 약속을 지키는 수단입니다. 더 높은 스레드가 준비되면 스케줄러는 지금 도는 스레드를 멈추고 CPU를 넘깁니다. 멈춘 스레드는 나중에 멈춘 지점부터 다시 돕니다.

락을 기다리며 잠든 스레드

락은 공유하는 데이터를 한 번에 한 스레드만 건드리게 하는 장치입니다. 여럿이 한꺼번에 고치면 값이 깨지므로 필요합니다. 락을 쥐고 도는 코드 구간을 임계 구역이라고 부릅니다.

이미 잡힌 락을 잡으려는 스레드는 잠들어 기다립니다. 잠든 스레드는 「돌 준비가 된 스레드」 목록에서 빠집니다. 락을 쥔 스레드가 락을 놓아야 비로소 깨어납니다.

스케줄러의 약속은 준비된 스레드에만 걸립니다. 잠든 높은 스레드가 언제 깨어날지는 락을 쥔 스레드가 얼마나 빨리 도느냐에 달려 있습니다. 그 스레드의 우선순위가 낮으면 높은 스레드의 운명이 낮은 우선순위에 묶입니다.

세 스레드로 본 역전

스레드 셋을 우선순위 순서로 높은 스레드, 중간 스레드, 낮은 스레드라고 부르겠습니다. 높은 스레드와 낮은 스레드는 같은 락을 씁니다. 중간 스레드는 락과 무관한 일을 합니다. CPU는 하나입니다.

앞의 사무실 이야기와 맞추면 사장이 높은 스레드, 과장이 중간 스레드, 신입이 낮은 스레드입니다. 신입이 꽂아 둔 카드가 락입니다.

sequenceDiagram
    participant L as 낮은 스레드
    participant K as 락
    participant H as 높은 스레드
    participant M as 중간 스레드
    L->>K: 잡는다
    K-->>L: 잡혔다
    Note over L,H: 높은 스레드가 깨어나 낮은 스레드를 선점한다
    H->>K: 잡으려 한다
    K-->>H: 이미 잡혀 있다 · 잠든다
    Note over L,M: 중간 스레드가 깨어나 낮은 스레드를 선점한다
    Note over M: 락과 무관한 일을 끝까지 한다
    M-->>L: CPU를 돌려준다
    L->>K: 놓는다
    K-->>H: 잡혔다 · 깨어난다

그림을 문장으로 옮기면 이렇습니다.

1. 낮은 스레드가 락을 잡고 임계 구역에 들어갑니다
2. 높은 스레드가 깨어나 낮은 스레드를 선점합니다
3. 높은 스레드가 같은 락을 잡으려다 막혀 잠듭니다. CPU는 낮은 스레드에게 돌아갑니다
4. 중간 스레드가 깨어납니다. 낮은 스레드보다 높으므로 낮은 스레드를 선점합니다
5. 중간 스레드가 도는 동안 낮은 스레드는 못 돕니다. 락도 못 놓습니다
6. 중간 스레드가 끝나야 낮은 스레드가 락을 놓습니다. 그제야 높은 스레드가 깨어납니다

셋째 단계까지는 이상한 것이 없습니다. 높은 스레드는 낮은 스레드가 임계 구역을 마칠 때까지만 기다리면 됩니다. 넷째 단계부터가 역전입니다.

한도가 있는 기다림과 한도가 없는 기다림

셋째 단계의 기다림은 임계 구역 하나의 길이만큼입니다. 임계 구역을 짧게 짜 두면 이 기다림도 짧습니다. 락을 쓰는 설계라면 이만큼은 처음부터 감수합니다.

넷째 단계의 기다림은 중간 스레드가 얼마나 도느냐에 달려 있습니다. 중간 스레드는 락과 무관하므로 임계 구역 길이와 상관없이 오래 돌 수 있습니다. 중간 스레드가 여럿이면 차례로 이어서 돌 수도 있습니다.

높은 스레드가 무엇을 기다리는지 사슬을 따라가면 끝에 중간 스레드가 있습니다.

flowchart TD
    H["높은 스레드"] -->|"잠들어 기다린다"| K["락"]
    K -->|"낮은 스레드가 놓기를 기다린다"| L["낮은 스레드"]
    L -->|"CPU를 돌려받기를 기다린다"| M["중간 스레드들"]

가장 급한 스레드가 결국 락과 아무 관계도 없는 스레드들을 기다립니다. 그 스레드들의 수와 길이에 한도가 없으니 높은 스레드의 기다림에도 한도가 없습니다. 흔히 우선순위 역전이라 하면 이 한도 없는 기다림을 가리킵니다.

재현되는 조건

넷이 다 서면 우선순위 역전이 됩니다.

1. 스케줄러가 우선순위로 스레드를 고릅니다. 더 높은 스레드가 준비되면 선점합니다
2. 우선순위가 다른 두 스레드가 같은 락을 씁니다. 락을 못 잡은 스레드는 잠들어 기다립니다
3. 높은 스레드가 락을 요청하는 순간 낮은 스레드가 그 락을 쥐고 있습니다
4. 낮은 스레드가 락을 쥔 동안 둘 사이 우선순위의 스레드가 준비되어 낮은 스레드가 쓰던 CPU를 차지합니다

셋째가 빠지면 기다림 자체가 없습니다. 넷째가 빠지면 기다림은 임계 구역 하나의 길이에서 끝납니다. 넷째가 한도 없는 기다림을 만드는 조건입니다.

넷째는 시점이 맞아야 섭니다. 낮은 스레드가 락을 쥔 짧은 구간에 중간 스레드가 깨어나야 하므로 드물게만 겹칩니다. 터진 뒤에 같은 상황을 다시 만들기도 어렵습니다.

CPU가 여럿이면 낮은 스레드가 다른 CPU에서 계속 돌 수 있습니다. 이때는 중간 스레드가 CPU를 전부 차지해야 넷째가 섭니다. CPU가 하나일 때 가장 쉽게 재현됩니다.

데드락·기아와 갈리는 점

데드락·기아·우선순위 역전은 「누가 멈추고 저절로 풀리나」에서 갈립니다. 기아는 한 스레드가 다른 스레드들에게 계속 밀려 차례를 못 받는 고장입니다.

데드락은 서로를 기다리는 고리가 있어서 밖에서 끊지 않으면 영원히 멈춥니다. 우선순위 역전에는 고리가 없습니다. 기다림의 사슬이 중간 스레드에서 끝나므로 언젠가는 풀립니다.

기아와는 누가 다치느냐가 다릅니다. 기아에서는 밀린 낮은 스레드 자신이 못 나아갑니다. 우선순위 역전에서는 낮은 스레드가 밀린 결과가 위로 번져 가장 높은 스레드가 멈춥니다.

늦음이 곧 고장인 시스템

우선순위 역전은 결국 풀립니다. 문제가 되는 곳은 「언젠가」로는 부족한 시스템입니다.

실시간 시스템은 일마다 끝내야 하는 시각이 정해진 시스템입니다. 이 시각을 마감이라고 부릅니다. 모터 제어나 센서 읽기처럼 늦으면 결과가 쓸모없어지는 일을 맡습니다.

이런 시스템은 대개 엄격한 우선순위 스케줄링을 씁니다. 그러면 한도 없는 기다림이 곧바로 마감 초과로 이어집니다.

워치독 타이머는 정해진 시간 안에 신호가 안 오면 시스템이 멈췄다고 보고 다시 시작시키는 타이머입니다. 마감을 넘긴 장비는 흔히 이 타이머에 걸립니다. 우선순위 역전이 겹칠 때마다 장비가 이유 없이 재시작하는 모습으로 드러납니다.

시간을 나눠 쓰는 범용 운영체제의 스케줄러는 보통 낮은 스레드에게도 CPU를 조금씩 나눠 줍니다. 덕분에 기다림이 끝없이 늘지는 않습니다. 낮은 스레드가 받는 몫이 작을수록 기다림은 길어지므로 급한 요청의 응답이 튀는 모습으로 나타납니다.

알아채는 신호

락이 있고 우선순위가 섞인 곳에서 급한 스레드가 이유 없이 늦으면 이 고장을 의심합니다. 기다린 시간과 그 시간 동안 CPU를 쓴 스레드를 나란히 놓고 보면 가려집니다.

셋째 줄이 데드락과 가르는 신호입니다. 데드락이면 락을 쥔 스레드도 무언가를 잠들어 기다립니다. 우선순위 역전에서는 락을 쥔 스레드가 돌 준비를 마친 채 CPU만 못 받고 있습니다.

막는 방법

막는 방법은 대개 락을 쥔 낮은 스레드가 중간 스레드에게 밀리지 않게 하는 것입니다. 이름 있는 수단은 아래 넷입니다.

우선순위 상속을 세 스레드 이야기에 넣으면 넷째 단계가 사라집니다. 높은 스레드가 잠드는 순간 낮은 스레드가 높은 우선순위를 빌립니다. 중간 스레드는 이제 낮은 스레드보다 낮으므로 선점하지 못합니다. 낮은 스레드는 락을 놓는 순간 원래 우선순위로 돌아갑니다.

우선순위 천장 프로토콜은 올리는 때가 다릅니다. 상속은 락을 기다리는 스레드가 생겨야 올립니다. 천장은 흔히 락을 잡는 순간 미리 올려 두므로 중간 스레드가 끼어들 틈이 처음부터 없습니다.

관련 항목

우선순위 역전과 이름이 나란히 불리는 동시성 고장

데드락 · 라이브락 · 기아 · 경쟁 상태 · 락 경합 · 락 호위

우선순위 역전을 막는 수단

우선순위 상속 · 우선순위 천장 프로토콜 · 인터럽트 비활성화 · 락 없는 자료구조

우선순위 역전을 일으키는 운영체제 스케줄링 요소

운영체제 · 스케줄러 · 스케줄링 · 우선순위 · 선점 · 문맥 교환 · 실행 큐

우선순위 역전에 얽히는 동기화 도구

락 · 뮤텍스 · 세마포어 · 임계 구역 · 스핀락 · 조건 변수

우선순위 역전이 마감 초과로 번지는 시스템

실시간 시스템 · 실시간 운영체제 · 임베디드 시스템 · 워치독 타이머 · 마스 패스파인더

우선순위 역전이 벌어지는 실행 단위

스레드 · 프로세스 · 태스크 · 커널 스레드