[OS] Deadlock

Terminology

Deadlock은 두 개 이상의 프로세스가 서로의 자원을 필요로 하면서 상대방의 작업 완료를 무한정 기다리는 현상이다. 이 상황에서 각 프로세스는 상대방이 필요로 하는 특정 이벤트를 제공할 수 있는데, 모든 관련 프로세스가 서로의 이벤트를 기다리면서 어느 쪽도 진행할 수 없게 되어 결국 모두 정지하게 된다.

Deadlock의 필요조건에는 4가지가 있다.

1. 상호 배제 (Mutual Exclusion): 요구하는 자원이 다른 프로세스에 의해 사용 중일 경우, 해당 자원이 방출될 때까지 기다려야 한다.
2. 보유 대기 (Hold-and-Wait): 프로세스가 최소 하나 이상의 자원을 보유한 상태에서 추가 자원을 획득하기 위해 대기할 수 있다.
3. 비선점 (No Preemption): 다른 프로세스나 운영체제는 프로세스가 자발적으로 자원을 해제할 때까지 자원을 강제로 회수할 수 없다.
4. 순환 대기 (Circular Wait): 자원 할당 그래프에서 사이클이 존재해야 하며, 이는 각 프로세스가 순차적으로 다음 프로세스가 요구하는 자원을 보유하고 있어 서로가 서로를 기다리는 상태를 의미한다. 단일 자원 인스턴스의 경우, 사이클은 데드락을 발생시키는 필요 충분조건이지만, 다중 자원 인스턴스에서는 사이클이 존재하면 데드락이 발생할 수 있는 충분조건이며, 'knot'가 필요 충분조건이다.

knot는 다중 자원 시스템에서 여러 프로세스와 자원 간의 복잡한 종속성을 나타내는 구조이다. 이 구조는 각 프로세스가 여러 자원에 대해 순환적 의존성을 가지고 있어, 단순한 사이클 이상의 복잡한 상호작용을 포함한다. 하나 이상의 사이클이 형성될 가능성이 높다.

단일 인스턴스. 좌측은 사이클 존재x -> deadlock x. 우측은 사이클 존재 o -> deadlock o.

다중 인스턴스. 좌측은 knot 존재 x -> deadlock x. 우측은 knot 존재 o -> deadlock o.

 

왜 필요한가? (Policy)

데드락이 발생하면 프로세스들은 서로 필요한 이벤트를 기다리며 진행을 멈추게 된다. 이로 인해 시스템이 완전히 정지할 수 있기 때문에 데드락 문제를 해결하는 것은 필수적이다. 프로세스가 다른 프로세스의 자원이나 이벤트를 기다리는 동안, 시스템의 자원이 비효율적으로 사용되거나 전혀 사용되지 않는 상황이 발생할 수 있다. 이처럼 데드락 상황은 시스템의 전반적인 성능과 효율성을 저하시키므로, 효과적인 데드락 해결 방법이 필요하다. 이를 통해 시스템은 자원을 최적으로 활용하고, 프로세스의 실행이 원활하게 유지될 수 있다.

 

데드락 해결방법에는 4가지가 있다.

1. 무시 (The Ostrich Approach): 데드락 발생을 무시하는 방법으로, 데드락의 발생 빈도가 낮고 해결 비용이 높은 경우 적합할 수 있다. 시스템 설계상 데드락이 심각한 문제가 되지 않는다고 판단될 때 사용된다.
2. 예방 (Deadlock Prevention): 데드락이 발생할 수 있는 4가지 필요 조건 중 최소 하나를 제거하여 데드락을 사전에 방지한다. 예를 들어, 자원을 한 번에 하나만 할당하거나, 프로세스가 자원을 요청할 때 이미 보유한 자원을 모두 방출하도록 요구하는 방법이 있다. 이 접근법은 자원 활용도를 저하시킬 수 있다.
3. 탐지 후 복구 (Deadlock Detection and Recovery): 데드락의 발생을 탐지하고 복구하는 방식으로, 시스템이 주기적으로 데드락 여부를 체크하고, 발견된 데드락을 해결하기 위해 프로세스를 종료하거나 할당된 자원을 회수한다. 이 방법은 데드락 발생 후 대처를 요구하므로, 탐지 알고리즘과 복구 전략이 중요하다.
4. 회피 (Deadlock Avoidance): 시스템이 자원 요청에 대해 안전하지 않은 상태로 이어질 가능성이 있는 요청은 승인하지 않음으로써 데드락을 회피한다. 이를 위해 Banker’s Algorithm과 같은 안전 알고리즘을 사용하여, 모든 요청이 시스템을 안전 상태로 유지할 수 있도록 관리한다. 회피 기법은 사전 정보를 바탕으로 결정을 내리며, 시스템의 자원 요구와 할당 상태에 대해 깊은 이해를 필요로 하고, 때로는 큰 처리 오버헤드를 초래할 수 있다.

 

