데드락 문제 및 그 해법

 데드락(DeadLock)은 전혀 풀릴 가능성이 없는 잠김 상태로서 컴퓨터에서는 이 집합의 모든 프로세스가 대기상태이고 이들이 기다리는 이벤트는 이 집합 속의 다른 프로세스에 의해서 발생해야 하는 경우로 정의된다.다익스트라는 이러한 현상을 식사중인 철학자 문제로 비유해서 설명했다.

식사중인 철학자(Dining philosopher)

  5명의 철학자들이 원탁에 둘러 앉아서 배가 고프면 스파게티를 먹고 배가 부르면 생각에 잠기는 작업을 반복할때 스파게티를 먹기 위해서는 젓가락 두 개가 필요한데.젓가락은 철학자 사이마다 한 개씩 놓여있다.따라서 스파게티를 먹기 위해서는 다른 철학자의 젓가락을 필수적으로 공유해야한다.

식사중인 철학자 문제

이때 데드락은 흔히 일어나지 않고 다음과 같은 상황에서 일어난다.어느날 모든 철학자가 동시에 스파게티를 먹기 위해서 각자 우선 자신의 왼쪽(오른쪽)에 있는 젓가락 1개를 소유하는 상황이 발생하면 한 젓가락을 확보한 상태에서 아무도 또 하나의 젓가락을 확보하지 못해서 결국 아무도 식사를 계속할 수 없는 경우가 발생한다.이때 젓가락을 자원,철학자를 프로세스라 생각하면 된다.

 

평상시에는 사거리 통행에서도 관측이 가능하다.

 

사거리 통행 문제의 모델링

 p1에서 좌회전을 하기 위해서는 R1,R2,R3를 사용해야하고 만일 도중에 한 군데라도 다른 차로에서 사용하게 되면 통행을 할 수 없다.물론 현대에서는 신호등을 사용하기에 데드락은 발생하지 않지만 신호등이 없을 경우 그 어느차도 더 이상 앞으로 못가는 상황이 발생 할 수 있다.

그렇다면 사거리의 데드락 해결 방안들을 생각해보면 다음과 같다.

1. 사거리를 완전한 입체교차로로 변경 -> 자원 낭비가 매우 심함
2. 모든 운전자가 준수하는 사거리 통과 규칙 제정 -> 신호등 설치 등등
3. 모든 운전자는 데드락이 발생할 가능성이 없을 때만 진입 -> 비보호 시스템(운전자가 잘 판단해야함)
4. 전방이 비어있으면 일단 진입 -> 데드락 상황이 발생하면 해결 조치
5. 아무런 대책없이 방치 -> 노답

데드락 문제의 모델링

데드락 정의(프로세스 집합 S)

 집합 S의 모든 프로세스들이 waiting 상태이고 이들이 기다리는 event는 S의 다른 프로세스들에 의해 발생해야하는 상태.

시스템내의 모든 프로세스가 대상이 아니라 일부 프로세스에 국한됨.

 

따라서 이러한 프로세스간의 자원 할당이나 요구를 시각적으로 나타낼 수 있다.자원할당 그래프(RAG: Resource Allocation Graph)로 표현한다.이때 각 자원들은 상호 배제 관계이다.프로세스는 원으로 표시하고 자원들은 사각형으로 표시한다.그래프간의 간선은 요구 에지(Request Edge)들과 할당 에지(Assignment edge)들로 구성된다.

자원할당 그래프

이 그래프로 데드락을 확인할 수 있다.단순히 사이클이 발생되고 사이클에 포함된 자원들은 한 개씩만 존재하면 데드락이 발생한 상태고 만일 자원당 여러 개가 존재할 경우에는 사이클이 존재해도 데드락이 아닐 수 있다.이는 언젠가는 언락이 될 가능성이 존재하기 때문이다.

사이클의 존재와 데드락

데드락의 발생 조건은 다음과 같다.

1. 상호 배재(Mutual exclusion) : 특정 자원은 특정 시점에 오직 한 개의 프로세스만 사용할 수 있다.
2. 선점 불가(No preemption) : 자원은 선점하여 사용할 수 없고 먼저 확포한 프로세스가 스스로 해제해야 다른 프로세스가 사용가능하다.
3. 보유 및 대기(Hold and wait) : 최소한 하나의 자원을 확보하고 있으면서 다른 프로세스들이 확보한 자원을 추가로 확보하기 위해 기다리는 프로세스가 존재한다.
4. 원형 대기(Circular wait) : p1이 p2가 확보한 자원을 기다리고,p2가 p3이 확보한 자원을 기다리고 p3는 p1이 확보한 자원을 기다리는 형태의 원형 대기 상태가 존재한다.

따라서 다음의 조건중 하나만 불만족시켜도 데드락이 발생하지 않는다.

데드락 방지 기법(Deadlock prevention)

 상호 배제 및 선점 불가 조건은 자원의 특성에 의해 결정되기에 이 조건을 건들 수 는 없다.따라서 보유 및 대기,원형 대기를 피하는 알고리즘을 사용한다.

1. 기확보 자원의 반납 : 보유 및 대기 조건을 피하는 것으로 이미 자원을 확보한 상태에서 다른 자원을 확보하려고 했을 때 이가 불가능하면 확보한 자원도 반납하는 것이다.하지만 자원의 특성상 이미 확보하여 사용중이던 자원을 완료하기 전에 해제하는 것은 불가능하거나 매우 어렵다.
2. 동시에 사용할 자원들은 일괄 확보 : 보유 및 대기 조건을 피하는 것으로 여러 뮤텍스를 한꺼번에 확보하는 기능이 필요하다.하지만 이는 당장 사용하지 않을 자원들까지도 미리 확보하기에 자원 운용에서 효율성이 떨어지고 여러 개의 자원을 사용하는 프로세스는 실행할 기회가 매우 작아져서 기아 문제가 발생할 수 있다.
3. 동시 사용 자원들의 확보순서 고정 : 원형 대기 조건을 피하는 것으로 자원들에 대해 요청 순서를 사이클이 없도록 고정 해놓고,프로세스들은 항상 이 순서에 따라 자원들을 요청하도록 한다.

