Deadlock의 개념 / 해결 방법

Deadlock 이란?

- 두 개 이상의 작업이 서로 상대의 작업이 끝나기만을 기다리고 있어 더 이상 다음 단계로의 진행이 불가한 상태.

- 한정된 자원을 둘 이상의 작업이 동시에 이용하려고 할 때 발생할 수 있다.

- ex)

    Process1이 Resource1을 사용하고 있고, Resource2를 필요로 하고

    Process2는 Resource2를 사용하고 있고, Resource1을 필요로 할 때,

    Process1은 Resource2를 Process2에 할당되어 있기 때문에 가져올 수 없다.

    또한, Process2 역시 같은 이유로 Resource1을 가져올 수 없다.

    그래서, 두 프로세스는 해당 자원을 받을 때 까지 무한정 대기하는 상황이 발생하는데, 이를 Deadlock이라고 한다.

 

Deadlock 발생조건

- Deadlock은 아래 4가지 조건이 모두 충족될 때 일어난다. 따라서, 하나의 조건이라도 성립하지 않으면, 혹은 성립하지 않도록 한다면 Deadlock은 발생하지 않는다.

 

 - 상호배제 (Mutual exclusion) : 하나의 자원은 하나의 프로세스만 사용할 수 있어야 한다.

 - 점유대기 (Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

 - 비선점 (No preemption) : 다른 프로세스에 할당된 자원은 해당 프로세스에서 작업을 끝내기 전까지 뺏어올 수 없다.

 - 순환대기 (Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

 

Deadlock 해결방법

- 각 발생조건에 대해 성립하지 않도록 한다. 일반적인 해결방법은 아직 없다고 알려져 있다.

 

   Deadlock 예방 : 자원 사용의 효율이 떨어지고, 비용이 많이 드는 문제점이 있음.

    - 상호배제 조건 제거 : 

       하나의 자원을 여러 프로세스에서 접근 가능하도록 한다.

    - 점유대기 조건 제거 : 

       프로세스가 실행 될 때, 필요한 모든 자원을 한번에 할당하고 더이상 해당 자원을 사용하지 않으면

       다른 프로세스에서 자원을 요구하도록 한다.

    - 비선점 조건 제거 : 

       자원을 이미 사용하고 있는 프로세스에게 자원의 반납을 요구하고 기다리게 한다.

    - 순환대기 조건 제거 : 

       자원에 번호를 매기고 번호에 따라 순차적으로 요구하도록 한다.

 

   Deadlock 회피 : 순환대기가 발생하지 않도록 자원 할당 상태를 검사한다. 비용이 많이 든다.

     - 은행원 알고리즘, 자원 할당 그래프 알고리즘

 

   Deadlock 무시 : Deadlock의 발생확률이 낮은 경우, 발생하더라도 무시하도록 한다.

 

   Deadlock 탐지 : Deadlock의 발생을 탐지하고 회복한다. 성능에 영향을 미칠 가능성이 있다.