Mechanism

이제 각각의 Deadlock 해결 방법에 대해 소개해보겠다.

 

1. The Ostrich Approach

타조가 위험을 감지하면 머리를 모래 속에 숨긴다는 오해에서 비롯되었으며, 문제가 발생할 때 그 문제를 무시하거나 간과하는 전략이다. 그래서 데드락이 발생할 가능성이 낮거나, 발생해도 시스템의 전반적인 성능이나 안정성에 큰 영향을 미치지 않을 때 적합하다. 다만, 타조 접근법은 근본적인 문제를 해결하지 않고 일시적으로 회피하기 때문에, 장기적인 안정성과 신뢰성 확보에는 적합하지 않을 수 있다.

 

2. Deadlock Prevention

• 상호 배제 (Mutual Exclusion): 공유 가능한 자원(예: 읽기 전용 파일)을 활용하거나 자원 스풀링을 통해 상호 배제의 요구를 완화할 수 있다. 이는 자원이 독점적으로 사용될 필요가 없을 때 유용하다.
• 보유 및 대기 (Hold and Wait): 프로세스가 자원을 요청할 때 이미 보유한 자원을 유지하지 못하게 하여, 모든 필요한 자원을 한 번에 요청하도록 한다. 또는 이미 보유한 자원을 해제하고 필요한 자원을 새로 요청할 수 있다. 이 방법은 프로세스가 시작될 때 모든 필요 자원을 한번에 요청하도록 강제하는 것을 포함할 수 있다.
• 비선점 (No Preemption): 현재 보유하고 있는 자원을 선점할 수 있도록 하는 것이 아니라, 사용 중인 자원에 대해 다른 프로세스가 요청할 경우, 현재 프로세스가 그 자원을 해제하고 나중에 다시 요청할 수 있도록 하는 방법을 의미한다. 즉, 자원이 필요할 때 기존에 할당된 자원을 강제로 회수하고, 그 자원을 요구하는 다른 프로세스에 할당할 수 있다.
• 순환 대기 (Circular Wait): 모든 자원에 고유 번호를 할당하고, 프로세스가 번호가 낮은 순서대로만 자원을 요청할 수 있도록 함으로써 순환 대기 조건을 방지한다. 이 접근법은 자원을 순차적으로만 요청할 수 있게 하므로, 자원 활용의 병렬성이 제한될 수 있다는 단점이 있다.

 

3. Deadlock Detection and Recovery

데드락이 발생할 수 있다는 것을 인정하면서도, 발생한 후에 이를 탐지하고 해결하는 데 초점을 맞춘다. 이 방법은 주로 데드락을 피할 수 없는 복잡한 시스템에서 사용된다.

Detection

• 탐지 알고리즘: 시스템은 주기적으로 또는 특정 조건 하에서 자원 할당 그래프(Resource Allocation Graph, RAG)를 분석하여 데드락의 가능성을 탐지한다. 이 그래프에서 사이클이 존재하면 데드락이 발생했다고 판단할 수 있다. 사이클은 여러 프로세스가 서로의 자원을 기다리고 있음을 나타낸다.
• 자원 및 프로세스 모니터링: 시스템은 자원의 사용 상태와 프로세스의 대기 상태를 지속적으로 모니터링하여 데드락을 의심할 만한 상황을 파악한다. 이때 Coffman Algorithm을 사용하기도 한다. 모니터링 빈도가 중요한데, 자원 요청 시마다 탐지 알고리즘을 실행하는 것이 오버헤드를 증가시킬 수 있으므로, 시스템의 부하와 자원 사용률에 따라 적절한 빈도를 설정하는 것이 중요하다. 이는 시스템 성능과 안정성 사이의 균형을 맞추는 데 핵심적인 역할을 한다.

Recovery

