24. 두 엔티티 상호작용의 락 획득 순서 (ABBA 데드락)

난이도 최상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 두 엔티티 상호작용의 락 획득 순서 (ABBA 데드락)

난이도: 최상

답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계

요약

두 락을 인자 순서대로 잡는다. (A) a.Lock → (B) b.Lock. 스레드1 이 Link(x, y) 를, 스레드2 가 Link(y, x) 를 동시에 호출하면, 스레드1 은 x 를 잡고 y 를 기다리고, 스레드2 는 y 를 잡고 x 를 기다린다 → ABBA 교착(데드락). 두 락 사이의 DoSomeWork() 가 창을 넓혀 재현이 쉬워진다. 게다가 자기 자신(a == b)에 대해서도 같은 락을 두 번 잡는데, C# lock 은 재진입 가능이라 이 경우는 멈추지 않지만(주의: 다른 동기화 도구면 자기 교착) 의미상 검증이 필요하다. 정답 한 줄: 모든 코드가 락을 "전역적으로 동일한 순서"(예: Id 오름차순)로 획득하게 만들어 순환 대기를 원천 차단하라.

변별: problem8(ReaderWriterLockSlim 쓰기 기아/재진입)·problem9(락프리 스택 ABA)와 달리, 본 문제는 다중 락의 획득 순서로 인한 순환 대기(데드락) — 락 계층/전순서가 핵심이다.

문제점

(A)(B) 인자 순서 기반 락 획득 — 순환 대기/데드락 (동시성) ★간판

분류 태그: lock-ordering deadlock / ABBA / circular wait.
증상: 양방향 동시 호출 시 두 스레드가 서로가 쥔 락을 영원히 기다린다. 해당 워커 스레드가 묶이고, 그 락에 의존하는 다른 요청까지 연쇄로 멈춘다(전역 장애로 번질 수 있음).
재현 조건: 같은 두 엔티티에 대해 반대 방향((x,y) 와 (y,x))으로 동시 진입. 두 락 사이의 작업이 길수록 확률↑.
근본 원인: 데드락 4조건 중 순환 대기(circular wait) 를 깨지 못함. 락 획득에 전역적 전순서(total order)가 없다.

(보강) 자기 자신/유효성

분류 태그: self-interaction / validation.
증상: a == b 면 같은 락을 두 번 — C# lock(Monitor)은 재진입 가능이라 통과하지만, 비재진입 동기화(SemaphoreSlim 등)였다면 자기 교착. 의미상 자기 링크는 보통 거부해야 한다.

수정안 (정확한 코드)

전역 락 순서를 강제한다. 두 락을 항상 Id 오름차순으로 획득(Id 동률이면 객체 식별자로 타이브레이크). 그러면 어떤 호출이든 같은 순서로 잡아 순환이 불가능하다.

public void Link(Entity a, Entity b)
{
    if (ReferenceEquals(a, b)) return;          // 자기 자신 거부(또는 단일 락 처리)

    // 전역 전순서: Id 오름차순. Id 동률 시 RuntimeHelpers 로 타이브레이크.
    Entity first = a, second = b;
    if (a.Id > b.Id ||
        (a.Id == b.Id &&
         System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(a)
         > System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(b)))
    {
        first = b; second = a;
    }

    lock (first.Lock)
    {
        DoSomeWork();
        lock (second.Lock)
        {
            a.Bond++;
            b.Bond++;
        }
    }
}

핵심: 인자 순서가 아니라 객체의 전역 순서로 락을 잡는다. 스레드1·스레드2 모두 Id 작은 쪽을 먼저 잡으므로 순환 대기가 성립하지 않는다.

대안: 한 쌍을 보호하는 단일 락(pair lock)으로 묶거나, 상호작용을 단일 스레드/큐로 직렬화하면 다중 락 자체가 사라진다.

더 나은 설계 (+ 트레이드오프)

락 계층(lock hierarchy): 자원에 레벨을 부여하고 "낮은 레벨 → 높은 레벨" 순서만 허용. 디버그 빌드에서 순서 위반을 어서션으로 잡는다. 트레이드오프: 규율/도구 필요.
try-lock + 백오프: Monitor.TryEnter 로 둘째 락 획득 실패 시 첫째를 놓고 재시도(라이브락 방지를 위해 랜덤 백오프). 순서 강제가 어려운 동적 상황에 유효(트레이드오프: 복잡·기아).
상호작용 직렬화: 두 엔티티가 속한 존/룸을 한 스레드가 소유하면 락 없이 순차 처리. 크로스-존 상호작용은 메시지로(트레이드오프: 지연).
락 보유 중 외부 호출 금지: 두 락을 쥔 채 콜백/네트워크/DB 호출을 하면 데드락·지연이 급증. 임계영역을 짧게.

면접 포인트

데드락 4조건과 그중 실무에서 가장 잘 깨는 것 — 순환 대기 제거(전역 락 순서). 왜 "Id 같은 키로 정렬"이 정답인지 설명.
C# lock(Monitor)은 재진입 가능, SemaphoreSlim 은 아님 — 자기 교착 차이. 두 락 사이의 작업을 줄여 창을 좁히는 것도 완화책(근본은 순서).
try-lock+백오프 vs 전순서의 트레이드오프(라이브락/기아 위험), 그리고 "락 쥐고 외부 호출 금지" 원칙.

