18. 데드락과 뱅커 알고리즘: Chapter 8. Deadlocks (Part 2)

8.6 교착 상태 회피Deadlock Avoidance

• 데드락 예방 알고리즘은 요청 방법에 제한을 두어 교착 상태를 예방함
• 이 제한은 데드락이 발생하기 위한 필요 조건 중 적어도 한 가지는 성립되지 않도록 보장함
• 그러나 이런 방식으로 데드락을 예방할 때 장치의 이용률이 저하되고 시스템 총처리율throughput이 감소한다는 문제가 발생
• 교착 상태 회피 
  • 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것
  • 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 각 요청에 대해서 가능한 미래의 교착 상태를 피하고자 스레드가 대기해야 하는지에 대한 여부를 결정할 수 있음
• 가장 단순하고 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것

 

 

안전 상태Safe State

• 안전 상태
  • 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원(최대 요구 수를 요구하더라도) 교착 상태를 야기시키지 않고 차례로 모두 할당해줄 수 있는 상태
  • 즉, 시스템이 안전 순서Safe Sequence를 찾을 수 있는 상태
    • <T1, T2, ... , Tn>과 같은 스레드 순서가 안전하다는 말은 모든 Ti가 요청하는 자원을 시스템에 현재 남아있는 자원과 앞에서 수행을 마칠 모든 스레드 Tj들이(j < i) 반납하는 자원들로 만족시켜 줄 수 있음을 뜻함
• 시스템 상태가 안전하다면 교착상태가 아님
• 교착 상태에 있는 시스템은 불안전한 상태에 있음
• 그러나 시스템 상태가 불안전하다고 해서 반드시 데드락에 빠진다는 것을 뜻하는 것은 아님
• 시스템이 불안정하다는 말은 앞으로 데드락에 빠질 수 있다는 것을 뜻함
• 교착 상태 회피 알고리즘의 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것으로 함
• 최초의 상태는 안전함
• 그 후 스레드들이 자원을 요청하면 시스템은 자원을 즉시 할당할 수 있는지, 아니면 스레드가 대기해야 하는지 결정해야 함
• 요청한 자원을 즉시 승낙해 주는 경우는 시스템의 상태가 안전 상태에서 안전상태로 옮길 때 뿐임

 

 

자원 할당 그래프 알고리즘Resource-Allocation Graph Algorithm

• 만약 각 자원 유형마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 자원 할당 그래프의 변형을 사용할 수 있음
• 예약 간선claim edge라는 새로운 타입의 간선을 도입함
  • 예약간선 Ti -> Rj는 Pi가 미래에 자원 Ri를 요청할 것을 의미하 
  • 요청 간선과 유사하지만 점선으로 표시함
• 자원 할당 그래프의 사이클을 탐지하여 안전성을 검사할 수 있음
• 만약 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 됨
• 사이클이 발견 되면 할당은 시스템을 불안전 상태로 만들 것이므로 스레드 Ti는 자신의 요청이 충족될 때 까지 기다려야 함

• 왼쪽 그림에서 T2가 R2를 요청한다고 가정
• R2는 현재 가용 상태지만 R2를 T2에 할당할 경우 그래프에 사이클이 생겨 시스템이 불안정한 상태에 있게 됨
• 만약 T1이 T2를 요청하고 T2가 R2를 요청하면 데드락이 발생함

 

 

은행원 알고리즘Banker's Algorithm

• 자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없음
• 뱅커스 알고리즘
  • 종류마다 자원이 여러 개씩 있을 경우 사용할 수 있는 교착 상태 회피 알고리즘
  • 이 알고리즘을 은행에 적용하면 고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 고객의 요청을 다 들어줄 수 있게 되기 때문에 이러한 이름이 붙여짐
