[OS] 교착 상태 (deadlock)

시스템에는 유한 개의 자원이 존재하고 프로세스는 이 자원을 사용한다.

 

자원을 사용하기 위해 프로세스는 자원을 요청하고 사용하고 해제한다.

 

만약 사용하려는 자원이 이미 다른 프로세스에 의해 사용 중이라면 대기 상태에 들어간다.

 

그런데 어떤 집합의 모든 프로세스가 자원을 할당받기를 기다리고 있고 각 프로세스가 이 집합의 어떤 프로세스가 소유 중인 자원을 할당받기를 기다리고 있다면 이를 교착 상태(deadlock)에 있다고 한다.

 

<예시>

 

https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C

 

교착 상태는 다음과 같은 4가지 조건을 만족해야 교착 상태라고 한다.

 

1. 상호배제 : 한 번에 하나의 프로세스만 자원을 사용할 수 있다.
2. 점유와 대기 : 프로세스는 최소한 하나의 자원을 점유하고 있고 다른 프로세스가 점유 중인 자원을 대기 중이다.
3. 비선점 : 점유된 자원은 점유 중인 프로세스가 자원의 사용을 끝내고 해제 할 때까지는 해당 자원을 얻을 수 없다.
4. 순환 대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 점유 중이다.

자원 할당 그래프

프로세스를 P 자원을 R이라고 한다면 P -> R은 프로세스가 자원 R을 요청한 것이고 R -> P는 자원 R을 프로세스 P가 점유 중이라는 뜻이다.

 

다음과 같은 자원 할당 그래프는 교착 상태(deadlock)이다.

 

만약 자원 할당 그래프가 사이클을 이루지 않는다면 교착 상태가 아니다.

 

만약 자원 할당 그래프가 사이클을 이룬다면 교착 상태일 가능성이 있다.

 

사이클을 이룰 때 왜 교착 상태일 가능성이 있다는 말은 사이클이어도 교착 상태가 아닐 수 있다는 것이다.

 

위 그림과 같이 각 자원이 할당할 수 있는 개수가 하나라면 교착상태이지만 자원이 할당할 수 있는 개수가 여러 개 일수도 있기 때문이다.

 

다음 그림은 사이클을 이루고 있지만 교착 상태는 아니다.

교착 상태 해결 방법

교착 상태를 해결하는 방법은 크게 3가지가 존재한다.

 

1. 교착 상태 예방 : 교착 상태 4가지 조건 중 한 가지가 발생하지 않도록 한다. 
2. 교착 상태 회피 : 운영 체제가 프로세스 자원 요청을 관리한다. 자원 요청을 거절하는 방식을 사용한다.
3. 교착 상태 탐지 : 교착 상태가 발생하면 시스템을 복구하는 방식으로 해결한다.

교착 상태 예방

1. 상호배제 x

여러 프로세스가 자원을 공유할 수 있도록 한다. 하지만 공유할 수 없는 자원도 있기 때문에 이 조건을 통해 교착 상태를 예방하는 것은 어렵다.

 

2. 점유와 대기  x

프로세스 실행 전에 필요 자원을 미리 점유하는 방법과 자원을 점유하지 않은 프로세스만 자원을 요청하도록 하는 방법이 있다.

 

그런데 전자의 경우 할당 받은 자원을 오래 동안 사용하지 않는다면 효율이 떨어지고 후자의 경우 여러 자원이 필요한 프로세스가 존재할 수 있다.

3. 비선점 x

한 프로세스가 자원을 점유 중인데 바로 점유할 수 없는 자원을 또 요청한다면 이미 가지고 있던 자원을 모두 해제한다.

 

아니면 한 프로세스가 자원 R을 점유 중인 상태에서 대기를 하고 있다고 하자. 이 상황에서 다른 프로세스가 자원 R을 요청하면 대기 중인 프로세스로부터 자원 R을 뺏어 오는 방법도 있다.

 

4. 순환 대기 x

 자원에 번호를 부여하고 낮은 번호부터 할당한다.

 

프로세스는 자신이 점유 중인 자원보다 번호가 큰 자원만 요청할 수 있도록 하는 방법이 있고 요청하려는 번호보다 작은 자원을 점유 중이라면 전부 해제하는 방법이 있다.

 

교착 상태 회피

운영 체제가 프로세스가 필요한 자원의 정보를 미리 알고 있어야 한다.

 

이러한 정보들을 바탕으로 자원 요청이 들어오면 교착 상태가 발생하지 않도록 조절해준다.

 

크게 은행가 알고리즘과 자원 할당 그래프 알고리즘이 있다.

 

1. 은행가 알고리즘

 

프로세스가 3개가 있고 현재 시스템에 자원이 9개가 존재한다고 하자.

 

그 중 P1이 4, P2가 2, P3가 1만큼 자원을 점유 중이라고 하자.

	최대 자원	현재 점유 자원	필요 자원
P1	9	4	5
P2	4	2	2
P3	4	1	3

총 7개의 자원이 점유 중이므로 현재 할당 가능한 자원의 양은 2개이다.

 

위 프로세스 중 P2만이 필요한 자원이 2개이기 때문에 할당한다.

 

P2가 2개의 자원을 할당 받아서 작업을 마치고 해제하면 4개의 자원이 돌아오게 된다.

 

P3는 3개의 자원만 있으면 되므로 P3에게 자원을 할당하면 P3도 작업을 마치고 4개의 자원을 반납한다.

 

이제 자원이 5개가 생기고 P1에게도 자원을 할당할 수 있게 되었다.

 

P2 -> P3 -> P1 순서로 자원을 할당하면 교착 상태가 발생하지 않도록 조절할 수 있는 것이다.

 

이러한 P2 -> P3 -> P1을 안전한 순서라고 한다.

 

2. 자원 할당 그래프 알고리즘

이 알고리즘은 각 자원마다 하나의 인스턴스가 존재할 때 사용할 수 있는 알고리즘이다.

 

기존 자원 할당 그래프에서 요청 가능선을 추가한다.

 

이 요청 가능선이란 미래에 프로세스가 요청할 가능성이 있다는 것을 의미하고 점선으로 표현한다.

 

진짜 요청한다면 요청 가능선을 할당선으로 바꾸고 사이클 존재 여부를 검사한 후 없을 때만 요청을 허용한다.

 

교착 상태 탐지 

교착 상태 탐지는 교착 상태를 허용하고 교착 상태가 발생했을 때 시스템을 복구하는 방식이다.

 

자원이 하나의 인스턴스만 가지고 있는지 아닌지에 따라 방법이 달라진다.

 

1. 자원별 하나의 인스턴스 존재

자원 할당 그래프를 대기 그래프로 변경한다.

 

대기 그래프는 자원을 그리지 않고 프로세스만 그린다.

 

P1 -> P2의 의미는 P1이 P2가 점유 중인 자원을 대기한다는 의미이다.

 

자원 할당 그래프에 요청선인 P1 -> R과 할당선인 R -> P2가 있다면 대기 그래프에 P1 -> P2가 추가되는 것이다.

 

<대기 그래프 예시>

주기적으로 대기 그래프의 사이클 여부를 조사하여 교착 상태를 발견한다.

 

2. 자원별 여러 인스턴스 존재

은행가 알고리즘과 비슷하게 진행된다.

 

중간에 실행할 수 있는 프로세스가 없다면 교착 상태인 것으로 판단한다.