기아 상태 (Starvation / Indefinite Blocking)

핵심 인사이트 (3줄 요약)

  1. 본질: 기아 상태 (Starvation)는 스케줄러의 특정 자원 할당 정책(예: 우선순위, SJF)으로 인해, 조건에 부합하지 않는 특정 프로세스가 준비 큐(Ready Queue)에 무한정 갇혀 CPU를 단 1틱도 배정받지 못하는 '무기한 대기(Indefinite Blocking)' 현상이다.
  2. 가치: 교착 상태(Deadlock)가 프로세스들이 서로의 자원을 물고 늘어져 다 같이 멈추는 시스템 붕괴라면, 기아 상태는 시스템 자체는 잘 돌아가지만 철저한 계급 사회에서 소외된 계층만 영원히 굶어 죽는 스케줄링의 구조적 모순을 보여준다.
  3. 융합: 이를 해결하기 위해 운영체제는 큐에서 기다린 시간만큼 우선순위를 인위적으로 높여주는 노화(Aging, 에이징) 기법을 도입하거나, 절대적 기아를 방지하는 라운드 로빈(RR), CFS(가상 실행 시간 기반) 아키텍처로 진화하게 되었다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

  • 개념: 스케줄러가 특정 규칙(우선순위가 높거나, 실행 시간이 짧거나)을 가진 프로세스를 편애하여 자원을 분배할 때, 그 규칙에서 소외된 프로세스(우선순위가 낮거나 덩치가 큰 작업)가 평생토록 CPU를 할당받지 못하고 레디 큐에 방치되는 현상이다.
  • 필요성: 한정된 자원을 어떻게 분배할 것인가를 고민할 때 '효율성(SJF)'이나 '중요성(우선순위)'을 극대화하려다 보면 필연적으로 버려지는 약자가 생긴다. 운영체제는 최소한의 공정성(Fairness)을 담보하여 사용자가 제출한 모든 작업이 "느리더라도 언젠가는 끝난다"는 신뢰를 제공해야 하므로, 이 기아 현상을 감지하고 타파할 메커니즘이 필수적이다.
  • 💡 비유: 인기 있는 뷔페에서 음식(CPU)이 새로 나올 때마다 달리기 빠르고 덩치 큰 학생들(우선순위 높은 프로세스)이 새치기해서 다 가져가 버려, 줄 맨 뒤에 선 어린아이(낮은 우선순위)는 식당 문 닫을 때까지 한 입도 못 먹고 서 있는 **'무한 새치기 피해'**와 같다.
  • 등장 배경: SJF(가장 짧은 작업 우선) 알고리즘이 평균 대기 시간을 극적으로 줄인다는 사실이 증명되었지만, 짧은 I/O 1ms짜리 프로세스들이 1초에 수천 개씩 쏟아져 들어오면 100ms짜리 긴 프로세스는 아예 실행을 못 한다는 사실이 뒤늦게 발견되었다. 이후 IBM 7094 메인프레임에서 1967년에 제출된 작업이 1973년 시스템 셧다운 때까지 한 번도 실행되지 못한 채 발견된 충격적 사건을 계기로 학계의 집중 연구 대상이 되었다.
  [기아 상태의 발생 구조 시각화 (우선순위/SJF 모델)]

  (신규 유입 스트림: 짧거나 우선순위 높은 VIP들)
  VIP 1 ▶ VIP 2 ▶ VIP 3 ▶ VIP 4 ──────┐
                                       ▼ (무한 새치기 진입)
  [ Ready Queue (철저한 신분제) ]           [ CPU (실행) ]
  | 꼴찌 프로세스 | ─▶ (앞으로 전진 불가) ◀── VIP들만 빙빙 돌며 CPU 독점
  (1년째 대기 중)

[다이어그램 해설] 기아 상태의 핵심은 큐 자체가 막힌 것이 아니라(Deadlock과 다름), 시스템 자체는 100% 이용률로 팽팽 잘 돌아가고 있다는 점이다. 단지 큐 정렬 조건이 철저한 능력주의(짧은 시간)나 신분제(우선순위)를 따르기 때문에, 하위 계급인 '꼴찌 프로세스' 앞쪽으로 새로운 VIP들이 계속 꽂히는 구조적 모순을 보여준다.

  • 📢 섹션 요약 비유: 도로에 앰뷸런스와 소방차(VIP)가 1분 간격으로 끊임없이 지나간다면, 일반 승용차(꼴찌)는 법규(스케줄링)를 지키기 위해 갓길에 세워둔 채 평생 동안 목적지에 도착할 수 없는 딜레마에 빠집니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

