교착상태란 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기를 기다리며 더 이상 작업을 진행할 수 없는 상태를 말합니다. 교착상태는 아사현상과 비슷하지만 잘못된 정책으로 인해 프로세스의 작업이 지연되는 아사현상과 달리 여러 프로세스가 작업하는 환경에서 자연스럽게 발생하는 문제입니다. 따라서 운영체제는 교착상태가 나타나면 강제로 해결해줘야 합니다.
교착 상태의 발생
교착상태는 시스템 자원, 공유 변수, 파일, 응용 프로그램 등을 사용할 때 발생할 수 있습니다. 교착 상태를 설명하는 대표적인 예시는 바로 식사하는 철학자 문제입니다.
철학자 4명이 둥그런 식탁에 앉아 식사를 합니다. 철학자는 두 개의 젓가락이 있어야 식사가 가능하죠. 철학자가 식사를 하는 알고리즘은 다음과 같습니다.
- 왼쪽 젓가락을 집는다.
- 오른쪽 젓가락을 집는다.
- 두 개의 젓가락으로 식사를 진행한다.
철학자들은 각각 식사를 위해 작업을 진행합니다. 왼쪽 젓가락을 들고 그 다음 오른쪽 젓가락을 들기 위해 옆을 바라봅니다. 그러나 이미 오른쪽에 있는 젓가락은 다른 철학자의 왼쪽에 들려있습니다. 결국 철학자들은 오른쪽 젓가락이 생기기만을 기다리다 아무도 밥을 먹지 못하고 굶어 죽게 됩니다.
철학자들의 어이없는 저녁식사는 교착 상태가 어떻게 발생하는지 뚜렷하게 보여줍니다. 여기서 알 수 있는 교착 상태 발생 조건은 다음과 같습니다.
- 철학자들은 서로 포크를 공유할 수 없다.
- 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다.
- 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다.
- 자원 할당 그래프가 원형이다.
교착 상태 필요조건
식사하는 철학자 문제에서 살펴본 교착 상태의 발생 조건을 일반화 시켜 보겠습니다. 교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족하는 상황에 발생합니다. 이 중 단 한가지라도 충족하지 않는다면 교착상태는 발생하지 않습니다.
- 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 이러한 자원은 임계규역으로 보호되어 다른 프로세스가 동시에 사용할 수 없다.
- 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없다.
- 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태를 의미한다. 즉, 다른 프로세스가 필요로 하는 자원을 점유한 채 다른 자원을 기다리는 상태를 말한다.
- 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원형을 이루어야 한다.
상호 배제와 비선점 조건은 임계구역과 관련이 있습니다. 임계구역을 보호하기 위해 lock을 사용하게 되면 상호 배제와 비선점 조건이 충족되어 교착 상태가 발생할 수 있게 됩니다. 이러한 상태에서 프로세스들이 점유와 대기, 원형 대기를 만족하게 되면 발생합니다.
교착 상태 해결 방법
교착 상태를 해결하는 방법은 예방, 회피, 검출이 있습니다.
- 교착 상태 예방 - 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화 하는 방식입니다. 네 가지 중 하나의 조건이라도 없어진다면 교착 상태가 발생하지 않습니다. 그러나 이 방법은 실효성이 적어 잘 사용되지 않습니다.
- 교착 상태 회피 - 자원 할당량을 조절하여 교착 상태를 해결하는 방식입니다. 자원을 할당한 뒤 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것입니다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없어 실효성이 적습니다.
- 교착 상태 검출과 회복 - 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하며 교착 상태가 발생하는지 감시하는 방법입니다. 교착 상태가 발견되면 회복 단계가 진행됩니다.
각각의 구체적인 내용과 방법을 살펴보겠습니다.
교착 상태 예방
교착 상태 예방은 말 그대로 교착 상태를 유발하는 네 가지 조건을 예방하는 방법입니다. 각 조건당 어떤 방식으로 예방하는지 살펴보겠습니다.
1. 상호 배제 예방
시스템 내에서 독점적으로 사용할 수 있는 모든 자원을 없애는 방법입니다. 시스템 내의 모든 자원이 공유 가능하다면 교착 상태가 발생하지 않습니다. 그러나 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용해서 보호해야 하는 자원은 반드시 존재합니다.
당장 프린터기와 같은 직관적인 장치부터 임계구역을 배우며 살펴봤던 문제들이 발생할 수 있습니다.
2. 비선점 예방
모든 자원을 비선점으로 만들어 빼앗을 수 있도록 만드는 방법입니다. 하지만 임계구역을 위한 잠금을 사용하면 사실상 빼앗는 것이 불가능하고, 어떤 기준으로 빼앗을지, 빼앗아서 얼마나 사용할 수 있는지 등의 기준을 정할 수 없습니다. 우선순위의 지정 방법에 따라 아사 현상을 야기할 가능성도 있습니다.
3. 점유와 대기 예방
프로세스가 자원을 점유하고 있는 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 이를 위해 프로세스 시작 초기에 사용할 모든 자원을 한꺼번에 점유하고 만약 하나라도 점유하지 못할 경우 모든 자원을 반납해야 합니다.
하지만 특정 프로세스가 어떤 자원을 사용하는지 모두 아는것은 불가능합니다. 프로세스 실행 도중에 자원이 필요해지는 경우가 있기 때문입니다. 또한 자원의 활용성이 떨어지게 되고, 많은 자원을 사용하는 프로세스는 적은 자원을 사용하는 프로세스보다 불리합니다. 이러한 방법을 실제로 구현하면 예전에 사용하던 일괄 작업 방식으로 동작하게 되어 많은 불편함을 야기할 수 있습니다.
4. 원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 막는 방법입니다. 시스템의 자원마다 특정 번호를 지정하고 번호가 작은 번호를 할당 받은 상태에서만 큰 번호의 자원을 사용할 수 있고, 그 반대의 경우는 불가능 하도록 만듭니다. 즉, 큰 번호의 자원을 점유한 상황에선 작은 번호의 자원을 기다릴 수 없도록 합니다.
이렇게 하면 자원을 할당받는 방향성이 생겨 원형 대기가 일어날 일이 없게 되어 교착 상태를 방지할 수 있습니다. 그러나 프로세스 작업 진행에 유연성이 떨어지고 자원 번호를 붙이는 규칙을 지정하는데 어려움이 큽니다.
교착 상태의 4가지 조건을 예방하는 방식들을 살펴보았는데요. 이처럼 교착 상태를 예방 한다는 것은 매우 어려우며 프로세스 작업 방식을 제한하고 자원을 낭비하는 등 사실상 사용할 수 없습니다. 따라서 우리는 다른 방법론을 찾아야 합니다.
교착 상태 회피
교착 상태 회피는 프로세스에 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법입니다. 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 바랭하는 범위에 있으면 프로세스를 대기시킵니다.
교착 상태 회피는 자원의 총수와 현재 할당된 자원 수를 기준으로 시스템을 안정 상태, 불안정 상태로 나누어 안정 상태를 유지하도록 자원을 할당합니다.
은행원 알고리즘
교착 상태 회피의 대표적인 방법으로 은행원 알고리즘이 있습니다. 은행원 알고리즘에서는 각 프로세스가 자신이 사용할 자원의 최대 수를 운영체제에 통지합니다. 또한 각 프로세스에 실제로 할당된 자원의 수는 할당 자원으로 표시합니다. 그리고 자신이 선언한 최대 자원에서 현재 할당된 자원 수를 빼면 기대 자원이 됩니다. 그리고 전체 자원에서 각 프로세스에 할당되고 남은 자원의 수를 가용 자원 이라고 합니다.
이러한 조건하에 자원을 다음과 같이 할당합니다.
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다.
- 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.
쉽게 얘기하면 음식점에서 a매뉴는 10인분, b매뉴는 13인분, c매뉴는 25인분이 있을 때 손님의 예약을 10명 이상은 받지 않는 방식과 유사합니다.
예약을 받은 손님이 모두 a매뉴만을 시킨다고 해도 문제가 발생하지 않기 때문이죠. 그러나 12명의 예약을 받고 12명 모두 a매뉴를 주문한다면 문제가 발생할 수 있습니다.
그러나 포스팅에 아무런 그림도 없고, 생각보다 불친절한 설명에서도 예측 가능하듯 교착 상태 회피 역시 문제점이 많아 잘 사용되지 않습니다. 교착 상태 회피는 다음과 같은 문제점이 존재합니다.
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다. 이는 위에서 살펴본 것 처럼 알 수 없는 경우가 많다.
- 시스템의 전체 자원 수가 고정적이어야 한다. 그러나 시스탬 내의 자원의 수는 유동적으로 변하는 경우가 많다.
- 자원이 낭비된다. 손님 예약의 예에서 살펴보듯 최대 48인분의 재료가 있음에도 예약은 최대 10명까지만 받을 수 있다.
이러한 이유로 교착 상태 회피 역시 쓰이지 않습니다.
교착 상태 검출
지금까지 잘 사용하지 않는 교착 상태 예방/회피를 살펴보았습니다. 이들은 문제를 실제로 해결하기엔 무리가 있었죠.
현실적으로는 교착 상태 검출을 통해 프로세스의 작업을 관찰하며 교착 상태 여부를 계속 주시하며 회복하는 방식이 필요합니다.
교착 상태 검출에는 크게 타임아웃을 이요하는 방법과 자원 할당 그래프를 이용하는 방법이 있습니다.
타임아웃을 이용한 교착 상태 검출
타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태로 간주하여 처리하는 방법입니다. 타임아웃 개념은 다양한 분야에서 사용되며 실제 구현도 어렵지 않다는 장점이 있습니다. 그러나 타임아웃방식에는 다음과 같은 문제점들이 있습니다.
- 엉뚱한 프로세스가 단지 대기 시간이 길다는 이유로 교착 상태로 간주되어 강제 종료될 수 있다.
- 분산 데이터베이스 등 네트워크로 연결된 시스템에는 적용할 수 없다.
하지만 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호하는 방법입니다. 이 다음에 살펴볼 자원 할당 그래프를 이용하는 방법도 있지만 이는 구현이 너무 어렵기 때문입니다. 자주 발생하지도 않을 교착 상태를 위해 자원 할당 그래프를 유지하며 모든 자원을 감시하는 것은 어렵운 일이죠.
그래서 타임아웃을 이용하는 방법을 '가벼운 교착 상태 검출', 자원 할당 그래프를 이용하는 방법을 '무거운 교착 상태 검출'이라고 부릅니다. 윈도우에서 '프로그램 응답이 없어 종료합니다'라는 메시지는 대표적인 타임아웃 방법입니다. (실제로 종료한다고 하다가 복구가 되는 경험도 많이 있을 거라고 생각합니다. 저도 그러니까요..)
타임아웃 방식은 잠금을 얻어 작업을 하는 중 종료되면 데이터의 일관성이 깨지는 문제가 발생할 수 있는데 데이터베이스와 같은 시스템에서는 이를 체크포인트와 롤백을 사용해 해결합니다.
요즘 개발자라면 익숙한 깃 역시 이러한 방식으로 관리되고 있습니다.
자원 할당 그래프를 이용한 교착 상태 검출
자원 할당 그래프는 모든 자원과 프로세스 할당 상태를 나타내어 확인하는 방법입니다.
단일 자원의 경우 자원 할당 그래프에 사이클이 있으면 교착 상태이며, 다중 자원의 경우 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워나가며 교착 상태 발생 여부를 판단합니다.
이러한 방식은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 장점이 있습니다. 그러나 자원 할당 그래프를 유지,갱신하고 사이클을 검사하는 오버헤드는 단점이라고 볼 수 있습니다.
교착 상태 회복
교착 상태가 검출되면 이를 회복하는 교착 상태 회복 단계가 필요합니다. 회복 단계에선 교착 상태가 발생한 프로세스를 종료하는데 종료하는 방법은 크게 2가지가 있습니다.
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료 - 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 있음. 따라서 종료 후 다시 실행할 때 순차적으로 실행해야 하며 이 때 어떤 순서로 실행할지 정하는 기준이 필요함.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 - 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하며 나머지의 상태를 파악하는 방법입니다. 우선순위가 낮고, 작업 시간이 짧으며 자원을 많이 사용하는 프로세스부터 종료합니다.
출처)
- 쉽게 배우는 운영체제, 조성호, 한빛아카데미
