데드락

둘 이상이 서로가 쥔 것을 기다리다 아무도 나아가지 못하는 상태입니다. 각자 자기 것은 놓지 않은 채 상대가 놓아 주기를 기다립니다. 밖에서 끼어들어 하나를 빼앗거나 한쪽을 되돌리기 전까지는 그대로 멈춰 있습니다. 한국어로는 교착 상태라고도 부릅니다.

상세

1971년 Coffman·Elphick·Shoshani 의 논문 System Deadlocks 가 이 상태를 정의합니다. 서로 다른 태스크들이 낸 자원 요청이 어떤 순서로 승인되면, 두 개 이상의 태스크로 이루어진 무리가 나아가지 못하게 될 수 있다는 것입니다. 그 무리에 속한 태스크는 저마다 자원을 독점한 채, 같은 무리의 다른 태스크가 지금 쥐고 있는 자원이 풀리기를 기다립니다.

논문은 이어서 못을 박습니다. 기다리는 것 말고 일시적인 대안조차 없다면 그 태스크들은 데드락에 빠져 영영 나아가지 못한다는 것입니다. 멈춤이 오래 가는 것이 아니라, 밖에서 개입하지 않는 한 끝이 없습니다.

자원이 무엇인지는 정해져 있지 않습니다. 오라클 자바 튜토리얼은 스레드 두 개 이상이 서로를 기다리며 영원히 블록된 상황을 데드락이라고 적습니다. PostgreSQL 문서는 두 개 이상의 트랜잭션이 각각 상대가 원하는 락을 쥔 상태를 데드락이라고 적습니다. 잠기는 것이 자바 객체든 테이블의 한 행이든 형태만 다르고, 서로가 쥔 것을 기다린다는 자리는 같습니다.

PostgreSQL 문서는 명시적 잠금을 쓰면 데드락 가능성이 커질 수 있다고 적으면서, 로우 수준 락의 결과로도 데드락이 일어날 수 있다는 것을 따로 짚습니다. 명시적 잠금을 한 줄도 쓰지 않아도 일어날 수 있다는 뜻입니다.

발생 조건

Coffman 논문은 데드락이 선 자리에서 다음 네 조건이 모두 작동하고 있었다고 적습니다. 그리고 이 조건들의 존재가 데드락 상태를 사실상 정의한다고 적습니다.

둘째 조건에 이 논문이 붙인 이름은 wait for 입니다.

넷째 조건이 그리는 고리는 태스크 둘일 때 가장 작습니다.

flowchart TD
    T1["태스크 하나"] -->|쥐고 있다| A["자원 A"]
    T2["태스크 둘"] -->|쥐고 있다| B["자원 B"]
    T1 -.->|기다린다| B
    T2 -.->|기다린다| A

태스크 하나는 자원 A 를 쥔 채 자원 B 를 기다리고, 태스크 둘은 자원 B 를 쥔 채 자원 A 를 기다립니다. 화살표를 따라가면 출발한 자리로 돌아옵니다. 고리가 닫혀 있으므로 누구도 먼저 놓지 못합니다.

넷이 함께 서야 데드락입니다. 논문은 데드락 가능성을 미리 배제하도록 시스템을 설계하려면 모든 시점에 필요조건 가운데 적어도 하나가 성립하지 않도록 보장해야 한다고 적습니다. 거꾸로 읽으면 하나만 무너뜨려도 이 상태는 서지 않습니다.

실제로 어느 칸을 무너뜨리는지도 문서에 적혀 있습니다. PostgreSQL 문서가 데드락을 피하는 방어책으로 첫손에 꼽는 것은, 데이터베이스를 쓰는 모든 애플리케이션이 여러 객체에 락을 잡을 때 일관된 순서로 잡게 만드는 것입니다. 모두가 같은 순서로 잡으면 고리의 마지막 칸이 닫히지 않으므로 넷째 조건이 서지 않습니다. 문서는 이것을 대체로 그렇다는 정도로 적습니다.

예시