기아 상태(Starvation) vs 교착 상태(Deadlock)의 심층 비교

둘 다 프로세스가 영원히 대기하는 현상이지만, 그 물리적 원인과 발생 아키텍처는 완전히 다르다.

비교 항목기아 상태 (Starvation)교착 상태 (Deadlock)
발생 원인스케줄러의 편향된 스케줄링 정책 (가벼운 작업 편애)프로세스 간 공유 자원의 순환 대기 (상호 배제 꼬임)
시스템 상태시스템은 매우 바쁘게 잘 돌아감 (이용률 높음)관련된 프로세스 모두 완전히 멈춤 (이용률 저하)
피해자오직 우선순위가 낮거나 작업이 긴 소수의 프로세스락(Lock) 사이클에 휘말린 모든 프로세스
주요 대기 큐Ready Queue (CPU 대기열)Wait Queue (I/O, Lock 대기열)
해결 기법에이징(Aging), 라운드 로빈(RR) 도입은행원 알고리즘, 교착 상태 무시(타조 알고리즘), 강제 Kill

구조적 해결책 1: 에이징 (Aging)

운영체제 커널이 기아 상태를 부수기 위해 발명한 가장 원초적이고 확실한 구제 정책이다.

  • 원리: 시간이 지남(늙어감)에 따라 스케줄러가 대기 중인 프로세스에게 "불쌍함 가산점(우선순위 승급)"을 부여한다.
  • 구현: 매 1초(또는 1,000틱)가 지날 때마다 레디 큐를 순회하며 대기 중인 프로세스의 우선순위 번호를 -1(리눅스 기준, 음수일수록 높음) 깎아준다.
  • 결과: 아무리 밑바닥 천민으로 태어난 프로세스라 하더라도, 수 분~수십 분이 지나면 옥황상제(최우선순위 0) 급으로 강제 신분 세탁이 이루어지므로 결국엔 무조건 CPU를 한 번은 잡게 된다. (수학적 유한 대기 증명 완료)
  ┌───────────────────────────────────────────────────────────────────┐
  │         에이징(Aging)에 의한 신분 상승(우선순위 역전) 시뮬레이션  │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │  시간(초) │ [VIP 그룹]의 우선순위 │ [P_꼴찌]의 우선순위 변화      │
  │  ────────┼───────────────────────┼────────────────────────        │
  │     0초  │         1 (고정)      │        120 (밑바닥)            │
  │    10초  │         1 (고정)      │        110 (-10 승급)          │
  │    50초  │         1 (고정)      │         70 (-50 승급)          │
  │   119초  │         1 (고정)      │          1 (-119승급)          │
  │   120초  │         1 (고정)      │    ⭐ 0 (최고 존엄 도달)       │
  │                                                                   │
  │  🚨 120초 시점 결과: P_꼴찌가 모든 VIP들을 무자비하게 밀어내고    │
  │                     CPU를 당당히 차지하며 기아 상태 탈출!         │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 철저한 계급 사회인 우선순위 큐에 '시간의 흐름'이라는 민주적인 요소를 섞어 넣은 것이다. 에이징의 핵심은 기울기(10초당 -10씩)를 조절하는 것이다. 이 기울기가 너무 가파르면 우선순위 큐가 사실상 FCFS(선착순)로 붕괴해버리고, 너무 완만하면 기아 탈출에 며칠이 걸린다.

  • 📢 섹션 요약 비유: 에버랜드 Q-Pass(VIP) 손님들이 계속 와서 일반 손님이 롤러코스터를 못 타더라도, 일반 손님의 대기 시간이 3시간을 넘기면 직원이 "아이고 오래 기다리셨습니다" 하고 Q-Pass보다도 먼저 태워주는 융통성이 바로 에이징입니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

스케줄러별 기아 상태(Starvation) 발생 확률 및 내성

스케줄링 기법기아 발생 가능성발생 사유 및 방어 메커니즘 (내성)
FCFS❌ 없음 (0%)큐에 들어온 순서대로 무조건 빼주므로 영원히 대기하지 않는다. (대신 호위 효과라는 다른 병에 걸림)
라운드 로빈 (RR)❌ 없음 (0%)순환 큐를 돌며 퀀텀 단위로 강제 교대하므로 기아가 절대 발생할 수 없다.
SJF / SRTF🔴 매우 높음짧은 프로세스만 쏙쏙 빼먹으므로 무거운 프로세스는 구조적 기아 상태에 빠진다.
우선순위 큐🔴 매우 높음특정 하위 계급은 VIP의 계속된 유입 시 절대권력에 눌려 기아에 빠진다.
MLFQ🟡 중간 (에이징으로 방어)하위 큐에 무거운 놈을 처박아 두지만, 주기적으로 최상위 큐로 다 퍼 올려주는(Boost) 에이징 덕에 기아를 탈출한다.

