← 문제로

2. 데드락: 4조건, 예방/회피, 락 순서와 경합 줄이기

난이도 중
내 답안
모범답안

모범답안 — 데드락: 4조건, 예방/회피, 락 순서와 경합 줄이기

난이도: 중

핵심 답변

  • 데드락 4조건(Coffman): ① 상호 배제(mutual exclusion) ② 점유 대기(hold and wait) ③ 비선점(no preemption) ④ 순환 대기(circular wait). 네 가지가 동시에 성립해야 데드락이 생기며, 하나라도 깨면 막을 수 있다.
  • 예방 vs 회피: 예방은 4조건 중 하나를 설계 단계에서 원천적으로 못 생기게 만드는 것(예: 전역 락 순서 강제 → 순환 대기 제거). 회피는 실행 중 자원 요청을 받을 때마다 안전 상태인지 검사해 위험하면 허용하지 않는 것(은행원 알고리즘). 서버 실무에서는 회피(런타임 검사 비용/사전 정보 필요)는 거의 안 쓰고, 락 순서 강제 같은 예방을 압도적으로 많이 쓴다.
  • 경합 줄이기: ① 락 범위(critical section)를 최소화 ② 락 분할/세분화(coarse → fine, 또는 샤딩) ③ 공유 자체를 줄이기(스레드 로컬 + 머지, lock-free, 읽기 위주면 RW락/RCU).

깊이 있는 설명 (메커니즘, 왜)

Coffman 4조건이 시나리오에서 어떻게 충족되나

스레드 T1이 Trade(P1, P2), T2가 Trade(P2, P1)을 동시에 실행:

  1. 상호 배제: InventoryLock은 한 번에 한 스레드만 잡는다. → 성립.
  2. 점유 대기: T1은 P1 락을 쥔 채로 P2 락을 기다린다. T2는 P2 락을 쥔 채 P1을 기다린다. → 성립.
  3. 비선점: 잡은 락을 강제로 빼앗을 수 없다. T1이 P2를 기다리는 동안 T1의 P1 락을 OS가 회수해주지 않는다. → 성립.
  4. 순환 대기: T1→(P2 락 대기)→T2→(P1 락 대기)→T1. 자원 대기 그래프에 사이클이 생긴다. → 성립.

네 조건이 모두 성립 → 두 스레드는 영원히 서로를 기다린다. 서버가 멈춘 이유다. 핵심 원인은 락 획득 순서가 호출자마다 다르다는 점(T1은 P1→P2, T2는 P2→P1)이다.

가장 실용적인 깨기: 순환 대기 제거 = 전역 락 순서

모든 스레드가 항상 같은 순서로 락을 잡으면 사이클이 생기지 않는다. 객체에 고유하고 안정적인 순서 키(예: PlayerId, 또는 객체 주소)를 부여하고 작은 키 → 큰 키 순으로 잡는다.

void Trade(Player a, Player b)
{
    // 안정적인 전역 순서로 정렬해 항상 같은 순서로 락 획득
    Player first  = a.Id < b.Id ? a : b;
    Player second = a.Id < b.Id ? b : a;

    lock (first.InventoryLock)
    {
        lock (second.InventoryLock)
        {
            MoveItems(a, b);
        }
    }
}

이제 T1, T2 모두 min(P1,P2) 락을 먼저 잡으려 하므로, 한쪽이 먼저 둘 다 잡고 끝낸 뒤 다른 쪽이 진행한다. 사이클 불가능.

동일 ID(a.Id == b.Id, 자기 자신과 거래)나 키 충돌은 별도 가드 필요. 주소를 키로 쓸 땐 ABI/이동 가능성에 주의.

