Dead-lock과 해결 방법

Dead-lock이 무엇인지 이해하고 어떻게 해결 할 수 있는지 알아보자.

 

---

1. Dead-lock 정의

---

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있어 결과적으로 아무것도 완료되지 못하는 상태.

 

Dead-lock 은 상호 배제, 점유 대기, 비선점, 순환 대기 4 가지 조건이 모두 만족하면 발생한다.

---

 

---

2. Dead-lock 발생 조건

---

a. Mutual exclusion (상호 배제)

  자원은 한 번에 한 프로세스만 사용 가능함.

 

b. Hold and wait (점유 대기)

  어떤 프로세스가 최소 하나의 자원을 점유하고 다른 프로세스가 사용하는 자원을 할당받기 위해 대기하고 있음.

 

c. No preemption (비선점)

  다른 프로세스가 사용중인 자원을 강제로 뺏을 수 없음.

 

d. Circular wait (순환 대기)

  프로세스 pA 가 pB가 사용중인 자원을 할당받기 위해 대기하고 pB는 pA의 자원을 할당받으려 대기중임. 

---

 

---

3. Dead-lock 해결 방법

---

a. 교착상태 예방

 

  위 에서 살펴본 교착상태 발생 조건 중 하나 이상을 제거함으로써 해결하는 방법이다.

  a-1. 상호 배제 조건 제거

    - 모든 자원의 공유를 허용함.

  a-2. 점유 대기 조건 제거

    - 필요한 모든 자원을 할당함.(자원 낭비 발생)

    - 자원을 점유하고 있지 않을 때만 다른 자원을 요청할 수 있도록 함.(기아 상태 가능성)

  a-3. 비선점 조건 제거

    - 할당 받을 수 없는 자원을 요청할 때 점유하고 있는 모든 자원을 반납하고 대기하게 함.(자원 낭비 발생)

  a-4. 순환대기 조건 제거

    - 자원에 고유 번호를 매기고 번호 순서대로 특정 방향으로만 자원을 요구하도록 함.(자원 낭비 발생)

    

 

b. 교착상태 회피

 

  교착상태가 발생하기 전 교착상태를 예측하고 회피하는 방법이다. 회피할 수 있는 조건을 달성하기 어렵고 자원을 요청할 때마다 회피 알고리즘을 사용하면 오버헤드가 크기 때문에 현실성 없는 방법이다.

 

c. 교착상태 탐지, 복구

 

  c-1. 교착상태 탐지

 

(a) 자원할당 그래프 (b) 대기 그래프

  교착 상태를 허용하되 탐지 알고리즘을 실행하여 교착상태를 탐지하면 복구하는 방법이다.

대기 그래프에서 Pn 이 Pk를 가리키고 있다면 Pn이 Pk가 사용하는 자원을 얻기 위해 대기하고 있다는 뜻이다.

대기 그래프에 순환이 발생하면 교착상태를 의미한다.

탐지 알고리즘을 너무 자주 호출할 경우 오버헤드가 커지기 때문에 적절한 시점과 주기에 호출할 필요가 있다.

 

  c-2. 교착상태 복구

 

  크게 1) 프로세스 종료 2) 자원 선점 두 가지 방식이 있다.

 

  1)은 교착 상태인 프로세스를 모두 종료하거나 교착 상태가 제거 될때까지 한 프로세스씩 중지하는 방법이다.

  2)는 교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에 할당하는 방법이다.

 

  복구 할 때 1) 희생자 선택 2) Rollback 3) 기아 상태를 주의해야 한다.

 

  어떤 프로세스를 죽이거나 자원을 선점할 지 선택하는 1) 희생자 선택. 1)을 적은 비용이 드는 프로세스 대상으로만 하면 해당 프로세스는 3) 기아 상태에 빠질 수 있다. 1)을 적절하게 하고 어느 수준까지 2) Rollback을 할 지 정해야 한다. 교착상태의 모든 프로세스를 재시작 할 지, 교착상태가 해결될 때까지만 Rollback을 할 지 정한다.

 

 

 

d. 교착상태 무시

 

 

교착상태를 무시하고 특별한 조치를 취하지 않는 방법이다. 교착상태를 주기적으로 탐지하거나 예방하기 위해서 필요한 오버헤드보다 교착상태를 무시할 때 더 이득이 큰 경우에 사용한다. 주로 Window, Linux등 운영체제에서 사용하는 방법이다.

---

 

 

참조 :

[10분 테코톡] 🚴‍♂️ 케빈의 Deadlock - YouTube,

교착상태(Dead Lock) 해결 방법 (tistory.com),

[OS/운영체제] Deadlock(데드락) - 정의, 발생 조건, 해결 방법 (velog.io)