교착 상태

개요

교착 상태(Deadlock)는 두 개 이상의 프로세스가 서로의 작업을 완료하기 위해 필요한 자원을 기다리며 영원히 진행되지 못하는 상태를 말한다.

교착 상태 발생 예시는 다음과 같다. 위와 같이 임계구역으로 보호되는 프린터와 스캐너가 필요한 두 프로세스 P1과 P2가 각각 프린터와 스캐너를 할당받은 후 양보하지 않는 경우를 예로 들 수 있다.

위와 같이 두 프로세스가 자원을 점유하고 서로 추가 자원을 기다리며 대기하는 상황에 교착 상태가 발생한다.

좀 더 구체적으로 어떤 조건이 충족되어야 교착 상태가 발생했다고 할 수 있는지 알아보자.

---

교착 상태 필요조건

교착 상태의 네 가지 필요 조건이 있다. 이를 모두 만족해야 교착 상태가 발생했다고 할 수 있다.

• 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
• 비선점: 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없다.
• 점유와 대기: 프로세스가 어떤 자원을 점유한 상태에서 추가 자원을 요청하며 기다려야 한다.
• 순환 대기: 점유와 대기를 하는 프로세스 간 관계가 원을 이뤄야 한다.

위에서 본 예시로 네 가지 조건을 살펴보자.

• 상호 배제: 프린터와 스캐너는 한 프로세스가 사용하면 다른 프로세스가 사용할 수 없는 배타적인 자원이다.
• 비선점: P1이 P2가 점유한 스캐너를 빼앗을 수 없다.
• 점유와 대기: 두 프로세스는 모두 하나의 자원을 점유한 상태에서 다른 프로세스의 자원을 기다리고 있다.
• 순환 대기: 프린터, 스캐너 그리고 두 프로세스의 관계가 원을 이루고 있다.

기아(Starvation) 상태와 교착(Deadlock) 상태의 차이점

기아 상태는 잘못된 정책으로 인해 특정 프로세스의 우선 순위가 계속해서 미뤄져 작업이 수행되지 않는 것이다. 따라서 Aging 기법으로 해결할 수 있다.

교착 상태는 잘못된 정책이 아니어도 자연적으로 발생한다. 따라서 Aging 기법이나 정책의 수정으로도 해결할 수 없다.

그렇다면 교착 상태는 어떻게 해결해야 할까?

---

교착 상태 해결 방법

교착 상태를 해결하는 방법은 예방(preventation), 회피(avoidance), 검출(detection)이며, 추가적으로 상태가 발견된 후 자원을 회복(recovery)하는 방법이 있다.

예방(preventation)

위에서 언급한 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 하지만 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.

• 상호 배제 예방: 독점적으로 사용할 수 있는 자원을 없애버린다. 하지만 현실적으로는 모든 자원을 공유할 수 없기 때문에 상호 배제를 무력화하긴 어렵다.
• 비선점 예방: 모든 자원을 빼앗을 수 있도록 만든다. 이 또한 현실적으로 모든 자원에 대해 적용할 수 없기 때문에 무력화하기 어렵다.
• 점유와 대기 예방: 자원을 요청할 때 전부 할당받거나 아예 할당받지 않는다. 이 방법은 자원에 대한 권한이 아닌 프로세스의 자원 사용 방식을 바꾼다는 점에서 위 두 예방 방식과는 다르지만, 작업 방식이 제한되고 자원이 낭비된다는 단점이 있다.
• 순환 대기 예방: 자원에 순서를 부여하고, 순서대로 자원을 요청하도록 한다. 이 방법 또한 점유와 대기 예방과 마찬가지로 작업 방식이 제한되고 자원이 낭비될 수 있다는 단점이 있다.

회피(Avoidance)

교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 할당을 취소하고 프로세스를 대기시키는 방법이다.

이 방법에선 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다. 그리고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

이 방법의 대표적인 구현 방식은 은행원 알고리즘이다. 대출 금액이 가능한 범위 내이면(안정 상태이면) 대출이 허용되지만 그렇지 않으면(불안정 상태) 거부되는 방식의 알고리즘이다.

문제점

• 모든 프로세스가 자신이 사용할 자원을 미리 선언해야 하지만 현실적으로 쉬운 일이 아니다.
• 시스템의 전체 자원수는 일시적인 고장이나 추가가 빈번하기 때문에 고정된 시스템 전체 자원 수를 계산하기 쉽지 않다.
• 불안정 상태가 되면 반드시 교착 상태가 발생하는 것이 아닌데도 자원을 할당하지 않기 때문에 자원 낭비가 발생한다.

검출(Detection)

1. 타임아웃: 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생했다고 간주하는 방법

   • 장점

     • 구현이 쉽다. -> 가벼운 교착 상태 검출이라고 불림

   • 단점

     • 교착 상태가 발생하지 않은 프로세스가 강제 종료될 수 있다.

     • 모든 시스템에 적용할 수 없다.

       • DB와 같은 프로세스는 데이터 일관성을 처리해야 하는 등 중요 조건이 있기 때문에 롤백과 같은 추가 작업이 필요하다.

2. 자원 할당 그래프: 시스템 내 프로세스가 어떤 자원을 사용하고 있는지를 알 수 있어 사이클을 통해 교착 상태를 감지할 수 있다.

   • 장점

     • 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다.

   • 단점

     • 구현이 어렵다. -> 무거운 교착 상태 검출이라고 불림
     • 그래프 유지 보수와 사이클 검사 작업으로 인한 오버헤드가 발생한다.

회복(Recovery)

교착 상태가 검출된 후 프로세스를 강제 종료하거나 자원을 회수해 교착 상태를 해결하는 방법이다.

1. 교착 상태를 일으킨 모든 프로세스 종료

2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

   • 각 프로세스의 우선순위, 작업 시간, 사용하는 자원의 수를 고려해 종료 순서를 정해야 한다.