교착 상태

교착 상태(deadlock)는 둘 이상의 프로세스가 서로 상대가 가진 자원을 기다리며 아무도 진행하지 못하는 상태다. 실기 시험에서는 발생 조건 네 가지의 이름과 뜻, 해결 방법 네 가지의 구분, 회피 기법인 은행원 알고리즘(banker's algorithm)을 묻는다. 자원 할당 그래프(프로세스와 자원의 요청·점유 관계를 그린 그림)와 탐지 알고리즘의 원리는 CS 카테고리의 교착 상태 문서가 다룬다.

발생 조건

교착 상태는 아래 네 조건이 모두 동시에 성립할 때만 생긴다. 그래서 하나라도 깨면 교착 상태를 막을 수 있고, 이 사실이 예방 기법의 출발점이다. 이 네 조건은 1971년 코프먼(Coffman) 등이 정리해 코프먼 조건이라고도 부른다.

조건	뜻
상호 배제(mutual exclusion)	자원을 한 번에 한 프로세스만 쓸 수 있다
점유와 대기(hold and wait)	자원을 하나 이상 가진 채 다른 자원을 더 기다린다
비선점(no preemption)	다른 프로세스의 자원을 강제로 빼앗을 수 없다
환형 대기(circular wait)	프로세스들이 원을 이루며 앞 프로세스의 자원을 기다린다

환형 대기는 순환 대기, 점유와 대기는 점유 대기라고도 한다(CS 쪽 문서의 표기). 예를 들어 P1은 자원 A를 쥐고 B를 기다리고, P2는 B를 쥐고 A를 기다리면 네 조건이 모두 성립해 둘 다 영원히 멈춘다.

해결 방법

해결 방법은 언제 손을 쓰느냐로 나눈다. 발생하기 전에 조건 자체를 없애면 예방, 발생할 수 있는 상황을 피해 가면 회피, 일단 두었다가 찾아내면 발견, 찾은 뒤 푸는 것이 회복이다.

방법	하는 일
예방(prevention)	네 조건 중 하나를 원천적으로 제거한다. 예: 필요한 자원을 한 번에 모두 요청하게 해 점유와 대기를 없앤다
회피(avoidance)	자원을 줄 때마다 안전한지 검사해 위험한 할당을 피한다. 은행원 알고리즘
발견(detection)	대기 관계에 고리가 생겼는지 탐지 알고리즘으로 확인해 걸린 프로세스를 가려낸다
회복(recovery)	걸린 프로세스 일부를 강제로 끝내거나 자원을 빼앗아 넘겨 고리를 끊는다

은행원 알고리즘

은행원 알고리즘(banker's algorithm)은 다익스트라(Dijkstra)가 제안했다. 은행이 모든 고객의 최대 대출 요구를 알고, 대출을 해 줘도 모든 고객이 끝내 상환할 수 있는 순서가 있을 때만 빌려주는 방식에서 이름이 나왔다. 그런 순서가 존재하는 상태를 안전 상태(safe state), 그 순서를 안전 순서라 한다.

판정 절차는 다음과 같다. 먼저 프로세스마다 필요량 = 최대 요구량 − 현재 할당량을 구한다. 그다음 필요량이 가용 자원 이하인 프로세스를 하나 골라 끝났다고 보고, 그 프로세스의 할당량을 가용 자원에 돌려준다. 이것을 반복해 모두 끝낼 수 있으면 안전 상태다.

자원 A·B·C의 가용량이 (2, 2, 1)이고 할당량과 최대 요구량이 P0 (1,0,1)·(4,2,2), P1 (2,1,0)·(3,2,1), P2 (0,1,1)·(2,3,3), P3 (1,1,0)·(2,2,1)이라 하자(괄호는 각각 자원 A, B, C의 개수이고, 앞이 할당량·뒤가 최대 요구량이다). 필요량은 P0 (3,2,1), P1 (1,1,1), P2 (2,2,2), P3 (1,1,1)이다. 번호가 작은 것부터 검사하면 P0는 필요량 (3,2,1)이 가용량 (2,2,1)보다 커서 넘어가고, 필요량이 가용량 이하인 P1을 먼저 끝내 가용량이 (4,3,1)이 되고, 이어 P0·P2·P3 순으로 모두 끝나므로 안전 상태다. 처음 가용량이 (0,0,1)이었다면 누구의 필요량도 채울 수 없어 불안전 상태다.

시험 포인트

• 발생 4조건: 상호 배제, 점유와 대기, 비선점, 환형 대기. 넷이 모두 성립해야 발생한다.
• "자원 할당 전 안전 여부를 검사해 교착 상태를 피한다", "은행원 알고리즘" → 회피.
• "네 조건 중 하나를 제거" → 예방. "프로세스 종료·자원 선점" → 회복.
• 필요량 = 최대 − 할당. 필요량 ≤ 가용인 프로세스부터 끝내고 할당량을 돌려받는다.