교착 상태 2

교착 상태에서 본 네 가지 필요조건을 실제로 어떻게 다루는지 이어서 다룬다. 교착 상태(deadlock)는 상호 배제(mutual exclusion), 점유 대기(hold and wait), 비선점(no preemption), 순환 대기(circular wait)가 모두 성립할 때만 생기므로, 대처법은 그중 하나를 어떻게 깨느냐로 정리된다. 방법은 미리 깨는 예방, 위험한 할당을 피하는 회피, 생긴 뒤 찾아 푸는 탐지 후 회복, 아예 두는 무시의 네 가지이고, 고전 예제와 실무에서 쓰는 방법, 비슷해 보이는 기아(starvation)와의 차이도 함께 본다.

대처 방법 네 가지

예방(prevention)은 네 조건 중 하나가 아예 성립하지 못하게 설계하는 것이다. 실무에서 가장 많이 쓰는 방법은 순환 대기를 깨는 것이다. 모든 잠금(lock)에 전역 순서를 정하고 항상 그 순서대로만 잡는다. 그러면 누구도 자기가 쥔 것보다 앞 순서의 잠금을 기다리지 않으므로, 기다림이 한 바퀴 돌아 처음으로 돌아오는 고리가 생길 수 없다. 점유 대기를 깨려면 필요한 자원을 한 번에 모두 요청하게 하고, 비선점을 깨려면 원하는 자원을 못 얻을 때 가진 것을 내려놓게 한다. 상호 배제는 깨기 어렵다. 프린터나 값을 고치는 중인 변수처럼 본래 한 번에 하나만 써야 하는 자원이 많기 때문이다.

회피(avoidance)는 자원을 줄 때마다 "이걸 주면 위험해지는가"를 계산해 위험하면 주지 않는 방법이다. 대표가 에츠허르 다익스트라(Edsger Dijkstra)가 만든 은행원 알고리즘(Banker's algorithm)이다. 각 프로세스(process)는 앞으로 필요한 최대량을 미리 신고한다. 운영체제는 요청을 들어준 뒤에도 모든 프로세스를 어떤 순서로든 끝까지 실행시킬 수 있는지 확인한다. 그런 순서가 있는 상태를 안전 상태(safe state)라고 하고, 요청을 들어주면 안전 상태가 깨질 때는 그 요청을 잠시 미룬다.

프로세스	최대 필요	현재 보유	더 필요
P1	8	4	4
P2	3	2	1
P3	6	2	4

자원이 모두 10개이고 2개가 남았다고 하자. P2에 1개를 주면 P2가 끝나며 쥐고 있던 3개를 모두 돌려줘 남은 자원이 4개가 된다. 그러면 P3, 이어서 P1도 끝낼 수 있다. 이렇게 P2, P3, P1 순서가 존재하므로 안전 상태다. 이때 P1이 2개를 더 달라고 하면 남는 자원이 0이 되고, 누구의 남은 필요량도 채울 수 없어 불안전 상태(unsafe state)가 된다. 그래서 P1의 요청은 미룬다. 불안전 상태가 곧 교착 상태는 아니지만 교착 상태로 갈 수 있는 상태다. 이 방법은 최대 필요량을 미리 알아야 하고 요청마다 계산해야 해서, 범용 운영체제에서는 거의 쓰지 않는다.

탐지 후 회복(detection and recovery)은 교착 상태를 허용하되 주기적으로 대기 그래프(wait-for graph, 누가 누구의 자원을 기다리는지 화살표로 그린 그래프)에서 사이클(cycle)을 찾고, 찾으면 한쪽을 종료하거나 자원을 빼앗아 푸는 방법이다. 데이터베이스가 대표적이다. MySQL의 InnoDB는 트랜잭션(transaction)끼리 서로의 잠금을 기다리며 원을 이룬 것을 감지하면, 그중 한 트랜잭션의 변경을 모두 취소하는 롤백(rollback)으로 잠금을 풀어 나머지가 진행되게 한다(InnoDB 잠금 참고).

무시는 교착 상태가 드물고 막는 비용이 크면 아무것도 하지 않는 선택이다. 문제가 없다고 모래에 머리를 묻는다는 뜻으로 타조 알고리즘(ostrich algorithm)이라고 부른다. 유닉스 계열과 Windows 같은 범용 운영체제의 기본 태도가 이것이고, 응용 프로그램의 잠금 교착은 프로그래머가 알아서 막아야 한다.

식사하는 철학자

식사하는 철학자 문제(dining philosophers problem)는 교착 상태를 설명하는 고전 예제다. 원탁에 철학자 다섯 명이 앉고, 사람 사이마다 포크가 하나씩 모두 다섯 개 놓여 있다. 먹으려면 양옆 포크 두 개가 필요하다. 모두가 동시에 왼쪽 포크를 들고 오른쪽 포크를 기다리면, 네 조건이 다 성립해 아무도 먹지 못한다.

해법은 조건 하나를 깨는 것이다. 한 명만 오른쪽 포크를 먼저 들게 하면, 그 사람과 이웃이 같은 포크를 먼저 노리게 되어 모두가 한 방향으로 기다리는 고리가 끊긴다. 순환 대기가 깨지는 것이다. 식탁에 동시에 앉는 사람을 네 명으로 제한해도 된다. 포크 다섯 개를 네 명이 나누므로 최소 한 명은 두 포크를 얻어, 기다림이 모두를 한 바퀴 돌아 이어질 수 없다. 두 포크를 한꺼번에 집을 수 있을 때만 집게 하면 점유 대기가 깨진다.

실무에서 막는 법

• 잠금 순서 고정: 계좌 이체라면 두 계좌 중 ID가 작은 쪽 잠금을 항상 먼저 잡는다. 순환 대기가 생기지 않는다.
• 타임아웃과 재시도: Java ReentrantLock.tryLock(시간)처럼 정해진 시간 안에 못 얻으면 가진 잠금을 풀고 잠시 뒤 다시 시도한다. 못 얻으면 스스로 자원을 내놓게 하므로 비선점 조건을 깨는 방법이다. 다만 모두가 똑같은 간격으로 물러났다 다시 부딪치면 계속 실패하는 라이브락(livelock)이 생길 수 있어, 재시도 간격에 무작위 값을 섞는다.
• 잠금 범위 줄이기: 잠금을 쥔 채 외부 호출이나 다른 잠금 획득을 하지 않는다. 쥐는 시간이 짧을수록 엇갈릴 기회가 줄어든다.

기아와의 차이

기아는 시스템 전체는 잘 돌아가는데 특정 실행 흐름만 계속 순서를 빼앗겨 자원을 받지 못하는 상태다. 교착 상태에서는 사이클에 걸린 모두가 멈추고 스스로는 풀리지 않는다. 기아는 운이 바뀌면 언젠가 받을 수도 있다는 점이 다르다. 기아는 오래 기다린 작업의 우선순위를 조금씩 올리는 에이징(aging)으로 막는다.

면접 포인트

• "실무에서는 어떻게 막나요?" → 잠금 순서 고정(순환 대기 제거), tryLock 타임아웃 후 내려놓기(비선점 제거), 잠금 범위 최소화.
• "은행원 알고리즘은?" → 회피 기법. 최대 필요량을 미리 알고, 요청을 들어줘도 안전 상태인지 확인한 뒤에만 준다.
• "운영체제는 교착 상태를 풀어 주나요?" → 범용 운영체제는 대개 무시(타조 알고리즘). DB는 탐지 후 한쪽을 롤백한다.
• 교착 상태 ≠ 기아. 불안전 상태 ≠ 교착 상태.