철학적 딜레마: 처리량(Throughput) vs 공정성(Fairness)

SJF가 기아를 발생시킴에도 매력적인 이유는, 짧은 놈 수십 개를 쳐내는 동안 무거운 놈 하나를 굶기면 시스템 전체의 처리량과 평균 대기시간 성적표가 미친 듯이 좋아지기 때문이다. 즉, 기아 상태는 단순한 '버그'라기보다는 다수의 이익을 위해 소수를 희생시키는 공리주의적 스케줄링의 필연적인 부작용이다. 반면 라운드 로빈(RR)이나 에이징(Aging)은 전체 효율이 조금 깎이더라도 "누구도 소외받지 않아야 한다"는 공정성(Fairness)을 강제하는 시스템적 세금이다.

  • 📢 섹션 요약 비유: 10명의 감기 환자와 1명의 대수술 환자가 있을 때, 감기 환자 10명부터 5분 만에 돌려보내면 병원 수익(처리량)은 최고지만 대수술 환자는 죽습니다(기아 상태). 사회적 규범(공정성)을 위해 수익을 포기하고 대수술 환자에게 수술방을 내어주는 것이 에이징과 RR의 철학입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

  1. 리눅스 OOM (Out Of Memory) Killer의 타깃 기아 문제: 서버 메모리가 부족해지면 OOM Killer 데몬이 점수가 가장 높은 프로세스를 찾아 죽인다. 이때 데이터베이스 백업 스크립트(하위 우선순위)가 I/O 대기만 하느라 실행을 못 하고 계속 큐에 남아있으면서 점수가 누적되어, 오히려 죄 없는 백업 스크립트가 OOM의 타깃으로 억울하게 죽는 기아+OOM 콤보 장애가 발생할 수 있다.
    • 실무 조치: 스크립트 실행 시 oom_score_adj 값을 마이너스로 세팅하여 면책 특권을 부여하고, 커널 CFS 스케줄러 튜닝을 통해 I/O 대기가 길어진 녀석들에게 vruntime 페널티를 줄여주어 한 번은 숨을 쉴 수 있게 해야 한다.
  2. 이벤트 루프와 스레드 풀에서의 기아 현상 (Thread Starvation): Java의 Tomcat 웹 서버에서 커넥션 풀(Thread Pool) 200개를 만들어 놨는데, 외부 느린 API를 호출하는(Timeout 30초) 결제 스레드 200개가 들어와서 풀을 꽉 채워버렸다(Blocked). 이때 가벼운 메인 페이지 조회(0.1초 컷) 요청들이 들어와도 워커 스레드를 할당받지 못해 무한 펜딩에 걸린다. 이것이 애플리케이션 레벨의 전형적인 스레드 기아 상태(Thread Pool Starvation)다.
    • 아키텍처 결단: 이를 막기 위해 무거운/느린 결제 API용 스레드 풀과, 가벼운 메인 조회용 스레드 풀을 물리적으로 격리(Bulkhead Pattern)하거나, 코루틴/비동기 이벤트 루프(WebFlux)를 도입해 1개의 스레드가 멈춰서 풀이 마르는 기아를 원천 봉쇄해야 한다.
  ┌───────────────────────────────────────────────────────────────────┐
  │     애플리케이션 스레드 풀(Thread Pool) 기아 상태 방어 트리       │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [특정 API 지연으로 인해 전체 서버 응답이 멈춤 (기아 발생)]      │
  │                │                                                  │
  │                ▼ 원인 분석                                        │
  │   소수의 무거운 작업이 제한된 스레드 풀을 전부 점유했는가?        │
  │          ├─ [예 (Thread Starvation 확정)]                         │
  │          │      │                                                 │
  │          │      ▼ 아키텍처 개선                                   │
  │          │  1. Bulkhead 패턴: 용도별 스레드 풀 분리 개설          │
  │          │  2. Circuit Breaker: 느린 API 강제 타임아웃 차단       │
  │          │  3. Non-blocking 전환: 스레드 대기 상태 제거           │
  │          │                                                        │
  │          └─ [아니오]                                              │
  │                 │                                                 │
  │                 ▼                                                 │
  │             DB 커넥션 부족, 혹은 실제 데드락(Deadlock) 의심       │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] CPU 스케줄러의 기아 상태는 OS 커널이 에이징(Aging)을 통해 알아서 막아주지만, 웹 서버(Tomcat, Nginx) 내부에 큐잉된 유저 스레드의 기아 상태는 철저히 백엔드 개발자의 책임이다. 아무리 가벼운 작업이라도 스레드 풀이라는 '입구'를 무거운 작업들이 다 막아버리면 유저 입장에서는 서버가 죽은 것과 똑같은 응답 불가에 빠진다.

  • 📢 섹션 요약 비유: 식당 출입문에 코끼리 3마리(무거운 스레드)가 서서 밥을 먹으며 문을 막아버리면, 토끼 100마리(가벼운 스레드)가 식당 밖에서 굶어 죽습니다. 코끼리 전용 문과 토끼 전용 문(Bulkhead Pattern)을 애초에 쪼개서 짓는 것이 백엔드 설계의 핵심입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

