[운영체제] 교착상태란?

1. 교착상태(Deadlock)

: Process나 Thread가 결코 일어날 수 없는 특정 Event를 기다리는 상태

 

2. 교착 상태의 4가지 필요 조건

4가지를 모두 만족해야 교착 상태가 발생한다.

• 상호 배제(Mutual Exclusion)
  : 여러 Process/Thread가 동시에 한 자원에 접근하지 못하도록 막는것
• 점유와 대기(Hold and Wait)
  : Process/Thread가 자원을 점유한 상태로 다른 자원을 점유하기 위해 대기하는 것
• 비선점(Nopreemption)
  : Process에서 자원을 할당 받으면 작업을 완료할 때까지 System에서 Process의 제어를 뺏을 수 없음
• 순환 대기(Circular Wait)
  : 점유와 대기를 하는 형태로 Cycle에 갇혀 빠져나갈 수 없는 상태

 

3. 교착 상태 해결법

: 교착 상태의 해결법으로는 교착 상태 예방, 교착 상태 회피, 교착 상태 탐지 및 복구, 교착 상태 무시가 있다.

 

3.1. 교착 상태 예방

: 교착 상태 필요 조건 중 하나를 거부하는 방식으로 예방하는 방법이다.

 

교착 상태는 발생하지 않으면 좋지만, 교착 상태가 발생하지 않는 환경을 만들어버린다면 자원을 효율적으로 사용할 수 없다.

e.g., 필요 조건 중 점유와 대기 조건을 거부해 한 Process가 자신이 필요한 자원을 모두 사용할 수 있을 때만 작업을 시작한다면 자원을 효율적으로 사용할 수 없다.

 

3.2. 교착 상태 회피

: 교착 상태를 인정하고 피해가는 방법으로 자원을 요청할 때마다 System의 상태를 판단하고 회피하는 전략을 사용한다.

☞ Overhead가 심하다.

e.g., 은행원 Algorithm

 

은행원 Algorithm
: System을 안전 상태/불안전 상태(교착 상태가 발생할 가능성이 있는 경우)로 구분하고 불안전 상태일 때는 대기하고 안전 상태일 때만 자원을 빌려주는 Algorithm으로 할당한 자원 수 고정, Process 수 고정, 제한된 시간 안에 자원 반납 등의 많은 조건이 필요하다.
☞ 현실에서는 자원이 동적으로 왔다갔다해 현실적으로는 불가능한 Algorithm이다.

 

3.3. 교착 상태 탐지 및 복구

: 교착 상태가 발생한 것 같을 때 탐지하고 복구하는 방법으로 교착 상태가 자주 발생하는 System에서 일반적으로 사용하는 방법이다.

☞ 교착 상태 회피에 비해 Overhead가 적다.

 

• 교착 상태 탐지
  : 교착 상태 존재 여부 및 교착 상태에 연관된 Process와 자원을 알아내는 전략을 사용하며 교착 상태의 4가지 필요 조건 중 순환 대기 존재 여부에 초점을 맞춰 교착 상태를 탐지한다.
  ☞ 탐지 Algorithm도 회피 Algorithm과 마찬가지로 Overhead가 있으므로 얼마나 자주(주기적으로, 자원 즉시 할당 여부에 따라, CPU 이용률에 따라 등) 탐지 Algorithm을 호출하는지가 관건이다.
  e.g., 자원 할당 그래프 소거

  자원 할당 그래프 소거 방식

  

• 교착 상태 복구
  : 순환 대기를 깨서 교착 상태로부터 회복하는 방식이다.
  e.g., 순환 대기가 깨질 때까지 Process 종료, 순환 대기에 포함된 Process 제어권 뺏고 Rollback
  ☞ 희생양이 될 Process는 남은 수행 시간, 자원 유형의 수 등 Systemp마다 다른 기준의 우선순위에 따라 결정된다.
      e.g., MySQL의 경우 Transaction Timeout시 교착상태이든 아니든 가장 작은 Transaction을 Rollback하며 Transaction의 크기는 삽입, 업데이트, 삭제된 행 수에 의해 결정된다.

 

3.4. 교착 상태 무시

: 교착 상태가 드물게 발생하는 System에서 일반적으로 사용하는 방법이다.