교착상태 회피, 교착상태 탐지 및 복구

 

1. 교착상태 회피 

- 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법 

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

 

- 안전상태: 교착상태가 발생하지 않음 

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

  -> 안전 순서열이 존재하는 경우 

 

- 불안전상태: 안전순서열이 존재하지 않는 경우 

 

 

안전순서열

- 순서 있는 프로세스의 집합 <p1, p2, ..., pn>에 대해서 

- 각 pi에 대해 pi가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나 혹은 여기에 pj에 할당된 자원까지 포함하여 충당 가능한 경우 

 

 

안전순서열이 되지 않는 경우 

 

 

 

 

1개 밖에 없는 상황에서 p2에게 나눠준 다음에 회수를 해와도 다음 것을 줄 수 있는 것이 없다. 

 

 

이 경우 먼저 p2에게 나눠주고 받아온 것으로 p3에게 나눠주면 모든 자원을 나눠주고 완수할 수 있다. 

 

 

교착상태는 불안전상태에서만 발생 가능 -> 항상 안전상태를 유지해야함 

-> 프로세스가 가용상태의 자원을 요구하더라도 프로세스는 대기상태가 될 수 있음 

-> 자원이용율은 다소 낮아지더라도 

 

 

 

교착상태 회피 알고리즘 

- 각 자원의 단위자원이 하나밖에 없는 경우 변형된 자원할당 그래프 이용

- 각 자원의 단위자원이 여러 개일수 있는 경우 은행원 알고리즘 이용 

 

 

변형된 자원할당 그래프

- 자원 정점에 표시하던 단위자원의 개수 제거

- 선언 간선 (pj, rj)추가 

  -> 앞으로 프로세스 pi가 자원 rj를 요구하게 될 것임을 의미

  -> 요구간선과 구분을 위해 점선으로 표시 

 

 

-> 자원을 요구 받으면 해당 선언간선을 요구간선으로 변경

-> 그 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환

 

 

 

 

 

은행원 알고리즘

- 자원을 요구받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인

- 안전상태가 보장되는 경우에만 자원 할당 

 

변수설정 

MAXi : pi의 최대요구

ALLOCi: pi의 할당자원

NEED: pi의 추가요구 

AVAIL: 가용자원 

 

 

 

 

 

 

2. 교착상태 탐지 및 복구 

 

사후에 처리하는 방법이다. 

 

교차상태 탐지

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

 

교착상태 복구

- 교착상태가 탐지된 경우 적절한 조치를 취해 정상상태로 복구 

 

 

Shoshani와 Coffman 알고리즘 

-> 현상황 체크

 

 

 

그런데 문제는 시간복잡도가 O(mn^2)으로 매우 비효율적 

 

-> 알고리즘 수행 시점을 조정

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

- 정해진 시간간격

- CPU 효율이 일정 수준 이하로 떨어질 때 

 

 

 

교착상태가 탐지되면 복구조치 

- 복구의 주체

  -> 오퍼레이터: 수작업으로 복구

  -> 운영체제: 자동으로 복구

- 복구방법

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

  -> 교착상태 프로세스가 할당받은 자원을 해제 

 

 

 

교착상태 프로세스 종료하기

- 모든 교착상태 프로세스를 종료: 단점은 진행했던 내용에 대한 복원비용이 크다

- 사이클이 제거될 때까지 교착상태 프로세스를 하나씩 종료: 매 프로세스 종료후 교착상태 재확인을 위한 비용 

 

 

교착상태 프로세스가 할당받은 자원을 해제

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

- 프로세스와 자원 선택 기준: 프로세스 진척도, 사용중인 자원의 수 등

- 프로세스의 복귀 시점도 제반 요소를 고려하여 결정

- 기아상태에 빠지지 않도록 프로세스 선택시 복구 횟수 고려 

 

 

 

 

 

 

---

참고자료: 운영체제(김진욱, 이인복 공저, KNOU press 출판)