Dead Lock (교착 상태)

이번 시간에는 프로세스 동기화의 마지막 Dead Lock 을 알아보자. 

 

Dead Lock 은 교착 상태라고도 하며 가장 쉬운 예시로 시골에 가면 흔히 겪는 좁은 1차선 도로로 차를 운전하다가 반대편에서 차가 와서 서로 오도가도 못하는 상황을 생각하면 쉽다. 

그리고 누구는 양보해서 긴 시간을 들여 빠져나가야하고 이는 프로세스도 똑같다.

 

운영체제에서 프로세스 간 교착 상태는 자원을 기다리다가 서로 Lock 된 상태로 대기하는 것을 의미하며 발생 조건은 다음과 같다. 

 

1. 상호 배제

> 프로세스가 작업 중일 때 다른 프로세스는 접근할 수 없다. 

 

2. 자원 비선점

> 자원을 할당 받은 프로세스의 자원을 다른 프로세스가 할당 받을 수 없다. 

 

3. Hold & Wait

> 자원을 할당 받으면 작업을 종료할 때 까지 대기한다.

 

4. 순환대기

> 서로 돌아가며 순서를 기다리다. 

 

단 두 줄로 교착상태 만들기

 

가장 간단한 예시로 A 와 B 의 뮤텍스를 위와 같이 설계한다면 프로세스 A 와 B 는 각자 자원을 1개 씩만 잡고 영원히 작업을 수행하지 못한채로 남아있게 될 것이다. 따라서 이번 시간에는 교착 상태를 해결하는 방법과 실제로 시스템이 교착 상태를 해결하는 정책에 대해서 알아보려고 한다. 

 

교착 상태의 해결 방법으로는 크게 4가지로 분류 된다. 

 

1. 교착 상태 방지

2. 교착 상태 회피

3. 교착 상태 감지 와 회복

4. 교착 상태 무시

 

먼저 교착 상태 방지는 위에 언급한 4가지 교착 상태의 조건을 깨버려 교착 상태가 발생하지 못하게 방지하는 것이다.

 

 

하지만 조건이 불만족할 경우 양날의 검이 되어 다른 더 큰 문제점을 야기 할 수 있기 때문에 정책을 적용할 환경이 조건을 불만족 해도 되는 상황일 경우에만 사용하는 것이 효율적이다. 

 

다음으로 교착 상태 회피는 교착 상태 조건을 만족하는 환경에서 특정 알고리즘을 도입해 교착 상태가 발생하지 않게 회피하는 것이다. 

 

교착 상태를 회피하는 방법은 여러 알고리즘이 있지만 기본적으로는 운영체제가 프로세스의 최대 필요 자원을 알고 그것을 미리 할당 해주는 방식으로 진행된다. 가장 대표적인 알고리즘으로는 은행원 알고리즘이 있으며 알기 쉽게 내 방식대로 풀어 써보려한다. 

 

고전 놀이 별들의 전쟁

 

위 사진은 병사를 생산하기 위한 건물의 상태 창이며 사용자는 가진 자원을 사용해 유닛을 생산할 수 있으며 유닛을 생산하는데는 어느 정도 시간이 소요된다. 

 

 

위와 같은 상황에 만약 병사를 생산하는 요청이 a1, b1, c1, b2, c2 로 들어왔다고 가정해보자.

 

그렇면 a1 와 b1 를 생산하는데 각각 100, 200 씩 자원을 할당해주고 나서 c1 의 생산 요청이 왔을 때 남은 200 의 자원을 할당해준다고 생각해보자.

 

그 이후 병사 a1 가 생산 되어 다시 자원 100 이 반납된 상태에서 다시 병사 b2 생산 요청이 들어오고 마찬가지로 100 을 할당해준다.

 

마지막으로 생산이 완료된 병사 b1 의 자원을 반납받고 다시 c2 요청이 들어와 c2 에게 200을 할당 해버리면 남는 자원은 0 이 된다.

 

그렇게 되면 다음과 같은 상태로 3개의 병사 생산 요청은 영원히 대기하게 된다. 

 

c1 : 200/400

b2 : 100/200

c2 : 200/400

 

하지만 실제 위 게임의 경우에는 생산 요청을 할 당시에 자원이 충분하지 않으면 거절되며 이와 동일한 방식으로 프로세스가 필요한 최대 자원량을 미리 알고 있는 상태에서 작업 요청이 들어온 경우 만약 현재 가용 가능한 자원이 충분하지 않으면 요청을 거부하여 약간은 지연이 생기더라도 교착 상태를 회피하는 것이 바로 은행원 알고리즘이며 이는 대표적인 교착 상태 회피 방법으로 제시된다. 

 

이어서 교착 상태 감지와 회복은 프로세스 간 교착 상태를 파악해 강제로 교착 상태를 해결하는 방식이다. 

먼저 교착상태의 감지는 다음과 같은 자원 할당 그래프(좌측) 및 그 연장선인 할당 그래프(우측)를 활용한다. 

 

 

P 는 프로세스 R 은 자원을 나타내며 R 내부의 점 하나는 자원을 나타낸다. (점이 하나면 뮤텍스고 둘 이상이면 세마포어) 이때 위와 같은 순환을 하게 되면 교착 상태가 반드시 발생하는 것으로 판단하지만 만약 자원이 하나 이상이라면 자원이 남는 경우도 있을 수 있다. 그럴 경우에는 교착 상태가 발생할 가능성이 있다고 판단한다.

 

이때 교착 상태 감지는 너비 우선 탐색으로 순환이 있는지 확인하는 것이며 이를 통해 순환이 있다고 판단되면 다음과 같은 방법으로 강제로 교착 상태를 해결한다. 

 

1. 연관된 프로세스 전체를 죽인다 / 순차적으로 하나씩 죽인다

2. 연관된 프로세스의 자원을 전체 회수한다 / 효율성을 따지면 하나씩 회수한다

 

다소 효율적이라고 보일 수 있는 이 방법에도 역시 탐색 간 프로세스 갯수 n 개에 O(n2) 이라는 막대한 탐색 시간이 걸리며 나아가 프로세스를 죽이고 자원을 회수하는 과정에서도 오버헤드 시간이 발생하며 사용자 모르게 강제로 프로그램이 종료될 수 있는 문제점이 발생한다. (컴퓨터의 입장에서는 OS 시스템 프로세스가 아니면 나머지 응용 프로그램의 프로세스에는 우선순위를 크게 따지지 않는다)

 

따라서 대부분의 OS 는 그냥 마지막 방법인 교착 상태 방지를 사용한다. 

 

교착 상태 방치는 교착 상태 발생 시 사용자에게 해당 상황을 인지시키고 사용자가 직접 연관된 프로세스를 종료하게 한다. 언뜻 비효율적일 수 있는 이 방법을 윈도우나 IOS 등 대부분의 OS 가 채택하고 있으며 개인적으로 생각해도 문제가 생긴 프로세스를 OS 가 나도 모르게 강제종료 시키기 보다는 그냥 내가 스스로 선택해서 종료 시키는 것이 최선이라고 생각한다. (거기에 대부분 CPU 스케쥴링은 선점형 RR 을 사용하니 발생할 일도 거의 없다)