IT › 컴퓨터 시스템 › 운영체제 › 프로세스 관리

Starvation기아 상태 · Starvation

시스템 전체는 계속 진행하는데 특정 프로세스나 스레드 하나가 자원 선택에서 거듭 밀려 끝없이 기다리는 상태이다. 선택 정책이 대기 시간을 보지 않을 때 생긴다.

1요약

  1. Starvation(기아)은 운영체제 스케줄러 · 스레드 라이브러리의 잠금 · DBMS 잠금 관리자에서 선택 정책이 특정 대기자를 거듭 건너뛰어 생기는 무한 대기이며, 그 위에서 에이징 · 공정 큐 · 티켓 락 · 쓰기 우선 같은 «대기 상한» 장치가 돈다.
  2. 시스템이 멈추지 않으므로 처리량 지표로는 보이지 않는다 — 리눅스 2.6.25 전 스핀락은 8코어 2소켓 Opteron 의 사용자 공간 시험에서 스레드마다 실행 시간이 최대 2배 벌어졌고, 이를 계기로 티켓 락이 들어왔다(LWN 2008).
  3. 「한 요청만 안 끝난다」는 다른 스레드가 같은 자원을 얻고 있는가로 가른다 — 다른 쪽이 계속 얻고 있으면 기아, 모두 잠들어 서로를 기다리면 교착상태, 모두 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쉽게 이해하기 — 손님이 끊이지 않는 열람실

작은 열람실 하나에 손님은 여럿이 함께 앉아 읽을 수 있지만, 서가를 정리하는 직원은 방이 텅 비어야 들어갈 수 있다. 문지기의 규칙은 «안에 손님이 있으면 새 손님도 들인다»이다. 손님이 몇 분마다 새로 와서 방이 한 번도 비지 않자, 정리 직원은 문 앞에서 하루 종일 기다린다. 열람실은 바쁘게 돌아가는데 한 사람만 끝내 들어가지 못하자, 관장은 번호표 기계를 들여와 온 순서대로 들이게 한다.

열람실 공유 자원 · 잠금 손님이 늘 3 ~ 4명 방이 비는 순간 없음 새 손님들 읽기 스레드 몇 분마다 끊임없이 옴 1 나가는 손님 잠금 해제 나가도 다른 손님이 남음 2 정리 직원 쓰기 스레드 방이 텅 비어야 들어감 하루 종일 문 앞 대기 3 못 들어감 규칙 문지기 선택 정책 안에 손님이 있으면 새 손님도 들임 = 읽기 우선 번호표 기계 공정 큐 · 티켓 온 순서대로 부름 직원은 앞 사람 수만큼만 대기 4 번호표가 직원 차례를 만든다 드나듦(진행) 끝없는 대기 차례 보장

그림 1 · 열람실은 계속 돌아가는데 정리 직원 한 명만 들어가지 못하고, 번호표로 온 순서를 지키게 하자 차례가 온다.

손님 입장안에 사람이 있으면 계속 들어옴
함께 읽기여럿이 동시에 앉음
문 앞 대기정리 직원은 빈 방을 기다림
하루가 감방이 한 번도 비지 않음
번호표온 순서대로 부름
정리 시작직원 차례가 옴
비유 — 문지기 규칙 실제 — 대기 순서 안에 손님이 있으면 새 손님도 들인다 들어온 순서는 보지 않음 읽기 우선 잠금 W R5 R6 R7 잠금 안 새 읽기가 W 를 앞지름 W 차례 = 오지 않음 · 대기 상한 없음 번호표 순서대로 들인다 받은 번호 = 부른 번호일 때 입장 티켓 락 · 공정 큐 7 · W 8 · R5 9 · R6 10 · R7 안 = 6번 W 차례 = 바로 다음 · 앞선 대기자 수만큼만 상자 안 숫자 = 받은 번호표(next) · 잠금 안 번호 = 지금 부른 번호(owner)

