분산 시스템 교착 상태 (Distributed Deadlocks)¶
분산 시스템 환경에서는 전역 상태(Global State)에 대한 정확한 지식을 갖기 어렵고 통신 지연이 발생하기 때문에, 교착 상태를 다루는 전략이 단일 시스템과는 다릅니다. 이 문서는 분산 환경에서의 교착 상태 처리 전략과 대표적인 탐지 알고리즘인 에지 체이싱(Edge Chasing)을 설명합니다.
1. 교착 상태 처리 전략¶
분산 시스템에서 교착 상태를 다루는 전략은 크게 예방(Prevention), 회피(Avoidance), **탐지 및 해결(Detection and Resolution)**로 분류됩니다. 이 중 **탐지 및 해결**이 가장 실용적인 접근법으로 평가받습니다.
1.1 교착 상태 예방 (Deadlock Prevention)¶
교착 상태 발생 가능성을 원천적으로 차단하는 방법입니다. * 방법: 프로세스 시작 전 모든 자원을 한 번에 획득하거나, 자원 점유 프로세스를 선점(Pre-emption)합니다. * 한계: 분산 시스템에서는 자원 활용 효율이 매우 낮아 비현실적입니다.
1.2 교착 상태 회피 (Deadlock Avoidance)¶
자원 할당 전 시스템이 안전한 상태(Safe state)로 남을지 미리 판단하는 방법입니다. * 방법: 자원 요청 승인 시 안전 상태가 유지될 경우에만 할당합니다. * 한계: 모든 사이트가 시스템의 전역 상태를 실시간으로 파악해야 하므로 분산 환경에서 구현하기 어렵습니다.
1.3 교착 상태 탐지 및 해결 (Detection and Resolution)¶
교착 상태 발생을 허용하되, 주기적으로 검사하여 해결하는 방식입니다.
가. 탐지 (Detection)¶
프로세스 간 대기 관계를 나타내는 **대기 그래프(Wait-For Graph, WFG)**에서 사이클(Cycle)을 찾습니다.
- 주요 탐지 알고리즘:
- 경로 푸싱(Path-pushing): 로컬 WFG 정보를 이웃으로 전송하여 전역 WFG를 구축.
- 에지 체이싱(Edge-chasing): 전역 WFG 없이 '프로브(Probe)' 메시지를 따라 이동하며 사이클 탐지. (오버헤드가 적어 효율적)
- 확산 연산(Diffusion computation): 에코 알고리즘 활용.
- 전역 상태 탐지(Global state detection): 시스템 스냅샷을 찍어 검사.
나. 해결 (Resolution)¶
탐지된 사이클 내의 프로세스 중 하나를 중단(Abort)**시켜 자원을 회수하고 진행을 재개합니다. 단, 정보 지연으로 인한 **유령 교착 상태(Phantom deadlock) 오인 가능성에 주의해야 합니다.
2. 에지 체이싱 (Edge Chasing) 알고리즘 상세¶
에지 체이싱은 전역 그래프를 구축하는 대신, 그래프의 간선(Edge)을 따라 프로브(Probe) 메시지를 전달하여 사이클 존재 여부를 확인합니다.
2.1 작동 단계¶
1. 시작 (Initiation)¶
트랜잭션 간 대기 관계를 모니터링하다가 특정 조건에서 탐지를 시작합니다. * 조건: 트랜잭션 \(T\)가 \(U\)를 기다리는데, \(U\)가 다른 서버**의 자원을 기다리는 경우. * **동작: 대기 관계(예: \(\langle T \rightarrow U \rangle\))를 포함한 프로브 메시지를 생성하여 \(U\)가 대기 중인 자원의 관리 서버로 전송합니다.
2. 탐지 및 전달 (Detection and Forwarding)¶
프로브를 수신한 서버는 경로 정보를 업데이트하고 전달합니다. * 확장: 프로브 \(\langle T \rightarrow U \rangle\)를 받은 서버는 \(U\)가 또 다른 트랜잭션 \(V\)를 기다리는지 확인합니다. 맞다면 정보를 추가하여 \(\langle T \rightarrow U \rightarrow V \rangle\)로 확장합니다. * 전달: \(V\)가 또 다른 서버의 자원을 기다린다면, 해당 서버로 프로브를 전달(Forwarding)합니다.
3. 사이클 확인 (Cycle Found)¶
프로브 메시지가 계속 전달되다가 시작 트랜잭션(Initiator)**으로 되돌아오는 경우입니다. * **판단: 프로브 경로에 이미 포함된 트랜잭션 \(T\)로 다시 돌아오면(예: \(\langle T \rightarrow U \rightarrow V \rightarrow T \rangle\)) 사이클이 형성된 것이며, 이는 교착 상태를 의미합니다. * 해결: 사이클 내 트랜잭션 중 하나를 중단(Abort)합니다.
2.2 대표 알고리즘 (Chandy-Misra-Haas)¶
- 프로브 메시지를
(i, j, k)형태의 삼중쌍(triplet)으로 구성합니다.- \(P_i\): 탐지를 시작한 프로세스
- \(P_j\): 현재 메시지를 보내는 프로세스
- \(P_k\): 메시지를 받는 프로세스
- 프로브가 시작 프로세스 \(P_i\)로 되돌아오면 교착 상태로 선언합니다.
이 방식은 메시지 크기가 작고 고정되어 있어 분산 시스템에서 매우 효율적입니다.