Starvation기아 상태 · Starvation
시스템 전체는 계속 진행하는데 특정 프로세스나 스레드 하나가 자원 선택에서 거듭 밀려 끝없이 기다리는 상태이다. 선택 정책이 대기 시간을 보지 않을 때 생긴다.
1요약
- Starvation(기아)은 운영체제 스케줄러 · 스레드 라이브러리의 잠금 · DBMS 잠금 관리자에서 선택 정책이 특정 대기자를 거듭 건너뛰어 생기는 무한 대기이며, 그 위에서 에이징 · 공정 큐 · 티켓 락 · 쓰기 우선 같은 «대기 상한» 장치가 돈다.
- 시스템이 멈추지 않으므로 처리량 지표로는 보이지 않는다 — 리눅스 2.6.25 전 스핀락은 8코어 2소켓 Opteron 의 사용자 공간 시험에서 스레드마다 실행 시간이 최대 2배 벌어졌고, 이를 계기로 티켓 락이 들어왔다(LWN 2008).
- 「한 요청만 안 끝난다」는 다른 스레드가 같은 자원을 얻고 있는가로 가른다 — 다른 쪽이 계속 얻고 있으면 기아, 모두 잠들어 서로를 기다리면 교착상태, 모두 CPU 를 쓰는데 아무도 끝내지 못하면 라이브락이다.
2등장 배경
1965년 Dijkstra 의 N 프로세스 상호 배제 해법은 임계 구역에 «누군가는» 들어가는 것을 보장했지만, Knuth 는 1966년 같은 해법에서 프로세스 하나가 무한히 밀릴 수 있음을 지적하고 대기 차례에 상한이 있는 해법을 냈다(Knuth 1966). 상호 배제만으로는 공정함이 보장되지 않는다는 문제가 이때 따로 떨어졌다.
1971년 Courtois · Heymans · Parnas 는 읽기 · 쓰기 문제에 두 해법을 냈다 — 읽기 지연을 최소로 하는 해법은 읽기가 이어지는 동안 쓰기를, 쓰기를 먼저 하는 해법은 그 반대를 막을 수 있다(Courtois 외 1971). 같은 해 Dijkstra 는 식사하는 철학자 다섯 명 문제에서 «이웃 둘의 공모로 한 철학자가 굶어 죽는» 경우를 들었고(EWD310), 이 장면에서 starvation 이라는 이름이 굳었다. Lamport 는 1974년 번호표 순서로 들어가는 빵집 알고리즘으로 먼저 온 쪽이 먼저 들어가는 순서를 보였다(Lamport 1974).
지금도 기본값은 대개 처리량 쪽이다. glibc 읽기 쓰기 잠금의 기본 종류는 읽기 우선이고 매뉴얼은 «읽기가 있는 한 쓰기는 굶는다»고 적으며(setkind_np(3)), Java ReentrantLock 도 공정성을 켜지 않으면 순서를 보장하지 않는다(ReentrantLock 문서).
3쉽게 이해하기 — 손님이 끊이지 않는 열람실
작은 열람실 하나에 손님은 여럿이 함께 앉아 읽을 수 있지만, 서가를 정리하는 직원은 방이 텅 비어야 들어갈 수 있다. 문지기의 규칙은 «안에 손님이 있으면 새 손님도 들인다»이다. 손님이 몇 분마다 새로 와서 방이 한 번도 비지 않자, 정리 직원은 문 앞에서 하루 종일 기다린다. 열람실은 바쁘게 돌아가는데 한 사람만 끝내 들어가지 못하자, 관장은 번호표 기계를 들여와 온 순서대로 들이게 한다.
그림 1 · 열람실은 계속 돌아가는데 정리 직원 한 명만 들어가지 못하고, 번호표로 온 순서를 지키게 하자 차례가 온다.
그림 2 · 문지기가 «들어온 순서»를 보지 않으면 정리 직원의 차례는 오지 않고, 번호표를 쓰면 앞 사람 수만큼만 기다린다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 열람실 | 공유 자원 · 읽기 쓰기 잠금 | 읽기는 여럿이, 쓰기는 혼자만 쥘 수 있다 |
| 손님 | 읽기 스레드 | pthread_rwlock_rdlock 으로 함께 들어간다 |
| 정리 직원 | 쓰기 스레드 · 기아 피해자 | pthread_rwlock_wrlock 에서 빈 잠금을 기다린다 |
| 문지기 규칙 | 선택 정책(읽기 우선) | 대기 시간을 보지 않고 지금 들어올 수 있는 쪽을 들인다 |
| 하루 종일 기다림 | 상한 없는 대기 | 시스템은 진행하는데 한 요청만 끝나지 않는다 |
| 번호표 기계 | 공정 큐 · 티켓 락 | 도착 순서대로 차례를 준다 |
| 오래 기다린 사람 먼저 | 에이징 | 기다린 시간만큼 우선순위를 올린다 |
| 정리 시작 | 대기 상한 보장 | 앞선 대기자 수만큼만 기다리고 들어간다 |
⚠ 비유가 맞지 않는 곳: 직원은 기다리다 지쳐 돌아갈 수 있지만 스레드는 제한 시간을 따로 주지 않으면 잠금 함수 안에서 영원히 잠들며, 번호표도 실제로는 대가가 있어 들어오는 순서를 강제하는 만큼 처리량이 줄어든다.
4구조 — 기아를 만드는 세 요소
기아는 ① 같은 자원을 노리는 경쟁자가 끊이지 않고 도착하고 ② 피해자가 그들과 함께 대기 집합에 남아 있으며 ③ 선택 정책이 대기 시간을 보지 않을 때 생긴다. 교착상태와 달리 대기 사슬은 닫히지 않고, 자원은 계속 누군가에게 넘어간다.
그림 3 · 자원은 쉬지 않고 넘어가지만 정책이 대기 시간을 보지 않으면 대기 집합의 W 는 영원히 뽑히지 않는다 — 상한 장치는 선택 정책에 붙는다.
| 요소 | 역할 | 기아가 생기는 예 | 근거 |
|---|---|---|---|
| 자원 | 경쟁 대상 | 읽기 쓰기 잠금 · CPU · 스핀락 · 행 잠금 | — |
| 경쟁자 흐름 | 계속 도착하는 요청 | 읽기 스레드 · 높은 우선순위 작업 · 짧은 작업 | Courtois 외 1971 |
| 선택 정책 | 다음 소유자를 고름 | 읽기 우선 · 고정 우선순위 · SJF · 먼저 잡는 쪽(비공정) | setkind_ |
| 피해자 | 거듭 뽑히지 않는 대기자 | 쓰기 스레드 · 낮은 우선순위 · 긴 작업 | EWD310 |
| 대기 상한 | 피해자의 차례를 보장 | 에이징 · 공정 큐 · 티켓 락 · 쓰기 우선 | Lamport 1974 |
대기 상한 장치는 «무엇을 기준으로 차례를 정하는가»가 다르다.
| 해결 | 차례 기준 | 대표 구현 | 대가 |
|---|---|---|---|
| 에이징 | 기다린 시간만큼 우선순위 상승 | 우선순위 스케줄러 | 올리는 주기 값 조정 |
| 공정 큐 | 도착 순서(FIFO) | new ReentrantLock(true) | 처리량 «often much slower»(ReentrantLock 문서) |
| 티켓 락 | 받은 번호(next) = 지금 번호(owner) | 리눅스 2.6.25 스핀락(LWN 2008) | CPU 수가 많으면 한 캐시 줄 경합 → MCS · 큐 락(Mellor-Crummey · Scott 1991) |
| 쓰기 우선 | 쓰기 대기가 있으면 새 읽기 차단 | PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP | 재귀 읽기 금지 · 쓰기가 이어지면 읽기가 밀림 |
🔑 기아는 자원이 «멈춘» 문제가 아니라 «순서가 없는» 문제다 — 그래서 해결은 자원을 늘리는 것이 아니라 정책에 대기 시간이나 도착 순서를 넣는 것이다.
5동작 — 읽기 우선 잠금에서 굶는 쓰기 스레드
직접 실행 환경 — WSL2 Ubuntu 22.04 · 커널 5.15.167 · glibc 2.35 · gcc 11.4.0 -O2 -pthread · 논리 CPU 32개. 시간 값은 이 실행 환경의 값이고, 판정은 획득 횟수와 반환 코드로 한다.
- 읽기 스레드 R1 ~ R4 를 0.5 ms 간격으로 띄우고, 각자
pthread_rwlock_rdlock→ 2.0 ms 읽기 → 해제 → 0.2 ms 쉼을 되풀이한다 — 2.2 ms 주기 중 2.0 ms 를 쥐므로 평균 3.6개가 늘 잠금 안에 있다. - 100 ms 뒤 쓰기 스레드 W 가
pthread_rwlock_timedwrlock을 3초 제한으로 부른다. - 기본 종류(
PTHREAD_RWLOCK_PREFER_READER_NP)에서는 W 가 기다리는 동안에도 새 읽기 요청이 W 를 앞질러 성공한다(setkind_np(3)). - 3초 동안 읽기 획득이 5,452회 일어나는 사이 잠금은 한 번도 비지 않는다.
- 3초 뒤 W 는 반환 코드 110(ETIMEDOUT)으로 끝난다 — 읽기 처리는 내내 진행했으므로 교착상태가 아니라 기아다.
- 같은 프로그램에서
pthread_rwlockattr_setkind_np로PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP를 주면, W 가 기다리는 동안 새 읽기 획득은 0회이고 이미 들어간 읽기가 끝나는 1.5 ms 뒤 W 가 잠금을 얻는다(두 번 실행 1.5 · 2.1 ms). - 대가로 W 가 줄을 서 있는 동안 새 읽기는 막히고, 쓰기가 연달아 오면 이번에는 읽기 쪽이 밀린다(Courtois 외 1971 둘째 해법).
그림 4 · 읽기 우선에서는 네 읽기의 보유 구간이 겹쳐 잠금이 비는 순간이 없어 W 가 3초 뒤 시간 초과로 끝나고(④⑤), 쓰기 우선에서는 새 읽기를 막아 1.7 ms 에 W 차례가 온다(⑥).
쓰기 우선 · 공정 큐는 «도착 순서»로 상한을 만들고, 우선순위 스케줄러는 순서를 버릴 수 없으므로 에이징으로 상한을 만든다. 아래는 설명용 가정 값이다 — 값이 클수록 높은 우선순위이고, 우선순위 5 작업 H 가 끊임없이 들어오는 동안 우선순위 1 작업 L 이 기다린다.
그림 5 · 에이징이 없으면 L 은 영원히 1 에 머물고, 2 tick 마다 1씩 올리면 8 tick 에 H 와 같아져 실행된다 — 최대 대기 = (5 − 1) × 주기.
🔑 에이징의 최대 대기는 «우선순위 차이 × 올리는 주기»로 정해진다 — 주기를 2 tick 에서 4 tick 으로 늘리면 상한도 8 tick 에서 16 tick 으로 두 배가 된다.
6비교 — 교착상태 · 라이브락 · 기아
| 기준 | 교착상태 | 라이브락 | 기아 |
|---|---|---|---|
| 시스템 진행 | 관련 스레드 전부 멈춤 | 전부 움직이지만 아무도 끝내지 못함 | 다른 스레드는 정상 진행 |
| 피해자 수 | 사슬에 든 둘 이상 | 서로 양보하는 둘 이상 | 하나(또는 한 부류) |
| 피해자 CPU | 0%(잠듦) | 높음(재시도 반복) | 0%(잠듦) 또는 실행 대기 |
| 대기 사슬 | 닫힌 원 | 원 없음 · 상태만 바뀜 | 원 없음 · 자원은 계속 넘어감 |
| 저절로 풀림 | 풀리지 않음 | 우연한 시점 차이로 풀리기도 함 | 경쟁자 흐름이 끊기면 풀림 |
| 해결 | 네 조건 중 하나 제거 · 철회 | 무작위 백오프 | 에이징 · 공정 큐 · 쓰기 우선 |
분석피해자 하나가 잠든 채 남고 다른 스레드가 같은 자원을 얻고 있으면 기아로 보고 정책을 바꾸며, 피해자들이 서로의 자원을 쥐고 있을 때만 교착상태 대책(잠금 순서)으로 넘어간다. 근거는 표의 「시스템 진행」 · 「대기 사슬」 행이다.
높은 우선순위 작업이 낮은 작업이 쥔 잠금 때문에 밀리는 우선순위 역전은 기아와 방향이 반대이며, 잠금 소유자가 기다리는 쪽의 우선순위를 물려받는 우선순위 상속으로 푼다(커널 rt-mutex 문서).
7실무 진단 — 순서에서 밀린 요청 가르기
분석먼저 늦는 요청 하나를 뺀 나머지 스레드가 같은 자원을 얻고 있는지 보고, 얻고 있으면 기아로 판단해 잠금 종류 · 공정성 · 우선순위 설정을 확인한다. 아무도 얻지 못하면 교착상태 · 라이브락 진단으로 넘긴다.
| # | 증상 | 의심 원인 | 구분 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 설정 갱신(쓰기)만 수 초째 안 끝나고 조회는 정상 | 읽기 우선 rwlock | 잠금 정책 | gdb -p <pid> -batch -ex "thread apply all bt" | 쓰기 스레드만 pthread_rwlock_wrlock 안에 있고 읽기 스레드는 자주 바뀌는 위치에 있음(GDB Threads · setkind_ |
| 2 | 스레드 하나만 진행 0 · CPU 는 바쁨 | 고정 우선순위 · 실시간 정책 | 스케줄링 | ps -L -o tid, | 같은 프로세스에 FF · RR 스레드가 R 상태로 돌고 피해 스레드는 TS 이며 pcpu 가 0 근처(ps(1)) |
| 3 | Java 요청 일부만 응답 시간이 수십 배 | 비공정 잠금의 끼어들기 | 잠금 정책 | jcmd <pid> Thread. 를 몇 초 간격 반복 | 같은 스레드가 매번 같은 잠금의 대기 목록에 남음 → 공정 잠금(true)으로 비교(jcmd · ReentrantLock 문서) |
| 4 | 다중 소켓 서버에서 스레드별 처리 시간이 크게 벌어짐 | 비공정 스핀락 | 잠금 구현 | 스레드별 처리 건수 · 실행 시간 집계 | 같은 일을 한 스레드 사이 차이가 2배 수준이면 티켓 · 큐 락 검토(LWN 2008) |
1 행처럼 스택을 두 번 이상 떠서 피해 스레드만 같은 함수에 머무는지 본다. 다른 스레드까지 같은 잠금 함수에서 멈춰 있으면 기아가 아니라 교착상태다.
8시험 대비
www.q-net.or.kr시험에서는 원인과 해결을 정리하는 정의 · 특징형, 교착상태 · 라이브락과 나란히 놓고 차이를 묻는 비교형이 나올 수 있다. 비교형이면 3 · 5 항목을 비교표 중심으로 늘린다.
- 개요 — 정의 · 「시스템은 진행 · 한 요청만 무한 대기」 · 스핀락 실행 시간 최대 2배 차이(LWN 2008)
- 발생 구조 — 그림 3 세 요소(경쟁자 흐름 · 대기 시간을 보지 않는 정책 · 피해자)
- 원인 — 우선순위 스케줄링 · SJF · 읽기 우선 락 · 비공정 락 · 그림 4 읽기 5,452회 · 쓰기 시간 초과
- 해결 — 에이징 · 공정 큐 · 티켓 락 · 쓰기 우선 표 · 그림 5 최대 대기 = 우선순위 차이 × 주기
- 교착상태 · 라이브락과 비교 — 시스템 진행 · 피해자 CPU · 대기 사슬 표
- 관련 현상 — 우선순위 역전 ↔ 우선순위 상속 한 줄
꼭 쓸 키워드
선택 정책대기 상한에이징공정 큐티켓 락읽기 우선쓰기 우선라이브락우선순위 역전우선순위 상속
다른 답안과 차이를 내는 한 가지는 그림 5 의 «최대 대기 = 우선순위 차이 × 올리는 주기» 식으로 에이징의 상한을 수치로 보이는 것이다.
9오해와 사실
- 오해기아는 교착상태의 가벼운 형태라서 교착상태 대책을 쓰면 함께 사라진다.사실기아에는 닫힌 대기 사슬이 없어 잠금 순서 규칙으로 막히지 않고, 차례 기준(도착 순서 · 대기 시간)을 정책에 넣어야 풀린다(Courtois 외 1971).
- 오해공정 잠금을 쓰면 스레드들이 고르게 진행한다.사실공정 잠금은 잠금 획득 순서만 보장하고 스레드 스케줄링의 공정성은 보장하지 않아, 한 스레드가 연달아 잠금을 얻을 수 있다(ReentrantLock 문서).
- 오해glibc 에서
PTHREAD_RWLOCK_PREFER_WRITER_NP를 주면 쓰기 기아가 사라진다.사실glibc 는 이 값을 무시하며, 쓰기 우선은PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP로만 된다(setkind_np(3)).
10핵심 정리
| 구분 | 차례 기준 | 기아 피해자 | 대기 상한 | 대표 구현 · 근거 |
|---|---|---|---|---|
| 읽기 우선 rwlock | 지금 들어올 수 있는 쪽 | 쓰기 스레드 | 없음 | glibc 기본 종류(setkind_ |
| 고정 우선순위 | 정해 둔 순위 | 낮은 순위 작업 | 없음 | 우선순위 스케줄러 |
| 비공정 스핀락 | 먼저 잡는 CPU | 멀리 있는 CPU | 없음 | 2.6.25 전 커널(LWN 2008) |
| 에이징 | 기다린 시간 | — | 우선순위 차이 × 주기 | 우선순위 스케줄러 보완 |
| 공정 큐 · 티켓 락 | 도착 순서 | — | 앞선 대기자 수 | ReentrantLock(true) · 빵집 알고리즘(Lamport 1974) |
| 쓰기 우선 rwlock | 쓰기 대기 유무 | 쓰기가 이어질 때 읽기 | 쓰기 쪽만 보장 | PREFER_ |
| 교착상태 · 라이브락 | — | 사슬에 든 전부 | — | 기아와 구분 · 사슬 · CPU 로 판정 |
11참고 문헌
- 먼저 볼 문헌
- ★ pthread_rwlockattr_setkind_np(3) Linux manual page — glibc 읽기 쓰기 잠금의 기본 종류가 쓰기 스레드를 굶긴다는 원문을 볼 때
- ★ Concurrent control with readers and writers — 읽기 우선 · 쓰기 우선 두 해법이 서로 다른 쪽을 굶기는 구조를 볼 때
- ★ Hierarchical ordering of sequential processes (EWD 310) — 식사하는 철학자 문제와 이웃 둘의 공모로 한 명이 굶는 경우를 원문으로 볼 때
- ★ Ticket spinlocks — 불공정 스핀락의 측정 수치와 티켓 락이 커널에 들어온 경위를 볼 때
- ★ Class ReentrantLock (Java SE 21 API) — 공정 잠금이 기아를 막는 대신 처리량을 내준다는 공식 설명을 볼 때
- 본문 근거
- Solution of a problem in concurrent programming control — E. W. Dijkstra · Communications of the ACM 8(9) 569 · 1965-09 ·
doi.org/10.1145/365559.365617· 확인 2026-11-04 - Additional comments on a problem in concurrent programming control — D. E. Knuth · Communications of the ACM 9(5) 321-322 · 1966-05 ·
doi.org/10.1145/355592.365595· 확인 2026-11-04 - A new solution of Dijkstra's concurrent programming problem — L. Lamport · Communications of the ACM 17(8) 453-455 · 1974-08 ·
doi.org/10.1145/361082.361093· 확인 2026-11-04 - Algorithms for scalable synchronization on shared-memory multiprocessors — J. M. Mellor-Crummey · M. L. Scott · ACM Transactions on Computer Systems 9(1) 21-65 · 1991-02 ·
doi.org/10.1145/103727.103729· 확인 2026-11-04 - RT-mutex implementation design (Linux kernel documentation) — The Linux Kernel documentation · 2026-11 ·
docs.kernel.org/locking/rt-mutex.html· 확인 2026-11-04 - ps(1) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man1/ps.1.html· 확인 2026-11-04 - jcmd (Java SE 21 Tools Reference) — Oracle · 2023-09 ·
docs.oracle.com/en/java/javase/21/docs/specs/man/jcmd.html· 확인 2026-11-04 - Debugging Programs with Multiple Threads (GDB manual) — GNU Project · 2026-11 ·
sourceware.org/gdb/current/onlinedocs/gdb.html/Threads.html· 확인 2026-11-04