[운영체제]chapter 08. Deadlock_#03 교착상태 탐색 후 회복

Deadlocks #3 교착상태 탐색(Detection) 후 회복(Recovery)

1. 교착상태 탐색(DeadLock Dection)

• 만약 시스템이 교착상태 방지(Prevent) 또는 회피(Avoid)를 하지 않는다면 교착상태가 발생할 것이다.
• 교착상태 탐색 환경에서의 시스템은 교착 상태 발생을 허용해준다. 대신 교착상태가 발생했는지 안했는지를 판단하기 위한 시스템의 상태를 설명하는 알고리즘을 제공한다. (교착 상태 탐색 알고리즘)
• 시스템은 교착상태가 발생하면 회복하는 알고리즘을 제공한다.

각각의 자원 유형의 인스턴스가 단일 인스턴스인 경우

• 자원-할당 그래프의 변형 대기 그래프(wait-for graph)를 유지
• 주기적으로 대기 그래프 안에 원형대기가 있는지 탐색하는 알고리즘을 수행
• 대기 그래프의 특징은 자원-할당 그래프에서 자원을 뺀 형태

 

같은 자원 요청 상황을 자원-할당 그래프와 대기 그래프로 표현한 그림

 

각각의 자원 유형의 인스턴스가 단일 인스턴스인 경우

• 각각의 자원 유형에 다수의 인스턴스가 있는 시스템에는 대기 그래프를 적용할 수 없다.

2. 교착상태 탐색 알고리즘

교착 상태 탐색 알고리즘의 데이터 구성

• Available[m]
• Allocation[n x m]
• Request[n x m]: 각각의 쓰레드의 현재 요청을 나타냄
  • 만약 Request[i][j] == k 라면 Thread i가 자원 유형 Rj의 k개의 인스턴스를 요청한다는 의미

교착 상태 탐색 알고리즘 수행과정

1. 길이 m과 n을 가진 work와 Finish 배열을 초기화 한다
   • work 배열의 각각의 값은 Available 배열의 요소값으로 초기화함
   • Finish 배열의 모든 요소에 대해서 초기화를 수행함
   • 만약 Allocation[i] != 0 라면 Finish[i] = false, Allocation[i] == 0이라면 Finish[i] = True
2. 다음 두 조건을 만족하는 인덱스 번호 i를 탐핵한다. 만약 두 조건을 만족하는 i가 없다면 4번 과정으로 이동
   1. Finish[i] == false
   2. Request[i] <= Work
3. 2번 과정의 두 조건을 만족하는 인덱스 번호 i가 있다면 다음 과정을 수행
   1. Work = Work + Allocation[i]
   2. Finish[i] = True
   3. 2번 과정으로 이동
4. 만약 0 <= ㅑ <n에 대해서 Finish[i] == false라면 해당 시스템은 교착상태에 있는 상태. 더욱이 Tread Ti는 교착상태에 있는 쓰레드를 의미

교착상태 탐색 알고리즘 수행 예제

• T = {T0,T1,T2,T3,T4}: 다섯개의 Tread를 가진 집합 T
• R = {A, B, C} : 3개의 자원 유형을 가진 집합 R
• A = 7, B =2, C= 6: 각각의 자원 유형에 따른 인스턴스의 개수

 

• 위 수행 결과와 같이 safe Sequence가 계산 되므로 교착상태가 없는 상태

.

 

• 수행 결과 Tread T0을 제외한 다른 모든 Tread가 교착상태에 빠지게 됨을 알 수 있다.

교착 상태 탐색 알고리즘을 수행하여 교착 상태가 존재하는 경우

• 교착상태가 발생되었다고 알림
• 또는 시스템이 교착상태로 부터 자동적으로 회복(Recovery)을 수행
  • 프로세스와 쓰레드 종료
  • 자원 선점 수행

교착 상태 회복(Deadlock Recovery) 방법

• 프로세스와 쓰레드의 종료
  • 모든 교착상태 프로세스를 무시
  • 교착상태 원형 대기가 종료 될때까지 하나의 프로세스를 무시한다. 하나의 프로세스를 무시하면 다른 프로세스가 작업을 수행하게 되어 풀릴 수 있다.
• 자원 선점
  1. 피해자 선택: 비용을 최소화하기 위해서 선점의 순서를 고려함
  2. 롤백(Rollback):안전한 상태로 프로세스를 롤백하고 재시작함
  3. 기아(Starvation): 피해자로 지목된 횟수를 한정하여 기아를 예방함

정리

• 교착상태 탐색 알고리즘을 수행하여 교착 상태가 발생하는지를 확인
• 교착상태가 발생하면 프로세스와 쓰레드를 종료하는 방법을 사용하거나 자원을 선점하는 방법으로 교착상태로 부터 회복