PostgreSQL 의 두 트랜잭션

PostgreSQL 문서가 로우 수준 락만으로 데드락이 나는 자리로 든 예제입니다. 같은 accounts 테이블의 두 행을 두 트랜잭션이 반대 순서로 잠급니다.

-- 트랜잭션 하나
UPDATE accounts SET balance = balance + 100.00 WHERE acctnum = 11111;

-- 트랜잭션 둘
UPDATE accounts SET balance = balance + 100.00 WHERE acctnum = 22222;
UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 11111;

-- 트랜잭션 하나
UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 22222;

sequenceDiagram
    participant A as 트랜잭션 하나
    participant R1 as 11111 행
    participant R2 as 22222 행
    participant B as 트랜잭션 둘
    A->>R1: UPDATE · 락을 얻는다
    B->>R2: UPDATE · 락을 얻는다
    B->>R1: UPDATE · 기다린다
    A->>R2: UPDATE · 기다린다

첫 문장이 acctnum = 11111 행에 로우 수준 락을 얻습니다. 트랜잭션 둘의 첫 문장은 acctnum = 22222 행의 락을 얻어 그 행을 고칩니다. 둘째 문장은 고치려는 행이 이미 잠겨 있는 것을 발견하고, 락을 얻은 트랜잭션이 끝나기를 기다립니다. 이제 트랜잭션 둘이 트랜잭션 하나를 기다립니다. 그다음 트랜잭션 하나가 acctnum = 22222 행의 락을 잡으려 하지만 잡지 못합니다. 트랜잭션 둘이 이미 그 락을 쥐고 있기 때문입니다. 트랜잭션 하나가 트랜잭션 둘을 기다리고 트랜잭션 둘이 트랜잭션 하나를 기다립니다. 문서는 이것을 데드락 조건이라고 부르고, PostgreSQL 이 이 상황을 감지해 트랜잭션 가운데 하나를 중단시킨다고 적습니다.

중단된 쪽이 받는 값도 문서에 있습니다. PostgreSQL 의 에러 코드 부록은 Class 40 — Transaction Rollback 아래에 40P01 deadlock_detected 를 둡니다.

MySQL InnoDB 의 두 세션

성격이 다른 둘째 예입니다. 앞의 예제가 쓰기 락 두 개를 엇갈리게 잡았다면, 이쪽은 공유 락을 먼저 잡아 두고 서로의 배타 락을 요구합니다. MySQL 문서에 실린 예제입니다.

-- 준비
SET GLOBAL innodb_print_all_deadlocks = ON;
CREATE TABLE Animals (name VARCHAR(10) PRIMARY KEY, value INT) ENGINE = InnoDB;
CREATE TABLE Birds   (name VARCHAR(10) PRIMARY KEY, value INT) ENGINE = InnoDB;
INSERT INTO Animals (name,value) VALUES ("Aardvark",10);
INSERT INTO Birds   (name,value) VALUES ("Buzzard",20);

-- 세션 A
START TRANSACTION;
SELECT value FROM Animals WHERE name='Aardvark' FOR SHARE;
UPDATE Birds SET value=40 WHERE name='Buzzard';

-- 세션 B
START TRANSACTION;
SELECT value FROM Birds WHERE name='Buzzard' FOR SHARE;
UPDATE Animals SET value=30 WHERE name='Aardvark';

세션 B 는 Birds 에 공유 락을 쥔 채 Animals 의 배타 락을 기다리고, 세션 A 는 Animals 에 공유 락을 쥔 채 Birds 의 배타 락을 기다립니다. 순환 대기가 서므로 InnoDB 가 이를 감지해 한쪽을 롤백합니다. 그때 클라이언트가 받는 메시지는 이렇습니다.

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

자바 스레드 둘

데이터베이스도 트랜잭션도 없이 스레드 둘만으로 같은 일이 납니다. 오라클 자바 튜토리얼의 예제입니다.

