시스매

운영체제 기아 상태 완벽 정복 핸드북 원인부터 해결까지

18 min read

2025-10-06 21:29

운영체제 기아 상태 완벽 정복 핸드북 원인부터 해결까지

  • 운영체제에서 기아 상태]는 특정 프로세스가 실행에 필요한 자원을 계속해서 할당받지 못해 무기한 대기하는 현상을 의미한다.

  • 이는 주로 우선순위 기반 스케줄링에서 고우선순위 프로세스들에게 계속 밀리거나, 불공정한 자원 할당 정책 때문에 발생한다.

  • 기아 상태를 해결하기 위해 프로세스의 대기 시간에 비례해 우선순위를 높여주는 ‘에이징(Aging)’ 기법이나, 모든 프로세스에게 공평한 실행 기회를 보장하는 스케줄링 알고리즘을 사용한다.

1. 만들어진 이유: 왜 프로세스는 굶주리는가?

운영체제는 여러 프로세스가 한정된 시스템 자원(CPU, 메모리 등)을 효율적으로 나눠 쓰도록 관리하는 지휘자와 같다. 이 지휘자는 ‘스케줄링’이라는 규칙에 따라 각 프로세스에게 자원을 배분한다. 하지만 이 규칙이 특정 프로세스에게만 유리하게 적용된다면 어떻게 될까? 마치 레스토랑에서 계속해서 들어오는 VIP 손님들 때문에 일반 손님이 끝없이 기다리기만 하는 상황이 발생할 수 있다. 운영체제에서 이러한 현상을 기아 상태(Starvation) 또는 **무한 봉쇄(Indefinite Blocking)**라고 부른다.

기아 상태는 시스템의 **공정성(Fairness)**과 효율성을 해치는 심각한 문제다. 특정 프로세스가 영원히 실행되지 못하면, 그 프로세스가 처리해야 할 작업은 완료될 수 없고, 이는 전체 시스템의 성능 저하 또는 오작동으로 이어질 수 있다. 예를 들어, 시스템의 상태를 주기적으로 백업하는 낮은 우선순위의 프로세스가 기아 상태에 빠진다면, 치명적인 장애 발생 시 데이터를 복구하지 못하는 상황이 발생할 수도 있다.

이러한 기아 상태의 발생 가능성을 이해하고 해결하는 것은 안정적이고 예측 가능한 운영체제를 설계하는 데 있어 핵심적인 과제다. 따라서 기아 상태의 근본적인 원인을 파악하고, 이를 방지하기 위한 다양한 기법들이 고안되었다.

2. 구조: 기아 상태의 해부

기아 상태는 하나의 원인이 아닌, 여러 시스템적 요인들이 복합적으로 작용하여 발생한다. 그 핵심 구조를 해부해 보면 다음과 같은 원인들을 발견할 수 있다.

가. 핵심 원인: 우선순위 스케줄링의 함정

가장 흔한 원인은 **엄격한 우선순위 기반 스케줄링(Priority Scheduling)**이다. 이 방식은 각 프로세스에 우선순위를 부여하고, 항상 우선순위가 가장 높은 프로세스를 먼저 실행한다. 효율적으로 보이지만, 만약 시스템에 높은 우선순위의 프로세스가 끊임없이 유입된다면 어떻게 될까? 낮은 우선순위의 프로세스는 CPU를 할당받을 기회를 영원히 얻지 못하고 ‘굶주리게’ 된다.

  • 비유: 인기 많은 맛집의 예약 시스템과 같다. 예약 손님(고우선순위)이 계속해서 들어오면, 현장에서 기다리는 손님(저우선순위)은 언제 식사를 할 수 있을지 기약할 수 없다.

나. 자원 독점과 불공정한 정책

특정 프로세스가 자원을 비정상적으로 오래 점유하거나, 자원 할당 정책 자체가 불공정할 때도 기아 상태가 발생할 수 있다. 예를 들어, 최단 작업 우선(Shortest Job First, SJF) 스케줄링은 실행 시간이 짧은 프로세스를 먼저 처리하여 시스템의 평균 대기 시간을 줄이는 데 효과적이다. 하지만 실행 시간이 긴 프로세스는 계속해서 유입되는 짧은 프로세스들에 밀려 무한정 대기할 수 있다.

다. 기아 상태와 혼동하기 쉬운 개념들

기아 상태는 교착 상태(Deadlock), 라이브락(Livelock)과 자주 혼동되지만, 명확한 차이가 있다.

