데드락(Deadlock)
기술노트
데드락(Deadlock)
개념
데드락(Deadlock)은 두 개 이상의 프로세스나 쓰레드가 서로 상대방이 점유하고 있는 자원을 기다리며 무한히 대기하는 상태를 의미합니다. 교착 상태라고도 불리며, 시스템 자원의 비효율적 사용과 프로그램 실행 중단을 초래할 수 있는 심각한 문제입니다.
데드락의 발생 조건
데드락이 발생하기 위해서는 다음 네 가지 조건이 동시에 충족되어야 합니다:
상호 배제 (Mutual Exclusion)
- 자원은 한 번에 하나의 프로세스만 사용할 수 있음
- 사용 중인 자원을 다른 프로세스가 사용하려면 해당 자원이 해제될 때까지 기다려야 함
점유와 대기 (Hold and Wait)
- 프로세스가 이미 하나 이상의 자원을 점유한 상태에서 다른 프로세스가 사용 중인 자원을 추가로 요청하며 대기함
비선점 (No Preemption)
- 이미 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
- 자원을 점유한 프로세스가 자발적으로 해제하기 전까지는 다른 프로세스가 사용할 수 없음
순환 대기 (Circular Wait)
- 프로세스들이 원형으로 자원을 요청하는 상태
- 프로세스 P1은 P2가 가진 자원을 기다리고, P2는 P3가 가진 자원을 기다리고, ..., Pn은 P1이 가진 자원을 기다리는 상황
데드락 예시
실생활 예시
- 교차로 교통 체증: 네 방향에서 모든 차량이 서로의 진입 공간을 점유하며 움직이지 못하는 상황
- 식사하는 철학자 문제: 원형 테이블에 앉은 철학자들이 양쪽의 포크를 모두 집으려고 할 때 발생하는 데드락
컴퓨터 시스템 예시
- 데이터베이스 락: 트랜잭션 A가 테이블 X의 락을 획득하고 테이블 Y의 락을 기다리는 동안, 트랜잭션 B가 테이블 Y의 락을 획득하고 테이블 X의 락을 기다리는 상황
- 쓰레드 동기화: 쓰레드 1이 뮤텍스 A를 잠그고 뮤텍스 B를 기다리는 동안, 쓰레드 2가 뮤텍스 B를 잠그고 뮤텍스 A를 기다리는 상황
- 프로세스 자원 할당: 프로세스 A가 프린터를 사용 중이며 스캐너를 요청하고, 프로세스 B가 스캐너를 사용 중이며 프린터를 요청하는 상황
데드락 다이어그램
데드락은 자원 할당 그래프(Resource Allocation Graph)를 통해 시각화할 수 있습니다:
- 원: 프로세스를 나타냄
- 사각형: 자원을 나타냄
- 프로세스→자원 화살표: 자원 요청을 나타냄
- 자원→프로세스 화살표: 자원 할당을 나타냄
그래프에 순환이 존재하면 데드락이 발생할 가능성이 있습니다.
데드락 처리 방법
예방 (Prevention)
데드락의 네 가지 필요 조건 중 하나 이상을 원천적으로 제거하는 방법:
- 상호 배제 조건 제거: 공유 가능한 자원 사용 (읽기 전용 파일 등)
- 점유와 대기 조건 제거:
- 프로세스 시작 시 모든 필요한 자원을 한꺼번에 할당
- 자원을 요청할 때는 보유한 자원을 모두 해제
- 비선점 조건 제거: 자원을 점유한 프로세스가 다른 자원을 요청할 수 없는 경우, 보유한 자원을 선점(강제 해제) 가능하도록 함
- 순환 대기 조건 제거: 모든 자원 유형에 전체적인 순서를 부여하고, 프로세스는 오름차순으로만 자원 요청 가능
회피 (Avoidance)
시스템이 항상 안전 상태(Safe State)를 유지하도록 자원 할당을 제어하는 방법:
- 은행원 알고리즘(Banker's Algorithm):
- 각 프로세스가 자원을 요청할 때, 할당 시 안전 상태가 유지되는지 확인 후 결정
- 프로세스의 최대 자원 요구량을 미리 알고 있어야 함
- 사용 가능한 자원, 할당된 자원, 최대 필요 자원을 계산하여 안전 순서 존재 여부 확인
탐지 및 복구 (Detection and Recovery)
데드락 발생을 허용하되, 주기적으로 탐지하고 발견 시 복구하는 방법:
- 탐지 방법:
- 자원 할당 그래프에서 순환 탐지
- 대기 그래프(Wait-for Graph) 분석
- 복구 방법:
- 프로세스 종료: 데드락 관련 프로세스 모두 종료 또는 순차적으로 하나씩 종료
- 자원 선점: 데드락 상태 프로세스로부터 자원을 강제로 회수하여 다른 프로세스에게 할당
- 선점 대상 선택 기준: 우선순위, 누적 CPU 사용 시간, 남은 작업량 등
무시 (Ignorance)
데드락을 처리하기 위한 어떠한 조치도 취하지 않고 발생 시 사용자 개입을 통해 해결:
- 타조 알고리즘(Ostrich Algorithm): 문제를 무시하고 발생 시 시스템 재시작
- 데드락 발생 빈도가 낮고, 탐지/복구 비용이 높은 경우 선택
- 대부분의 운영체제가 채택하는 방식
데드락 방지를 위한 프로그래밍 기법
락 계층화 (Lock Hierarchies)
- 모든 락에 번호를 부여하고 항상 오름차순으로만 획득하도록 함
- 프로그래머가 락 획득 순서를 일관되게 유지해야 함
락 타임아웃 (Lock Timeouts)
- 락 획득 시도 시 일정 시간이 지나면 포기하고 재시도
- 간단하지만 라이브락(Livelock) 문제 발생 가능
데드락 감지 라이브러리
- 락 획득/해제 시도를 모니터링하여 데드락 가능성 감지
- Java의 ThreadMXBean, C++의 DeadlockDetector 등
단일 쓰레드 설계
- 멀티스레딩을 피하고 비동기, 이벤트 기반 설계 사용
- Node.js와 같은 싱글 스레드 이벤트 루프 모델
데드락과 관련된 개념
라이브락 (Livelock)
- 프로세스가 서로에게 양보하느라 실제 작업을 진행하지 못하는 상태
- 데드락과 달리 프로세스들이 상태는 변경되지만 실질적 진행은 없음
기아 상태 (Starvation)
- 특정 프로세스가 필요한 자원을 계속해서 할당받지 못하는 상태
- 우선순위가 낮은 프로세스가 계속 대기하는 상황
우선순위 역전 (Priority Inversion)
- 낮은 우선순위 프로세스가 높은 우선순위 프로세스가 필요로 하는 자원을 점유하여, 높은 우선순위 프로세스가 대기하게 되는 상황
실제 사례
Mars Pathfinder 사례
- 1997년 화성 탐사선이 우선순위 역전으로 인한 데드락 상황 발생
- 정기적인 시스템 리셋으로 임시 대응 후 소프트웨어 패치로 해결
데이터베이스 시스템
- 동시 트랜잭션 처리 중 락 경쟁으로 인한 데드락
- 대부분의 DBMS는 데드락 감지 및 해결 매커니즘 구현
운영체제 자원 관리
- 파일 시스템 락, 메모리 할당, I/O 장치 접근 시 발생 가능
- 타임아웃 및 자원 사용 우선순위 정책으로 대응
관련 주제
- 동시성 프로그래밍(Concurrent Programming)
- 임계 구역(Critical Section)
- 세마포어(Semaphore)와 뮤텍스(Mutex)
- 운영체제 자원 관리
- 트랜잭션 처리 시스템
