276. 데드락 회피를 위한 Lock Hierarchy (락 순서화)

⚠️ 이 문서는 다중 스레드 환경에서 서로 다른 자원을 점유하려다 시스템이 영원히 멈춰버리는 데드락(교착 상태)의 4가지 발생 조건 중 '환형 대기(Circular Wait)'의 고리를 수학적으로 완벽하게 끊어내어 데드락을 원천 봉쇄하는 가장 고전적이고 강력한 설계 기법인 '락 순서화(Lock Hierarchy)'를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 락 순서화(Lock Hierarchy)는 시스템 내의 모든 락(공유 자원)에 1번, 2번, 3번과 같은 절대적인 계층(순위) 번호를 부여하고, 모든 스레드가 무조건 번호가 낮은 락부터 차례대로 획득하도록 강제하는 규칙이다.
  2. 가치: A 스레드가 1번 락을 쥐고 2번 락을 기다릴 때, B 스레드가 2번 락을 쥐고 1번 락을 요구하는 역방향의 꼬리 물기(환형 대기) 상황 자체가 시스템 구조상 절대 발생할 수 없게 만들어 데드락을 원천적으로 예방한다.
  3. 융합: 리눅스 커널, 데이터베이스 트랜잭션, 금융 시스템 등 락을 2개 이상 동시에 쥐어야 하는 복잡한 소프트웨어를 설계할 때 반드시 지켜야 하는 시큐어 코딩 및 아키텍처 설계의 제1원칙이다.

Ⅰ. 개요: 꼬리 물기의 악몽 (Context & Necessity)

은행에서 'A 계좌'에서 돈을 빼서 'B 계좌'로 송금하는 프로그램을 짠다고 가정해 보자. 잔액이 꼬이지 않게 하려면 A 계좌에 락(Lock)을 걸고, 동시에 B 계좌에도 락을 걸어야 한다.

  • 데드락의 발생 (순서가 없을 때)
    • 스레드 1: A $\rightarrow$ B 로 송금 시도. [A 계좌 락 획득], B 계좌 락 대기 중.
    • 스레드 2: B $\rightarrow$ A 로 송금 시도. [B 계좌 락 획득], A 계좌 락 대기 중.
    • 결과: 스레드 1과 스레드 2가 서로가 가진 락을 내놓으라고 요구하며, 우주가 멸망할 때까지 영원히 멈춰버린다. (환형 대기, Circular Wait)

데드락의 4대 발생 조건(상호배제, 점유대기, 비선점, 환형대기) 중 앞의 3개는 현실적으로 없애기 힘들다. 학자들은 가장 만만한 **"환형 대기(서로 꼬리 물기)"**를 없애는 작전을 짰다. "모든 자원에 서열(번호)을 매기고, 무조건 서열 순서대로만 자물쇠를 잡게 하자!" 이것이 **Lock Hierarchy(락 순서화)**다.

📢 섹션 요약 비유: 좁은 골목길(교차로)에서 양쪽 차가 서로 양보 안 하고 버티는 게 데드락입니다. 이 문제를 해결하기 위해 아예 도로에 일방통행 표지판(락 순서화)을 세워서, 모든 차가 무조건 남쪽에서 북쪽으로만 지나가게 법으로 강제하여 마주 보며 막히는 상황 자체를 없애버린 것입니다.

Ⅱ. Lock Hierarchy의 작동 원리와 증명

해결책은 간단하지만 파괴적이다. 계좌 번호가 작은 쪽부터 먼저 락을 건다는 절대 규칙을 코드에 박아버리는 것이다.

1. 규칙 적용 후의 완벽한 교통정리

(가정: A 계좌번호는 100번, B 계좌번호는 200번이다.)

  • 스레드 1 (A $\rightarrow$ B 송금): 작은 번호인 A(100번) 락을 먼저 획득하고, 그다음에 B(200번) 락을 요구한다.
  • 스레드 2 (B $\rightarrow$ A 송금): (과거엔 B부터 잡았지만) 이제 규칙에 의해, 작은 번호인 A(100번) 락을 먼저 획득해야만 B(200번) 락을 요구할 수 있다.

2. 시간의 흐름에 따른 충돌 회피 증명

  • 스레드 1이 A 락을 먼저 잡았다.
  • 스레드 2가 실행된다. 스레드 2도 (도착지가 A니까) A 락부터 잡으려 한다.
  • 하지만 A 락은 스레드 1이 쥐고 있다! 스레드 2는 B 락을 아직 잡지도 못한 채 얌전히 문 밖에서 대기(Block)하게 된다.
  • 스레드 1은 아무 방해 없이 B 락을 잡고, 송금을 끝내고, A와 B 락을 모두 풀어준다.
  • 그제야 스레드 2가 A 락을 잡고 정상적으로 작업을 시작한다. 데드락 완전 소멸!