구분기아 상태 (Starvation)교착 상태 (Deadlock)라이브락 (Livelock)
상태프로세스는 대기(Ready) 상태에 있지만 스케줄러에 의해 선택되지 못함여러 프로세스가 서로가 점유한 자원을 기다리며 블록(Blocked) 상태에 빠짐프로세스들은 계속 상태를 변경하며 능동적으로 움직이지만, 실질적인 진행은 없음
진행고우선순위 프로세스들은 계속 실행됨모든 관련 프로세스가 멈춤모든 관련 프로세스가 헛된 작업만 반복하며 멈춤
원인스케줄링 정책의 불공정성상호 배제, 점유와 대기, 비선점, 원형 대기 4가지 조건 동시 충족잘못된 상호 회피/복구 메커니즘
비유계속된 VIP 손님 때문에 식사를 못하는 일반 손님두 차량이 외나무다리 양 끝에서 마주 보고 멈춰 선 상황복도에서 마주친 두 사람이 서로 같은 방향으로 계속 피하려다 지나가지 못하는 상황

3. 사용법: 기아 상태 해결 및 예방 가이드

기아 상태를 해결하고 예방하는 것은 시스템의 안정성을 보장하는 핵심 기술이다. 주요 해결책은 ‘기다린 자에게 복이 오게’ 만들거나, 애초에 ‘모두에게 공평한 기회를 주는’ 방식으로 요약할 수 있다.

가. 노화(Aging): 기다림의 가치를 높이다

가장 대표적인 해결책은 에이징(Aging) 기법이다. 이는 오랫동안 대기열에서 기다린 프로세스의 우선순위를 점진적으로 높여주는 방식이다. 아무리 우선순위가 낮게 시작했더라도, 충분한 시간이 지나면 결국 가장 높은 우선순위를 갖게 되어 언젠가는 실행될 기회를 보장받는다.

  • 작동 원리: 시스템은 주기적으로 대기 중인 모든 프로세스를 검사한다. 일정 시간 이상 대기한 프로세스가 있다면, 그 프로세스의 우선순위를 한 단계씩 높인다.

  • 예시: 0(가장 높음)부터 255(가장 낮음)까지의 우선순위 범위를 가진 시스템을 가정해 보자.

    1. 프로세스 A는 우선순위 200으로 생성되어 대기 큐에 들어간다.

    2. 시스템은 10초마다 대기 중인 프로세스의 우선순위를 1씩 높인다.

    3. 프로세스 A가 계속 선택받지 못하면, 10초 후에는 199, 20초 후에는 198로 우선순위가 계속 높아진다.

    4. 결국 우선순위가 시스템 내의 다른 프로세스들보다 높아지는 시점이 오고, CPU를 할당받게 된다.

에이징 기법 의사 코드(Pseudo-code):

FUNCTION scheduler_tick():
  FOR EACH process IN ready_queue:
    process.wait_time = process.wait_time + 1
    
    // 일정 대기 시간을 초과하면 우선순위를 높인다 (숫자가 낮을수록 높음)
    IF process.wait_time > AGING_THRESHOLD:
      IF process.priority > MIN_PRIORITY:
        process.priority = process.priority - 1
      process.wait_time = 0 // 대기 시간 초기화

FUNCTION select_process_to_run():
  // 우선순위가 가장 높은 프로세스를 선택
  return process with the minimum priority value in ready_queue

나. 공정한 스케줄링 알고리즘 채택

애초에 기아 상태가 발생하기 어려운 구조의 스케줄링 알고리즘을 사용하는 것이 근본적인 해결책이 될 수 있다.

  1. 라운드 로빈 (Round-Robin, RR):

    • 개념: 모든 프로세스에게 ‘타임 슬라이스(Time Slice)’ 또는 ‘퀀텀(Quantum)‘이라는 동일한 크기의 CPU 사용 시간을 할당하고, 준비 큐를 순환하면서 차례대로 실행시킨다.

    • 기아 상태 방지 원리: 어떤 프로세스도 무한정 기다리지 않는다. 아무리 많은 프로세스가 있더라도, 정해진 시간((n-1) * q, 여기서 n은 프로세스 수, q는 퀀텀)이 지나면 반드시 자신의 차례가 돌아온다. 우선순위 개념이 없어 특혜를 받는 프로세스가 존재하지 않는다.

  2. 완전 공정 스케줄러 (Completely Fair Scheduler, CFS):

    • 개념: 현대 리눅스 커널의 기본 스케줄러로, ‘이상적인 멀티태스킹 CPU’를 모델링한다. 모든 프로세스에게 CPU 시간을 완벽하게 공평하게 분배하는 것을 목표로 한다.

    • 기아 상태 방지 원리: CFS는 각 프로세스가 얼마나 오래 실행되었는지를 vruntime(virtual runtime)이라는 값으로 추적한다. 그리고 항상 vruntime이 가장 작은 프로세스, 즉 가장 적게 실행된 프로세스를 다음에 실행할 대상으로 선택한다. 따라서 특정 프로세스가 오랫동안 실행되지 못했다면 vruntime이 가장 작아져 다음 실행 순서로 뽑힐 확률이 매우 높아지므로, 기아 상태에 빠지지 않는다.