다른 조건을 깨는 대안

  • 점유 대기 제거: 필요한 락을 모두 한 번에(원자적으로) 잡거나(std::lock(m1, m2) / std::scoped_lock 은 데드락 회피 알고리즘 내장), 아예 못 잡으면 가진 것을 다 놓고 재시도(try_lock 백오프).
  • 비선점 우회: try_lock 타임아웃 → 실패 시 롤백 후 재시도. 라이브락 위험이 있어 백오프/지터 필요.
  • 상호 배제 제거: 애초에 공유를 없애기(아래 실무 연결).

응용/실무 연결 (게임서버에서)

  • 팀 규칙: 전역 락 계층(lock hierarchy)을 문서화. "락 A는 항상 락 B보다 먼저", "같은 레벨 락은 ID 오름차순" 같은 순서를 정하고, 디버그 빌드에서 순서 위반을 감지하는 락 래퍼(스레드별 보유 락 스택을 추적해 역순 획득 시 assert)를 둔다. 우편·길드창고·거래가 모두 인벤토리 락을 잡아도 동일 순서만 지키면 데드락이 안 난다.
  • 더 나은 구조: 거래를 단일 스레드 액터로. 두 인벤토리를 직접 락하는 대신, 거래를 "거래 매니저 스레드/잡큐"에 메시지로 보내 순차 처리하면 락 자체가 사라진다. 룸 단위로 플레이어가 묶여 있으면 룸 스레드에서 처리. 크로스 룸 거래만 별도 조정.
  • 경합 줄이기 실전: 글로벌 매칭 풀 같은 핫스팟은 하나의 큰 락 대신 샤딩(버킷별 락)으로 분산. 통계는 스레드 로컬에 모았다가 주기적으로 머지. 읽기 비율이 압도적이면 ReaderWriterLockSlim/RCU.

흔한 오답·함정

  • "락을 하나만 쓰면 데드락은 절대 없다" → 단일 락만으로도 재진입(같은 스레드가 같은 비재귀 락을 또 잡으면) 셀프 데드락이 가능하다. 또한 락 + 콜백/이벤트가 다른 락을 다시 잡으면 숨은 순환이 생긴다.
  • "데드락과 라이브락은 같다" → 라이브락은 멈추진 않지만(스레드가 계속 양보/재시도) 진전이 없는 상태. try-lock 백오프를 잘못 짜면 발생.
  • "타임아웃 락이면 데드락 해결" → 타임아웃은 데드락을 감지·복구할 뿐 예방이 아니며, 잘못하면 라이브락/재시도 폭주를 부른다. 순서 강제가 더 근본적.
  • "락을 잘게 쪼개면 항상 빨라진다" → 락 개수가 늘면 획득/해제 오버헤드와 데드락 위험이 커진다. 세분화는 경합 측정 후 핫스팟에만.

꼬리질문 대비

  1. Q: std::scoped_lock(m1, m2)는 어떻게 데드락을 피하나? A: 내부적으로 여러 mutex를 데드락 회피 알고리즘(std::lock)으로 잡는다. 한 락 획득 후 다른 락을 try_lock 하다 실패하면 이미 잡은 것을 모두 풀고 순서를 바꿔 재시도한다. 점유 대기/순서 문제를 라이브러리가 처리. (C# lock엔 직접 대응물이 없어 순서 정렬을 손으로 한다.)

  2. Q: 락 순서를 강제해도 데드락이 날 수 있는 경우는? A: 순서 외부에서 들어오는 콜백/재진입, 동적으로 잡는 락의 순서가 런타임에 결정되는 경우, 또는 락 외의 자원(DB 트랜잭션 락, 세마포어)이 섞여 순서 규칙 밖에서 사이클을 만들 때. 그래서 락 계층에 외부 자원도 포함시켜야 한다.

  3. Q: 경합이 심한지 어떻게 측정하나? A: 락 대기 시간/획득 횟수 카운터, 프로파일러의 lock contention 뷰, perf의 spin/futex 대기, 또는 락 래퍼에 대기 시간 히스토그램을 심는다. 추측 말고 측정 후 핫스팟만 손본다.

← 문제로 돌아가기