해설 · C++

해설 — 두 엔티티 상호작용의 락 획득 순서 (ABBA 데드락) (C++)

난이도: 최상

답변 프레임워크: 요약 → 문제 분류 → 원인 → 수정안 → 더 나은 설계

요약

두 std::mutex 를 인자 순서대로 잡는다. (A) a.m → (B) b.m. Link(x, y) 와 Link(y, x) 가 동시에 들어오면 ABBA 데드락. C++ std::mutex 는 비재귀(non-recursive) 라, 자기 자신(&a == &b)에 대해 호출하면 같은 뮤텍스를 두 번 잠가 즉시 자기 교착(UB/데드락) — C# lock(재진입 가능)과 결정적으로 다른 지점이다. 정답 한 줄: std::scoped_lock(a.m, b.m)(데드락 회피 알고리즘) 또는 전역 락 순서(주소/Id)로 순환 대기를 차단하고, 자기 자신 호출을 먼저 걸러라.

변별: problem5/9(메모리 순서·ABA)와 달리, 본 문제는 다중 뮤텍스의 획득 순서/순환 대기가 핵심. C++ 트윈은 비재귀 뮤텍스의 자기 교착까지 드러낸다.

문제점

(A)(B) 인자 순서 락 획득 — ABBA 데드락 (동시성) ★간판

분류 태그: lock-ordering deadlock / circular wait.
증상: 양방향 동시 호출 시 두 스레드가 서로의 뮤텍스를 영원히 대기. 워커가 묶이고 연쇄 정지.
재현 조건: (x,y) 와 (y,x) 동시 진입. DoSomeWork() 가 창을 넓힘.
근본 원인: 락 획득에 전역 전순서가 없어 순환 대기가 성립.

(자기 자신) 비재귀 뮤텍스 이중 잠금 — 자기 교착 (동시성/UB) ★간판

분류 태그: self-deadlock / non-recursive mutex relock (UB).
증상: &a == &b 면 a.m 을 잡은 뒤 b.m(=같은 뮤텍스)을 또 잠가 멈춘다. 표준상 같은 스레드가 보유한 비재귀 뮤텍스 재잠금은 UB.
근본 원인: 자기 상호작용을 거르지 않음 + 뮤텍스가 비재귀.

수정안 (정확한 코드)

std::scoped_lock 의 데드락 회피(여러 뮤텍스를 한 번에, 순서 무관하게 안전 획득)를 쓰고, 자기 자신은 먼저 처리한다.

#include <mutex>

void Link(Entity& a, Entity& b)
{
    if (&a == &b)            // 자기 자신: 단일 락으로 처리(또는 거부)
    {
        std::lock_guard<std::mutex> l(a.m);
        a.bond += 2;         // 의미에 맞게
        return;
    }

    // 두 뮤텍스를 데드락 없이 동시 획득(C++17)
    std::scoped_lock lk(a.m, b.m);   // 내부적으로 std::lock 의 회피 알고리즘 사용
    a.bond++;
    b.bond++;
}

또는 명시적 전순서(주소/Id 기준)로:

void Link(Entity& a, Entity& b)
{
    if (&a == &b) { std::lock_guard<std::mutex> l(a.m); a.bond += 2; return; }
    Entity* first  = a.id <= b.id ? &a : &b;
    Entity* second = a.id <= b.id ? &b : &a;
    std::lock_guard<std::mutex> l1(first->m);
    std::lock_guard<std::mutex> l2(second->m);
    a.bond++; b.bond++;
}

핵심: std::scoped_lock/std::lock 은 여러 뮤텍스를 순환 대기 없이 획득한다(둘 다 못 잡으면 잡은 것을 놓고 재시도). 전역 순서 방식도 동일 효과. 자기 자신은 단일 락으로.

주의: DoSomeWork() 가 두 락 사이에 꼭 필요하면 scoped_lock 으로 한 번에 잡은 뒤 임계영역 안에서 호출하되, 락을 쥔 채 블로킹/네트워크/콜백 호출은 피한다.

더 나은 설계 (+ 트레이드오프)

std::scoped_lock 기본 채택: 다중 락은 거의 항상 이걸로. 명시적 순서가 필요하면 주소/Id.
락 계층 + 디버그 검증: 자원 레벨을 정의하고 역순 획득을 디버그에서 어서션.
상호작용 직렬화: 두 엔티티의 소유 스레드/큐로 순차 처리 → 다중 락 제거(트레이드오프: 크로스-스레드 지연).
임계영역 최소화: 락 보유 중 외부 호출 금지. 비재귀 뮤텍스를 기본으로(재귀 뮤텍스는 설계 냄새일 때가 많다).

면접 포인트

std::scoped_lock/std::lock 이 데드락을 어떻게 피하는가(all-or-nothing 시도+백오프), 그리고 전역 락 순서와의 관계.
std::mutex 는 비재귀 → 같은 스레드 재잠금 UB. std::recursive_mutex 는 보통 설계 냄새.
데드락 4조건 중 순환 대기를 깨는 게 실무 정석. 락 쥐고 외부 호출 금지, 임계영역 최소화.

← 문제로 돌아가기