• 자료구조
  • 시스템이 자원을 할당하고 있는 상태를 나타냄
  • n = 스레드의 수
  • m = 자원의 종류 수
  • Available
    • 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기가 m
    • Available[i] = k라면 현재 Rj를 k개 사용할 수 있다는 것을 뜻함
  • Max
    • 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬로 크기가 m
    • Max[i][j] = k라면 현재 스레드 Ti가 Rj를 최대 k개까지 요청할 수 있음을 나타냄
  • Allocation
    • 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n * m
    • Allocation[i][j] = k라면 현재 스레드 Ti가 Rj를 k개 사용 중임을 나타냄
  • Need
    • 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬로 크기가 n * m
    • Need[i][j] = k라면 스레드 Ti가 향후 Rj를 k개까지 더 요청할 수 있음을 뜻함
    • Need[i][j] = Max[i][j] - Allocation[i][j]

• 안전성 알고리즘: 시스템이 안전한지 아닌지를 알아낼 수 있는 알고리즘
  1. Work와 Finish는 크기가 m, n인 벡터이며 Work = Available로 초기값을 주고, i=0,1, ... n-1에 대해서 Finish[i] = false를 초기값으로 설정
  2. 아래 두 조건을 만족시키는 i값을 탐색하고 찾을 수  없으면 4로 이동
     • Finish[i] = false
     • Need[i] <= Work
  3. Work = Work + Allocation[i], Finish[i] = true로 설정한 뒤 2번으로 이동
  4. 모든 i값에 대해서 Finish[i] == true이면 이 시스템은 안전 상태에 있음
• 자원 요청 알고리즘: 자원 요청이 안전하게 들어줄 수 있는지를 검사하는 알고리즘
  1. Request[i] <= Need[i]이면 2번으로 이동. 아닐 경우 시스템에 있는 자원의 개수보다 더 많이 요청했으므로 오류로 처리
  2. Request[i] <= Available이면 3번으로 이동. 아닐 경우 요청한 자원이 당장은 없으므로 Pi는 기다려야 함
  3. 마치 시스템이 Ti에게 자원을 할당해준 것처럼 시스템에 상태 정보를 아래와 같이 바꾸고, 이렇게 바뀐 상태가 안전하다면 Ti에 여기에 반영된 정보대로 자원을 할당하고 불안전하다면 원상태로 복귀되고 Ti는 Request[i]가 만족할 때까지 기다려야 함
     • Available = Available - Request[i] 
     • Allocation[i] = Allocation[i] + Request[i] 
     • Need[i] = Need[i] - Request[i] 

• 예시
  • 다섯개의 프로세스 T0부터 T4까지 있다고 가정
  • A,B,C 세 종류의 자원이 있다고 가정
    • A 자원 10개, B 자원 5개, C 자원 7개가 있다고 가정
  • 위 그림은 시스템의 현재 상태의 스냅샷을 나타냄
  • 안정성 알고리즘 적용
    1. Work와 Finish는 크기가 m, n인 벡터이며 Work = (3,3,2)이고 Finish = {False, False, False, False, False}
    2. Finish[i] = false이고 Need[i] <= Work인 i값을 탐색
       1. i = 0
          • Need(7,4,3) <= Work(3, 3, 2) -> False
       2. i = 1
          • Need(1,2,2) <= Work(3, 3, 2) -> True
          • Work = Work + Allocation[1] = (3,3,2) + (2,0,0) = (5,3,2) / Finish =  {False, True, False, False, False}
       3. i = 2
          • Need(6,0,0) <= Work(5, 3, 2) -> False
       4. i = 3
          • Need(0,1,1) <= Work(5, 3, 2) -> True
          • Work = Work + Allocation[3] = (5,3,2) + (2,1,1) = (7,4,3) / Finish =  {False, True, False, True, False}
       5. i = 4
          • Need(4,3,1) <= Work(7, 4, 3) -> True
          • Work = Work + Allocation[4] = (7,4,3) + (0,0,2) = (7,4,5) / Finish =  {False, True, False, True, True}
       6. i = 2
          • Need(6,0,0) <= Work(7, 4, 5) -> True
          • Work = Work + Allocation[2] = (7,4,5) + (6,0,0) = (13,4,5) / Finish =  {False, True, True, True, True}
       7. i = 0
          • Need(7,4,3) <= Work(13, 4, 5) -> True
          • Work = Work + Allocation[0] = (13,4,5) + (0,1,0) = (13,5,5) / Finish =  {True, True, True, True, True}
  • 이 시스템은 <T1, T3, T4, T2, T0>의 순서는 안전성 기준을 만족하므로 안전함