public synchronized void bow(Friend bower) {
    System.out.format("%s: %s has bowed to me!%n", this.name, bower.getName());
    bower.bowBack(this);
}
public synchronized void bowBack(Friend bower) {
    System.out.format("%s: %s has bowed back to me!%n", this.name, bower.getName());
}

두 객체가 서로에게 bow 를 부릅니다. 두 메서드 모두 synchronized 라 자기 객체의 락을 쥐어야 들어갈 수 있고, bow 는 자기 락을 쥔 채로 상대의 bowBack 을 부릅니다. 튜토리얼은 이 프로그램을 돌리면 두 스레드가 bowBack 을 부르려 할 때 둘 다 블록될 가능성이 아주 크다고 적습니다. 그리고 어느 블록도 끝나지 않는다고 적습니다. 각 스레드가 상대가 bow 에서 빠져나오기를 기다리기 때문입니다.

경계

락을 오래 기다려 멈춘 것처럼 보이면 데드락인가. 아닙니다.

PostgreSQL 은 이 둘을 시간으로 갈라 놓습니다. deadlock_timeout 은 데드락 조건이 있는지 검사하기 전에 락을 기다리는 시간입니다. 문서는 데드락 검사가 상대적으로 값이 비싸서 서버가 락을 기다릴 때마다 검사를 돌리지는 않는다고 적습니다. 운영 애플리케이션에서 데드락이 흔하지 않다고 낙관적으로 가정하고, 검사에 들어가기 전에 얼마간 그냥 락을 기다린다는 것입니다. 기본값은 1초입니다. 문서는 이 값이 전형적인 트랜잭션 시간을 넘어서는 것이 이상적이라고 적습니다. 그래야 기다리는 쪽이 데드락 검사를 결심하기 전에 락이 풀릴 확률이 올라가기 때문입니다. 상대가 언젠가 끝나면 풀리는 대기는 발생 조건의 넷째 칸이 서지 않습니다. 기다림이 길다는 것만으로는 고리가 닫히지 않습니다.

라이브락은 데드락인가. 아닙니다.

오라클 자바 튜토리얼은 한 스레드가 다른 스레드의 동작에 반응해 움직이고 그 다른 스레드의 동작 또한 누군가에 대한 반응일 때 라이브락이 생길 수 있다고 적습니다. 데드락과 마찬가지로 라이브락에 걸린 스레드도 더 나아가지 못합니다. 다만 문서는 이 스레드들이 블록되어 있지 않다고 못 박습니다. 서로에게 반응하느라 너무 바빠서 일을 재개하지 못할 뿐입니다. 문서가 든 비유는 복도에서 마주친 두 사람입니다. 알퐁스가 가스통을 지나가게 하려고 왼쪽으로 비키고 가스통은 알퐁스를 지나가게 하려고 오른쪽으로 비킵니다. 여전히 서로를 막고 있는 것을 보고 알퐁스는 오른쪽으로, 가스통은 왼쪽으로 움직입니다. 발생 조건의 둘째 칸이 서지 않습니다. 자원을 쥔 채 멈춰 기다리는 것이 아니라 계속 움직이고 있습니다.

관련 항목

기다림을 만드는 잠금·동시성 개념

락 · 테이블 · 로우 수준 잠금 · 테이블 수준 잠금 · 어드바이저리 락 · 트랜잭션 · 격리 · 비관적 잠금 · MVCC(Multiversion Concurrency Control, 다중 버전 동시성 제어) · SELECT FOR UPDATE · SELECT FOR SHARE · 스레드

데드락을 이루는 조건

상호 배제 · 점유한 채 대기 · 비선점 · 순환 대기

조건을 표현하는 이론 개념

상태 그래프 · P and V 연산

데드락 예제가 나오는 플랫폼

PostgreSQL · MySQL · InnoDB · 오라클 · 자바 · 세션

데드락과 맞세워지는 대립 개념

라이브락 · 기아

데드락 검사를 조절하는 설정

deadlock_timeout · innodb_print_all_deadlocks

터졌을 때 보이는 값

40P01 · deadlock_detected · 40001 · 1213 · 롤백