교착 상태 (Deadlock)
쉽게 풀면
좁은 외길 다리 위에서 양쪽에서 온 자동차 두 대가 마주쳤다고 생각해보세요. 서로 "네가 먼저 후진해"라며 양보를 기다리기만 하면 두 차 모두 영원히 움직이지 못합니다. 컴퓨터 프로그램에서도 이런 일이 벌어집니다. 프로세스 A는 자원 1을 가진 채 자원 2를 기다리고, 프로세스 B는 자원 2를 가진 채 자원 1을 기다리면, 둘 다 서로가 자원을 놓아주기만 기다리다가 영원히 멈춰버립니다. 이 상태가 바로 교착 상태입니다.
왜 중요한가
교착 상태는 운영체제, 데이터베이스, 분산 시스템, 병렬 프로그래밍 등 여러 자원을 여러 주체가 동시에 다투는 거의 모든 시스템에서 발생할 수 있는 근본적인 문제라, 시스템의 신뢰성과 가용성을 다루는 논문에서 반드시 고려해야 하는 실패 모드로 등장합니다. 특히 다중 코어 환경이나 분산 데이터베이스처럼 동시성이 커질수록 발생 가능성과 파급 효과가 커지기 때문에, 이를 예방·탐지·회복하는 기법 자체가 하나의 독립된 연구 주제로 다뤄지기도 합니다.
핵심 정리
- 교착 상태는 둘 이상의 주체가 서로가 쥔 자원을 기다리며 영원히 멈춘 상태입니다. Coffman 등(1971)은 다음 네 조건이 동시에 성립할 때 생긴다고 정리했습니다.
- 상호 배제(자원을 한 번에 하나만 쓴다), 점유 대기(자원을 쥔 채 다른 자원을 기다린다), 비선점(쥔 자원을 강제로 빼앗을 수 없다), 순환 대기(기다리는 관계가 원형으로 닫힌다)입니다.
- 넷 중 하나만 깨도 교착 상태는 일어나지 않습니다. 락을 항상 같은 순서로 잡거나(순환 대기 방지), 필요한 자원을 한꺼번에 요청하거나(점유 대기 방지), 시간 제한 후 락을 놓는(비선점 보완) 방법이 대표적입니다.
- 방지 말고도 은행가 알고리즘 같은 회피, 자원 할당 그래프에서 순환을 찾아 사후 복구하는 탐지·복구, 문제를 무시하는 방식이 쓰입니다.
예시로 보기
스레드 1이 락 A 다음 B를, 스레드 2가 락 B 다음 A를 잡는 경우와, 둘 다 A 다음 B 순서로 잡는 경우를 코드로 가능한 모든 실행 순서에 대해 검사했습니다(각 스레드는 두 락을 모두 얻으면 둘 다 놓는다고 가정).
| 락 획득 순서 | 가능한 실행 경로 | 교착 상태로 끝난 경로 | 정상 종료한 경로 |
|---|---|---|---|
| 스레드 1: A→B, 스레드 2: B→A | 4 | 2 | 2 |
| 스레드 1: A→B, 스레드 2: A→B (순서 통일) | 2 | 0 | 2 |
순서가 엇갈리면 ‘스레드 1이 A를, 스레드 2가 B를 먼저 잡는’ 경로에서 서로 상대 락을 기다리며 멈춥니다. 모든 경로가 교착 상태로 끝나는 것은 아니므로 테스트에서 한 번 통과했다고 안전한 것은 아닙니다. 락 순서를 통일하면 순환 대기가 생기지 않아 교착 상태 경로가 사라집니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 교착 상태는 프로그램이 느려지는 것이다. | 느려지는 것이 아니라 관련 주체가 더 진행하지 못하고 멈추는 것입니다. |
| 락을 쓰면 안전하다. | 락을 잘못된 순서로 쓰면 오히려 교착 상태의 원인이 됩니다. |
| 한 번도 안 걸렸으니 교착 상태가 없다. | 실행 순서(타이밍)에 달려 있어 드물게만 재현될 수 있습니다. |
| 교착 상태와 경쟁 상태는 같다. | 경쟁 상태는 실행 순서 때문에 결과가 틀리는 문제이고, 교착 상태는 진행이 멈추는 문제입니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 데이터베이스 트랜잭션들이 자원을 잠그는 순서가 뒤엉키면 서로 기다리다 멈추는 문제가 생길 수 있어, 항상 같은 순서로 자원을 잠그도록 규칙을 정해 해결했다는 뜻입니다.
여러 컴퓨터가 네트워크로 연결된 분산 환경에서는 메시지가 늦게 도착하는 것만으로도 서로 기다리는 순환 구조가 생길 수 있고, 이를 일정 시간 이상 응답이 없으면 탐지해내는 방법을 제안했다는 뜻입니다.
조금 더 깊게 보면
교착 상태가 성립하려면 자원을 독점 사용, 이미 가진 자원을 유지한 채 다른 자원을 대기, 강제로 자원을 빼앗을 수 없음, 대기가 순환 구조를 이루는 조건이 동시에 만족되어야 한다는 것이 고전적으로 알려져 있습니다. 이 조건 중 하나만 깨뜨려도 교착 상태를 막을 수 있어서, 락 획득 순서를 고정하거나 자원 요청을 한 번에 몰아서 하는 방식이 실무에서 흔히 쓰이며, 발생을 막는 대신 자원 할당 그래프에서 순환을 찾아 사후에 탐지하고 복구하는 접근도 함께 연구됩니다.
주의할 점
교착 상태는 경쟁 상태와 헷갈리기 쉽지만 다른 개념입니다. 경쟁 상태는 결과가 실행 순서에 따라 잘못 나오는 문제이고, 교착 상태는 아예 진행 자체가 멈춰버리는 문제입니다. 뮤텍스와 세마포어 같은 동기화 도구도 사용 방식이 잘못되면 오히려 교착 상태를 유발할 수 있습니다.
헷갈리기 쉬운 용어
| 용어 | 한 줄 설명 | 증상 |
|---|---|---|
| 교착 상태(deadlock) | 서로 기다리며 모두 멈춤 | CPU도 거의 쓰지 않고 멈춤 |
| 라이브락(livelock) | 서로 양보하며 계속 상태를 바꾸지만 진전이 없음 | 바쁘게 움직이는데 진행 없음 |
| 기아(starvation) | 특정 주체만 계속 자원을 받지 못함 | 다른 주체는 진행 |
| 경쟁 상태 | 실행 순서에 따라 결과가 달라지는 오류 | 결과가 틀림 |
| 뮤텍스 | 한 번에 하나만 임계구역에 들이는 락 | 교착 상태의 재료가 되기도 하는 도구 |
참고 문헌
- Coffman, E. G., Elphick, M., & Shoshani, A. (1971). System deadlocks. ACM Computing Surveys, 3(2), 67–78.
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley.
- Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.