OS(0516) - Deadlock 처리 방법

#Deadlock Avoidance - Motivation

A에게 프린터가 이미 할당, t에서 B는 플로터 요

- Example to motivate a D.A. algorithm

1. state p - 아무 프로세스도 돌지 않음

2. state q - 스케줄러가 A를 실행

3. state r - 스케줄러가 B를 실행

4. state s - 스케줄러가 A를 실행하고, A가 프린터를 요청, 받음

5. state t - 스케줄러가 B를 실행하고, B가 plotter를 요청, 받음

- 음영처리된 영역을 보면

    > \\\는 양쪽 프로세스가 프린터를 동시에 사용 -> 그러나 mutual exclusion에 의해 허용되지 않음

    > ///는 비슷하지만, 플로터

- "unsafe"

    > OS가 이 박스에 들어가면, 데드락 걸림 -> 음영 영역(illegal mutual exclusion)에 들어가야 하기 때문

        > 모든 경로는 위나 오른쪽으로만 진행 가능함

    > 박스는 unsage - 들어가면 안됨

        > state t에서, 오른쪽으로가서 unsafe영역을 피해야 함

- state t에서, OS는 B의 요청을 충족시킬지 말지 결정해야 함

    > 좋은 선택이 deadlock 피함

    > 미리 어떤 자원이 필요한지 알아야 함

 

#Deadlock Avoidance - Safe and Unsafe States

- (a)는 safe, 모든 프로세스가 정상적으로 종료될 수 있다는 뜻

    > B는 추가적으로 2 리소스 요청, 1 남음

        > B종료 후 반환, 5 free

    > C가 5 요청, 0 free

        > C종료 후 7 반환

    > A가 6 더 가져오고, 종료

 

- (a)에서 시작, (b)에 도달했다고 가정, A의 다른 리소스를 조금 떼줌

    > B runs, asks for 2 more resources, 0 free

        > B종료, 4 free

    > C can`t run - wants 5 resources

        > A도 5 요청하므로 불가

- State (b)는 unsafe, 데드락이 걸릴수도 있는 상태

    > 데드락 상태는 아니다 - 시스템이 조금씩 돌릴 순 있음

    > 데드락은 아마 안일어날 것이다 -> A가 자신의 리소스를 반환, C가 실행될 수 있도록함

 

#The Banker`s Algorithm for Single Resources

- Resource request algorithm:

    > 은행원은 각 요청이 발생할 때마다 해당 요청이 safe으로 연결되는지 여부를 결정

    > safe이라면 요청 승인

    > 아니라면 연기

- 안전성 알고리즘:

    > 상태가 안전한지 여부를 판단하기 위해 은행원은 어떤 고객에게 충분한 자원 제공하는지 확인

    > 그렇다면, 고객이 자원을 사요으 완료, 해제 할것으로 가정

    > 다른 고객에게 또 충분히 제공하는지 확인

    > 모든 대출이 최종적으로 상환된다면, safe, 초기 요청 승인

 

#Evaluation of Deadlock Avoidance Using the Banker`s Algorithm

- 장점:

1. 데드락 감지 및 복구과 같은 자원 선점 및 상태 롤백 불요

2. Deadlock prevention보다 제한적인 요구사항 없음

- 단점:

1. 각 프로세스의 최대 자원 요구량이 사전에 명시돼야 함

2. 고려되는 프로세스는 동기화 요구사항에 의해 제한되지 않은 독립적

3. 고정된 자원 수(자원 추가 및 자원 손상 불가)와 프로세스 수(프로세스 추가 및 삭제 불가)가 있어야 함

4. 큰 오버헤드. 자원 요청시마다 알고리즘 사용해야 함

 

#데드락 해결 접근법 평가

- The Ostrich Approach - 문제 무시

    > 데드락이 빈번하지 않으면 좋은 해결책

- Deadlock prevention - 4가지 데드락 조건중 하나 제거

    > 제한적임

- Deadlock detection and recovery - 데드락 감지한 후 데드락 해제

    > 감지 빈도와 성능/오버헤드 추가 사이의 균형 유지해야 함

- Deadlock Avoidance - 데드락으로 이어지지 않는 요청만 수행

    > 사전에 너무 많은 정보가 필요, 동적이지도 않음(프로세스나 자원 추가 불가), 많은 오버헤드 발생