[운영체제] 교착상태Ⅱ

목차

1. 교착상태 회피
2. 교착상태 탐지 및 복구
3. 복합적 접근방법

---

1. 교착상태 회피

: 교착상태 회피

- 프로세스의 자원 사용에 대한 사전 정보를 활용하여

  교착상태가 발생하지 않는 상태에 머물도록 하는 방법

⇒ 사전 정보 : 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량

 

■ 프로세스의 상태 영역

- 안전상태 : 안전 순서열이 존재

- 불안전상태 : 안전 순서열이 존재하지 않음 => 교착상태

* 안전상태 : 교착상태를 회피하면서 각 프로세스에게 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태

 

■ 안전 순서열

- 순서 있는 프로세스의 집합<p1, p2, ・・・, pn>

- 각 pi에 대해 pi가 추가로 요구할 수 있는 자원 소요량이 현재 가용 상태이거나

  혹은 현재 가용인 자원에 pj(단 kj < i)에 할당된 자원까지 포함하여 할당 가능한 경우

 

: 교착상태 회피 알고리즘

■  각 자원 유형의 단위자원이 여러 개일 경우

- 은행원 알고리즘

■ 각 자원 유형의 단위자원이 하나 밖에 없는 경우

- 변형된 자원할당 그래프

 

:  각 자원 유형의 단위자원이 여러 개일 경우 

■ 은행원 알고리즘

- 자원을 요청받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서

  그것이 안전상태가 보장되는 경우에만 자원을 할당

* AVAIL : 가용자원

* MAXi : pi의 최대요구

* ALLOCi : pi의 할당자원

* NEEDi : pi의 추가요구

 

:  각 자원 유형의 단위자원이 하나밖에 없는 경우 

■ 변형된 자원할당 그래프

- 할당간선(rj, pi) : 자원 rj가 프로세스 pi에 할당됨

- 요구간선(pi, rj) : 프로세스 pi가 자원 rj를 요구함

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

 

■ 변형된 자원할당 그래프

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

---

2. 교착상태 탐지 및 복구

:  교착상태 탐지 

■ 교착상태 탐지

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

 

■ Shoshani와 Coffman 알고리즘

 

:  교착상태 복구 

■ 프로세스 종료

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

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

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

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

 

■ 자원 회수

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

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

---

3. 복합적 접근방법

:  복합적 접근방법 

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

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

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

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

---

정리하기

- 교착상태를 처리하는 방법은 교착상태를 방지, 회피, 탐지하여 이를 복구하는 방법 등이 있다.

- 교착상태 회피 방법은 프로세스의 자원 사용에 대한 사전 정보를 활용해

  교착상태가 발생할 수 있는 불안전상태가 되는 것을 피한다.

- 은행원 알고리즘은 프로세스가 요구한 자원을 할당해 줄 경우

  안전 순서열이 존재하는지를 검사하여 요구 수용 여부를 결정한다.

- 변형된 자원할당 그래프에서 선언간서을 할당간선으로 바꾸어도 사이클이 발생하지 않는 안전상태일 경우

  자원 요청을 수용한다.

- 교착상태 탐지 및 복구 방법은 교착상태가 발생하였는가를 탐지한 후,

  희생자를 선택하여 프로세스를 중지시키거나 자원을 선점한다.