데드락 — 서로가 서로를 기다리다 멈추다

앞 편의 자물쇠들은 공유 자원을 보호하지만, 여럿을 잘못 쓰면 새로운 재앙을 부른다 — **데드락(교착 상태)**이다. A가 자물쇠 1을 쥔 채 자물쇠 2를 기다리고, B가 자물쇠 2를 쥔 채 자물쇠 1을 기다리면 — 둘 다 영원히 멈춘다. 누구도 양보하지 않으니 시간이 흘러도 안 풀린다. 좁은 다리에서 마주 온 두 차가 서로 안 물러나는 것과 같다. 데드락이 언제 생기고, 어떻게 막는지를 본다.

네 가지가 모두 모일 때 — Coffman 조건

데드락은 아무 때나 생기지 않는다. 네 가지 조건이 동시에 충족돼야만 생긴다(Coffman 조건). ① 상호 배제 — 자원을 한 번에 하나만 쓸 수 있다. ② 점유와 대기(hold and wait) — 이미 하나를 쥔 채 다른 걸 기다린다. ③ 비선점(no preemption) — 쥔 자원을 강제로 뺏을 수 없다(자발적 반납만). ④ 순환 대기(circular wait) — A→B→C→A처럼 기다림이 고리를 이룬다.

다이어그램 로딩 중…

중요한 건 — 이 넷이 모두 있어야 데드락이라는 점이다. 그래서 넷 중 하나만 깨도 데드락은 안 생긴다 — 이게 모든 대응의 출발점이다. (출처: Coffman conditions.)

어떻게 다루나 — 예방·회피·탐지·무시

데드락 대응은 네 갈래다. **예방(prevention)**은 네 조건 중 하나를 원천적으로 못 생기게 한다. 가장 실용적인 게 순환 대기 깨기 — 모든 스레드가 자원을 항상 같은 순서로 잠그게 하면 고리가 안 생긴다(A도 B도 락1 먼저, 락2 나중이면 서로 엇갈릴 일이 없다). *"여러 자원을 잠글 땐 락 순서를 일관되게"*가 바로 이 예방의 실천이다. **회피(avoidance)**는 실행 중에 — 이 요청을 들어주면 데드락 위험이 있나를 미리 계산해, 안전한(safe) 상태가 유지될 때만 자원을 준다(은행원 알고리즘: 모두가 최대치를 요구해도 끝낼 수 있는지 확인). **탐지(detection)**는 일단 허용하고, 주기적으로 자원 할당 그래프에 고리가 생겼나 검사해 — 발견하면 일부를 강제 종료·롤백해 푼다(DB가 흔히 이 방식: 데드락을 감지해 한 트랜잭션을 희생시킨다). 마지막으로 무시(타조 알고리즘) — 아주 드물면 그냥 두고, 나면 재시작한다(많은 OS의 현실적 선택). (출처: Deadlock prevention/avoidance/detection.)

사촌들 — 라이브락과 우선순위 역전

데드락과 헷갈리는 사촌이 둘 있다. **라이브락(livelock)**은 — 멈추진 않는데 진행도 못 하는 상태다. 좁은 복도에서 마주친 둘이 서로 같은 방향으로 비키기를 반복하며 영영 못 지나가는 것과 같다(데드락 회피를 어설프게 짜면 생긴다). **우선순위 역전(priority inversion)**은 — 높은 우선순위 작업이 낮은 우선순위 작업이 쥔 락을 기다리는데, 그 사이 *중간 우선순위 작업이 낮은 작업을 선점*해 — 높은 작업이 사실상 중간 작업에 막히는 역설이다(화성 탐사선 Pathfinder의 유명한 버그). 해법은 우선순위 상속 — 높은 작업이 기다리는 동안 락을 쥔 낮은 작업의 우선순위를 잠시 올려 빨리 끝내게 한다. (출처: Priority inversion.)

실무에서는 — 데이터베이스의 데드락(여러 행을 잠글 때 순서 일관·짧은 트랜잭션·재시도)이 바로 이 OS 데드락이 데이터 계층에 그대로 나타난 것이다. 임베디드·실시간 시스템(RTOS)에서는 우선순위 역전과 상속이 핵심 주제다. 결국 데드락 대응의 왕도는 — *예방(특히 락 순서 일관)*으로 애초에 고리를 안 만드는 것이고, 못 막으면 짧은 보유·재시도로 충돌을 작게 만드는 것이다.