• 만약 T1이 A자원 한 개와 C자원 2개를 추가로 요청한다고 가정 했을 때 자원 요청 알고리즘 적용
  1. Request[1] < Need[1] = (1,0,2) <= (1,2,2) -> True
  2. Request[1] < Available = (1,0,2) <= (3,3,2) -> True
  3. 마치 시스템이 T1에게 자원을 할당해준 것처럼 시스템에 상태 정보 변경한 결과(위 이미지) 상태 정보로 안전성 검사 알고리즘 체크
     1. Available = Available - Request[1] = (3,3,2) - (1,0,2) = (2,3,0)
     2. Allocation[1] = Allocation[1] + Request[1] = (2,0,0) + (1,0,2) = (3,0,2)
     3. Need[i] = Need[i] - Request[i] = (1,2,2) - (1,0,2) = (0,2,0) 
• 안전성 알고리즘의 결과로 <T1, T3, T4, T0, T2>가 안전성 조건을 만족시킴
• 따라서 T1의 요청을 들어줄 수 있음
• 만약 T4이 (3,3,0)을 요청할 경우 자원이 모자라므로 들어줄 수 없음 (자원 요청 알고리즘 2번에서 False로 결과 도출)
• 만약 T0이 (0,2,0)을 요청할 경우 자원은 충분하지만 상태를 불안전 상태로 만드므로 들어줄 수 없음(자원 요청 알고리즘 3번에서 안전성 알고리즘 결과 False로 결과 도출)

 

 

8.7 교착 상태 탐지Deadlock Detection

• 위의 뱅커스 알고리즘을 비롯한 교착 상태 회피 자원을 요청할 때마다 실행 되므로 오버 헤드가 큼
• 이러한 이유로 데드락을 허용하고 회복하는 교착 상태 탐지 알고리즘 고안
• 교착 상태 탐지
  • 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
  • 교착 상태로부터 회복하는 알고리즘

 

 

각 자원 유형이 한 개씩 있는 경우

• 대기 그래프wait for graph를 사용하여 고착 상태 탐지 알고리즘 정의
  • 대기 그래프: 자원 할당 그래프(a)에서 자원 유형의 노드를 제거하고 적절한 간선을 결합한 그래프
• 대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재
• 교착 상태를 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있음
• 따라서 주기적으로 그래프에서 사이클을 탐지하는 알고리즘을 호출함

 

 

각 유형의 자원을 여러 개 가진 경우

• 대기 그래프는 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없음
• 종류마다 자원이 여러 개씩 있을 경우 교착 상태 탐지 알고리즘 사용
• 자료구조
  • 시스템이 자원을 할당하고 있는 상태를 나타냄
  • n = 스레드의 수
  • m = 자원의 종류 수
  • Available
    • 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기가 m
    • Available[i] = k라면 현재 Rj를 k개 사용할 수 있다는 것을 뜻함
  • Allocation
    • 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n * m
    • Allocation[i][j] = k라면 현재 스레드 Ti가 Rj를 k개 사용 중임을 나타냄
  • Request
    
    • 각 스레드갸 향후 요청중인 자원의 개수를 나타내는 행렬로 크기가 n * m
    • Request[i][j] = k라면 스레드 Ti가 Rj를 k개 요청 중임을 뜻함
