교착상태

교착상태, Dead Lock

교착상태란 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 말한다. 아래 사진에서처럼 서로 사다리를 점유하고 있는 상태에서 위의 사람은 내려가려하고, 아래 사람은 올라가려 해 서로가 비켜주기만을 하염없이 기다리는 현상이다. 이러한 현상은 흔히 다중 프로그래밍 환경에서 발생한다.

사다리와 사람이 맞다.

교착상태 발생의 필요 충분 조건

교착상태가 발생하려면 아래 네 가지 조건을 모두 충족시켜야 한다.

▪️ 상호 배제 Mutual Exclusion : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

▪️ 점유와 대기 Hold and Wait : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

▪️ 비선점 Non-preemption : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.

▪️ 환형 대기 Circular Wait : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

해결법

예방, Prevention

교착상태가 발생하지 않게 사전에 예방하는 방법으로, 자원 낭비가 가장 심한 기법이다. 간단히 필요 조건 중 하나를 부정하면 된다.

▪️ 상호 배제 부정 : 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있게 한다.

▪️ 점유와 대기 부정 : 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.

▪️ 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

▪️ 환형 대기 부정 : 프로세스들을 선형으로 구성하고 앞이나 뒤 한쪽으로만 프로세스의 자원을 요구하게 한다.

회피, Avoidance

교착상태가 발생하면 적절히 피해나가는 방법으로 크게 자원 할당 그래프 알고리즘과 은행원 알고리즘이 있다.

> 은행원 알고리즘 Banker’s Algorithm

다익스트라가 제안한 기법으로 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사한다. 자원 할당량을 사전에 파악해 교착상태를 회피할 수 있지만, 자원의 양과 사용자 수가 일정해야하는 등의 제약 조건이 있다.

발견, Detection

시스템에 교착상태가 발생했는지 점검해 교착상태에 있는 프로세스와 자원을 발견한다. 교착상태 발견 알고리즘과 자원 할당 그래프를 통해 탐지한다.

회복, Recovery

교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.

> 프로세스 종료

▪️ 교착상태에 있는 모든 프로세스 종료

▪️ 교착상태에 있는 프로세스들을 하나씩 종료

> 자원 선점

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