4. 심화 내용: 기아 상태의 변종과 현실 세계의 예

기아 상태는 CPU 스케줄링뿐만 아니라 다양한 시스템 환경에서 변형된 형태로 나타난다.

가. 우선순위 역전 (Priority Inversion)

기아 상태와 유사하지만 더 복잡한 문제로 우선순위 역전이 있다. 이는 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스의 실행을 막는 역설적인 상황을 말한다.

  • 발생 시나리오:

    1. L (낮음), M (중간), H (높음) 세 가지 우선순위의 프로세스가 있다.

    2. L이 공유 자원(예: Lock)을 획득하여 사용 중이다.

    3. H가 실행되어 L이 가진 자원을 요청하지만, L이 자원을 해제할 때까지 H는 대기(Blocked) 상태가 된다.

    4. 여기까지는 정상적인 흐름이다. 그런데 이때 L보다 우선순위가 높은 M이 실행 준비 상태가 된다.

    5. 스케줄러는 대기 중인 H와 실행 가능한 M, L 중에서 M의 우선순위가 가장 높다고 판단하여 M에게 CPU를 할당한다.

    6. 결과적으로 L은 M 때문에 실행되지 못하고, H는 L이 자원을 놓아주기만을 기다리며 무한정 대기할 수 있다. 가장 중요한 H가 무관한 M 때문에 실행되지 못하는 역전 현상이 발생한 것이다.

  • 해결책: 우선순위 상속(Priority Inheritance). L이 H를 막고 있는 동안, L의 우선순위를 일시적으로 H의 우선순위까지 높여준다. 이렇게 하면 M이 L을 선점할 수 없게 되고, L이 빠르게 작업을 마친 뒤 자원을 해제하여 H가 신속하게 실행될 수 있다.

  • 실제 사례: 1997년 화성 탐사선 패스파인더(Pathfinder)호에서 이 문제로 인해 시스템 리셋이 반복되는 심각한 오류가 발생했으나, 우선순위 상속 옵션을 활성화하여 원격으로 해결한 일화는 매우 유명하다.

나. 현실 세계의 기아 상태

  • 데이터베이스 시스템: 여러 트랜잭션이 특정 데이터에 대한 락(Lock)을 요청할 때 발생할 수 있다. 만약 락 스케줄러가 특정 트랜잭션(예: 오래 걸리는 분석 쿼리)에게 계속 기회를 주지 않고 새로 도착하는 짧은 트랜잭션들만 먼저 처리한다면, 해당 분석 쿼리는 영원히 실행되지 못하는 기아 상태에 빠질 수 있다.

  • 네트워크 라우터: 서비스 품질(QoS)을 위해 비디오 스트리밍 같은 고우선순위 패킷을 일반 웹서핑 같은 저우선순위 패킷보다 먼저 처리하도록 설계된다. 만약 고우선순위 패킷이 홍수처럼 밀려오면, 저우선순위 패킷은 계속해서 폐기되거나 전송이 지연되어 기아 상태를 겪을 수 있다.

결론: 공정함에 대한 끊임없는 고찰

기아 상태는 단순히 하나의 알고리즘 오류가 아니다. 이는 한정된 자원을 어떻게 ‘공정하게’ 분배할 것인가에 대한 운영체제의 근본적인 철학을 담고 있는 문제다. 엄격한 우선순위는 반응성을 높일 수 있지만 공정성을 해칠 수 있고, 절대적인 공정함은 때로 시스템의 전체 처리량을 감소시킬 수 있다.

따라서 현대 운영체제는 에이징, 공정한 스케줄링 알고리즘, 우선순위 역전 방지 메커니즘 등 다양한 기법을 통해 효율성과 공정성 사이의 정교한 균형을 맞추려 노력한다. 개발자로서 이러한 기저의 원리를 이해하는 것은, 우리가 만드는 소프트웨어가 예측 가능하고 안정적으로 동작하도록 만드는 중요한 밑거름이 될 것이다.

그래프 뷰