┌────────────────────────────────────────────────────────────────────────────┐
│           Lock Hierarchy를 통한 데드락 원천 봉쇄 시각화                    │
├────────────────────────────────────────────────────────────────────────────┤
│                                                                            │
│ ❌ [ 락 순서가 없을 때 (데드락 쾅!) ]                                      │
│   스레드 1 (A->B) :  [Lock A] 꽉 쥠  ──(기다림)──▶ [Lock B] 필요           │
│   스레드 2 (B->A) :  [Lock B] 꽉 쥠  ──(기다림)──▶ [Lock A] 필요           │
│   *(서로 꼬리 물기, 시스템 마비)*                                          │
│                                                                            │
│ 🛡️ [ 락 계층화 적용 후 (항상 고유번호가 작은 놈부터 잡을 것!) ]            │
│   * A번호=1, B번호=2                                                       │
│   스레드 1 (A->B) :  [Lock A (1번)] 획득 성공!                             │
│   스레드 2 (B->A) :  나도 무조건 1번부터 잡아야해! [Lock A (1번)] 요청!    │
│                    -> "앗 스레드1이 쓰고 있네? 조용히 밖에서 기다리자..."  │
│                                                                            │
│   스레드 1 (A->B) :  [Lock B (2번)] 마저 획득 성공 -> 송금 완료!           │
│   스레드 2 (B->A) :  드디어 [Lock A], [Lock B] 획득 성공 -> 송금 완료!     │
└────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 데드락은 '내가 자원을 쥔 상태에서 남의 자원을 뺏으려 할 때' 터진다. 순서화 규칙을 강제하면, 스레드 2는 자신의 자원(B)을 아예 손에 쥐기도 전에(점유 전) 남의 자원(A) 문 앞에서 차단당한다. 구조적으로 '점유 대기(Hold and Wait)' 상태가 환형으로 엮이는 고리를 수학적으로 싹둑 끊어버린 것이다.

Ⅲ. 실무 도입 시의 딜레마 (구현의 어려움)

이론은 완벽하지만, 실무에서 이 원칙을 지키는 것은 지옥 같은 작업이다.

  1. 동적인 자원의 순서 매기기
    • 계좌 송금처럼 '계좌 번호'라는 명확한 ID가 있으면 다행이다. 하지만 리눅스 커널 안에서 파일 시스템 락, 메모리 락, 네트워크 락 수만 개가 얽혀 있는데, 이들의 순위를 어떻게 매길 것인가?
    • 수천 쪽짜리 설계 문서에 "1번 락은 A, 2번 락은 B..." 라고 강제로 규정(Hierarchy Document)해 두고, 모든 커널 개발자가 이 문서를 외우고 코딩해야 한다. (리눅스 커널 소스에 락 획득 순서가 주석으로 적혀 있는 이유다.)
  2. 모듈화의 파괴 (Composability 붕괴)
    • 최신 소프트웨어는 컴포넌트(부품)를 조립해서 만든다. Component_A는 내부적으로 X 락을 쓰고, Component_B는 Y 락을 쓴다.
    • 메인 함수에서 A()와 B()를 연속으로 부르면, 나도 모르는 사이에 X 락과 Y 락이 꼬여 데드락이 터질 수 있다. 즉, 락의 내부 구현이 외부로 노출되어야만 순서를 지킬 수 있으므로 캡슐화와 객체지향 설계가 박살 난다.

Ⅳ. 결론

"가장 단순한 규칙이 가장 완벽한 방패가 된다." Lock Hierarchy(락 순서화)는 다중 스레드 환경에서 복수 개의 락을 동시에 쥐어야 하는 프로그래머가 목숨처럼 지켜야 할 철칙이다. 비록 컴포넌트 간의 캡슐화를 해치고 개발자에게 극도의 주의력을 요구하는 단점이 있지만, 오직 이 규칙만이 데드락이라는 통제 불능의 괴물을 시스템 구조적으로, 수학적으로 100% 숨통을 끊어놓을 수 있는 유일하고 확실한 해독제이기 때문이다.

📌 관련 개념 맵

  • 해결하려는 문제: 데드락 (Deadlock)
  • 제거하는 데드락 조건: 환형 대기 (Circular Wait)
  • 대체재 / 발전 기술: 트라이-락 (Try-Lock: 안 잡히면 내 락 풀고 포기), STM (소프트웨어 트랜잭셔널 메모리)
  • 실무 패턴: 은행 계좌 송금 알고리즘, 리눅스 커널의 Fine-grained 락 설계

👶 어린이를 위한 3줄 비유 설명

  1. 두 친구가 색칠 공부를 하는데, 철수는 빨간펜을 쥐고 파란펜을 달라고 떼쓰고, 영희는 파란펜을 쥐고 빨간펜을 달라고 떼쓰면서 둘 다 그림을 못 그리고 영원히 멈춰버렸어요 (데드락).
  2. 선생님이 강력한 규칙(Lock Hierarchy)을 만들었어요. "무조건 빨간펜부터 잡은 사람만 파란펜을 만질 수 있다!"
  3. 이제 영희는 파란펜을 잡고 싶어도 빨간펜이 철수 손에 있으니까 아예 펜을 하나도 못 잡고 조용히 기다리게 돼요. 철수가 다 쓰고 펜 2개를 내려놓으면 그제야 영희가 색칠을 할 수 있게 되어 다툼이 완전히 사라졌답니다!