detection ALG

Data Structure

  • m = #(resources type)
  • n = #(process)
Available
  • vector
    • length = m
  • available resource instance of each type
Allocation
  • matrix
    • n * m
  • To each process, #(resource of each type)
Request
  • matrix
    • n * m
    • index = [i, j] and its value = k : $P_i$ request k resource to $R_j$

ALG

  • Work and Finish be vectors of length m and n
목표:
  지금 deadlock에 걸린 process가 있는지 찾기
 
초기화:
  Work = Available
 
  각 process Pi에 대해:
    Allocation[i] == 0 이면:
      Finish[i] = true
    Allocation[i] != 0 이면:
      Finish[i] = false
 
반복:
  Finish[i] == false 이고 Request[i] <= Work 인 process Pi를 찾기
 
  찾으면:
    Work += Allocation[i]
    Finish[i] = true
    다시 반복
 
  못 찾으면:
    반복 종료
 
판정:
  Finish[i] == false 인 process가 하나라도 있으면:
    system is in deadlock
 
  Finish[i] == false 인 process Pi는:
    deadlocked process