교착 상태가 자원을 자유롭게 할당한 결과(자원 부족) 라면, 기아 상태는 작업이 결코 사용할 수 없는 자원을 계속 기다리는 결과(교착 상태)를 예방하려고 자원을 할당할 때 발생(기다림)하는 결과이다.
보편적인 기아 상태 정의
운영체제에서의 "기아 상태"는 프로세스 스케줄링에서 발생할 수 있는 현상을 말한다.
기아 상태는 CPU 스케줄링 알고리즘 중 하나인 "스케줄러 기아 현상"에 의해 발생한다. 스케줄러 기아 현상은 우선순위가 낮은 프로세스가 항상 우선순위가 높은 프로세스에게 밀려서 실행 기회를 얻지 못하는 상태를 의미한다.
일반적으로 운영체제는 다양한 프로세스를 관리하며, 우선순위를 부여하여 실행 순서를 결정한다. 그러나 스케줄러 기아 현상은 우선순위가 낮은 프로세스가 계속해서 우선순위가 높은 프로세스에게 밀려나 실행되지 못하는 상황이다. 이는 우선순위 역전이 발생하거나 우선순위가 부여되지 않은 경우에 자주 발생할 수 있다.
스케줄러 기아 현상을 방지하기 위해서는 우선순위 역전을 해결하고 우선순위가 적절히 조정되도록 스케줄링 알고리즘을 설계해야 한다. 운영체제는 다양한 스케줄링 알고리즘을 사용하여 프로세스들을 효율적으로 관리하고, 기아 상태를 최소화하는 노력을 한다.
이를 다익스트라가 제안한 "식사하는 철학자" 문제를 살펴보면서 기아 상태를 알아보자.
위 그림을 보면 테이블 둘레에는 포크(fork)가 5개 놓여 있다. 그리고 지역 풍슴에 따라 철학자들은 반드시 포크 2개로 식사한다. 그런데 포크가 5개라서 철학자 5명이 동시에 식사할 수 없고(포크가 10개 필요), 2명만 동시에 식사할 수 있다.
- 철학자는 한 번에 포크 한 개만 들 수 있다. 다른 철학자가 이미 왼쪽 포크을 쓰고 있다면( 경쟁 상태) 그가 내려놓을 때까지 대기한다.
- 왼쪽을 들었으면 오른쪽 포크를 든다(공유 자원). 들 수 없다면 대기한다.
- 두 포크을 모두 들었다면 일정 시간 동안 식사한다.
- 식사를 마쳤으면 오른쪽 포크을 내려 놓은 후 왼쪽 포크을 내려놓는다.
- 다시 배고프면 1번부터 진행한다.
모든 철학자가 배가 고파서(5명 모두 의자에 앉아 있을 때) 동시에 왼쪽 포크를 집고 오른쪽 포크를 집으려 한다면 교착 상태에 빠지게 되므로 모두 굷게 된다. 물론 이런 교착 상태는 여러 가지 해결책이 있을 것이다.
- 포크를 5개 더 산다.
- 포크 1개로만 식사한다.
- 철학자가 최대 4명만 동시에 않을 수 있게 제한한다. (1명은 포크 2개를 사용할 수 있다.
하지만 가장 간단한 해결책은 각 포크를 세마포어로 표시하는 것이다.
철학자는 포크에 해당하는 세마포어에 대한 P(wait) 연산을 수행하고 나서 포크를 집는다. 즉, 포크는 해당 세마포어에 대한 V(signal) 연산을 수행하여 내려놓는다.
따라서 공유 데이터는 다음과 같아.
semaphore fork[5];여기서 fork 의 모든 요소는 1로 초기화된다. 그리고 철학자 i 의 구조는 아래와 같다.
그런데 이 해결 방법은 두 이웃 철학자가 동시에 식사할 수는 없으나 교착 상태가 발생할 가능성 때문에 배재해야 한다.
철학자 5명 모두가 동시에 배가 고파서 왼쪽 포크를 집었다고 가정하자. fork 의 모든 요소는 0 이 된다. 그리고 각 철학자가 오른쪽 포크를 집을 때 영원히 기다리게 되므로 교착 상태가 발생한다.
이때는 몇 가지 해결책이 있다.
- 철학자 4명만 테이블에 동시에 앉도록 한다.
- 철학자가 양쪽 포크를 모두 사용할 수 있을 때 포크를 집을 수 있도록 허용(이것은 임계 영역 안에서 해야함) 한다.
- 비대칭 해결법을 사용한다. 즉, 홀수 번째 철학자는 왼쪽 포트를 집은 후 오른쪽 포크를 집게 하고, 짝수 번째 철학자는 오른쪽 포크를 집은 후 왼쪽 포크를 집게 한다.
마지막으로 식사하는 철학자 문제의 해결ㄹ책은 철학자 중 한명이라도 굶어 죽는 일이 없어야 한다는 사항을 만족시켜야 한다.
교착 상태 해결책은 기아 상태(starvationo) 의 가능성을 제거하지 못한다. 따라서 기아 상태 해결은 먼저 기다리는 작업을 발견하고 각 작업이 기다린 시간을 조사-추적해야 한다.
또 시스템은 기사 상태를 발견하면 즉시 새로운 작업의 시작을 대기하도록 조치해야 한다. 그러나 이 경우 빈번한 시스템 대기로 처리량이 감소할 수 있으므로 매우 신중한 접근이 필요하다.
참고
- 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미