[운영체제] 데드락 2 : 데드락 처리 방법 - Deadlock Detection and Recovery, Deadlock Ignorance

Banker's Algorithm

테이블을 만들어 "최악의 상황"을 고려하여 자원을 줄지 말지를 결정하는 것이다.

• 현재 할당 중인 Allocation
• 프로세스가 최대로 요청할 Max
• 현재 할당 가능한 여유 자원인 Avaliable
• 프로세스가 앞으로 최대 얼마나 요청할 수 있는지 Need

자원 할당을 결정할 때 Avaliable와 Need만 비교하면 된다.
지금 얘가 얼마를 요청했는지가 중요한게 아니라, 앞으로 얼마나 더 달라고 징징될지를 고려하는 것이다.

위 상황에서 P0이 A 1, B 1을 요청했다고 치자.
줄 수는 있다. 여유가 된다.
그런데 이걸 줘도 p0은 앞으로 A6,B3,C3을 더 달라고 할 수 있다.
그럴 경우 줄 수가 없다. 그럼 데드락 발생할 가능성이 생긴다.
따라서 주지 않는다.

Deadlock Detection and Recovery

데드락 발생해도 냅둔다.
대신 가끔 살펴보고 데드락이 발생했으면 리커버리를 해 주는 것이다.

왼쪽 그림을 더 간단하게 표현한게 오른쪽 그림이다.
화살표를 '내가 원하는 걸 얘가 지금 들고 잇구나' 생각하면 된다.

Deadlock Avoidance 처럼 미리 자원 최대 사용량을 알 필요가 없다.
발생하든 말든 일단 냅둔다니까?

• 자원이 싱글 인스턴스 : cycle이 그려지면 데드락
• 자원이 멀티 : banker's와 비슷한 방법 활용
• Wait for graph 알고리즘
  - 자원 할당 그래프의 변형
  -사이클이 존재하는지를 주기적으로 조사 O(N^^2)
  -위 그림의 오른쪽이다.

자원 당 멀티 인스턴스인 경우, 뱅커스 알고리즘처럼 테이블을 만들어,
"낙관적인" 상황을 가정한다.

위 상황을 보자. 현재 Request에 자원들을 요청 중인 상황인데, 빈 자원이 없다.
먼저 요청이 없는 P0, P2를 보자.
'현재 요청이 없으니 얘들은 필요한게 전부 있나보네? 그럼 끝나고 반납하겠네?"
라고 최대한 낙관적인 상황을 가정하는 것이다.
그럼 Avaliable이 3,1,3이 될 것이다.

이제 이걸 p1,p3,p4 중 선택해서 주는 것이다.
위 예시는 어딜 줘도 된다.
p1에 2,0,2를 줬다고 치자. 그럼 얘는 현재 요청이 0일 것이고,
지금 자원들을 모두 반납할 거라고 가정하는 것이다.
그럼 또 자원을 합쳐서 p3,p4를 주는 것이다.

가능하니까 데드락이 발생하지 않는다.

위 예시에서 P2가 000이 아닌 001을 요청한다고 해보자.
그럼 요청이 없는게 p0의 010이다. 이걸 원하는 프로세스? 하나도 없다.
그럼 데드락인 것이다.

Recovery

1. Process termination : 연루된 모든 프로세스 다 죽여
2. Resource Preemption : 하나씩 죽이면서 데드락 풀리는 지 확인 (자원 하나씩 뺏어서 데드락이 풀리는지 확인)

Deadlock Ignorance

생기든 말든 알빠노?
디텍션과 리커버리, 어보이던스를 위한 오버헤드가 크니까.

데드락 생기면 프로세스들이 멈추겠지? 그럼 인간 니가 알아서 프로세스 종료 하셈 ㅋ