• 교착 상태 탐지 알고리즘: 시스템이 데드락에 걸렸는지 아닌지를 알아낼 수 있는 알고리즘
  1. Work와 Finish는 크기가 m, n인 벡터이며 Work = Available로 초기값을 주고, i=0,1, ... n-1에 대해서 Allocaiton[i] != 0이면 Finish[i] = false이고  Allocaiton[i] == 0이면 Finish[i] = true로 초기값 설정
  2. 아래 두 조건을 만족시키는 i값을 탐색하고 찾을 수  없으면 4로 이동
     • Finish[i] = false
     • Request[i] <= Work
  3. Work = Work + Allocation[i], Finish[i] = true로 설정한 뒤 2번으로 이동
  4. 어떠한 i값에 대해서 Finish[i] == false이면 이 시스템은 교착 상태에 빠져 있는 것으로 판단

• 예시
  • 다섯개의 프로세스 T0부터 T4까지 있다고 가정
  • A,B,C 세 종류의 자원이 있다고 가정
    • A 자원 7개, B 자원 2개, C 자원 6개가 있다고 가정
  • 위 그림은 시스템의 현재 상태의 스냅샷을 나타냄
  • 교착 상태 탐지 알고리즘을 적용한 결과, 이 시스템은 <T0, T2, T3, T1, T4>의 순서로 작업을 다 끝낼 수 있고 이때 모든 i에 대해서 Finish[i] == true가 가 됨을 알 수 있음

• 만약 T2이 C자원 한 개를 추가로 요청한다고 가정 했을 때 교착 상태 탐지 알고리즘을 적용
  
  • 위 이미지는 시스템의 현재 상태의 스냅샷을 나타냄 (Request 행렬이 변화함)
  • 이 시스템은 데드락에 빠짐
  • T0의 자원을 회수해도 다른 프로세스들이 자원을 충족시켜줄 방법이 없음
  • 따라서 T1, T2, T3, T4가 데드락에 빠짐

 

 

탐지 알고리즘 적용

• 탐지 알고리즘의 실행 빈도수에 관한 2가지 관점
  1. 데드락이 얼마나 자주 일어나는가?
  2. 데드락이 일어나면 통상 몇 개의 스레드가 거기에 연루되는가?
• 데드락이 자주 일어나면 탐지 알고리즘도 자주 돌려야 함
• 그러나 자원을 요청할 때마다 탐지 알고리즘을 돌리면 오버헤드가 너무 크게 됨
• 오버헤드를 줄이는 간단한 대안은 지정된 시간 간격으로, 예를 들면 한 시간에 한 번 또는 CPU 이용률이 40% 이하로 떨어질 때 탐지 알고리즘을 호출하는 것 등이 있음

 

 

8.8 교착 상태로부터의 회복Recovery from Deadlock

• 탐지 알고리즘이 데드락이 존재한다고 결정했을 때, 여러 대안의 처리 방법이 존재함
  1. 운영자가 수작업으로 처리
  2. 시스템이 자동으로 데드락으로부터 회복하게 하는 것
• 데드락을 깨뜨리는 2가지 방법
  1. 한 개 이상의 스레드를 중지abort 시키는 것
  2. 데드락에 있는 하나 이상의 스레드들로부터 자원을 선점preempt 하는 것

 

 

프로세스와 스레드의 종료

• 교착 상태 프로세스를 모두 중지
  • 확실하게 데드락 상태의 사이클을 깨드리지만 비용이 큼
• 교착 상태가 제거될 때까지 한 프로세스씩 중지
  • 각 프로세스가 중지될 때 마다 교착 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 데드락에 있는지 확인해야 하므로 상당한 오버헤드를 유발함

 

 

자원 선점

• 자원 선점을 이용해 교착 상태를 제거하려면, 교착 상태가 깨어질 때 까지 프로세스로부터 자원을 계속 선점해 이 자원들을 다른 프로세스에 주어야 함
• 자원 선점 시 3가지 고려사항
  1. 희생자 선택selection of a victim: 어느 프로세스가 선점될 것인가?
  2. 후퇴rollback: 선점 당한 프로세스를 안전한 상태로 후퇴시켜야 함
  3. 기아 상태starvation: 자원들이 동일한 프로세스로부터 항상 선점되지 않는다는 것을 어떻게 보장하는가?, 즉 기아 상태가 발생하지 않는 것을 어떻게 보장하는가?