교착 상태 탐지(Deadlock Detection)
시스템이 교착 상태 예방 혹은 방지 알고리즘을 사용하지 않는 경우
- 다음 2가지 알고리즘들을 반드시 지원해야 한다.
- 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
- 교착 상태로부터 회복하는 알고리즘
- 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행 시간 비용이 든다.
- 또한, 교착 상태로부터 회복할 때 내재하는 가능한 손실을 포함하는 오버헤드가 필요
각 지원 유형이 한 개씩 있는 시스템
대기 그래프(wait-for graph)
- 해당 경우,
대기 그래프를 사용해서 교착 상태 알고리즘을 정의
대기 그래프(wait-for graph) : 자원 할당 그래프의 변형
- 대기 그래프를 얻는 방법
- 자원 할당 그래프로부터 자원 유형의 노드 제거 및 적절한 간선들을 결합
(a) 자원 할당 그래프, (b) 대응되는 대기 그래프
- 대기 그래프에서
T(i) → T(j)로의 간선
→ 프로세스 T(j)가 가지고 있는 자원들에 대해, 프로세스 T(i)가 그 자원이 필요하여 자원 방출 대기
T(i) → T(j)는 해당 자원 할당 그래프가 자원 R(q)에 대해
두 개의 간선 T(i) → R(q)와 R(q) → T(j)를 포함하는 경우에만 대기 그래프에 존재
대기 그래프의 특징
- 대기 그래프는 종류마다 자원이 여러 개씩 존재하는 상황에서 사용할 수 없음
- 대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재
- 교착 상태 탐지를 위해
- 시스템은 대기 그래프를 유지할 필요가 있음
- 주기적으로 그래프에서 사이클을 탐지하는 알고리즘을 호출
- 그래프 사이클 탐지 알고리즘은 O(n^2)의 연산을 요구
n : 그래프에 있는 정점(vertice)의 수
BCC 툴킷
- Linux에서 사용자 프로세스가 Pthreads mutex 락과 관련된 잠재적 교착 상태 감지 도구 제공
- BCC 도구
deadlock_detector
pthread_mutex_lock() 및 ㅇpthread_mutex_unlock()
함수 호출을 추적하는 검사점을 삽입하여 작동
- 동작 과정
- 지정된 프로세스가 두 함수 중 하나를 호출
- deadlock_detector는 해당 프로세스의 mutex락에 대한 대기 그래프 구성
→ 그래프에서 사이클을 감지하면 교착 상태 가능성을 보고
각 유형의 자원을 여러 개 가진 시스템
- 해당 방식은 시시각각 내용이 달라지는 자료 구조를 사용
사용하는 자료구조
Available : 각 종류의 자원이 현재 몇 개가 가용한 건지를 나타내는 벡터(크기 m)Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬(크기 n * m)Request : 각 스레드가 현재 요청 중인 자원의 개수를 나타내는 행렬(크기 n * m)
- Request [i][j] == k : 현재 T(i)가 R(j)를 k개 요청 중임을 뜻함
해당 탐지 알고리즘의 원리
- 가능한 모든 할당 순서를 조사해 보는 방식
- 가정
- Work와 Finish는 크기가 m과 n인 벡터
- Work = Available로 초기값을 준다.
- i = 0, 1, …, n-1에 대해 Allocation(i) ≠ 0이면, Finish [i] = false
- 그렇지 않으면 Finish [i] = true
- 동작 과정
- 아래 두 조건을 만족시키는 i 값을 찾는다. 찾을 수 없다면 3번으로 이동
- Finish [i] == false
- Request(i) ≤ Work
- Work = Work + Allocation(i)
Finish [i] = true
→ 이후 1번으로 이동
- 시스템이 스레드 T(i)의 자원을 회수하는 이유
Request(i) ≤ Work로부터 프로세스 T(i)가 교착 상태에 빠져 있지 않음을 확인
→ 해당 프로세스가 작업을 마치기 전까지 더 이상의 추가적인 자원을 필요로 하지 않음
→ 작업을 마치면 T(i)은 가지고 있던 모든 자원을 반납하고 시스템을 떠난다.
- 해당 가정이 틀렸다면 교착 상태는 다음에 발생함
→ 이 탐지 알고리즘의 다음 차례 때 교착 상태를 탐지할 수 있다.
- 어떠한 값 i에 대해 Finish [i] == false이면, 이 시스템은 교착 상태에 빠져 있는 것
- T(i)가 교착 상태에 빠져있다.
- 이때의 i 값 → (0 ≤ i < n)
- 이 탐지 알고리즘을 실행하는 데는
m * n^2개의 연산이 필요
해당 시스템 예시
교착상태가 발생하지 않는 경우
시스템의 현재 상태
- 가정
- 다섯 개의 스레드 (T0 ~ T4)까지 존재
- 시스템에 A, B, C 세 가지 종류의 자원이 있다.
- A 자원 = 7개
- B 자원 = 2개
- C 자원 = 6개
- 시스템의 현재 상태는 위의 표에 나와 있다.
- 해석
- 이 시스템은 교착 상태에 처해있지 않다.
- 알고리즘을 돌려보면 <T0, T2, T3, T1, T4> 순서로 작업을 다 끝낼 수 있다.
- 이때 모든 i에 대해 Finish [i] == true를 성립한다.
교착 상태가 발생하는 경우
- 위 과정에서 T2가 C 자원을 한 개 더 요청하는 경우
T2가 C 하나 요청
- 시스템이 교착 상태에 빠지게 된다.
- T0의 자원을 회수한다고 해도, 다른 프로세스들이 요구하는 자원을 충족시킬 방법 X
→ T1, T2, T3와 T4가 교착 상태에 빠지게 된다.
탐지 알고리즘 사용
탐지 알고리즘은 언제 사용하는가?
- 2가지 관점에 달려있음
- 교착 상태가 얼마나 자주 일어나는가?
- 교착 상태가 일어나면 통상 몇 개의 스레드가 거기에 연루되는가?
교착 상태가 자주 일어나는가?
- 교착 상태가 자주 발생한다면 탐지 알고리즘도 자주 돌려야 한다.
- 교착 상태가 된 스레드로부터 자원을 회수하기 전에는 해당 자원을 아무도 쓰지 못함
- 시간이 지날수록 교착 상태에 연루되는 스레드의 수가 증가할 수 있음
교착 상태가 발생하면, 몇 개의 스레드가 거기에 연루되는가?
- 교착 상태가 발생하는 시점
→ 스레드가 자원 요청을 했는데, 그 요청이 즉시 만족되지 못하는 시점
- 극단적인 방법으로는 스레드 요청이 즉시 만족되지 못할 때마다 탐지 알고리즘을 돌림
- 교착 상태에 연루된 스레드와 교착 상태를 야기한 장본인 스레드도 알 수 있음
- But, 자원을 요청할 때마다 탐지 알고리즘을 호출하는 것은 높은 오버헤드 발생
- 자원이 여러 종류가 있다면 한 자원에 대한 요청이 그래프상에서 사이클을 만드는 결과 초래 가능
- 오버헤드를 줄이는 대안 → 지정된 시간 간격
- 예를 들어, 1시간에 한 번씩 또는 CPU의 이용률이 40% 이하일 때만 탐지 알고리즘 호출
- 탐지 알고리즘을 임의의 시간에 호출하면 안 되는 이유
- 자원 그래프가 여러 개의 사이클을 포함할 수 있게 됨
→ 어느 스레드가 교착 상태를 야기한 장본인인지 알 수 없게 되어버림
교착 상태로부터 회복
- 탐지 알고리즘이 교착 상태 존재한다고 가정 → 여러 대안의 처리 방법이 존재
- 교착 상태 발생을 운영자(operator)에게 통지해, 운영자가 수작업으로 처리하는 것
- 시스템이 자동으로 교착 상태로부터 회복하게 하는 것
교착 상태를 깨뜨리는 2가지 방법
- 순환대기를 깨뜨리기 위해 단순히 1개 이상의 스레드를 중지(abort)
- 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preempt)
프로세스와 스레드의 종료(Process and Thread Termination)
프로세스/스레드 abort를 위해 사용하는 2가지 방법
- 2가지 방법 모두 종료된 프로세스에게 할당되었던 모든 자원 시스템을 회수
교착 상태 프로세스를 모두 중지
- 해당 상태는 교착 상태의 사이클을 깨뜨리지만, 비용이 크다.
- 비용이 큰 이유
- 해당 프로세스가 오랫동안 연산했을 가능성이 있음
- 이들 부분 계산의 결과들을 반드시 폐기해야 함
→ 이후 다시 계산을 해야 함
교착 상태가 제거될 때까지 한 프로세스씩 중지
- 각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출하고,
프로세스들이 아직도 교착 상태에 있는지 확인
프로세스 중지가 어려운 이유
- 프로세스가 파일을 갱신하는 도중인데 그 프로세스를 중지했을 경우
→ 해당 파일은 부정확한 상태가 되어버림
- 프로세스가 mutex락을 점유한 상태로 공유 데이터를 갱신하는 도중 중지한 경우
→ 시스템은 락 상태를 사용 가능한 상태로 복구해야 함
중지 프로세스 선택 결정을 위한 요인
- 부분 종료 방식을 사용할 경우
→ 교착 상태 프로세스들 중에 어느 프로세스를 중지해야 할지 결정해야 함
→ 프로세스들을 중지시켰을 때 유발되는 비용이 최소인 프로세스들을 중지시켜야 함
- 프로세스 결정을 위한 요인
- 프로세스의 우선순위가 무엇인지
- 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는데 더 필요한 시간
- 프로세스가 사용한 자원 유형의 수
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
자원 선점(Resource Preemption)
- 교착 상태가 깨어질 때까지 프로세스로부터 자원을
계속 선점해 다른 프로세스에 줌으로 교착 상태 제거
자원 선점 방식에서 고려해야 할 3가지 사항
희생자 선택(selection of a victime) : 어느 자원과 프로세스들이 선점될 것인가?
- 비용을 최소화하기 위해서 선점의 순서를 결정해야 함
- 비용 요인
- 교착 상태 프로세스가 점유하고 있는 자원의 수
- 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간 등
후퇴(rollback) : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
- 필요한 자원이 부족하기 때문에 교착 상태에 있는 프로세스를 정상 실행할 수 없다.
→ 이 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작해야 함
- 후퇴의 가장 간단한 해결안 - 프로세스를 중지시키고 재시작하는 것
- 완전히 후퇴시키는 방식
- 해당 방식은 실행하는 모든 프로세스의 상태에 대한 많은 정보를 유지할 것을 필요로 함
- 프로세스를 딱 교착 상태를 깨뜨릴 수 있을 정도로 후퇴시킨다면 더 효과적
기아 상태(starvation) : 기아 상태가 발생하지 않는 것을 어떻게 보장할 것인가?
- 자원들이 동일한 프로세스로부터 항상 선점되지 않다는 것을 어떻게 보장할 것인가?
- 희생자의 선택이 시스템에서는 동일한 프로세스가 항상 희생자로 선택될 수 있음
→ 그 결과 자신의 태스크를 영원히 완료하지 못하는 기아 상태에 있게 될 수 있다.
- 프로세스가 단지 (작은) 한정된 시간 동안만 희생자로 선정된다는 것을 반드시 보장해야 함
- 일반적인 해결 방법 : 비용 요소에 후퇴의 횟수를 포함하는 방법
