교착상태(데드락)의 4가지 조건

교착상태(deadlock)는 둘 이상의 프로세스가 서로가 점유한 자원을 기다리며, 누구도 앞으로 나아가지 못하고 무한히 멈춰 있는 상태다. 흔한 비유가 좁은 외길에서 마주 오는 두 대의 차다. 서로 상대가 비켜주기를 기다리지만, 둘 다 후진할 생각이 없으면 영원히 그 자리에 선다.

교착상태의 4가지 필요조건

데드락은 아래 네 조건이 동시에 성립할 때에만 발생한다. 하나라도 깨지면 교착은 생기지 않는다. 그래서 시험에서는 “4가지를 모두 만족해야 한다”는 점과, 각 조건이 무엇을 뜻하는지를 묻는다.

상호 배제(Mutual Exclusion): 한 자원을 한 번에 하나의 프로세스만 사용할 수 있다. 프린터처럼 공유 불가능한 자원이 있어야 한다.
점유와 대기(Hold and Wait): 자원을 이미 하나 이상 쥔 채로, 다른 프로세스가 가진 자원을 추가로 기다린다.
비선점(No Preemption): 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없다. 자원은 그것을 쥔 프로세스가 스스로 놓아야만 반환된다.
환형 대기(Circular Wait): 프로세스들이 원형으로 자원을 기다린다. P1은 P2의 자원을, P2는 P3의 자원을, …, 마지막이 다시 P1의 자원을 기다려 고리가 닫힌다.

기억법으로 “상·점·비·환”으로 앞 글자만 외우면 4지선다에서 빠뜨린 조건을 골라내기 쉽다.

예시

두 프로세스 P1, P2와 두 자원 R1, R2를 생각하자. P1이 R1을 잡은 상태에서 R2를 요청하고, 동시에 P2가 R2를 잡은 상태에서 R1을 요청한다. R1과 R2는 각각 한 프로세스만 쓸 수 있고(상호 배제), 둘 다 자기 자원을 쥔 채 상대 것을 기다리며(점유와 대기), 서로 빼앗지 못하고(비선점), P1→R2→P2→R1→P1으로 고리가 닫힌다(환형 대기). 네 조건이 모두 맞았으니 교착이다.

교착상태 처리 방법

대응은 크게 네 갈래다. 앞의 셋은 예방·회피·탐지, 마지막은 발생 후 회복이다.

예방(Prevention): 4가지 조건 중 하나를 원천적으로 못 갖추게 설계한다. 예를 들어 자원에 번호를 매겨 오름차순으로만 요청하게 하면 환형 대기가 깨진다. 확실하지만 자원 이용률이 떨어진다.
회피(Avoidance): 자원을 줘도 안전한지 매번 검사해, 안전 상태(safe state)일 때만 할당한다. 대표 기법이 은행원 알고리즘(Banker’s Algorithm)이다.
탐지(Detection): 교착을 그냥 두되, 자원 할당 그래프 등으로 발생을 주기적으로 검사한다.
회복(Recovery): 탐지되면 프로세스를 강제 종료하거나, 자원을 선점해 빼앗아 고리를 끊는다.

시험에 자주 나오는 포인트

4가지 조건의 이름과 뜻, 그리고 “동시에 모두 성립”해야 한다는 점.
예방은 4조건 중 하나를 부정하는 것, 회피는 은행원 알고리즘이라는 짝을 정확히 연결하기.
회복 방법으로 프로세스 종료와 자원 선점 두 가지를 구분하기.