그림 2 · 문지기가 «들어온 순서»를 보지 않으면 정리 직원의 차례는 오지 않고, 번호표를 쓰면 앞 사람 수만큼만 기다린다.

비유 속 역할실제 이름실제로 하는 일
열람실공유 자원 · 읽기 쓰기 잠금읽기는 여럿이, 쓰기는 혼자만 쥘 수 있다
손님읽기 스레드pthread_rwlock_rdlock 으로 함께 들어간다
정리 직원쓰기 스레드 · 기아 피해자pthread_rwlock_wrlock 에서 빈 잠금을 기다린다
문지기 규칙선택 정책(읽기 우선)대기 시간을 보지 않고 지금 들어올 수 있는 쪽을 들인다
하루 종일 기다림상한 없는 대기시스템은 진행하는데 한 요청만 끝나지 않는다
번호표 기계공정 큐 · 티켓 락도착 순서대로 차례를 준다
오래 기다린 사람 먼저에이징기다린 시간만큼 우선순위를 올린다
정리 시작대기 상한 보장앞선 대기자 수만큼만 기다리고 들어간다

⚠ 비유가 맞지 않는 곳: 직원은 기다리다 지쳐 돌아갈 수 있지만 스레드는 제한 시간을 따로 주지 않으면 잠금 함수 안에서 영원히 잠들며, 번호표도 실제로는 대가가 있어 들어오는 순서를 강제하는 만큼 처리량이 줄어든다.

4구조 — 기아를 만드는 세 요소

기아는 ① 같은 자원을 노리는 경쟁자가 끊이지 않고 도착하고 ② 피해자가 그들과 함께 대기 집합에 남아 있으며 ③ 선택 정책이 대기 시간을 보지 않을 때 생긴다. 교착상태와 달리 대기 사슬은 닫히지 않고, 자원은 계속 누군가에게 넘어간다.

① 경쟁자 흐름 R5 도착 R6 도착 R7 도착 끊이지 않고 들어옴 ② 대기 집합 W · 대기 3초째 R5 · 방금 도착 R6 · 방금 도착 ③ 선택 정책 읽기 우선 대기 시간을 보지 않음 R5 자원 읽기 잠금 보유 R1 ~ R4 비는 순간 없음 해제 → 다시 선택 W 만 남음 = 기아 대기 상한 장치 — 정책에 차례 기준을 넣는다 에이징(대기 시간) · 공정 큐 · 티켓 락(도착 순서) · 쓰기 우선(쓰기 대기) 선택 정책에 붙음 경쟁 요청 피해자 선택 정책 자원 · 정상 흐름 대기 상한(해결)

그림 3 · 자원은 쉬지 않고 넘어가지만 정책이 대기 시간을 보지 않으면 대기 집합의 W 는 영원히 뽑히지 않는다 — 상한 장치는 선택 정책에 붙는다.

