오늘은 교착 상태에 대해서 배운다.
동시에 실행되는 여러 프로세스가 각자 필요한 자원을 할당 받아 실행되는데 그 과정에서 아무것도 못하고 정지해버리는 상태를 교착상태라고 한다.
왜 발생하는지, 어떻게 해결하는지 알아보자
식사하는 철학자 문제
다섯명의 철학자 앞에 음식이 놓여져 있다.
이 음식은 2개의 포크로만 먹을 수 있다.
순서는 아래와 같다.
1. 생각하다가 사용 가능하다면 왼쪽 포크를 집는다.
2. 생각하다가 사용 가능하다면 오른쪽 포크를 집는다.
3. 왼쪽 오르쫀 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번부터 반복
문제는 모든 철학자가 동시에 식사를 진행한다면 1번까지 진행하고 2번을 진행하지 못한다.
오른쪽 포크는 이미 다른 철학자가 점유하고 있기 때문이다.
즉 한두명이 식사를 하는 것은 문제가 되지 않지만 모두가 식사를 한다면 문제가 발생한다.
식사하는 철학자 문제는 대표적인 교착 상태의 가상 시나리오이다.
즉 교착상태는
서로가 점유하고 있는 자원에 대해서 탐하기 때문에
이러지도 저러지도 못하는 것이다.
자원 할당 그래프
자원 할당 그래프는
교착 상태를 단순하게 표현할 수 있다.
자원 할당 그래프에서
사각형 = 자원
원 = 프로세스
사각형 내 점 = 사용할 수 있는 자원의 개수
교착상태는 자원 할당 그래프가 원의 형태를 가진다.
교착 상태 발생 조건
4가지를 모두 만족해야 교착 상태가 발생한다.
상호 배제
하나의 자원은 하나의 프로세스만 할당받을 수 있다.
점유와 대기
자원을 할당받을 상태에서 다른 자원을 할당받기 기다리는 상태
비선점
사용하고 있는 자원에 대해서 뺏지 못하고 그 자원을 다 사용할 때까지 기다렸다가 할당받아야 한다.
원형 대기
자원 할당 그래프가 원형이면 교착 상태가 발생할 수 있다.
원이라고 해서 무조건 교착상태인것은 아니다.
단, 교착상태는 무조건 자원 할당 그래프가 원형이다.
교착 상태 해결 방법
크게 3가지
- 앞서 배운 교착 상태 발생 조건 중 하나라도 일어나지 않도록 예방
- 교착 상태가 발생하지 않을 정도고 자원을 조금씩 할당하는 회피
- 자원을 제약없이 할당하다가 교착상태가 검출되면 교착상태 회복
교착 상태 예방
상호 배제를 없애기
➡️ 현실적으로 불가능
점유과 대기 없애기
➡️ 운영체제는 특정 프로세에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분
- 문제점
- 자원 활용률이 낮아진다.
당장 자원이 필요해도 기다려야 하고 사용되지 않으면서 오랫동안 할당되는 자원을 양산 - 많은 자원을 사용하는 프로세스가 불리하다.
적은 자원을 쓰는 프레스는 쉽게 자원을 할당 받을 수 있으나 많은 자원을 사용하는 프로세스는 그 타이밍이 잘 오지 않아 기아 현상이 발생될 수 있다.
- 자원 활용률이 낮아진다.
비선점 조건 없애기
➡️ 선점하여 사용할 수 있는 일부 자원에 대해서만 효과적
예를 들어 프린터는 선점할 수 없다. 무조건 비선점 조건만 가능
원형 대기 없애기
➡️ 자원에 번호를 부여해서 오름차순으로 자원을 할당 하지만 현실적으로 불가능하다. 모든 자원에 번호를 부여할 수 없고 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어진다.
결론
교착 상태를 만드는 4가지 조건 중 하나를 제거하여 교착 상태가 발생하지 않도록 예방하는 것은 교착상태가 발생하지 않는 것을 보장하지 못한다.
교착 상태 회피
교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식
프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세스들이 한번에 많은 자원을 요구한다면, 본인이 가져야 하는 최대 자원을 요구한다면 교착 상태가 발생할 위험이 있다.
용어 정리
- 안정 상태
=교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
= 안전 순서열대로 프로세스들에 자원을 배분하여 교착상태가 발생하지 않는 상태 - 불안정 상태
= 교착 상태가 발생할 수도 있는 상태
= 안전 순서열이 없는 상태 - 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다.
정리
교착 상태 회피는 조금씩 자원을 할당하되, 안전 순서열에 의해서 자원을 할당하여 안정 상태를 유지하도록 자원을 할당하는 방식이다.
교착 상태 검출 후 회복
➡️ 교착 상태 발생을 인정하고 교착 상태 발생 후 사후에 조치하는 방식
선점을 통한 회복
교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식
프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스를 모두 강제 종료
- 단, 한 방에 교착상태를 해결할 수 있지만 그만큼 많은 프로세들이 작업 내역을 잃게 된다.
- 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
- 작업 내역을 잃은 프로세는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정이 오버헤드를 야기한다.
+) 교착상태 아예 무시하기
타조알고리즘 방식도 있다.
타조가 위기에 놓이면 머리를 땅에 묻고 모르는 체하는 모습에서 따온 이름
