Appearance
데드락 (DeadLock, 교착 상태)
두 개 이상의 실행 흐름이 서로가 가진 자원을 기다리느라 영원히 진행하지 못하는 상태
보통 프로세스뿐 아니라 스레드 사이에서도 발생할 수 있다. 시스템 자원이 한정되어 있고, 자원 획득 순서가 잘못 설계되면 교착 상태가 생긴다.
(마치 외나무다리 양 끝에서 서로 비켜주기만 기다리는 상황과 비슷하다.)
데드락이 일어나는 예
프로세스 1은 자원 1을 잡은 채 자원 2를 기다리고, 프로세스 2는 자원 2를 잡은 채 자원 1을 기다리면 순환 대기가 생긴다. 이 상태에서는 둘 다 앞으로 진행하지 못한다.
데드락 발생 조건
아래 4가지가 모두 성립해야 데드락이 가능하다.
상호 배제(Mutual Exclusion)
동시에 하나의 실행 흐름만 사용할 수 있는 자원이 있어야 한다.
점유 대기(Hold and Wait)
어떤 실행 흐름이 이미 자원을 가진 상태에서 다른 자원을 추가로 기다려야 한다.
비선점(No Preemption)
이미 할당한 자원을 강제로 빼앗기 어렵다.
순환 대기(Circular Wait)
실행 흐름들이 원형으로 서로의 자원을 기다린다.
데드락 처리 방법
1. 예방(Prevention)
교착 상태의 필요 조건 중 하나를 아예 깨뜨리는 방식이다.
- 상호 배제 완화: 읽기 전용 데이터처럼 공유 가능한 자원은 공유하게 설계
- 점유 대기 제거: 필요한 자원을 한 번에 모두 요청하게 함
- 비선점 완화: 가능한 자원이라면 회수 후 재시도하게 함
- 순환 대기 제거: 락 순서를 전역적으로 정해 그 순서대로만 획득
예방은 강력하지만, 병렬성을 떨어뜨리거나 자원 활용률을 낮출 수 있다.
2. 회피(Avoidance)
요청이 들어올 때마다 "이 자원을 지금 줘도 안전 상태(safe state)가 유지되는가?"를 판단하고, 안전하지 않으면 할당을 미루는 방식이다.
- 대표 알고리즘: 은행원 알고리즘(Banker's Algorithm)
- 각 프로세스가 최대 자원 요구량을 미리 알아야 해서 실제 범용 OS에서는 거의 그대로 쓰지 않는다.
참고
Resource Allocation Graph 기반 설명은 주로 단일 인스턴스 자원을 가정한 이론 모델이다. 실제 시스템에서는 은행원 알고리즘이나 wait-for graph, 락 순서 같은 실용적 전략이 더 중요하다.
3. 탐지(Detection)
교착 상태를 허용하되, 주기적으로 검사해서 찾아내는 방식이다.
- 단일 인스턴스 자원에서는 wait-for graph의 cycle로 탐지할 수 있다.
- 여러 인스턴스 자원에서는 별도의 탐지 알고리즘이 필요하다.
탐지는 계산 비용이 들고, 발견 시점까지 이미 시스템 일부가 멈춰 있을 수 있다.
4. 회복(Recovery)
교착 상태가 확인되면 문제를 끊기 위해 일부 실행 흐름이나 자원을 희생한다.
- 프로세스/스레드 종료
- 전체를 한꺼번에 종료
- 비용이 낮은 것부터 하나씩 종료
- 자원 선점 및 롤백
- 선점 가능한 자원에 한해 회수 후 다시 시도
- 데이터 일관성을 위해 체크포인트/롤백이 필요할 수 있음
모든 자원이 선점 가능한 것은 아니다. 예를 들어 프린터 출력이나 파일 시스템 갱신 같은 작업은 중간 강제 회수가 어렵다.
실무에서는?
범용 운영체제와 애플리케이션은 보통 은행원 알고리즘보다 다음 전략을 많이 쓴다.
- 락 획득 순서 고정
- 가능한 한 짧은 임계 구역 유지
trylock, timeout, backoff 사용- 상위 수준 동시성 구조 사용
즉, 실무에서는 "교착 상태를 예쁘게 탐지하고 회복"하기보다 애초에 잘 설계해서 예방하는 쪽이 훨씬 흔하다.
주요 질문
- 데드락이 무엇이고, 발생 조건 4가지는 무엇인가요?
- 예방, 회피, 탐지, 회복의 차이는 무엇인가요?
- 실무에서 락 순서를 정하는 이유는 무엇인가요?