교착상태 회피 알고리즘

5.3.2 회피

(2) 각 유형의 단위자원이 하나밖에 없을 경우

변형된 자원할당 그래프

- 할당간선 (\(r_j\) , \(p_i\)) : 자원 \(r_j\)가 프로세스 \(p_i\)에 할당됨

 

- 요구간선 (\(p_i\) , \(r_j\)) : 프로세스 \(p_i\) 가 자원 \(r_j\) 를 요구함 

 

- 선언간선 (\(p_i\) , \(r_j\)) : 앞으로 프로세스 \(p_i\) 가 자원 \(r_j\) 를 요구하게 될 것임

 

 

** 자원을 요청받으면 그 요구 간선을 할당 간선으로 변환하여도 사이클이 발생되지 않는 경우에만 자원을 할당

( 이 부분 너무 어려워서 pass~~~ )

 

 

5.3.3 탐지 및 복구

탐지 및 복구

- 시스템 교착상태 여부를 탐지하기 위해 주기적으로 상태 조사 알고리즘을 수행

 

교착상태 복구

- 교착상태가 탐지된 경우 복구조치에 들어감

 

(1) 탐지 

시스템이 교착상태에 있는지 여부를 탐지하기 위해 Shoshani와 Coffman의 알고리즘을 이용할 수 있다.

 

- Shoshani와 Coffman의 알고리즘

① 길이가 각각 𝑚, 𝑛인 WORK와 FINISH 초기화 

          WORK ← AVAIL

          ALLOC𝑖 ≠ 0이면 FINISH(𝑖) ← false

          그렇지 않으면 FINISH(𝑖) ← true, 𝑖=1, 2, …, n

② FINISH(𝑖) = false이고 REQ𝑖≤WORK인 𝑖 찾기

    그런 𝑖가 없으면 go to ④

③ WORK ← WORK + ALLOC𝑖

     FINISH(𝑖) ← true

     go to ②

④ 어떤 𝑖에 대하여 FINISH(𝑖)=false이면 교착상태

→ FINISH(𝑖)=false인  \(p_i\)는 교착상태임

 

> 알고리즘 수행 시점 

- 즉시 받아들일 수 없는 할당요구가 있을 때

- 정해진 시간간격 또는 CPU 효율이 일정 수준 이하로 떨어질 때

 

 

(2) 복구

> 복구 주체

- 오퍼레이터 : 교착상태 발생을 알려주면 수작업으로 복구

- 시스템 : 자동적으로 복구

 

> 복구의 방법

- 교착상태 프로세스를 종료

- 교착상태 프로세스로부터 자원을 회수

 

> 프로세스 종료

- 모든 교착상태 프로세스를 종료

 → 단점 : 그동안 진행했던 내용들에 대한 복원 비용이 큼

 

- 사이클리 제거될 때까지 프로세스를 하나씩 종료

 → 단점 : 종료 대상을 선택하기위한 비용, 매번 교착상태 재확인을 위한 비용

 

> 자원 회수 

- 사이클이 제거될 때까지 자원을 단계적으로 선점하여 다른 프로세스들에 할당

- 고려사항 : 희생자 선택, 복귀, 기아상태

 

 

 

5.3.4 복합적 접근방법

> 방지, 회피, 탐지 및 복구를 복합적으로 사용

 - 자원을 유형에 따라 계층적으로 분류

 - 각 계층에 대하여 자원순서를 부여

 - 각 계층별로 방지, 회피, 탐지 및  복구 중 적절한 방법을 적용