7. Dead Lock , 교착상태

여러개의 프로세스들이 한정된 자원을 가지고 서로 경쟁할때 생기는 문제로 대기 중인 프로세스들이 다시는 그 상태를 변경시킬 수 없을때의 상황을 "Dead Lock", 즉, 교착상태라고 한다.

일반적으로 프로세스는  1) 요청 2) 사용 3) 방출 의 과정을 따른다.

1. 교착상태 특징

교착상태는 아래의 4가지 조건을 성립할때 발생할 수 있다.

---

1) 상호 배제 ( Mutual Exclusion )

- 한 번에 한 프로세스만이 그 자원을 사용할 수 있고, 다른 프로세스가 자원을 요청하면, 요청 프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다.

2) 점유하며 대기 ( Hold and Wait )

- 프로세스는 최소한 하나의 자원을 가지고 있는 상태에서 , 다른 프로세스에 의해 점유된 자원을 얻기 위해서는 반드시 대기해야 한다.

3) 비선점 ( No Preemption )

- 자원들을 선점할 수 없다. 자원이 강제적으로 방출될 수 없으며, 점유중인 프로세스가 일을 종료한 후 그 프로세스에 의해서 방출이 가능하다.

4) 순환 대기 ( Circular Wait )

- 대기하고 있는 프로세스의 집합 { P0, P1,,,, Pn } 이 있다. P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고,, 계속

---

첫번째 스레드 ( thread_one )은 first, second 순서로 락을 획득하고, 

두번째 스레드는 second, first 순으로 락을 획득한다. 이때 교착상태가 발생한다.

2) 자원 할당 그래프

교착상태를 좀 더 보기쉽고 정확하게 기술하는 방법으로 "시스템 자원 할당 그래프" 라는 방향 그래프로 나타낼 수 있다.

프로세스 Pi 에서 자원 Rj로의 방향간선은 "요청간선 ( Request )" 라고 표현하고, 자원 타입 Rj의 한 인스턴스가 프로세스 Pi로 할당된 것은 " 할당 간선 ( Assignment ) " 라고 한다.

현재 이런 자원할당 그래프가 있다고 하자.

보통 저 그래프에서 사이클이 생기면 교착상태라고 부른다 하지만 이 그래프는 사이클이 존재하지만 교착상태는 아니다. 왜냐하면 P4가 락을 방출하면 R2는 P3에서 자원을 할당할수 있기 떄문이다.

3) 교착상태 처리 방법 - 교착상태 예방

교착상태를 예방하는 방법으로 교착상태가 성립할 네개의 조건을 성립하지 않게 하는 방법이 있다.

1) 상호배제

- 이 조건은 공유가 불가능한 자원에 대해선 반드시 성립해야 한다. 일반적으로 상호배제 조건을 성립하지 않게 함으로 교착상태를 예방하는것은 불가능하다.

2) 점유하며 대기

- 이 조건이 발생하지 않는다는것을 보장하기 위해선 프로세스가 자원을 요청할때는 다른 자원을 가지고 있지 않다는것을 보장해야 한다.

각 프로세스가 실행되기 전 자신의 모든 자원을 요청하여 할당받게 한다. 또 다른 방법으로는 프로세스가 자원을 전혀 가지고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 방법이다. 프로세스가 추가적으로 요청을 하려면 자신의 모든 할당된 자원을 반드시 먼저 방출해야만 한다.

단점으로는 많은 자원들이 할당이 된 후 오랜시간동안 사용되지 않기 때문에 자원의 이용률이 낮을 수 있다는것이다.

3) 비선점

- 이미 할당된 자원이 선점되지 않아야 한다는 조건이다. 만약 자원을 점유하고있는 어떤 프로세스가 바로 할당할 수 없는 다른 자원을 요청하면, ( 대기해야 하는 ) 현재 점유중인 모든 자원들이 선점된다. 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 이미 점유하였던 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작될 것이다.

또한, 한 프로세스가 어떤 자원들을 요청하면, 이들이 사용가능한 것인지 검사한다.

4) 순환대기

- 이 조건이 성립되지 않도록 하는 한 가지 방법은 모든 자원 타입들에게 전체적인 순서를 부여하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 방법이다.

F(fisrt_mutex) = 1

F(second_mutex) = 5

라고 할때, thread_two 두번째 스레드는 second_mutex를 먼저 획득할수 없다.

락이 동적으로 획득된다면 락 순서를 부여한다고 하여 교착상태 예방을 보장하지 못한다. 예를들어 아래 코드를 보면

만약 두 개의 스레드가 계좌의 순서를 바꿔서 동시에 함수를 호출한다면 교착상태가 발생할 수 있다.

4) 교착 상태 처리방법 - 교착상태 회피

- 교착상태 예방의 부수적인 문제는 시스템 처리율이 감소된다는 것이다.