3의 경우 자원의 사용순서를 고정하면 할당순서가 한 방향으로 생기기에 자원할당 그래프의 사이클이 생길 수 없다.

하지만 우선순위가 높은 자원들에 대해 많은 할당 요청이 생길 수 밖에 없다.따라서 병목현상이 생길 수 있다.

데드락 회피 기법(Deadlock avoidance)

 자원 할당을 요청한 시점에 할당 여부를 결정한다.따라서 데드락 방지 기법에 비해서 자원 효율성이 높다.원리는 자원을 할당할 때 해당 자원을 확보하면 데드락 발생 가능성이 생기는 경우면 요청한 프로세스를 대기 상태로 전환시키고 아니면 요청대로 할당한다.데드락 회피 기법은 자원 할당을 요청받을 때마다 데드락 가능성을 검사하는 오버헤드가 발생한다.

 

 데드락 가능성을 조사하는 방법에는 여러 알고리즘이 존재한다.우선 각 자원 당 한 개씩만 존재하는 경우를 위한 방안으로는 자원 할당 그래프에서 미리 통보된 자원들에 대해 클레임 에지(Claim edge)를 추가하는 것으로 자원 할당을 요청한 시점에 클레임 에지를 요구 에지(Request edge)로 변경한다.자원을 할당하면 요구 에지를 할당 에지(Assignment edge)로 변경한다.이런식으로 변경하고 사이클이 존재하는지를 확인한다.

 

은행원 알고리즘(Banker's Algorithm)

 만일 동일한 자원이 여러 개 있을 경우에도 적용할 수 있도록 만들어진 알고리즘으로 이 알고리즘은 단순한 자원 할당 그래프의 사이클 유무가 아니라 여러개의 시나리오를 생각해봐야한다.이 알고리즘은 실제 은행에서의 사례에서 유래됬다.

우선 은행이 100원의 잔고를 보유하고 있을때 A,B,C가 각각 30,40,50원을 대출받기 위해 대기한다 가정하자.A,B,C한테 골고루 돈을 대출해주면 아무도 돈을 값지 못하고 상환도 못하기에 적어도 은행은 한명은 상환 할 수 있는 상태여야 한다.따라서 A한테 먼저 대출해주고 A가 상환을 완료하면 다시 B한테 대출하는식으로 해결하면된다.이런식으로 데드락이 발생하지 않는경우를 안전상태라 하고 만일 너무 많이 대출해줘서 잔고가 부족해지거나 매우 적어지면 불안상태라 하며 이를 통해 데드락 발생 가능성을 판단한다.

데드락 탐지 및 복구(Deadlock detection and recovery)

 이 해법은 데드락을 회피하거나 방지하지 않고 데드락이 발생했다면 이를 탐지하고 복구하는 방법이다.이는 방지,회피 기법은 오버헤드가 발생하고 자원 사용의 효율성이 떨어지고 데드락은 자주 발생하지 않고 낮은 확률로 발생하기에 가능한 해법이다.데드락 탐지 및 복구는 우선 자원의 할당 요청시 이미 할당되지 않았으면 무조건 할당한다.이후 데드락의 발생 여부는 적절한 시점마다 검사한다.만일 검사중 데드락 발생이 탐지되면 적절히 복구한다.이 방식은 자원의 활용율을 극대화 하고 데드락 회피 기법에 비해 오버헤드가 감소한다.

 

 그렇다면 데드락 탐지를 적절한 시점마다 검사하는데 이를 구체적으로 검사 시점을 따져보면 다음과 같다.

1. 요청 자원이 이미 사용 중일 때마다 검사 : 오버헤드가 큼
2. 특정 주기마다 한번씩 : 데드락 발생후 시간이 지날수록 연관된 프로세스가 증가함.
3. CPU 활용률이 낮은 시점 : 2번의 이유와 비슷하다.

데드락 탐지를 하는 검사 주체는 커널이 직접하거나 커널 모드에서 실행되는 전담 프로세스를 통해서 한다.만일 데드락이 탐지되면 크게 2가지의 방법으로 북구를 한다.

 

롤백(Rollback)

 프로세스별로 체크포인트를 일정 시간마다 생성한다.이 체크포인트에는 레지스터값,현재 상태 등등 많은 데이터가 포함된다.이후 데드락이 발생하면 데드락에 연루된 프로세스들이 데드락 발생 전의 상태로 돌아간다.이 방식은 현실적으로 힘든 방식이다 우선 체크포인트를 생성하는데 많은 오버헤드가 발생하기도 하고 데드락에 연루된 프로세스들이 많을 경우에는 사실상 불가능하다.

 

강제 종료 및 자원 해제

 가장 현실적이고 단순한 복구 방법으로 데드락에 연루된 프로세스들의 전부 혹은 일부를 강제로 종료시키고 이들이 사용 중이던 자원들을 해제하는 방법이다.하지만 이 방식도 프로세스별로 어느 정도 진행된 상태에서 강제로 종료될 경우 발생할 수 있는 문제들에 대한 검증도 필요하다.

 

데드락을 처리하는 방안들을 비교해보면 다음과 같다.

 

 

데드락 처리 방안들의 비교