교착 상태

교착 상태(deadlock)는 둘 이상의 실행 흐름이 서로 상대가 쥔 자원을 기다리느라 아무도 앞으로 나가지 못하는 상태다. 누가 먼저 양보하지 않는 한 영원히 풀리지 않는다. 교착 상태는 네 가지 조건이 한꺼번에 성립할 때만 생기므로, 대처법은 모두 "그중 하나를 어떻게 깨느냐"로 정리된다.

가장 흔한 모양: 잠금 두 개를 반대 순서로

스레드(thread) 두 개와 뮤텍스(mutex) 두 개만 있으면 교착 상태를 만들 수 있다.

스레드 1: lock(A); lock(B); ... unlock(B); unlock(A)
스레드 2: lock(B); lock(A); ... unlock(A); unlock(B)

스레드 1이 A를 잡은 직후 스레드 2가 B를 잡으면, 스레드 1은 B를, 스레드 2는 A를 기다린다. 둘 다 상대가 풀어 주기를 기다리며 잠들고, 상대도 똑같이 잠들어 있으니 아무도 풀지 않는다. 이 버그는 두 스레드가 딱 그 순간에 엇갈릴 때만 나타나서, 테스트에서는 멀쩡하다가 운영 중 부하가 몰릴 때 터지기 쉽다.

네 가지 필요조건

교착 상태는 다음 네 조건이 모두 동시에 성립할 때만 생긴다. 하나라도 빠지면 생기지 않는다. 처음 정리한 사람의 이름을 따서 코프먼 조건(Coffman conditions)이라고도 한다.

조건	뜻	위 예에서
상호 배제(mutual exclusion)	자원을 한 번에 하나만 쓸 수 있다	뮤텍스는 한 스레드만 잡는다
점유 대기(hold and wait)	자원을 쥔 채로 다른 자원을 기다린다	A를 쥔 채 B를 기다린다
비선점(no preemption)	남이 쥔 자원을 강제로 빼앗을 수 없다	남의 잠금을 대신 못 푼다
순환 대기(circular wait)	기다림이 원을 이룬다	1은 2를, 2는 1을 기다린다

네 조건 가운데 앞의 셋은 잠금을 쓰는 프로그램이라면 대개 늘 성립한다. 뮤텍스는 원래 한 스레드만 잡고 남이 대신 풀 수 없으며, 코드는 잠금 하나를 쥔 채 다른 잠금을 잡는 일이 흔하기 때문이다. 그래서 교착 상태가 실제로 생기느냐는 마지막 순환 대기, 즉 대기 관계를 따라가면 처음으로 돌아오는 고리가 생기느냐에 달린 경우가 많다.

자원 할당 그래프

누가 무엇을 쥐고 무엇을 기다리는지는 자원 할당 그래프(resource allocation graph)로 그린다. 프로세스(process)나 스레드와 자원을 정점(vertex)으로 두고, 화살표로 된 간선(edge)을 긋는 방향 그래프(directed graph)다. 자원에서 프로세스로 가는 화살표는 "할당됨", 프로세스에서 자원으로 가는 화살표는 "요청 중"이다.

다이어그램 로딩…

화살표를 따라가면 처음으로 돌아오는 사이클(cycle)이 보이면 순환 대기가 있다는 뜻이다. 자원마다 인스턴스(instance, 같은 종류 자원의 실제 한 개. 프린터가 두 대면 인스턴스가 두 개)가 하나뿐이면 사이클은 곧 교착 상태다. 같은 종류 자원이 여러 개 있으면 사이클이 있어도 풀릴 수 있다. 사이클 밖에서 같은 자원의 다른 인스턴스를 쥔 프로세스가 일을 마치고 내놓으면, 기다리던 쪽이 그것을 받아 고리가 끊기기 때문이다. 그래서 이때 사이클은 교착 상태의 가능성일 뿐이다.

이어지는 내용은 교착 상태 2에서 다룬다. 네 조건 중 하나를 깨는 예방, 은행원 알고리즘(Banker's algorithm)으로 피하는 회피, 탐지 후 회복과 무시, 식사하는 철학자 문제(dining philosophers problem), 실무에서 막는 법, 기아(starvation)와의 차이를 본다.

면접 포인트

• "교착 상태의 네 조건은?" → 상호 배제·점유 대기·비선점·순환 대기. 넷이 동시에 성립해야 생기고, 하나만 깨도 막힌다.
• "가장 흔한 교착 상태는?" → 두 스레드가 잠금 두 개를 반대 순서로 잡는 경우. 엇갈릴 때만 나타나 테스트에서 잘 안 잡힌다.
• 사이클 = 교착 상태는 자원 인스턴스가 하나일 때만. 여러 개면 가능성일 뿐이다.