교착 상태 해결 방법(Deadlock Solution)에 대해 설명하세요
Keyword
예방, 회피, 회복, Deadlock 발생 조건, Safe State, Unsafe State, 강제 종료, 자원 선점
Script
Deadlock은 예방하거나 회피, 회복을 통해 해결할 수 있습니다.
먼저, Deadlock 예방은 Deadlock 발생 조건 중 하나를 부정하면 됩니다. 즉, 상호 배제(mutual exclusion)을 부정하거나, 점유와 대기(hold and wait)를 금지하거나, 선점(preemption)을 허용하거나, 순환 대기를 풀어주면 됩니다.
그리고 DeadLock 회피는 주기적으로 Deadlock 발생 가능성을 검사해서 이를 회피하는 방식입니다. Deadlock이 발생하지 않는 Safe State가 아닌, Unsafe State일 경우, Deadlock이 발생할 수 있는 상태입니다. 즉, Deadlock 회피는 계속해서 Safe State를 유지하는 것입니다.
마지막으로, Deadlock 회복은 Deadlock을 허용하되, Deadlock을 탐지하고, 강제 종료 혹은 자원 선점을 통해 Deadlock을 회복합니다.
Additional
교착 상태 예방(Deadlock Prevention)
교착 상태를 예방하는 것은 사실 효율적인 방식이 아니다. 리소스가 많이 필요하고, 오버헤드가 과도해질 수 있다.
상호 배제 부정(No Mutual Exclusion)
상호 배제는 critical section의 자원을 여러 프로세스가 동시에 사용할 수 없게 만드는 것이다. 하지만, 이 제약을 풀면 모든 프로세스가 자원을 동시에 사용할 수 있게 된다. 그럼 Deadlock이 발생할 수 없다.
그런데 결국 이 방법은 동기화를 보장할 수 없기 때문에, 현실적으로 상호 배제를 부정하는 것으로 교착 상태 문제를 해결할 수는 없다.
점유와 대기 금지(No Hold and Wait)
점유와 대기는 프로세스가 자원을 점유한 채로 다른 자원을 대기하는 것을 의미한다. 그런데 결국 이렇게 프로세스가 동작하는 것을 금지한다면, Deadlock은 발생할 수 없다.
사실 이 방법도 현실성이 전혀 없다. 결국 이 방식에서는 한 프로세스가 어떤 자원을 점유하고 있다면, 다른 프로세스는 그 자원을 쓰지 못하는 것 뿐 아니라, 한 프로세스가 자신에게 필요한 모든 자원을 동시에 점유할 수 없다면 영원히 실행될 수 없다. 이렇게 되면, 자원 분배의 효율성이 매우 떨어지게 되고, 프로세스가 실행 중간에 다른 새로운 자원이 필요하게 되어도 hold를 할 수 없기 때문에, 처음부터 모든 자원을 다시 할당받아야하는 매우 비효율적인 방식이 된다.
선점의 허용(Allow Preemption)
선점을 허용한다는 것은 강제로 자원의 할당을 빼앗을 수 있다는 것이다. 선점을 허용하는 것으로써 Deadlock 문제는 해결될 수 있고, 현실적으로 가능한 Deadlock 예방 방법이다. 하지만, 작업의 진행 상태를 저장하는 자원(레지스터, 메모리 등)에는 적용할 수 있지만, 그렇지 않은 프린터와 같은 자원에는 적용이 어렵다.
순환 대기 금지(No Circular Wait)
만약 모든 자원에 우선 순위를 둔다면, 각 프로세스가 우선순위 순으로 오름차순으로만 자원을 요청할 수 있게 제한할 수 있다. 그럼 Deadlock 문제는 해결할 수 있다. 하지만 이 방식도 결국 우선순위를 매겨야하고, 우선순위를 어떻게 매기는지에 따라서 효율성과 특정 자원의 활용성이 달라질 수 있기 때문에, 이를 모두 고려해서 작업하는 것이 쉬운일 이 아니다.
교착 상태 회피(Deadlock Avoidance)
Deadlock 회피에는 기본적으로 Safe State와 Unsafe State 개념이 사용된다.
Safe State는 Deadlock이 절대 발생하지 않는 경우가 존재하고, Deadlock이 없는 프로세스 실행 순서인 Safe Sequence가 존재하는 것이다. 반면, Unsafe State는 Deadlock에 빠질 가능성이 존재하는 상태이다.
그렇다면 Deadlock 가능성은 어떻게 평가하는가?
3개의 정보와 하나의 가정이 전제되어야 한다.
- 가용한 자원의 인스턴스 수
- 모든 프로세스마다 보유하고 있는 자원의 수
- 모든 프로세스마다 필요한 총 자원의 수
가정: 프로세스는 필요한 자원을 모두 사용하고 한 번에 해제한다.
결국 이 정보와 가정을 바탕으로 Deadlock 발생 가능성을 체크하고, 항상 Safe State를 유지하는 것이 핵심 아이디어이다.
대표적으로 은행원 알고리즘과 자원 할당 그래프를 이용한 방법이 존재한다.
교착 상태 검출 (Deadlock Detection)
wait-for graph
자원 할당 그래프에서 프로세스 간의 대기 관계만 추출하면, wait-for 그래프를 얻을 수 있다. 물론 이 경우는 자원의 인스턴스가 하나일 때 사용이 가능한데, 이 때 만약 wait-for 그래프에 cycle이 발생하면, Deadlock이 발생했다고 판단한다.
교착 상태 회복 (Deadlock Recovery)
프로세스 종료(Process Termination)
Deadlock의 원인이 되는 프로세스를 모두 종료하거나, 한 번에 하나의 프로세스만 종료하면서 Deadlock이 풀리는지 Check하는 방법이다.
물론 프로세스를 강제로 종료하기 때문에, 그렇게 좋은 방법은 아니지만 효율적인 방법이긴 하다. Deadlock 발생 확률이 낮을 때 쉽게 문제를 해결할 수 있기 때문이다.
자원 선점(Resource Preemption)
프로세스의 자원을 선점하여 강제로 빼앗는 방법이다.
희생 프로세스에 따라, 희생 비용을 최소화하는 프로세스의 자원을 빼앗아서 Deadlock을 해결한다. 물론 어떤 프로세스로부터 자원을 빼앗아오면, 자원이 빼앗긴 프로세스는 롤백 과정을 거치거나 처음 상태로 되돌려줘야한다. 그런데 희생 프로세스의 기준에 따라서 계속해서 같은 프로세스만 희생될 수 있다는 단점이 있다.
Reference