• 프로세스 종료: 데드락에 관련된 하나 이상의 프로세스를 강제로 종료하여 사이클을 끊는다. 이는 무작위로 또는 특정 기준(예: 우선순위, 실행 시간, 자원 사용량)에 따라 결정될 수 있다.
• 자원 선점: 데드락을 일으킨 프로세스로부터 자원을 회수하여 다른 프로세스에 재할당함으로써 문제를 해결한다. 이 방법은 프로세스의 상태를 안정적으로 유지할 수 있어야 실행 가능하다. check point를 통해 안전한 상태로 roll back할 수도 있다. 이는 복구 과정에서 데이터 손실을 최소화하고 시스템의 일관성을 유지하는 데 도움을 준다.
• 프로세스 재시작: 강제 종료된 프로세스를 안전한 상태에서 다시 시작하여 작업을 계속할 수 있도록 한다.

이처럼 데드락이 발생하면 대응하는 방식으로 데드락 회피나 예방보다 유연하게 자원을 관리할 수 있다. 단점은, 데드락의 탐지와 복구 과정이 시스템에 추가적인 부하를 일으킬 수 있다는 점이다. 프로세스 종료나 자원 선점은 실행 중인 작업에 영향을 줄 수 있으며, 사용자 경험을 저하시킬 수 있다.

 

4. Deadlock Avoidance

시스템이 데드락에 빠지지 않도록 안전하게 자원을 할당하는 전략이다. 이 방법은 시스템에 현재 사용 가능한 자원, 이미 할당된 자원, 그리고 각 프로세스가 미래에 요구할 수 있는 최대 자원을 고려하여 작동한다. 주로 동적으로 자원을 할당하면서 데드락의 가능성을 회피하기 위해 사용된다.

데드락 회피 알고리즘은 프로세스에 자원을 할당하기 전에, 그 할당이 시스템을 데드락으로 이끌지 않는 안전한 상태를 유지할 수 있는지 판단한다. 여기에는 대표적으로 Banker’s Algorithm이 사용된다.

 

* 안전 상태(Safe State): 시스템이 모든 프로세스가 최대 자원 요구량만큼 자원을 필요로 할 때도, 주어진 순서대로 자원을 할당함으로써 모든 프로세스가 완료될 수 있는 상태이다. 이 상태에서는 어떠한 프로세스도 데드락에 빠지지 않는다.

 

Banker’s Algorithm은 다중 프로세스 시스템에서 안전한 순서로 자원을 할당하는 방법을 제공한다. 이 알고리즘은 몇 가지 전제 조건이 필요하다. 첫째, 각 프로세스가 평생 요구할 최대 자원량을 예측할 수 있어야 한다. 둘째, 각 프로세스는 다른 프로세스의 자원 요구에 독립적이어야 하며, 셋째, 자원의 수가 고정되어 있어 추가나 제거가 불가능해야 한다. 이러한 조건들이 충족되면, 시스템은 현재의 자원 할당 상태와 남은 자원량을 지속적으로 감시하며 각 요청이 안전 상태를 유지하는지 확인한다.

Banker's Algorithm은 각 프로세스의 요구에 따라 자원을 한꺼번에 몰아주는 것이 아니라, 각 프로세스가 요구하는 자원이 안전 상태를 유지할 수 있을 때만 할당한다. 프로세스에 자원을 할당하기 전에, 그 할당이 시스템을 안전 상태에 유지할 수 있는지를 평가한다. 시스템은 모든 프로세스가 자신의 최대 요구량만큼 자원을 안전하게 할당받을 수 있는 순서, 즉 안전 순서를 찾아내려고 한다. 만약 자원을 실험적으로 특정 순서에 따라 모든 프로세스에 할당했을 때 최종 상태가 안전 상태라면, 그 초기 요청은 승인될 수 있다. 이 방식으로 시스템은 언제나 안전 상태를 유지하며 각 프로세스의 자원 요구를 최대한 만족시키려고 한다.

* 안전 순서(Safe Sequence): 프로세스들을 특정 순서로 자원을 할당할 때 모든 프로세스가 성공적으로 완료될 수 있도록 하는 순서이다. 이 순서대로 자원을 할당하면 시스템은 항상 안전 상태를 유지할 수 있다. 해당 순서를 알기 위해 Safety algorithm을 사용한다. 해당 알고리즘은 banker’s algorithm의 일부이다.

 

Deadlock Avoidance를 통해 데드락이 발생할 가능성을 사전에 차단하면서 자원 할당을 최적화할 수 있다. 또한, 프로세스가 예상치 못하게 중단되는 일 없이, 필요한 자원을 안전하게 확보할 수 있다. 다만, 모든 프로세스의 최대 자원 요구량을 미리 알아야 하며, 이는 실시간으로 변동될 수 있는 프로세스의 요구를 반영하기 어렵다. 알고리즘이 복잡하고, 관리해야 할 정보가 많아 시스템의 오버헤드가 증가할 수도 있다.