교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)

Presentation on theme: "교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)"— Presentation transcript:

1 교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
운영 체제는 실시간으로 탐지 알고리즘 수행하여 교착 상태를 탐지하여야 함 교착 상태가 존재하면 정상 처리될 수 있게 이를 회복(recovery)해야 함 - 이 과정에서 프로세스와 자원의 낭비가 초래됨 자원 할당 그래프를 이용하여 탐지할 수 있음 그래프 내의 모든 프로세스에 대하여 화살표를 제거할 수 있으면 교착 상태는 없고 제거 불가능 하다면 교착 상태일 가능성이 있음 OS07

2 교착 상태 해결 : 교착 상태 탐지 탐지 알고리즘 교착 상태 확인 후 회복을 위해 시스템이 해야 할 작업
교착 상태 회피 알고리즘의 변형 교착 상태 확인 후 회복을 위해 시스템이 해야 할 작업 ① 프로세스에 할당된 자원에 관한 정보뿐만 아니라 자원 할당 요청에 대한 정보도 유지해야 함 ② 교착 상태 유무를 알기 위해 이 정보를 이용할 알고리즘이 제공 되어야 함 OS07

3 교착 상태 해결 : 교착 상태 탐지 탐지 알고리즘(Shoshani and Coffman algorithm)
n개의 프로세스, m개의 자원 종류 Available : 각 종류(자원)에서 사용 가능한 자원 수를 나타내는 값이 m인 벡터 Allocation : 현재 각 프로세스에 할당된 각 종 자원의 수를 정의한 (n x m) 행렬 Request : 각 프로세스가 현재 요청한 자원을 나타내는 (n x m) 행렬 (1) Work와 Finish는 각각의 값이 m과 n인 벡터. 초기치로 Work = Available; if Allocation[i, j] ≠ 0 then Finish[i] = false otherwise Finish[i] = true 단, i=1, 2, …, n (2) 다음과 같이 되는 i 값을 찾는다. a. Finish[i] = false b. Request[i, j] ≤ Work[j] 만일, 이러한 i 값이 존재하지 않는다면 4단계로 간다. (3) Work[j] = Work[j] + Allocation[i, j] Finish[i] = true go to step (2) (4) 모든 i에 대하여 Finish(i) = true이면, 이 시스템은 안전 상태, 또한 Finish(i) = false이면 P(i)는 교착 상태 OS07

4 (예) 교착 상태 탐지 알고리즘 : 1. 미교착 상태의 경우
(자원 수 : A=9, B=5, C=7) 할당량 (Allocation) 요구량 (Request) 잔여량 (Available) A B C 1 2 3 ⑤ p1 6 4 9 5 7 ② p2 ④ p3 8 ① p4 ③ p5 미교착 상태 순서 : <P4, P2, P5, P3, P1> OS07

5 (예) 교착 상태 탐지 알고리즘 : 2. 교착 상태의 경우
(예) 교착 상태 탐지 알고리즘 : 2. 교착 상태의 경우 (자원 수 : A=9, B=5, C=7) 할당량 (Allocation) 요구량 (Request) 잔여량 (Available) A B C 1 2 3 p1 6 4 p2 p3 ① p4 p5 5 8 p4가 수행되고 (2)를 만족하는 프로세스가 없으므로 (4)에서 p1, p2, p3, p5가 false이므로 교착상태가 탐지 됨 OS07