[운영체제] 7. 교착상태 - (4) 교착상태 발견 및 복구

📍1. 교착상태 발견 전략

요청된 자원들이 할당 가능한 상황이면 항상 프로세스에게 할당함

1-1. 자원 할당이 거절될 때마다 발견 알고리즘 수행

✔️교착상태를 빠른 시점에 발견할 수 있음
✔️발견 알고리즘이 간단함 (단일 환형 대기)
✔️잦은 검사로 오버헤드가 큼

1-2. 주기적 또는 기준에 의해 발견 알고리즘 수행

✔️시스템의 처리율 및 처리기 이용률이 저하
✔️다중 환형 대기와 연관되어 알고리즘이 복잡함

2-1. 필요한 벡터 및 행렬

✔️자원 벡터(R) : 시스템에 존재하는 자원의 전체 개수
✔️가용 벡터(V) : 현재 사용 가능한 자원의 개수

✔️할당 행렬(A) : 프로세스가 할당 받아 점유하고 있는 자원의 개수
✔️요청 행렬(Q) : 프로세스가 요청한 자원의 개수

2-2. 알고리즘 : 가용 자원으로 완료될 수 있는 프로세스를 발견

1️⃣할당 행렬(A)에서 행의 값이 모든 0인 프로세스를 표시

2️⃣현재 사용 가능한 자원의 개수(V)를 벡터 W의 초기값으로 설정

3️⃣표시되지 않은 프로세스들 중에서 요청 행렬 Q의 행의 값이 W보다 작거나 같은 프로세스를 찾아 표시

✔️1≤k≤m인 모든 k에 대해서 Qik ≤ Wik가 성립

✔️만약 이러한 프로세스가 없으면 알고리즘을 종료

☑️알고리즘이 종료된 이후에 표시되지 않은 프로세스가 존재한다면 그 프로세스들에서 교착상태가 발생한 것!!

2-3. 수행 결과: 자원 할당 그래프

2--4. 교착상태 복구 알고리즘

✔️교착상태에 포함되어 있는 모든 프로세스를 종료시킴

✔️교착상태에 포함되어 있는 각 프로세스를 이전의 검사점으로 되돌린 후(백트래킹) 모든 프로세스를 다시 수행시킴

✔️교착상태가 없어질 때까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료시킴

✔️교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킴

2-5. 교착상태 발견 및 복구 방법의 장단점

✔️장점
- 프로세스 시작을 지연시키지 않으므로 많은 병행성을 허용함

✔️단점
- 선점에 의한 손실이 발생
- 잦은 검사는 상당한 처리기 시간을 낭비함

✔️‘교착상태는 발생하지 않을 거야’ 하고 아무 대책을 취하는 않는 접근법

- 사용자나 관리자가 의심 가는 프로세스를 종료시키거나 시스템 재시작(reboot) 하는 방법으로 해결
- 거의 발생하지 않거나 아주 드물게 발생하는 것에 비해 3가지 교착상태 해결에는 상대적으로 비용이 많이 들기 때문

✔️주의
- 핵 시스템, 비행기, 미사일 등 시스템 재시작이 파국을 초래할 hard realtime 시스템이나 환자 감시 시스템 등에는 적합하지 않음