개발기록
교착상태(Deadlock)의 모든 것: 심층 분석과 해결 전략 본문
1. 서론
운영체제와 병렬 컴퓨팅 환경에서 발생하는 가장 복잡하고 까다로운 문제 중 하나가 바로 교착상태(Deadlock)입니다. 이 글에서는 교착상태의 개념부터 시작하여 발생 조건, 다양한 해결 방법, 그리고 실제 시스템에서의 적용 사례까지 상세히 다루겠습니다.
2. 교착상태의 정의와 특징
2.1 교착상태의 정의
교착상태란 두 개 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 무한히 대기하는 상황을 말합니다. 이는 시스템 자원의 비효율적 사용을 초래하고, 최악의 경우 시스템 전체의 정지를 야기할 수 있습니다.
2.2 교착상태의 특징
- 상호 의존성: 교착상태에 빠진 프로세스들은 서로에게 필요한 자원을 보유하고 있습니다.
- 무한 대기: 교착상태가 해결되지 않는 한, 관련된 프로세스들은 영원히 진행되지 못합니다.
- 자원 낭비: 교착상태에 빠진 프로세스들이 보유한 자원은 사용되지 않은 채 낭비됩니다.
- 시스템 성능 저하: 교착상태는 전체 시스템의 처리량과 응답 시간에 부정적인 영향을 미칩니다.
3. 교착상태의 발생 조건
교착상태가 발생하기 위해서는 네 가지 조건이 동시에 충족되어야 합니다. 이를 '커피숍(Coffman) 조건'이라고 부릅니다.
3.1 상호 배제(Mutual Exclusion)
- 정의: 최소한 하나의 자원이 독점적으로 사용되어야 합니다.
- 예시: 프린터와 같은 하드웨어 자원은 한 번에 하나의 프로세스만 사용할 수 있습니다.
- 중요성: 이 조건은 많은 시스템 자원의 본질적 특성이므로 완전히 제거하기 어렵습니다.
3.2 점유 대기(Hold and Wait)
- 정의: 프로세스가 최소한 하나의 자원을 보유한 채로 다른 프로세스에 할당된 자원을 추가로 요청해야 합니다.
- 예시: 프로세스 A가 자원 X를 보유한 채로 자원 Y를 요청하는 상황.
- 문제점: 이 조건으로 인해 자원이 효율적으로 사용되지 못하고 대기 상태가 길어질 수 있습니다.
3.3 비선점(No Preemption)
- 정의: 이미 할당된 자원은 해당 프로세스가 스스로 반납하기 전까지 강제로 빼앗을 수 없습니다.
- 예시: CPU 스케줄링에서의 비선점 방식.
- 영향: 이 조건으로 인해 높은 우선순위의 프로세스도 필요한 자원을 즉시 획득하지 못할 수 있습니다.
3.4 순환 대기(Circular Wait)
- 정의: 프로세스의 집합 {P0, P1, ..., Pn}에서 P0는 P1이 가진 자원을 기다리고, P1은 P2가 가진 자원을 기다리고, ..., Pn은 P0가 가진 자원을 기다리는 순환 형태의 대기 상황이 발생해야 합니다.
- 특징: 이 조건은 교착상태의 가장 직접적인 원인이 됩니다.
- 탐지 방법: 자원 할당 그래프를 통해 시각화하고 탐지할 수 있습니다.
4. 교착상태 해결 방법
교착상태를 해결하기 위한 방법은 크게 세 가지 접근 방식으로 나눌 수 있습니다.
4.1 교착상태 예방 (Deadlock Prevention)
교착상태 예방은 앞서 언급한 네 가지 필요 조건 중 최소한 하나를 제거하여 교착상태의 발생 가능성 자체를 없애는 방법입니다.
4.1.1 상호 배제 조건 제거
- 방법: 모든 자원을 공유 가능하게 만듭니다.
- 장점: 완벽한 교착상태 예방이 가능합니다.
- 단점: 현실적으로 모든 자원을 공유 가능하게 만드는 것은 불가능합니다.
- 적용 예: 읽기 전용 파일은 여러 프로세스가 동시에 접근할 수 있습니다.
4.1.2 점유 대기 조건 제거
- 방법 1: 프로세스 실행 전 모든 필요한 자원을 할당받게 합니다.
- 방법 2: 자원이 필요할 때 보유 중인 자원을 모두 놓고 다시 요청하게 합니다.
- 장점: 점유 대기 상황을 원천적으로 방지할 수 있습니다.
- 단점: 자원 이용률이 떨어지고, 기아 상태가 발생할 수 있습니다.
4.1.3 비선점 조건 제거
- 방법: 자원을 점유 중인 프로세스로부터 해당 자원을 빼앗을 수 있게 합니다.
- 장점: 높은 우선순위 프로세스의 빠른 처리가 가능합니다.
- 단점: 선점 과정에서 오버헤드가 발생하고, 일관성 문제가 생길 수 있습니다.
- 적용 예: CPU 스케줄링의 선점 기법
4.1.4 순환 대기 조건 제거
- 방법: 자원에 고유한 번호를 할당하고, 프로세스가 오름차순으로만 자원을 요청하게 합니다.
- 장점: 구현이 비교적 간단하고 효과적입니다.
- 단점: 자원 사용의 유연성이 떨어지고, 자원 이용률이 감소할 수 있습니다.
4.2 교착상태 회피 (Deadlock Avoidance)
교착상태 회피는 자원을 할당할 때마다 시스템의 상태를 검사하여 안전한 상태를 유지하도록 하는 방법입니다.
4.2.1 은행원 알고리즘 (Banker's Algorithm)
- 개념: Edsger Dijkstra가 제안한 알고리즘으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 방식에서 착안했습니다.
- 동작 원리:
- 프로세스가 자원을 요청합니다.
- 시스템은 자원을 할당한 후의 상태가 안전한지 검사합니다.
- 안전하다면 자원을 할당하고, 그렇지 않다면 다른 프로세스가 자원을 해제할 때까지 대기합니다.
- 장점: 교착상태를 효과적으로 예방할 수 있습니다.
- 단점:
- 미리 최대 자원 요구량을 알아야 합니다.
- 사용 가능한 자원의 수가 고정되어 있어야 합니다.
- 실행 중 새로운 프로세스가 들어올 수 없습니다.
4.2.2 자원 할당 그래프 알고리즘
- 개념: 자원 할당 상태를 그래프로 표현하여 교착상태 가능성을 파악합니다.
- 방법:
- 자원 요청 시, 할당 엣지를 요청 엣지로 변환했을 때 사이클이 생기는지 검사합니다.
- 사이클이 생기지 않는 경우에만 자원을 할당합니다.
- 장점: 직관적이고 시각적인 방법으로 교착상태를 파악할 수 있습니다.
- 단점: 복잡한 시스템에서는 그래프가 매우 복잡해질 수 있습니다.
4.3 교착상태 탐지 및 복구 (Deadlock Detection and Recovery)
이 방법은 교착상태가 발생하도록 놔두고, 주기적으로 탐지하여 발생 시 복구하는 방법입니다.
4.3.1 탐지 (Detection)
- 방법:
- 자원 할당 그래프를 주기적으로 검사합니다.
- 그래프에서 사이클을 찾아 교착상태를 탐지합니다.
- 장점: 시스템 운영의 유연성을 제공합니다.
- 단점: 탐지 주기에 따라 오버헤드가 발생할 수 있습니다.
4.3.2 복구 (Recovery)
교착상태 복구는 크게 두 가지 방법으로 나눌 수 있습니다:
프로세스 종료
- 방법 1: 교착상태에 있는 모든 프로세스를 종료합니다.
- 방법 2: 교착상태가 해결될 때까지 한 번에 하나씩 프로세스를 종료합니다.
- 장점: 확실하게 교착상태를 해결할 수 있습니다.
- 단점: 프로세스 종료에 따른 비용이 발생합니다.
자원 선점
- 방법: 교착상태의 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당합니다.
- 고려사항:
- 희생자 선택: 최소의 비용으로 선점할 프로세스를 선택합니다.
- 롤백: 선점된 프로세스를 안전한 상태로 롤백합니다.
- 기아 상태: 동일한 프로세스가 계속해서 희생되는 것을 방지해야 합니다.
5. 실제 시스템에서의 교착상태 처리
실제 운영체제와 데이터베이스 시스템에서는 교착상태를 어떻게 다루고 있을까요?
5.1 운영체제에서의 교착상태 처리
대부분의 현대 운영체제(Windows, Linux, macOS 등)는 교착상태에 대해 특별한 예방이나 회피 기법을 사용하지 않습니다. 대신 다음과 같은 접근 방식을 취합니다:
타조 알고리즘 (Ostrich Algorithm): 교착상태를 무시하고, 발생 시 사용자나 관리자의 개입을 기다립니다.
- 이유: 교착상태 발생 빈도가 낮고, 예방/회피 기법의 오버헤드가 크기 때문입니다.
- 대응: 주로 프로세스 강제 종료나 시스템 재부팅으로 해결합니다.
제한적 탐지 및 복구: 특정 중요 자원에 대해서만 교착상태를 탐지하고 복구합니다.
- 예: 파일 시스템의 잠금(lock) 관리
시간 제한 사용: 자원 할당에 시간 제한을 두어 간접적으로 교착상태를 방지합니다.