데드락(Deadlock)에 대해서 설명해주세요

데드락은 두 개 이상의 프로세스(또는 스레드)가 서로가 보유한 자원을 기다리며 영원히 진행할 수 없는 상태입니다. 1971년 Coffman이 정의한 4가지 조건이 동시에 성립할 때만 데드락이 발생합니다.

하나라도 깨지면 데드락은 일어나지 않습니다. 아래 카드를 클릭하여 각 조건의 의미와 예방법을 확인해 보세요.

자원 할당 그래프(Resource Allocation Graph, RAG)는 프로세스와 자원 간의 의존 관계를 시각화하는 도구입니다. 그래프에 사이클이 존재하면 데드락이 발생했거나 발생 가능한 상태입니다.

두 시나리오를 전환하며 사이클이 형성되는 순간 데드락이 감지되는 과정을 체험해 보세요.

자원이 다중 인스턴스를 가질 때는 사이클이 있어도 데드락이 아닐 수 있습니다.

예방(Prevention)은 설계 단계에서 4조건 중 하나를 원천 제거하고, 회피(Avoidance)는 요청마다 안전 상태를 검사합니다.

탐지(Detection)는 발생 후 복구하고, 무시(Ignorance)는 발생 빈도가 낮다고 판단해 처리하지 않습니다. 각 전략의 트레이드오프를 탭으로 비교해 보세요.

은행가 알고리즘(Banker's Algorithm)은 Dijkstra가 1965년 고안한 대표적인 데드락 회피 알고리즘입니다. OS가 자원 요청을 받을 때 "이 요청을 허용해도 모든 프로세스가 결국 완료될 수 있는가"를 시뮬레이션합니다.

안전 상태(Safe State)란 현재 할당 상태에서 모든 프로세스가 순서대로 완료될 수 있는 안전 순열(Safe Sequence)이 하나라도 존재하는 상태입니다.

아래에서 탐색 과정을 직접 확인해 보세요.

실제 멀티스레드 코드에서 데드락은 주로 두 스레드가 서로 다른 순서로 락을 획득할 때 발생합니다. 가장 간단하고 효과적인 해결책은 Lock Ordering — 항상 동일한 순서로 락을 획득하는 것입니다.

tryLock()을 사용하면 락 획득 실패 시 바로 포기하고 재시도하는 방식으로도 회피할 수 있습니다.

세 가지 시나리오를 탭으로 비교해 보세요.

데이터베이스에서도 데드락은 자주 발생합니다. 두 트랜잭션이 서로 상대방이 잠근 행(row lock)을 기다리는 상황입니다. MySQL InnoDB는 Wait-for Graph를 주기적으로 검사하여 사이클을 탐지하고, 비용이 적은 트랜잭션을 자동으로 희생자(victim)로 선택해 롤백합니다.

애플리케이션 레벨에서는 항상 동일한 순서로 테이블/행에 접근하거나, 트랜잭션을 짧게 유지하거나, SELECT ... FOR UPDATE로 선제적 잠금을 거는 방식으로 예방할 수 있습니다.