좁은 외길 다리 한가운데에서 양쪽에서 들어온 자동차 두 대가 마주 섰다고 가정하겠습니다. 두 운전자 모두 상대가 먼저 물러나기를 기다리며 꼼짝하지 않는다면, 두 차는 영원히 다리를 건너지 못합니다. 누구의 잘못이라고 하기도 어렵지만, 아무도 앞으로 나아가지 못하는 상황이 만들어진 것입니다.

컴퓨터 안에서도 이와 똑같은 일이 벌어지는데, 이를 ‘교착 상태(Deadlock)’라고 합니다. 교착 상태란 쉽게 말해 여러 프로그램이 서로 상대가 가진 자원을 기다리느라, 누구도 작업을 이어 가지 못하고 멈춰 버린 상태를 의미합니다. 컴퓨터가 고장 난 것도 아닌데 갑자기 멈춘 것처럼 보이는 현상 가운데 상당수가 바로 이 교착 상태 때문입니다.

본 자료에서는 교착 상태가 어떤 모습으로 나타나는지, 교착 상태가 생기는 네 가지 조건은 무엇인지, 이를 설명하는 유명한 사례와 컴퓨터가 교착 상태에 대처하는 방법까지 차례로 살펴보겠습니다.

서로 기다리다 멈춰 버리는 컴퓨터

교착 상태는 어떻게 생길까

컴퓨터 안에서는 여러 프로그램이 동시에 돌아가며 프린터, 파일, 메모리 같은 자원을 나누어 씁니다.

(1) 한 번에 하나만 쓰는 자원
어떤 자원은 여러 프로그램이 동시에 쓰면 내용이 뒤엉키기 때문에, 한 프로그램이 쓰는 동안 다른 프로그램은 기다려야 합니다. 이때 자원을 잠시 독차지하는 장치를 잠금(Lock)이라고 부릅니다.

(2) 엇갈린 순서가 만든 멈춤
예를 들어 첫 번째 프로그램은 파일 A를 잠근 채 파일 B를 기다리고, 두 번째 프로그램은 파일 B를 잠근 채 파일 A를 기다리는 경우가 있습니다. 두 프로그램 모두 자기 것은 놓지 않고 상대의 것만 기다리기 때문에, 둘 다 영원히 멈춘 채로 남게 됩니다.

(3) 겉으로 보이는 모습
교착 상태에 빠진 프로그램은 오류 메시지도 없이 그저 응답하지 않습니다. 은행 전산망이나 예약 시스템처럼 많은 요청을 한꺼번에 처리하는 곳에서는 이런 멈춤이 큰 문제로 이어질 수 있습니다.

교착 상태가 생기는 네 가지 조건

1971년 컴퓨터 과학자 에드워드 코프먼(Edward G. Coffman Jr.)은 교착 상태가 생기려면 다음 네 가지 조건이 동시에 갖춰져야 한다고 정리했습니다. 그의 이름을 따 이를 코프먼 조건이라고 부릅니다.

• 상호 배제(Mutual Exclusion): 자원을 한 번에 한 프로그램만 쓸 수 있습니다.
• 점유와 대기(Hold and Wait): 프로그램이 이미 자원을 하나 쥔 채로 다른 자원을 더 기다립니다.
• 비선점(No Preemption): 남이 쥐고 있는 자원을 억지로 빼앗을 수 없고, 가진 쪽이 스스로 내놓아야만 합니다.
• 순환 대기(Circular Wait): 1번은 2번을, 2번은 3번을, 3번은 다시 1번을 기다리는 식으로 기다림이 고리처럼 이어집니다.

(1) 하나만 끊어도 풀린다
네 조건 가운데 하나라도 빠지면 교착 상태는 생기지 않습니다. 그래서 교착 상태를 막는 방법은 대부분 이 네 고리 가운데 하나를 끊는 데서 출발합니다.

식사하는 철학자들 문제

교착 상태를 설명할 때 가장 자주 쓰이는 이야기는 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라(Edsger W. Dijkstra)가 낸 문제에서 비롯된 ‘식사하는 철학자들 문제(Dining Philosophers Problem)’입니다.

(1) 문제의 상황
둥근 식탁에 철학자 다섯 명이 앉아 있고, 사람과 사람 사이에 포크가 하나씩, 모두 다섯 개 놓여 있습니다. 철학자는 생각하다가 배가 고파지면 양옆의 포크 두 개를 모두 집어야만 식사를 할 수 있습니다.

(2) 모두가 굶게 되는 순간
다섯 명이 동시에 왼쪽 포크를 집어 들면, 모두 오른쪽 포크를 기다리게 됩니다. 아무도 왼쪽 포크를 내려놓지 않으니 결국 다섯 명 모두 식사를 하지 못하고 기다리기만 합니다. 네 가지 조건이 모두 갖춰진 전형적인 교착 상태입니다.

(3) 간단한 해결책
포크마다 번호를 붙이고 누구나 번호가 작은 포크부터 집도록 정하면 기다림의 고리가 생기지 않습니다. 순서 하나를 정하는 것만으로 순환 대기를 끊을 수 있다는 점을 잘 보여 줍니다.

컴퓨터가 교착 상태에 대처하는 법

운영체제와 데이터베이스는 상황에 따라 여러 방법을 골라 씁니다.

(1) 미리 막기
자원을 쓰는 순서를 정해 두거나, 필요한 자원을 처음에 한꺼번에 요청하게 해서 네 조건 가운데 하나가 아예 생기지 않도록 합니다.

(2) 피해 가기
자원을 내주기 전에 이 요청을 들어주면 나중에 교착 상태가 생길 수 있는지 미리 계산해 봅니다. 데이크스트라가 고안한 은행원 알고리즘(Banker’s Algorithm)이 대표적인 방법으로, 은행이 대출을 내줄 때 모든 손님의 요구를 끝까지 채울 수 있는지 따져 보는 것과 비슷합니다.

(3) 찾아서 풀기
교착 상태가 생기는 것을 일단 허용하고, 누가 누구를 기다리는지 살펴 고리가 발견되면 프로그램 하나를 멈추거나 처음부터 다시 실행해 매듭을 풉니다. 많은 데이터베이스가 이 방식을 씁니다.

(4) 모른 척하기
교착 상태가 아주 드물게 일어나고 피해도 작다면 굳이 막지 않고, 생기면 다시 시작하는 쪽을 택하기도 합니다. 모래에 머리를 묻는 타조에 빗대어 이를 타조 알고리즘(Ostrich Algorithm)이라고 부릅니다.

교착 상태는 누구 하나가 잘못해서가 아니라, 모두가 자기 몫을 쥔 채 상대만 기다릴 때 생기는 문제입니다. 그래서 해결책도 순서를 정하고, 때로는 가진 것을 먼저 내려놓는 데서 시작됩니다.

서로 붙잡은 손을 하나만 놓아도 길이 열린다는 사실을 아는 것, 그것이 멈춘 시스템을 다시 움직이게 하는 지혜의 첫걸음입니다.