데드락

이창준·2023년 5월 9일

데드락 :

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

위의 그림과 같이 자동차(프로세스)들이 각각의 도로(자원)를 점유한 상태에서 다른 자동차(프로세스)들이 사용하고 있는 도로(자원)를 사용하기 위해 대기하고 있지만, 도로 위에서 이러지도 저러지도 못하는 상황을 예시로 들 수 있음.

상호 배제 : 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
=> 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
점유 대기 : 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
비선점 : 이미 할당된 자원을 강제로 빼앗을 수 없다.
=> 이미 할당된 자원을 강제적으로 빼앗을 수 없음
순환 대기 : 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
=> 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

예방 방법은 교착상태가 애초에 일어나지 않도록 방지하는 방법으로 교착상태의 발생조건 4가지 중 하나를 부정함으로써 교착상태를 예방

상호 배제 부정 : 여러 개의 프로세스가 동시에 공유자원을 사용할 수 있음.
점유 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 함.
비선점 부정 : 모든 자원에 대한 선점을 허용.
순환 대기 부정 : 자원을 선형으로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 함.

※ 그러나 이렇게 교착상태 발생조건을 방지해서 데드락을 예방하는 방법은 시스템 처리량이나 자원 사용의 효율성을 떨어트리는 단점 존재

교착상태가 발생할 가능성이 있는 자원 할당(Unsafe allocation)을 하지 않고 안전한 상태(Safe state)에서만 자원 요청을 허용하는 방법

교착상태 회피를 하기 위해서는 아래와 같은 가정이 필요
- 프로세스 수 고정
- 자원의 종류와 수 고정
- 프로세스가 요구하는 최대 자원의 수를 알아야 함
- 프로세스는 자원 사용 후 반드시 반납
Safe state : safe sequence(교착상태를 발생시키지 않고 자원을 할당하는 순서)가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태를 의미
Unsafe state : 교착상태가 발생할 가능성이 있는 상태

먼저 시스템이 데드락 예방이나 회피법을 사용하지 않았을 때, 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용

1) 탐지(Detection) :

시스템에 데드락이 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것을 의미한다. 교착상태가 탐지되었다면 회복 기법을 통해 교착상태를 복구
탐지 기법은 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드(성능 저하)가 발생

2) 회복(Recovery) :