Deadlock의 처리 방법
Deadlock Avoidance
프로세스가 시작될 때, 그 프로세스가 최대로 사용할 자원을 미리 declare.
이 프로세스는 평생의 내가 최대로 자원을 요청할 때는 어떤 자원을 몇개까지 요청할 수 있다를 알려줌
프로세스가 자원을 요청했을 때, deadlock 가능성이 있다면 할당하지 않고, 안전할 때만 자원을 할당해주는 방법.
자원당 instance가 하나밖에 없을 때는 자원 할당 그래프를 이용해서 deadlock avoidance를 할 수 있음.
자원당 instance가 여러개 있는 경우에는 Banker's Algorithm 을 이용해서 deadlock avoidance를 할 수 있었음.
Example of Banker's Algorithm
만약에) 0번 프로세스가 A 자원 하나를 요청했을 때,
A의 남은 자원은 3개이기 때문에 요청을 받아들일 수는 있음. 근데 안줌.
이 알고리즘은 최악의 경우를 가정하기 때문에,
하나만 요청하고 반납할지 모르겠지만, 프로세스 0번은 A 7개, B 4개, C 3개가 최대요청이다.
현재 가용자원 A 3개, B 3개, C 2개로 충족이 되지 않는다.
충족이 되면, 어떤 요청이든 받아들이고, 충족이 안되면, 요청 받아들이지 않음.
P1의 요청은 다 받아줌. 최대 요청을 현재 자원이 충족할 수 있음.
각 프로세스의 최대요청 자원을 다 충족할 수 있는 sequence가 존재하면은 이 상황은 safe한 상태
=> 절대 deadlock이 생기지 않는 상태
즉, Banker's algorithm은 프로세스가 각자 최대요청을 해도 deadlock이 생기지 않는 요청만을 받아들인다.
- deadlock은 안생김.
- 사실, 굉장히 비효율적임. (자원이 남아도는데도 안줌)
process가 n개가 있는데 가용자원이 남아있는 상황.
가용자원만 가지고 최대요청을 처리할 수 있는 process가 있겠죠
그 process한테 가용자원을 투자하면 MAX를 충족시켰기 때문에 그 자원을 언젠가 뱉어내겠죠.
그 process는 끝.
그 이후,
n-1개의 process 중 최대 요청을 충족할 수 있는 프로세스한테 ~~ 반복...
이렇듯 safe sequence가 있다면 deadlock을 avoidance 할 수 있다. => 아주 안전한 방법
unsafe 하다고 해서 deadlock은 아님.
p1 request (1,0,2)
프로세스1이 A=1개, C=2개를 요청했을 때
가용자원 A,C가 남아있기 때문에 주는게 아니고, 최대요청인 A1,B2,C2를 가용자원으로 모두 충족할 수 있기 때문에 자원을 준다.
Deadlock Detection and Recovery
Deadlock은 빈번히 발생하는 event가 아니기 때문에 미연에 방지를 하기 위한 비효율적 방법은 별로.
남은 자원있으면 다 주고,
상황이 이상하면 deadlock detection을 하고, 발견되면 recovery 한다.
자원당 instance가 하나밖에 없는 경우
자원할당 그래프를 이용해서 deadlock detection을 한다.
자원당 instance가 여러개 있을 경우
table을 그려서 현재 상황이 deadlock인지 detection 할 수 있다.- 사실은, 그래프를 이용하는게 table의 subset임. 자원당 instance가 하나밖에 없다해도 그래프를 굳이 안그리고, table 형태로 해도됨.
- 자원당 instance가 하나밖에 없는 상황에서도 table로 그려놓고, Banker's 알고리즘을 사용하는게 더 간단함.
그래도 설명해볼것.
자원당 instance가 한 개일 때 deadlock 찾기)
deadlock을 찾아낼 때 (b) 그래프 같이 자원을 생략하면 더 사이클을 찾기 쉽다
보면, p1 => p2 => p4 사이클 하나, p4 => p1 => p2 => p3 순환 사이클 확인 !
사이클을 찾는 overhaed는 얼마나 될까?
화살표 최대의 경우: n개 프로세스 각각에 대해서 n-1개의 선이 있는 것.
즉, 화살표는 n * (n-1)개 이다.
따라서 사이클을 찾는것은 O(n^2)이면 된다.
자원당 instance가 여러개일 때 deadlock 찾기)
- deadlock detection은 MAX 값은 주어지지 않아. 왜냐하면 그냥 자원 필요하다고 하면 다 자원을 주기 때문임.
- 보수적 X, 낙관적 접근
- deadlock인지 아닌지 알려면, 요청 자원이 없는 process가 가지고 있는 자원을 다 쓰고 반납하면 그걸 또 다른 process한테 할당하는 방식을 계속 반복적으로 낙관적으로 보면서 deadlock을 detection 한다.
- 예)0번 프로세스는 b 하나를 가지고 있다. 반납할 것이다 ~~~ => 2번 프로세스는 a3개, c3개도 반납할 것이다 ~~ => 그러면, 가용자원 a3, b1, c3개가 생김 => 그러면, p1이 요청한 자원 a2, c2를 줄 수 있게 됨. 이런식으로 간다.
그런데 만약,
P2가 자원C 하나를 요청하는 걸로 변경한다면?
- 자원 요청을 안한 Process는 p0밖에 없음. 그래서 그 프로세스가 할 일 다하고 B를 내놓는다. => 그런데 B를 원하는 process는 없음. => 어떤 프로세스도 일이 끝나지 않아 자원을 내놓지 않음 => Deadlock
이런식으로 하다가, Deadlock이 발견이 되면 Recovery를 하면 됩니다.
1) deadlock에 연루된 process를 사살해버려,,,
- 모든 process를 한꺼번에 죽인다.
- deadlock이 끝날 때까지 하나씩 죽여
2) deadlock에 연루된 process에게서 자원을 뺏는다.
Deadlock Ignorance
deadlock이 생기지 않는다고 가정