실제로 눈으로 보기

데드락을 일부러 만든다

#include <pthread.h>
#include <unistd.h>

pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t B = PTHREAD_MUTEX_INITIALIZER;

void *t1(void *_) {
    pthread_mutex_lock(&A); sleep(1);      // A 를 잡고
    pthread_mutex_lock(&B);                // B 를 기다린다
    pthread_mutex_unlock(&B); pthread_mutex_unlock(&A);
    return NULL;
}
void *t2(void *_) {
    pthread_mutex_lock(&B); sleep(1);      // B 를 잡고
    pthread_mutex_lock(&A);                // A 를 기다린다  ← 순환 대기 완성
    pthread_mutex_unlock(&A); pthread_mutex_unlock(&B);
    return NULL;
}

sleep(1)이 핵심이다. 없으면 대부분 데드락이 안 난다 — 한쪽이 너무 빨리 끝나 겹치지 않기 때문이다. 실무의 데드락이 부하가 몰릴 때만 나타나는 이유가 이것이다. 타이밍이 맞아야 네 조건이 동시에 성립한다.

멈춘 프로세스가 어디서 멈췄나

ps -eo pid,stat,wchan:25,comm
#  PID STAT WCHAN                     COMMAND
# 8123 Sl+  futex_wait_queue          a.out      ← 락을 기다리는 중

cat /proc/8123/task/*/stack 2>/dev/null   # 커널 스택 (권한 필요)

wchan이 커널 안 어디서 자고 있는지를 알려 준다. futex_wait이면 사용자 공간 락 대기다.

gdb -p 8123 -batch -ex "thread apply all bt" 2>/dev/null | head -20
# Thread 3 (LWP 8125):
# #0  futex_wait () at ...
# #1  __GI___pthread_mutex_lock (mutex=0x555555558060 <B>) ...
# #2  t1 () at deadlock.c:9
# Thread 2 (LWP 8124):
# #1  __GI___pthread_mutex_lock (mutex=0x555555558020 <A>) ...
# #2  t2 () at deadlock.c:15

두 스레드가 서로 다른 뮤텍스를 기다리고 있다는 것이 스택에 그대로 나온다. 데드락 진단의 표준 절차가 이것이다 — 모든 스레드의 스택을 떠서, 서로가 서로를 기다리는 고리를 찾는다.

예방이 가장 실용적이다

// 락에 전역 순서를 정하고 항상 그 순서로 잡는다 — 순환 대기가 성립할 수 없다
void transfer(Account *from, Account *to, long amt) {
    Account *first  = from->id < to->id ? from : to;    // 주소나 ID 로 순서 고정
    Account *second = from->id < to->id ? to   : from;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    ...
}

네 조건 중 순환 대기를 깨는 것이 가장 싸다. 상호 배제는 없앨 수 없고, 비선점을 깨려면 롤백이 필요하며, 점유와 대기를 없애려면 한 번에 다 잡아야 한다. 반면 순서를 정하는 것은 규칙 하나로 끝난다.

// 타임아웃 — 영원히 기다리지 않는다
struct timespec ts = { .tv_sec = time(NULL) + 2 };
if (pthread_mutex_timedlock(&B, &ts) != 0) {
    pthread_mutex_unlock(&A);       // 물러섰다가 다시 시도한다
}

물러설 때 무작위 지연을 넣지 않으면 둘이 동시에 물러났다 동시에 재시도해 계속 부딪힌다 — 그것이 라이브락이다.

정리하면, 데드락은 상호 배제·점유와 대기·비선점·순환 대기 네 조건이 모두 모일 때 생기는 상호 교착이다 — 그래서 넷 중 하나만 깨면 막을 수 있다(가장 실용적인 건 락 순서 일관으로 순환 대기 깨기). 대응은 예방·회피(은행원)·탐지(DB)·무시(타조) 네 갈래이고, 사촌인 *라이브락(진행 없는 분주함)*과 *우선순위 역전(상속으로 해결)*도 함께 알아 둔다. 이 모든 동시성 이야기 — 경쟁 조건·자물쇠·데드락 — 는 스레드가 자원을 공유하기에 생긴다. 다음은 그 자원 중 가장 중요한 것, 메모리를 OS가 어떻게 속이는지다.