deadlock이 무엇인지 설명해 주세요

Deadlock의 네 가지 필요 조건은 각각 무엇인가요?

네 조건이 모두 동시에 충족될 때만 deadlock이 발생합니다. 하나라도 깨지면 deadlock은 일어나지 않습니다.

상호 배제(mutual exclusion): 자원을 한 번에 하나의 작업만 점유할 수 있습니다. lock이나 프린터처럼 공유 불가능한 자원에서 성립합니다.
점유와 대기(hold and wait): 자원을 하나 이상 점유한 채 다른 자원을 기다립니다. thread A가 lock 1을 잡고 lock 2를 기다리는 상태입니다.
비선점(no preemption): 점유 중인 자원을 강제로 빼앗을 수 없습니다. 자원을 가진 thread가 스스로 놓아야 합니다.
순환 대기(circular wait): 작업들이 원형으로 서로의 자원을 기다립니다. A→B→C→A처럼 기다림이 순환합니다.

예방 전략은 이 조건 중 하나를 깨는 방식으로 접근합니다. lock 순서를 강제하면 순환 대기를, 자원을 한꺼번에 요청하면 점유와 대기를 깰 수 있습니다.

화장실 비유로 네 조건을 대입하면:

상호 배제: 화장실 칸은 한 명만 쓸 수 있습니다.
점유와 대기: 1칸에 들어가 잠근 채로, 2칸이 비길 기다립니다.
비선점: 안에 있는 사람을 강제로 끌어낼 수 없습니다. 스스로 나올 때까지 기다려야 합니다.
순환 대기: A는 B가 쓰는 칸을 기다리고, B는 A가 쓰는 칸을 기다립니다.

네 조건이 동시에 성립해야 deadlock이 생기는 이유는, 하나라도 깨지면 순환이 불가능하기 때문입니다. 예를 들어 비선점 조건을 깨면(강제 선점 허용) OS가 자원을 강제로 회수해 순환을 끊을 수 있습니다. DB의 deadlock victim 선택이 이 방식입니다.

lock 순서를 고정하면 왜 deadlock을 막을 수 있나요?

순환 대기 조건을 깨기 때문입니다. 모든 thread가 항상 같은 순서로 lock을 획득하면 어떤 thread도 앞 순서 lock을 가진 채 뒤 순서 lock을 기다리는 일이 없어 순환이 생기지 않습니다.

나쁜 예:
Thread A: lock(user) → lock(order)
Thread B: lock(order) → lock(user)  ← 순서가 다름
 
좋은 예:
Thread A: lock(user) → lock(order)
Thread B: lock(user) → lock(order)  ← 항상 user 먼저

실무에서 여러 자원을 잡아야 할 때는 자원에 고유한 순번을 부여하고 낮은 번호부터 획득하는 것이 일반적입니다.

왜 순서 고정이 순환을 깨는지 논리적으로 보면, 모든 자원에 전순서(total order)를 부여하면 "A가 B보다 큰 번호의 자원을 잡고 B보다 작은 번호를 기다린다"는 상황이 불가능해집니다. 항상 낮은 번호 → 높은 번호 방향으로만 획득하면, 그래프에 역방향 엣지가 생길 수 없어 사이클 자체가 만들어지지 않습니다.

화장실 비유로는, 모든 사람이 "반드시 1번 칸이 비어야 2번 칸에 들어간다"는 규칙을 따르면, 1번을 기다리는 사람이 2번을 잡고 있는 일이 없어집니다. 순서가 일방통행이 되면 순환이 성립하지 않습니다.

timeout을 쓰면 deadlock을 해결할 수 있나요?

완전한 해결이 아닌 복구 전략입니다. 일정 시간 lock을 얻지 못하면 이미 잡은 lock을 풀고 나중에 재시도하면 deadlock 상태에서 빠져나올 수 있습니다.

단점이 있습니다. 재시도가 동시에 일어나면 같은 deadlock이 재현될 수 있어 jitter(무작위 대기 시간)를 추가해야 합니다. 또한 부분적으로 완료된 작업을 rollback하는 로직도 함께 설계해야 합니다.