요소역할기아가 생기는 예근거
자원경쟁 대상읽기 쓰기 잠금 · CPU · 스핀락 · 행 잠금—
경쟁자 흐름계속 도착하는 요청읽기 스레드 · 높은 우선순위 작업 · 짧은 작업Courtois 외 1971
선택 정책다음 소유자를 고름읽기 우선 · 고정 우선순위 · SJF · 먼저 잡는 쪽(비공정)setkind_np(3)
피해자거듭 뽑히지 않는 대기자쓰기 스레드 · 낮은 우선순위 · 긴 작업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개. 시간 값은 이 실행 환경의 값이고, 판정은 획득 횟수와 반환 코드로 한다.

  1. 읽기 스레드 R1 ~ R4 를 0.5 ms 간격으로 띄우고, 각자 pthread_rwlock_rdlock → 2.0 ms 읽기 → 해제 → 0.2 ms 쉼을 되풀이한다 — 2.2 ms 주기 중 2.0 ms 를 쥐므로 평균 3.6개가 늘 잠금 안에 있다.
  2. 100 ms 뒤 쓰기 스레드 W 가 pthread_rwlock_timedwrlock 을 3초 제한으로 부른다.
  3. 기본 종류(PTHREAD_RWLOCK_PREFER_READER_NP)에서는 W 가 기다리는 동안에도 새 읽기 요청이 W 를 앞질러 성공한다(setkind_np(3)).
  4. 3초 동안 읽기 획득이 5,452회 일어나는 사이 잠금은 한 번도 비지 않는다.
  5. 3초 뒤 W 는 반환 코드 110(ETIMEDOUT)으로 끝난다 — 읽기 처리는 내내 진행했으므로 교착상태가 아니라 기아다.
  6. 같은 프로그램에서 pthread_rwlockattr_setkind_np 로 PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP 를 주면, W 가 기다리는 동안 새 읽기 획득은 0회이고 이미 들어간 읽기가 끝나는 1.5 ms 뒤 W 가 잠금을 얻는다(두 번 실행 1.5 · 2.1 ms).
  7. 대가로 W 가 줄을 서 있는 동안 새 읽기는 막히고, 쓰기가 연달아 오면 이번에는 읽기 쪽이 밀린다(Courtois 외 1971 둘째 해법).
가 · 읽기 우선(기본 종류) R1 R2 R3 R4 W 3초 뒤 110 4 읽기 5,452회 5 2 나 · 쓰기 우선(NONRECURSIVE_NP) R1 R2 R3 R4 W 1.7 ms 에 쓰기 잠금 획득 6 0 ms 뒤 새 읽기 0회 — 이미 들어간 R1 ~ R4 만 끝냄 0 2 4 6 8 10 ms 0 = W 가 쓰기 잠금을 요청한 때 · 막대 위치 = 실행 값(2.0 ms 보유 · 0.2 ms 쉼 · 0.5 ms 어긋남)으로 그린 모식 읽기 잠금 보유 쓰기 대기 쓰기 잠금 보유

그림 4 · 읽기 우선에서는 네 읽기의 보유 구간이 겹쳐 잠금이 비는 순간이 없어 W 가 3초 뒤 시간 초과로 끝나고(④⑤), 쓰기 우선에서는 새 읽기를 막아 1.7 ms 에 W 차례가 온다(⑥).

쓰기 우선 · 공정 큐는 «도착 순서»로 상한을 만들고, 우선순위 스케줄러는 순서를 버릴 수 없으므로 에이징으로 상한을 만든다. 아래는 설명용 가정 값이다 — 값이 클수록 높은 우선순위이고, 우선순위 5 작업 H 가 끊임없이 들어오는 동안 우선순위 1 작업 L 이 기다린다.

실효 우선순위 = 기본 1 + ⌊기다린 tick ÷ 주기⌋ (설명용 가정 값) 0 1 2 3 4 5 6 0 2 4 6 8 10 12 14 16 기다린 시간(tick) 우선순위(클수록 높음) H = 5 없음 = 끝없음 8 tick 에 L 실행 16 tick 주기 2 tick 주기 4 tick 계속 들어오는 H L · 에이징 없음 L · 주기 2 L · 주기 4 같으면 먼저 온 L 을 고름

그림 5 · 에이징이 없으면 L 은 영원히 1 에 머물고, 2 tick 마다 1씩 올리면 8 tick 에 H 와 같아져 실행된다 — 최대 대기 = (5 − 1) × 주기.

🔑 에이징의 최대 대기는 «우선순위 차이 × 올리는 주기»로 정해진다 — 주기를 2 tick 에서 4 tick 으로 늘리면 상한도 8 tick 에서 16 tick 으로 두 배가 된다.

6비교 — 교착상태 · 라이브락 · 기아

