본 설명은 책 “그림으로 배우는 구조와 원리 운영체제 개정 3판”를 읽으며 제 나름대로 해석하고 정리해 보았습니다.😉
교착 상태 탐지 알고리즘
교착 상태 탐지 알고리즘은 교착 상태 회복을 위한 알고리즘으로 교착상태에 대해 더 자세히 알고 싶다면
교착상태란? 링크를 참고하자.
교착 상태 탐지 알고리즘의 자료구조
교착 상태 탐지 알고리즘은 쇼사니와 코프만이 제안했다. 교착 상태 탐지알고리즘 또한 은행가 알고리즘에서 사용한 자료구조들과 비슷하다. (은행원 알고리즘이 궁금하다면 ? ✨ 은행가 알고리즘)
Available : 각 형태별로 사용 가능한 자원 수 (사용 가능량)을 표시하는 길이가 m 인 벡터이다.
- Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)을 정의 하는 n*m 행렬이다. Allocation[i, j] = k 이면, 프로세스 Pi는 자원 Rj를 k 개 할당받고 있다는 의미이다.
- Request : 각 프로세스의 현재 요청을 표시하는 n*m 행렬이다. Request[i, j]일 때 프로세스 Pi에 필요한 자원 수가 k개라면, 프로세스 Pi는 자원 Ri의 자원을 k개 더 요청한다.
교착 상태 탐지 알고리즘 동작 순서
탐지 알고리즘은 남아 있는 프로세스들의 할당 가능 순서를 모두 찾는다.
1단계 : Work와 Finish는 각각 길이가 m 과 n 인 벡터이다.
Work = Available로 초기화하고. Allocation[i] 가 0이 아니면 Finish[i] = False 로 아니면 True로 초기화 한다.
2단계 : 다음 조건을 만족하는 i 값을 찾는다.
Finish[i] == False
Request <= Work
조건에 맞는 i 가 없다면 4단계로 이동한다.
3단계 : 다음 조건과 일치하는지 여부를 판단하여 2 단계로 이동한다.
Work = Work + Allocation[i]
Finish[i] = True
4단계 : Finish[i] == False 라면, 1 <= i <= n 인 범위에서 시스템은 교착 상태에 있다. 또 프로세스 Pi도 교착상태에 있다.
교착 상태 탐지 알고리즘 예시 문제 풀이
Step 1
Available = (0, 0, 0) 으로 Work = (0, 0, 0) 그리고 Alloation[i] 값 중 0 인 값이 없으므로 Finish = (False, False, False, False, False) 로 초기화한다.
Step 2
먼저 P0 프로세스 부터 확인해보자. 먼저 P0 는 Allocation[0] = (0, 1, 0) 으로 P0에 할당되있는 자원이다. 그리고 Request[0] = (0, 0, 0) 로 Request[i] <= Work 가 성립하므로 P0를 실행할 수 있다.
Step 3
그러면 P0 실행후 자원 해제가 되면 Work =(0, 0, 0) + (0, 1, 0) = (0, 1, 0) 이고 Finish = (True, False, False, False, False) 이다.
Step 2
이제 다음 Finish[i] == False, Request <= Work 를 만족하는 i 를 찾아보자. 위의 step 2 에서 같은 방식으로 찾아보면 P2 이고 이 과정을 반복하게 되면 P0 -> P2 -> P3 -> P1 -> P4 의 순서로 실행이 되고 종료된다. 즉, Finish = (True, True, True, True, True) 로 현재 교착상태가 아닌 것을 탐지했다.
그런데 이때, P2가 자원 C를 1개 더 요청한다고 가정했을때 위의 표는 아래와 같이 수정된다.
그럼 방금 위에서 P0가 점유하고 있는 자원을 요청한다면, Work = (0, 0, 0) + (0, 1, 0) = (0, 1, 0) 으로
P1 P2 P3 P4 그 어느 누구도 프로세스들의 요청을 충족할 수 있지 않다. 따라서 이 시스템은 현재 교착 상태이다. 그러므로 프로세스 <P1, P2, P3, P4> 로 구성된 교착 상태가 존재한다.
은행원 알고리즘과 교착 상태 탐지 알고리즘의 차이
이전 포스트에서 교착상태 은행가 알고리즘 본사람들이라면 혹은 이에 대해 알고 있는 사람이라면, 이 둘이 왜 다르고 왜 나눠서 설명하지? 라고 의문이 들것이다. (나 또한 그랬으니까.. )
자료구조의 차이
은행원 알고리즘의 Need 자료구조와 탐지 알고리즘의 Request 자료구조는 다른 자료구조이다. 처음에 보면 같은 것이라고 착각할 수 있다.
Need 는 각 프로세스(스레드)가 향후 요청할 수 있는 자원의 수
Reuqest 는 각 프로세스(스레드)가 현재 할당된 자원말고도 **요청하는 자원의 수 ** 이다.
교착상태 해결 방법의 차이
은행원 알고리즘은 교착상태 해결 방법 중 교착상태 회피 방법에 속하는 것으로 말그대로 프로세스가 자원을 요청할때 교착 상태를 만나지 않기 위해 최악의 상황까지 고려 하는 기법인 것이다. 그리고 교착 상태 탐지 알고리즘 은 교착 상태가 일어났는지 일어나지 않았는지를 탐색, 탐지 할때 사용하는 알고리즘 기법인 것이다. 그래서 탐지를 했을때 교착상태이다 하면 이제 회복 알고리즘 을 통해 회복하는 것이다.
교착 상태 탐지 알고리즘의 사용
그러면 교착 상태 탐지 알고리즘을 언제 돌려야할까? 라는 질문에 대한 대답은 아래의 두가지로 답할 수 있다.
- 교착상태가 얼마나 자주 일어나는가?
- 교착 상태가 일어나면 통상 몇개의 스레드가 거기에 연루되는가?
극단적인 예로 교착상태가 자주 일어난다 싶으면 요청할때마다 탐지 알고리즘을 호출하는 것이다. 그렇게 되면 오버헤드가 너무 크게 된다. 따라서 이에 대한 대안은 지정된 시간 간격으로, 예를 들어 한시간에 한번 혹은 CPU 이용률이 40% 이하로 떨어질 때 탐지 알고리즘을 호출하는 것이다.
그래서 이제 교착 상태 탐지 알고리즘을 돌렸을때 교착 상태가 존재한다고 결정한다면 교착 상태 회복 을 진행하는 것이다. 어떠한 방식으로 교착 상태 회복을 진행하는지 궁금하다면 교착상태 해결방법 링크의 3번 headline을 참고하자.