3.3.8 Deadlock

교착 상태

3.3.8 교착 상태

교착 상태란?

교착 상태(deadlock)는 두 개 이상의 프로세스가 서로가 가진 자원을 기다리며 중단된 상태를 말합니다. 즉, 각 프로세스가 다른 프로세스가 점유하고 있는 자원을 요청하면서 무한 대기 상태에 빠지는 상황을 의미합니다.

교착 상태의 예시

예를 들어, 프로세스 A가 자원 X를 점유하고 있고, 프로세스 B가 자원 Y를 점유하고 있다고 가정합시다. 이때 프로세스 A는 자원 Y를 요청하고, 프로세스 B는 자원 X를 요청하면 두 프로세스는 서로의 자원을 기다리게 되어 교착 상태에 빠집니다.

다음 그림은 교착 상태를 시각적으로 보여줍니다.

+------------------+     +------------------+
|  프로세스 A       |     |  프로세스 B       |
|  자원 X 점유 중   |     |  자원 Y 점유 중   |
|  자원 Y 요청      |     |  자원 X 요청      |
+------------------+     +------------------+

교착 상태의 조건

교착 상태가 발생하기 위해서는 다음 네 가지 조건이 모두 만족해야 합니다:

1. 상호 배제(Mutual Exclusion): 한 번에 한 프로세스만 자원을 점유할 수 있습니다.

2. 점유와 대기(Hold and Wait): 자원을 점유한 프로세스가 다른 자원을 기다리며 점유한 상태를 유지합니다.

3. 비선점(Non-Preemption): 프로세스가 점유한 자원을 강제로 빼앗을 수 없습니다.

4. 환형 대기(Circular Wait): 두 개 이상의 프로세스가 서로의 자원을 기다리며 원형으로 대기 상태에 있습니다.

교착 상태의 해결 방법

교착 상태를 예방하고 해결하기 위해 다양한 기법이 사용됩니다. 주요 해결 방법은 다음과 같습니다:

1. 예방:

   • 교착 상태의 조건 중 하나를 제거하여 교착 상태가 발생하지 않도록 설계합니다.

   • 예를 들어, 프로세스가 자원을 요청할 때 필요한 모든 자원을 한 번에 할당받게 하여 점유와 대기 조건을 제거할 수 있습니다.

2. 회피:

   • 자원 할당의 최대치를 예측하고, 교착 상태가 발생하지 않도록 자원을 할당합니다.

   • 대표적으로 은행원 알고리즘(Banker's Algorithm)이 있습니다. 이는 프로세스가 자원을 요청할 때 시스템이 안전 상태인지 확인하고, 안전할 때만 자원을 할당합니다.

3. 발견:

   • 교착 상태가 발생했을 때 이를 탐지하고 해결합니다.

   • 주기적으로 자원 할당 그래프를 검사하여 교착 상태를 발견합니다.

   • 교착 상태가 발견되면 프로세스를 강제로 종료하거나 자원을 회수하여 문제를 해결합니다.

4. 회복:

   • 교착 상태가 발생했을 때 시스템을 회복시키는 방법입니다.

   • 교착 상태를 해결하기 위해 일부 프로세스를 중단하거나 자원을 회수합니다.

교착 상태의 예방

교착 상태를 예방하기 위해서는 자원 할당 전략을 신중하게 설계해야 합니다. 자원의 순서를 미리 정하여 프로세스가 자원을 요청할 때 순서에 따라 할당하면 환형 대기 조건을 피할 수 있습니다. 또한, 각 프로세스가 자원을 점유하기 전에 필요한 모든 자원을 요청하게 하여 점유와 대기 조건을 제거할 수도 있습니다.

은행원 알고리즘

은행원 알고리즘은 교착 상태를 회피하는 대표적인 방법으로, 프로세스가 자원을 요청할 때 시스템이 안전 상태인지 확인하고 자원을 할당합니다. 은행원 알고리즘의 주요 개념은 다음과 같습니다:

• 안전 상태(Safe State): 시스템이 모든 프로세스의 자원 요청을 순서대로 처리하여 교착 상태에 빠지지 않는 상태.

• 불안정 상태(Unsafe State): 시스템이 자원 할당을 잘못하여 교착 상태에 빠질 수 있는 상태.

은행원 알고리즘은 자원 할당의 최대치를 예측하여 안전 상태를 유지함으로써 교착 상태를 회피합니다.

결론

교착 상태는 시스템 자원을 사용하는 멀티프로세스 환경에서 자주 발생하는 문제입니다. 이를 예방하고 해결하기 위해 상호 배제, 점유와 대기, 비선점, 환형 대기와 같은 조건을 이해하고, 예방, 회피, 발견, 회복과 같은 기법을 적절히 활용해야 합니다. 이를 통해 안정적이고 효율적인 시스템을 구축할 수 있습니다.