데드락, 교착상태

<데드락>

- 교착 상태

- 한정된 자원을 여러 곳에서 사용 -> 둘 이상의 프로그램이 함께 멈추어 버리는 현상

- 어떤 프로세스가 자원을 요청했을때 그 자원을 사용할 수 없고, 프로세스가 대기 상태로 진입

- 대기 상태로 들어간 프로세스가 실행을 할 수 없을 경우

---

<발생 조건 - 모두 만족해야 한다>

1. 상호 배제 (Mutual exclusion)

- 자원 자체를 동시에 쓸 수 없는 경우

2. 점유 상태로 대기 (Hold and wait)

- 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다리는 상태.

- 예를 들면 Skype가 마이크와 카메라를 써야 하는데 마이크는 땡겨오는데 성공했지만 카메라 앱이 카메라를 잡고 있어서 그걸 기다리고 있고, 

  이 때문에 애꿎은 녹음기도 마이크를 못 쓰게 되는 상황

3. 선점 불가 (No preemption)

- 다른 프로세스가 자원을 선점할 수 없다.

- 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 선점할 수 없다.

- 우선순위 선점으로 해결 가능

4. 순환성 대기 (Circular wait)

- 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

---

<데드락 처리 방법>

1. 교착 상태 예방 및 회피

- 교착 상태를 예방하거나 회피하는 프로토콜을 이용

- 예방 : 교착 상태 발생 조건 중 하나를 제거함으로써 해결 ( 자원의 낭비가 심하다 )

- 상호 배제 부정 : 여러 개의 프로세스가 자원을 공유할 수 있도록 한다.

- 점유 대기 부정 : 프로세스가 실행되기 전 모든 자원을 할당한다.

- 선점 불가 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때, 점유하고 있는 자원을 반납하고, 요구한 자원을 위해 대기한다.

- 순환 대기 부정 : 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

- 회피 : 교착 상태가 되도록 허용한 후 회복시키는 방법

- 은행원 알고리즘 : 프로세스가 자원을 요구할 때 시스템은 장원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 회피하는 기법

- 안정 상태 ? 할당 : 대기

2. 교착 상태 탐지 및 회복

- 탐지 : 자원 할당 그래프를 통해 탐지할 수 있다.

- 자원을 요청할때마다 탐지 알고리즘 실행하는 경우 오버헤드가 발생한다.

- 자원 할당 그래프 예시

- 회복 : 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복

- 종료 : 교착 상태의 프로세스를 모두 중지

  : 교착 상태가 제거될 때까지 한 프로세스씩 중지

- 선점 : 교착 상태의 프로세스가 점유하고 있는 자원을 다른 프로세스에 할당, 해당 프로세스는 일시 정지 

  : 우선 순위가 낮거나 수행 회수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점

3. 교착 상태 무시

- 대부분의 시스템은 교착 상태가 잘 발생하지 않으며, 교착 상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

---

출처

http://includestdio.tistory.com/12

https://namu.wiki/w/Deadlock

---