기준교착상태라이브락기아
시스템 진행관련 스레드 전부 멈춤전부 움직이지만 아무도 끝내지 못함다른 스레드는 정상 진행
피해자 수사슬에 든 둘 이상서로 양보하는 둘 이상하나(또는 한 부류)
피해자 CPU0%(잠듦)높음(재시도 반복)0%(잠듦) 또는 실행 대기
대기 사슬닫힌 원원 없음 · 상태만 바뀜원 없음 · 자원은 계속 넘어감
저절로 풀림풀리지 않음우연한 시점 차이로 풀리기도 함경쟁자 흐름이 끊기면 풀림
해결네 조건 중 하나 제거 · 철회무작위 백오프에이징 · 공정 큐 · 쓰기 우선

분석피해자 하나가 잠든 채 남고 다른 스레드가 같은 자원을 얻고 있으면 기아로 보고 정책을 바꾸며, 피해자들이 서로의 자원을 쥐고 있을 때만 교착상태 대책(잠금 순서)으로 넘어간다. 근거는 표의 「시스템 진행」 · 「대기 사슬」 행이다.

높은 우선순위 작업이 낮은 작업이 쥔 잠금 때문에 밀리는 우선순위 역전은 기아와 방향이 반대이며, 잠금 소유자가 기다리는 쪽의 우선순위를 물려받는 우선순위 상속으로 푼다(커널 rt-mutex 문서).

7실무 진단 — 순서에서 밀린 요청 가르기

분석먼저 늦는 요청 하나를 뺀 나머지 스레드가 같은 자원을 얻고 있는지 보고, 얻고 있으면 기아로 판단해 잠금 종류 · 공정성 · 우선순위 설정을 확인한다. 아무도 얻지 못하면 교착상태 · 라이브락 진단으로 넘긴다.

#증상의심 원인구분확인 명령판정 기준(근거)
1설정 갱신(쓰기)만 수 초째 안 끝나고 조회는 정상읽기 우선 rwlock잠금 정책gdb -p <pid> -batch -ex "thread apply all bt"쓰기 스레드만 pthread_rwlock_wrlock 안에 있고 읽기 스레드는 자주 바뀌는 위치에 있음(GDB Threads · setkind_np(3))
2스레드 하나만 진행 0 · CPU 는 바쁨고정 우선순위 · 실시간 정책스케줄링ps -L -o tid,cls,rtprio,ni,stat,pcpu -p <pid>같은 프로세스에 FF · RR 스레드가 R 상태로 돌고 피해 스레드는 TS 이며 pcpu 가 0 근처(ps(1))
3Java 요청 일부만 응답 시간이 수십 배비공정 잠금의 끼어들기잠금 정책jcmd <pid> Thread.print 를 몇 초 간격 반복같은 스레드가 매번 같은 잠금의 대기 목록에 남음 → 공정 잠금(true)으로 비교(jcmd · ReentrantLock 문서)
4다중 소켓 서버에서 스레드별 처리 시간이 크게 벌어짐비공정 스핀락잠금 구현스레드별 처리 건수 · 실행 시간 집계같은 일을 한 스레드 사이 차이가 2배 수준이면 티켓 · 큐 락 검토(LWN 2008)

1 행처럼 스택을 두 번 이상 떠서 피해 스레드만 같은 함수에 머무는지 본다. 다른 스레드까지 같은 잠금 함수에서 멈춰 있으면 기아가 아니라 교착상태다.

8시험 대비

