교착상태

교착 상태(Deadlock)

다중 프로그래밍 환경에서 둘 이상의 프로세스가 함께 멈추어 버리는 현상
정상적으로 작동하는 상태라면 프로세스는 다음 상태로만 자원을 요청할 수 있다.

1. 요청

   • 프로세스는 자원을 요청한다. 요청이 즉시 허용되지 않으면 프로세스는 자원을 얻을 때까지 대기한다.

2. 사용

   • 프로세스는 자원에 대해 작업을 수행할 수 있다. 예를 들어 자원이 프린터라면, 프로세스는 그 프린터로 인쇄할 수 있다.

3. 방출

   • 프로세스가 자원을 방출한다.

필요 조건

1. 상호 배제(Mutual Exclusion)

   • 임계 구역에 접근할 수 있는 자원의 수가 제한된다.

2. 점유 및 대기(Hold and wait)

   • 프로세스가 자원을 점유하고 있는 상태이나 다른 프로세스의 자원을 얻기 위해 대기하고 있다.

3. 비선점(No preemtion)

   • 다른 프로세스가 점유한 자원을 강제로 방출시킨 뒤 뺏어올 수 없다.

4. 순환 대기(Circular wait)

   • 대기하고 있는 프로세스의 목록이 순서와 사이클을 이루고 있는 상태이다. 예를 들어 P1은 P2가 점유한 자원을 대기하고, P2는 P3의 자원을 대기한다(P1->P2->P3->...->P1).

교착상태 처리 방법

교착상태는 4가지 조건을 충족하는 경우에만 발생한다. 따라서 조건 자체를 회피하거나, 미충족 상태로 만드는 것이 일반적이다. 보통 아래의 3가지 경우로 교착상태를 처리한다.

1. 교착상태를 예방하거나 회피한다.
2. 교착상태에 진입하면 회복시킨다.
3. 문제를 무시하고 교착상태가 발생하지 않은 것처럼 작동한다.
   • 대부분의 운영체제가 사용하는 방법이다.

교착상태 예방

교착상태의 4가지 필요 조건이 일어나지 않도록 시스템을 제어한다.

1. 상호 배제 조건 제거

   • 동시 접근을 허가한다.
   • 근본적으로 공유가 불가능한 자원이 존재하며, 동시에 접근 시 위험한 결과를 초래할 수 있기 때문에 상호 배제 자체를 없애는 것은 지양한다.
     • 프린터와 같은 입출력 장치에 동시 접근을 허용한다고 생각해보자.
     • Mutex lock은 근본적으로 공유가 불가능하다.

2. 점유 대기 조건 제거

   • 프로세스가 자원을 점유하지 않았을 때만 자원을 요청할 수 있도록 한다.

3. 비선점 조건 제거

   • 자원을 점유하고 있는 프로세스가 다른 자원을 요구하면 점유하고 있던 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 한다.

4. 순환 대기 조건 제거

   • 프로세스 대기 순서에서 사이클을 제거한다. 사이클을 제거하기 위해 선형 순서로 분류하여 우선순위를 부여한다.

예방 기법은 자원의 낭비가 심하다.

교착상태 회피

교착상태가 발생했을 때 적절히 피해나가는 방법으로, 자원이 요청될 때 어떻게 요청될 지에 대한 추가 정보를 제공하도록 요구한다.

가장 단순하고 유용한 모델은 각 프로세스가 자신이 필요로 하는 각 타입의 자원마다 최대 수를 선언하도록 요구하는 것이다.

• 최대 수 정보를 미리 파악할 수 있다면, 교착상태를 회피하는 알고리즘을 만들 수 있다.

자원 할당 그래프 알고리즘

자원이 1개일 때 사용하는 알고리즘

자원 할당 그래프를 변형한다.

• 요청 간선과 할당 간선이라는 2가지 종류 간선을 사용했다. 예약 간선이라는 새로운 간선을 사용한다.
  • 예약 간선 Pi -> Rj는 Pi가 미래에 Rj를 요청할 것이라는 의미이다.
  • 예약 간선은 점선으로 표시한다.
• 예약 간선 Pi -> Rj가 있을 때, Pi가 Rj를 요청하면 예약 간선을 요청 간선으로 변환한다.
• Pi가 Rj를 방출할 때, 할당 간선 Rj -> Pi는 예약 간선으로 변환한다.
• 궁극적으로는 그래프 상 자원 요청/할당 시 발생하는 사이클을 제거하는 것이 목표이다. 예약 간선에 나타난 대로 실제로 요청했을 때 사이클이 발생하는지를 사이클 탐지 알고리즘으로 확인한다.
  • 사이클 탐지 알고리즘은 O(n^2)의 시간 복잡도를 갖는다. 여기서 n은 프로세스의 수이다.

은행원 알고리즘

고객들이 현금을 찾으러 와도 일정 순서대로 요청을 허용한다면 모든 고객의 요청을 다 들어줄 수 있다.

은행원 알고리즘을 적용하기 위한 알고리즘

1. Available
   • 가용 자원의 수를 저장한 크기가 m인 벡터
2. Max
   • 각 프로세스가 필요로 하는 자원의 최대 개수로, 크기가 n * m인 행렬
3. Allocation
   • 프로세스가 사용 중인 자원의 개수로, 크기가 n * m인 행렬
4. Need
   • 프로세스가 향후 요청할 수 있는 자원의 개수로, 크기가 n * m인 행렬
   • Need[i, j] = Max[i, j] - Allocation[i, j]가 성립한다.

Request[x] <= Available[x]가 성립하면, x에게 자원을 줘도 안전한 상태임을 보장할 수 있다.

즉, 다음의 순서를 따른다.

1. 자원 할당을 요청한다.
2. 자원을 할당해도 안정한 상태를 유지할 수 있으면 프로세스에게 자원을 할당한다.

실제로는 가용 자원의 개수 등을 예측하기 어렵기 때문에 사용에 제약이 있다.

교착상태 탐지

시스템이 교착상태 예방이나 회피 기법을 사용하지 않는다면 교착상태가 발생할 가능성이 있다.

이런 시스템에서는 교착상태 발생을 탐지하는 알고리즘을 지원해야 한다.

• 자원 할당 그래프

  • 위의 자원 할당 그래프 알고리즘과 유사하다.
  • 그래프가 사이클을 포함하는 경우 시스템에 교착 상태가 발생한 것이므로, 사이클 탐지 알고리즘으로 사이클 여부를 조사한다.

• 교착 상태 발견 알고리즘

  • 자원을 요청할 때마다 탐지 알고리즘을 호출하면 오버헤드가 너무 크다.
  • 오버헤드를 줄이기 위해 아래와 같은 방법을 사용한다.
    • 한 번 호출하면 일정 시간동안 호출하지 않는다. 예를 들어 한 시간에 한 번 CPU 이용률이 40% 이하로 떨어질 떄 탐지 알고리즘을 호출한다.

교착상태 회복

시스템이 교착상태로부터 벗어나는 방법이다.
교착상태를 벗어나는 데에는 2가지 방법이 있다.

1. 순환 대기를 깨뜨리기 위해 1개 이상의 프로세스를 중지한다.
2. 교착상태에 있는 하나 이상의 프로세스로부터 자원을 선점한다.