교착상태 탐지 및 복구

<교착상태 탐지(Deadlock Detection)>
- 교착상태 발생이 허용되는 시스템
  - 교착상태 예방/회피 알고리즘을 사용하지 않는 시스템

- 구성 방법
  - 탐지 알고리즘(Detection algorithm)
    - 시스템을 검사해 교착상태 발생여부 결정
  - 복구 기법(Recovery scheme)
    - 교착상태 상태로부터 회복




<자원 유형마다 인스턴스가 하나 있는 경우>
- 교착상태 탐지 알고리즘
  - 대기 그래프(Wait-for graph)
    - 자원 할당 그래프의 변형
      - 자원 유형의 노드 제거 후 적절한 간선들을 집합
    - Pi -> Pj : Pi is waiting for Pj

  - 주기적으로 그래프 안에서 사이클 존재를 탐지하는 알고리즘 
    - 사이클이 존재하면 교착상태 발생 가능




<자원 유형마다 인스턴스가 다수 있는 경우>
- Available 
  - 각 유형 당 가용 자원의 개수, 길이 m인 벡터

- Allocation 
  - 각 프로스세에게 현재 할당되어 있는 자원의 개수
  - nxm 행렬

- Request
  - 각 프로세스가 현재 요청중인 자원의 개수
  - nxm 행렬
  - Request[i, j] = k
    - Pi가 Rj 유형의 인스턴서를 k개 요청 중




<탐지 알고리즘(Detection Algorithm)>
1. Work : 길이 m인 벡터, Finish : 길이 n인 벡터
  - 초기화 : Work = Available 
IF(Allocation != 0) THEN Finish[i] = false
ELSEIF Finish[i] = true  for i = 0,1, ... , n-1

2. 다음 두 조건을 만족하는 i 값을 찾음
  - Finish[i] = false
  - Request[i] <= Work
    만족하는 i가 없으면, goto step 4

3. Work = Work + Allocation[i]
  Finish[i] = true
  goto step 2

4. 어떤 i에 대해 Finish[i] == false 이면 시스템 Pi는 교착상태에 빠져있다






<탐지 알고리즘의 사용>
- 사용회수 : "얼마나 자주 호출해야 하는가?"
  - 얼마나 자주 교착상태가 발생하는가?
  - 얼마나 많은 프로세스가 교착상태에 연루되나?

- 교착상태 발생 시점
  - 프로세스가 자원을 요청 했는데도 즉시 할당되지 못하는 시점에 호출
    - 탐지 알고리즘 호출로 교착상태 발생 프로세스를 찾을 수 있으나 오버헤드가 발생
  - 보통 일정시간마다 CPU 이용률이 40% 이하로 떨어지는 시점에 호출






<교착상태로부터 회복>
- 교착상태 처리 방법
  - 운영자에게 통지하여 수작업으로 처리
  - 시스템이 자동적으로 프로세스에서 회복

- 교착상태를 깨뜨리는 방법
  - 순환 대기를 깨기 위해 한 개 이상의 프로세스 수행을 중지(abort)시킴
  - 교착상태에 있는 한 개 이상의 프로세스의 자원을 선점(preempt)





<프로세스 중지(Process Termination)>
- 프로세스를 종료하고 할당된 자원들을 회수하여 교착상태를 제거
  - 교착상태인 모든 프로세스들을 종료
    - 이미 많이 수행한 연산 결과를 폐기하는 부담

  - 교착상태 사이클이 제거될 때마다 한 프로세스씩 종료
    - 각 프로세스가 종료될 때마다 탐지 알고리즘을 호출해야하는 부담

    - 어느 프로세스부터 종료시켜야 하는가? 
      - 우선순위?, 남은 수행 시간?, 자원의 유형과 수?, ...
        필요한 자원의 수?, 몇 개나 종료해야?, 실행 유형?...





<자원 선점(Resource Preemption) - 뺏어옴>
- 교착상태가 깨질 때까지 한 프로세스의 자원을 선점하여 다른 프로세스에 할당
  - 선점 자원의 선택(Selecting a victim) 
    - 어느 자원, 어느 프로세스를 선점할 것인가?

  - 복귀(Rollback)
    - 선점된 프로세스는 어떻게 처리하나?
      - 프로그램 시작 혹은 안전한 상태(-> 더 많은 정보 유지)로 복귀 시키고, 이후에 이 시점에서 다시 시작

  - 기아(Starvation)
    - 같은 프로세스로부터 항상 선점되지 않음을 어떻게 보장하는가? -> 비용 요소에 복귀 횟수 포함





<그런데, 교착 상태를 꼭 해결하려 해야 하나?
- 교착상태에 대한 통계치는 없다
  - 1년에 한 번, 혹은 10년에 한 번

- 교착상태는 반드시 발생
  - 하지만, 교착상태의 발생 가능성은 극히 적고
  - 교착상태를 피하기 위한 비용이 많이 들어 감





<교착상태 무시 : 타조(Ostrich) 알고리즘>
- Put your head in the sand 접근법
  - 교착상태는 발생하지 않을 거라 가정하고 아무 대책을 취하지 않는 접근법
    - 타조가 머리를 모래 속에 박고 자신이 보이지 않은 체하는 것

  - Unix와 원도우 등 현재 거의 모든 운영체제에서 사용
    - 의심가는 스레드를 종료시키거나 시스템 재시작(reboot)
    - 거의 발생하지 않거나 아주 드물게 발생하는 것에 비해 교착 상태 해결에는 상대적으로 비용이 많이 들기 때문

  - hard real-time 시스템에는 부적절
    - 환자 감지 시스템, 핵 시스템, 비행기, 미사일 등
      - 자원에 대한 프로세스의 할당 등에 대해 미리 적절한 조치 필요