[SW 용어] Deadlock 정리

Deadlock(교착상태)

1. Deadlock이란 여러 프로세스 혹은 스레드가 일어날 수 없는 이벤트나 자원할당을 무한정 대기하는 것이다.

2. 여러 프로세스가 동일 자원을 요청할 때 발생한다.

3. 아래 4가지 조건이 성립될 때 발생한다.

상호 배제(Mutual exclusion): 매 순간 하나의 프로세스만이 독점적으로 자원 사용한다.

비선점(Non-Preemption): 프로세스는 자원을 빼앗기지 않는다.

점유대기(Hold & Wait): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 반환하지 않는다.

순환대기(Circular wait): 자원을 기다리는 프로세스간 사이클이 형성되어 있다. (환형 - 뱀이 꼬리를 무는 형태)

 

---

 

Deadlock 해결방법

Deadlock 예방(Deadlock Prevention)

위 4가지 조건 중 하나를 제거

1. 상호 배제 제거: 임계 구역(Critical Section)을 제거한다.

2. 비선점 제거: 선점 가능 기법 사용한다. (ex. Round Robin-RR)

3. 점유 대기 제거: 프로세스가 자원을 요청대기 할 때 보유자원을 반환한다.

4. 순환 대기 제거: 자원 유형에 순서를 매기거나 프로세스간 자원요청이 순환하지 않게 설계한다.

 

---

 

Deadlock 회피(Deadlock Avoidance)

1. 자원요청을 할 시 자원할당이 Deadlock으로부터 안전한지 동적으로 조사 한다.

2. 해당 자원요청에 대해 자원할당을 하여도 Deadlock이 되지않으면 자원을 할당한다.

3. 주로 은행원 알고리즘을 사용한다.

---

※ 은행원 알고리즘이란?

1. MAX = 고객이 은행에 요구하는 모든 돈의 합 = 각 프로세스가 요구하는 모든 자원의 합

2. AVAILABLE = 은행이 현재 가지고 있는 돈 = 현재 시스템 가용 자원
3. ALLOCATION = 고객이 현재 빌려간 모든 돈의 합 = 각 프로세스에 할당된 자원의 합이다.

4. 안전 상태(Safe State) = 각 프로세스가 요구한 양만큼 자원을 할당해줄 수 있어 Deadlock으로부터 안전한 상태이다.

  - AVAILABLE > MAX

5. 불안전 상태(Unsafe State) = 프로세스가 요구한 양만큼 자원할당이 불가해 Deadlock이 될 수 있는 상태이다.

  - MAX > AVAILABLE

6. Safe State란 곧 Deadlock으로부터 안전한 상태이다.

 

---

Deadlock 탐지 및 회복 (Deadlock Detaction & Recovery)

1. 교착상태가 발생할 수 있는 상태로 유지한다.

2. 교착상태가 발생하면 찾아내어 해결한다.

3. 탐지는 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견한다.

4. 교착상태 발견 알고리즘 & 자원할당 그래프를 사용한다, 단점으론 자원추적에 있어 오버헤드가 발생한다.

5. 회복 방법으로는 아래 두가지가 있다.

  - 교착상태를 일으킨 프로세스를 종료한다. (교착상태에 걸린 프로세스를 모두 종료하거나 하나씩 종료)

  - 교착상태의 프로세스에 할당된 자원을 선점하여 자원을 회복한다.  (자원을 빼았겼다면 종료 혹은 블럭 상태, 빼앗은 자원을 교착상태에 빠진 다른 프로세스가 사용)