분산 시스템에서는 완벽한 deadlock detection이 어렵기 때문에 timeout이 주요 수단이 됩니다. 각 노드의 lock 상태를 중앙에서 실시간으로 파악하는 것 자체가 네트워크 비용이 크고, 네트워크 지연과 실제 deadlock을 구분하기도 어렵습니다.

재시도 시 동시에 같은 순서로 lock을 잡으려 하면 deadlock이 재현됩니다. exponential backoff + jitter 패턴으로 재시도 간격을 점점 늘리고 무작위 대기를 추가해 충돌 확률을 낮춥니다. AWS SDK, 대부분의 DB 클라이언트가 이 패턴을 씁니다.

OS나 DB는 deadlock을 어떻게 감지하나요?

wait-for graph로 순환을 탐지합니다. 어떤 작업이 어떤 작업의 자원을 기다리는지 방향 그래프로 표현하고, 주기적으로 사이클을 탐색합니다.

MySQL InnoDB는 트랜잭션 간 lock 대기 관계를 추적해 deadlock을 감지하면 롤백 비용이 적은 트랜잭션을 victim으로 선택해 강제 롤백합니다. PostgreSQL도 유사하게 deadlock detector를 백그라운드에서 실행합니다. 애플리케이션은 deadlock으로 중단된 쿼리를 받으면 재시도해야 합니다.

wait-for graph에서 사이클 탐지는 DFS로 구현합니다. 노드는 트랜잭션, 엣지는 "A가 B의 lock을 기다린다"는 관계입니다. DFS 중 이미 방문한 노드를 다시 만나면 사이클이 존재합니다.

MySQL InnoDB는 victim을 선택할 때 롤백 비용이 기준입니다. 주로 수정한 행 수가 적은 트랜잭션을 victim으로 고릅니다. 되돌릴 게 적을수록 손해가 작기 때문입니다. innodb_deadlock_detect 설정으로 감지를 끄고 lock timeout에만 의존할 수도 있는데, 고트래픽 환경에서 감지 자체의 lock 경합이 문제가 될 때 씁니다.

Deadlock, starvation, livelock은 어떻게 다른가요?

세 가지 모두 진행이 막히는 문제지만 원인이 다릅니다.

Deadlock: 서로 자원을 잡고 기다려 아무도 진행하지 못하는 상태. 외부 개입 없이 스스로 해소되지 않습니다.
Starvation: 특정 작업이 계속 우선순위에서 밀려 자원을 얻지 못하는 상태. 다른 작업들은 진행됩니다. 우선순위 기반 스케줄러에서 낮은 우선순위 thread가 영원히 실행되지 못하는 경우가 예입니다.
Livelock: 서로 상대방에게 양보하느라 상태가 계속 변하지만 실제 진전이 없는 상태. 복도에서 마주친 두 사람이 같은 방향으로 계속 비켜주는 상황과 비슷합니다.

Deadlock은 완전히 멈추고, livelock은 바쁘지만 진전이 없으며, starvation은 일부만 진행됩니다.

livelock의 실제 예는 이더넷의 CSMA/CD 프로토콜입니다. 두 장치가 동시에 데이터를 보내다 충돌을 감지하면 각자 잠깐 기다렸다가 재시도합니다. 만약 둘이 정확히 같은 시간만큼 기다리면 또 동시에 전송해 또 충돌합니다. 상태는 계속 변하지만 데이터는 전달되지 않습니다. 이를 막기 위해 각 장치가 무작위 시간을 기다리는 exponential backoff를 씁니다.

starvation은 aging으로 해결합니다. 오래 기다린 작업의 우선순위를 점진적으로 높여, 결국 실행될 기회를 보장합니다. 반대로 deadlock은 aging으로 해결할 수 없습니다. 우선순위와 무관하게 자원을 서로 잡고 있어 순환 자체가 문제이기 때문입니다.