출제 정보 컴퓨터시스템응용(140회, 137회, 132회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 원인과 해결을 정리하는 정의 · 특징형, 교착상태 · 라이브락과 나란히 놓고 차이를 묻는 비교형이 나올 수 있다. 비교형이면 3 · 5 항목을 비교표 중심으로 늘린다.

답안 목차
  1. 개요 — 정의 · 「시스템은 진행 · 한 요청만 무한 대기」 · 스핀락 실행 시간 최대 2배 차이(LWN 2008)
  2. 발생 구조 — 그림 3 세 요소(경쟁자 흐름 · 대기 시간을 보지 않는 정책 · 피해자)
  3. 원인 — 우선순위 스케줄링 · SJF · 읽기 우선 락 · 비공정 락 · 그림 4 읽기 5,452회 · 쓰기 시간 초과
  4. 해결 — 에이징 · 공정 큐 · 티켓 락 · 쓰기 우선 표 · 그림 5 최대 대기 = 우선순위 차이 × 주기
  5. 교착상태 · 라이브락과 비교 — 시스템 진행 · 피해자 CPU · 대기 사슬 표
  6. 관련 현상 — 우선순위 역전 ↔ 우선순위 상속 한 줄

꼭 쓸 키워드
선택 정책대기 상한에이징공정 큐티켓 락읽기 우선쓰기 우선라이브락우선순위 역전우선순위 상속

다른 답안과 차이를 내는 한 가지는 그림 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_np(3))
고정 우선순위정해 둔 순위낮은 순위 작업없음우선순위 스케줄러
비공정 스핀락먼저 잡는 CPU멀리 있는 CPU없음2.6.25 전 커널(LWN 2008)
에이징기다린 시간—우선순위 차이 × 주기우선순위 스케줄러 보완
공정 큐 · 티켓 락도착 순서—앞선 대기자 수ReentrantLock(true) · 빵집 알고리즘(Lamport 1974)
쓰기 우선 rwlock쓰기 대기 유무쓰기가 이어질 때 읽기쓰기 쪽만 보장PREFER_WRITER_NONRECURSIVE_NP
교착상태 · 라이브락—사슬에 든 전부—기아와 구분 · 사슬 · CPU 로 판정

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ pthread_rwlockattr_setkind_np(3) Linux manual page — glibc 읽기 쓰기 잠금의 기본 종류가 쓰기 스레드를 굶긴다는 원문을 볼 때
    man7.org · 2026-11 · man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html · 확인 2026-11-04
  3. ★ Concurrent control with readers and writers — 읽기 우선 · 쓰기 우선 두 해법이 서로 다른 쪽을 굶기는 구조를 볼 때
    P. J. Courtois · F. Heymans · D. L. Parnas · Communications of the ACM 14(10) 667-668 · 1971-10 · doi.org/10.1145/362759.362813 · 확인 2026-11-04
  4. ★ Hierarchical ordering of sequential processes (EWD 310) — 식사하는 철학자 문제와 이웃 둘의 공모로 한 명이 굶는 경우를 원문으로 볼 때
    E. W. Dijkstra · E.W. Dijkstra Archive (University of Texas at Austin) · 1971 · www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD310.html · 확인 2026-11-04
  5. ★ Ticket spinlocks — 불공정 스핀락의 측정 수치와 티켓 락이 커널에 들어온 경위를 볼 때
    J. Corbet · LWN.net · 2008-02 · lwn.net/Articles/267968/ · 확인 2026-11-04
  6. ★ Class ReentrantLock (Java SE 21 API) — 공정 잠금이 기아를 막는 대신 처리량을 내준다는 공식 설명을 볼 때
    Oracle · 2023-09 · docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/locks/ReentrantLock.html · 확인 2026-11-04
  7. 본문 근거
  8. 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
  9. 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
  10. 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
  11. 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
  12. RT-mutex implementation design (Linux kernel documentation) — The Linux Kernel documentation · 2026-11 · docs.kernel.org/locking/rt-mutex.html · 확인 2026-11-04
  13. ps(1) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man1/ps.1.html · 확인 2026-11-04
  14. jcmd (Java SE 21 Tools Reference) — Oracle · 2023-09 · docs.oracle.com/en/java/javase/21/docs/specs/man/jcmd.html · 확인 2026-11-04
  15. Debugging Programs with Multiple Threads (GDB manual) — GNU Project · 2026-11 · sourceware.org/gdb/current/onlinedocs/gdb.html/Threads.html · 확인 2026-11-04