CS & C++ Notes

8.7 Deadlock Detection

11 min read

일반적으로 시스템은 아래와 같은 dead lock을 예방하거나 피하는 알고리즘을 제공한다.

  1. 데드락 발생 여부를 판단하기 위해 시스템의 상태를 조사하는 알고리즘
  2. 데드락에서 회복하기 위한 알고리즘

해당 섹션에서는 1번에 대해서 알아본다.


알고리즘이 동작하는 방식은 2가지 요소에 의해 나누어진다.

  1. Single Instance of Each Resource Type (하나의 인스턴스)
  2. Several Instances of a Resource Type (여러 개의 인스턴스)

resource는 추상적 개체를 의미하고, instance는 실질적 요소를 의미한다.

알고리즘의 고려 사항
  1. 런타임 비용 : 시스템이 필요한 정보를 계속해서 업데이트하고 유지하는데 필요한 비용과, 데드락을 확인하기 위해 감지 알고리즘을 실행하는 비용.
  2. 잠재적 손실 : 데드락에서 회복하는 과정에서 발생할 수 있는 손실을 의미. 예를 들어, 데드락을 해결하기 위해 일부 작업을 중단시키거나, 데이터를 롤백(원래 상태로 되돌림)하는 등의 조치가 필요할 수 있으며, 이로 인해 시간이 소요되거나 데이터 손실이 발생할 수 있다.

요약하면 탐지 비용과 문제가 있을 경우 해결에 필요한 비용을 고려해야한다.

8.7.1 Single Instance of Each Resource Type

  • 그래프의 종류와 방식
    1. 대기-그래프(wait-for graph) : 모든 자원이 하나의 인스턴스만 가질 경우, 자원 노드를 제거하고 만든 그래프
    2. 자원-할당 그래프(Resource-allocation graph) : 모든 자원을 표시한 그래프

    single “리소스 to 인스턴스”이기 때문에 표기만 다를 뿐 결과는 같다.


  • 데드락 판단 : 대기-그래프에 사이클이 포함되어 있을 때, 데드락이 존재한다고 할 수 있다. 따라서 데드락 감지를 위해서는 사이클을 탐색하는 알고리즘을 사용하고 해당 알고리즘은 O()의 연산을 요구한다. (정점의 수가 n)

    물론 문제가 생긴다면 보다 적은 비용이 발생한다.

8.7.2 Several Instances of a Resource Type

Note

대기-그래프 방식은 각 자원 유형마다 여러 인스턴스가 있는 자원 할당 시스템에는 적용되지 않는다. 해당 섹션에서 여러개의 인스턴스를 가진 시스템에 적용 가능한 데드락 감지 알고리즘을 알아보자.

  • 알고리즘의 구조
    • Banker’s Alogrithm에서 사용된 것과 유사한 여러 시간 변화 데이터 구조를 사용한다.
      • Available : 각 유형의 사용 가능한 자원 수를 나타내는 길이 의 벡터
      • Allocation : 각 스레드에 현재 할당된 각 유형의 자원 수를 정의하는 행렬
      • Request : 각 스레드의 현재 요청을 나타내는 행렬.
  • 표기의 단순화
    • 행렬 Allocation과 Request의 행을 벡터로 취급한다.
    • Allocation와 Request로 이를 참조한다.
  • 알고리즘의 과정
    1. Work와 Finish를 각각 길이 m과 n의 벡터로 설정한다. Work = Available로 초기화한다. i = 0, 1, …, n-1에 대해, Allocation ≠ 0이면 Finish[i] = false이다. 그렇지 않으면 Finish[i] = true이다.
    2. 다음 조건을 모두 만족하는 인덱스 i를 찾는다: a. Finish[i] == false b. Request$_i$ ≤ Work 만약 그러한 i가 존재하지 않으면, 4단계로 이동한다.
    3. Work = Work + Allocation Finish[i] = true 2단계로 이동한다.
    4. 일부 i에 대해 0 ≤ i < n, Finish[i] == false이면 시스템은 데드락 상태에 있다. 더욱이, Finish[i] == false라면, 스레드 Ti는 데드락 상태에 있다.