에이징과 다단계 피드백 큐를 통해 시스템 내의 잠재적 기아 상태를 제거하면, 무거운 배치성(Batch) 작업이나 데몬 프로세스들도 예측 가능한 반환 시간(Bounded Turnaround Time) 내에 작업을 종료할 수 있어 시스템의 거시적인 찌꺼기(Zombie/Stale) 적체를 방지할 수 있다.

결론 및 미래 전망

운영체제 스케줄러 설계의 역사는 "효율(SJF)을 좇다 발생한 기아(Starvation)를 어떻게 우아하게 해결할 것인가"에 대한 해답 찾기였다. 현대 리눅스의 CFS(Completely Fair Scheduler)는 레드-블랙 트리(Red-Black Tree)를 사용하여 프로세스가 쓴 '가상 실행 시간(vruntime)'을 기록하고, 큐에서 대기하며 굶고 있는 녀석의 vruntime을 가장 작게 계산하여 무조건 트리의 왼쪽(최우선 탐색 노드)으로 밀어 넣는다. 즉, 에이징이라는 별도의 더러운 땜질 로직 없이도, 수학적 알고리즘 자체가 "굶은 놈을 1순위로 살려내는" 완벽한 공정성의 세계로 진화한 것이다.

  • 📢 섹션 요약 비유: 과거에는 굶어 죽어가는 빈민(기아 상태)을 찾아내기 위해 관리가 주기적으로 마을을 돌며 쌀(에이징 가산점)을 던져주는 수동적 구휼이었다면, 미래의 시스템(CFS)은 태어날 때부터 굶은 시간만큼 자동으로 통장 잔고(vruntime)가 늘어나 즉시 빵을 사 먹게 되는 완벽한 자동 복지 사회입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭관계 및 시너지 설명
노화 (Aging)기아 상태의 유일하고도 절대적인 카운터 백신으로, 대기 시간에 비례해 권력(우선순위)을 올려준다.
우선순위 스케줄링 (Priority)계급 사회를 만들어냄으로써 기아 상태라는 괴물을 탄생시킨 가장 근본적인 아키텍처다.
SJF (Shortest Job First)실행 시간이라는 우선순위 잣대를 들이대어 덩치 큰 프로세스들을 기아 상태로 몰아넣은 알고리즘이다.
교착 상태 (Deadlock)기아 상태와 자주 비교되나, 큐가 막혀서 다 죽는 데드락과 달리 시스템은 돌아가는데 나만 굶어 죽는 것이 기아다.
가상 실행 시간 (vruntime)리눅스 CFS가 기아 현상을 에이징 없이 우아하게 막아내기 위해 사용한 "과거에 얼마나 굶었나"를 측정하는 절대 지표다.

👶 어린이를 위한 3줄 비유 설명

  1. 급식소에서 "키가 작은 친구(짧은 작업)"나 "선생님(높은 우선순위)"만 먼저 밥을 주는 규칙이 생겼어요.
  2. 그런데 1학년 꼬마들이 끝없이 1만 명이나 밥을 먹으러 오면, 줄 맨 뒤에 선 6학년 뚱보 형은 밥통에 밥이 남아도는데도 하루 종일 밥을 구경도 못 하고 굶어 쓰러져요. 이걸 **기아 상태(Starvation)**라고 해요.
  3. 그래서 영양사 선생님이 "어구, 너 3시간이나 기다렸구나! 너무 불쌍하니까 키 커도 무조건 제일 먼저 밥 줄게!" 하고 나이(대기 시간)를 쳐서 살려주는 마법을 **에이징(Aging)**이라고 부른답니다!