1. Resource Allocation Graph
Deadlock 감지를 위해 사용되는 그래프로서, Directed Bipartite(이분) Graph
(노드가 두 그룹으로 분리되고, 간선은 같은 그룹이 아닌 다른 그룹 사이에만 생성된 그래프)
✔️ 노드 : Np (Process 노드) & Nr(Resource 노드)
✔️ 간선(Edge) : Np와 Nr 사이를 연결
(P, R) : edge를 request한 edge
(R, P) : Allocation된 edge
✔️ 변수 t
모든 자원의 타입에 대해서 t라는 변수가 존재하는데, 해당 자원의 unit 개수를 의미한다.
✔️ |(a,b)| : 노드 a에서 노드 b로 가는 edge의 개수
2. Deadlock Detection Example
✔️ 2개의 프로세스 P1, P2가 있는 상태
➡️ 교착상태인가?!
P1은 R1 두개를 갖고 있는데 R2를 요청중.
R2의 자원 하나는 Available하다.
P2는 R1에 하나, R2에 하나 요청중.
➡️ R2 자원 하나를 P1에 할당해주면 P1은 Sleep에서 깨어나서 실행할 것이고, p1이 종료되면 자원을 모두 반납할 것이다.
P2에게 R2와 R1을 할당해줄 수 있으므로 '교착상태가 아니구나!'
➡️ 만약 R2를 P2에게 할당해주면, P1은 R2 때문에 Sleep하고 P2는 R1 때문에 Sleep하므로 교착상태에 걸릴 것이다.
☑️ 현재 상태를 기준으로는 아직 교착 상태가 아니므로, 현재 상황에서의 "best case"를 본다! (VS avoidance는 worst case를 보는 기법)
3. Deadlock Detection Method
1) Graph Reduction
그래프의 edge를 하나씩 지워가면서 reduction하는 것이다.
✔️Edge가 전부 제거되면, "completely reduced"라고 보고 "교착 상태 없다"고 판단
✔️Edge가 전부 제거불가능하다면, "irreducable" 상태로 "교착 상태가 있다" 판단
📌 Unblocked Process란?!
✔️만약 프로세스가 요청한 자원들을 전부 할당받을 수 있는 상태라면, Unblocked Process이다.
✔️할당 받을수 없다면 blocked process다.
공식 ➡️ 모든 자원에 대해서, "프로세스가 각 자원을 요청한 개수 <= (해당 자원의 총 개수 - 자원에서 프로세스들에게 할당한 개수)"를 만족한다면 "unblocked"이다!
2) 리소스 제거 과정
Unblocked Process 노드의 간선을 모두 지운다.
모든 간선이 지워진다면, 'deadlock'이 없는 것이고 그렇지 않다면 'deadlock'이 있는 것이다.
(a) P1의 Edge를 전부 지운다.
(b) (P1이 리소스를 다 반납하면)
P2도 Unblocked되므로, Edge도 지울 수 있다.
(c) 모든 간선이 다 사라지므로, 이 상태는 deadlock이 없는 상태다.
(a) 초기 상태
p1 : r1, r2에 하나씩 요청 중. r1 2개, r2 1개 할당 받음.
p2 : r2 2개 요청, r3 1개 요청 중. r1 하나 할당 받음.
p3 : r3 1개 요청, r2 1개, r3 한개 할당 받음.
r1 : 잔여 자원 없음.
r2 : 잔여 자원 없음.
r3 : 잔여 자원 1개.
➡️ p3만 unblocked 상태이므로, p3의 간선을 제거한다.(b) P3이 반납한 이후
p1 : r1, r2에 하나씩 요청 중. r1 2개, r2 1개 할당 받음.
p2 : r2 2개 요청, r3 1개 요청 중. r1 하나 할당 받음.
r1 : 잔여 자원 없음.
r2 : 잔여 자원 1개.
r3 : 잔여 자원 2개.
➡️ 여전히 p1, p2는 blocked 상태임.
즉, 더 이상 간선을 지울 수 없으므로 p1과 p2는 교착상태이다.
📌 BUT! 교착상태 검출 기법의 문제 => 알고리즘의 시간복잡도가 매우 높다.
4. 다른 기법들
Case 1) 모든 리소스 타입의 Unit이 한개라면
-> 'Cycle Detection' 기법 : Cycle이 있으면 교착상태고, 그렇지 않으면 교착상태가 아니다! (간단하게 판별 가능)
-> 실제 컴퓨터 시스템에선 사실상 불가능
Case 2) Single Unit Request 일 경우
-> 가정: 한 프로세스가 요청을 '하나씩'만 한다.
ex) 한 프로세스가 r1에 하나, r2에 하나 요청 X.
-> 가정: 자원 할당이 가능하면, 즉시 할당한다.
-> Knot Detection을 하여 교착상태를 검출한다.
📌정리
Avoidance 기법은 'worst case'를 본다.
Detection 기법은 'best case(favorable case)'를 본다.
현재의 교착상태를 고민하며, 앞으로 발생할지 말지에 대해서는 고려하지 않는다.