이 알고리즘은 시스템이 데드락 상태에 있는지 감지하기 위해 의 연산을 요구한다.

  • 알고리즘 해설

    1. 2단계에서 Request ≤ Work(2b에서 결정)를 만족하는 즉시 스레드 의 자원을 회수하는이유

      : 가 현재 데드락에 관여하고 있지 않다는 것을 알고 있다(Request ≤ Work 때문에). 따라서, 낙관적으로 가 작업을 완료하는 데 더 이상 자원이 필요하지 않을 것이라고 가정한다.

    2. 1번의 가정이 틀릴 경우 데드락이 발생할 수 있지만, 다음 번 데드락 감지 알고리즘이 호출될 때 감지될 것이다.

    실행시간이 좀 걸려서 일시적으로 데드락이 발생할 수 있지만, 결국 인스턴스를 해제할 것이기 때문에, 낙관적으로 본다는 것 같다. 또 실행 흐름에 따라 추가로 Request를 요구할 수 있지만 알고리즘 실행 단계에서는 그렇지 않으니까 현재만 고려한다는 것.


- 예시1 - 스레드 $T_0$부터 $T_4$까지 다섯 개의 스레드와 세 가지 자원 유형 A, B, C가 있는 시스템이 있다고 가정 - 자원 유형 A는 7개의 인스턴스를 가지고 있으며, 자원 유형 B는 2개, 자원 유형 C는 6개의 인스턴스를 가지고 있다고 가정 - 자원 유형 B는 2개, 자원 유형 C는 6개의 인스턴스를 가지고 있다.
![[Pasted image 20260812133852.png|399]]
- 예시1의 결과 : 시스템이 데드락 상태가 아니라고 할 수 있다. 실제로, 알고리즘을 실행하면 <$T_0$, $T_2$, $T_3$, $T_1$, $T_4$>의 순서로 결과가 나와서 모든 i에 대해 `Finish[i] == true`가 되기 때문이다.
- 예시2 - 스레드 $T_2$가 $C$ 유형의 인스턴스를 하나 더 요청한다고 가정 ![[Pasted image 20260812134007.png]]
- 예시2의 결과 - 이제 시스템이 데드락 상태에 있다고 할 수 있다. 스레드 $T_0$의 자원을 회수할 수 있지만 다른 스레드의 요청을 충족시키기에는 사용 가능한 자원의 수가 충분하지 않기 때문이다. 따라서 $T_1$, $T_2$, $T_3$, $T_4$의 스레드들로 구성된 데드락이 존재한다.

해당 섹션이 설명만 보면 이게 뭔소리지 싶은데, request 조건이 맞으면, 자신이 원래 할당받았던 allocation을 해제하여, 다른 스레드들이 사용할 수 있도록 하고, 이를 Work에 추가한다는 것이다. 알고리즘을 적용하는 순간만을 생각하기 때문에 이렇게 동작하는 것 같다.

8.7.3 Detection-Algorithm Usage

  • 데드락 감지 알고리즘의 실행 요인

    1. 데드락이 발생할 가능성이 얼마나 자주 있는가?
    2. 데드락이 발생했을 때 영향을 받는 스레드의 수는 얼마나 되는가?

  • 고려사항

    • 데드락이 자주 발생한다면, 감지 알고리즘도 자주 호출해야 한다.
    • 데드락에 빠진 스레드에 할당된 자원은 데드락이 해결될 때까지 유휴 상태가 된다.
    • 데드락이 지속될 경우, 해당 사이클에 관련된 스레드의 수가 증가할 수 있다.
    • 데드락은 어떤 스레드가 즉시 수행될 수 없는 요청을 할 때만 발생한다.

  • 고려사항에 따른 데드락 방지 방안1

    • 시도하려는 요청으로 인해 데드락이 발생할 가능성이 있기 때문에, 자원 할당을 위한 요청이 즉시 승인될 수 없을 때 마다 데드락 감지 알고리즘을 호출한다. (극단적인 케이스)


      - 장점 : 데드락에 빠진 스레드 집합뿐만 아니라 데드락을 "유발한" 구체적인 스레드도 식별할 수 있다.
      • 단점 : 모든 자원 요청에 대해 데드락 감지 알고리즘을 호출하므로 계산 시간에 상당한 오버헤드를 발생한다.

  • 절충안

    • 정의된 간격으로 알고리즘을 호출하는 것을 고려한다.


    • 예시 : 시간당 한 번 또는 CPU 사용률이 40퍼센트 이하로 떨어질 때마다 호출한다.
      (데드락은 시스템 처리량을 저하시키고 CPU 사용률을 떨어뜨린다.)

    • 단점 : 어떤 스레드가 데드락을 “유발했는지” 알 수 없게된다.

그래프 뷰

백링크