[Chapter 7. 교착상태] 교착상태 처리 방법 - 탐지와 복구

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

교착 상태 처리 방법

1. 교착상태가 되지 않도록 사전에 조치하는 방법 (예방, 회피)

2. 교착상태 방치 후 탐지하여 복구하는 방법 (탐지, 복구)

 

교착상태 예방과 회피 방법을 사용하지 않을 경우에는

시스템의 상태를 주기적으로 검사하여 교착상태가 발생했는지를 탐지하는 알고리즘과

만약 교착상태가 탐지되었다면 교착상태로부터 시스템을 복구(회복)하는 알고리즘이 반드시 지원되어야 한다.

 

교착상태 탐지(detection)

---

교착상태를 탐지하는 알고리즘은 Banker's 알고리즘과 비슷한 원리로 동작한다.

 

 

이 알고리즘을 위해서는 아래의 자료구조들이 필요하다.

n : 프로세스의 수 / m : 자원의 종류 수

 

1. Available (길이 m의 벡터)

각 자원별 사용 가능 개수

Available[j] = k : 자원 유형 Rj는 현재 k개 사용 가능

 

2. Allocation (n×m 행렬)

현재 프로세스가 각 자원별 할당받고 있는 자원의 개수

Allocation[i, j] = k : 현재 프로세스 Pi가 자원 유형 Rj를 k개 할당받고 있음

 

3. Request

임의 시점에 프로세스의 자원 요청 개수

Request[i, j] = k : 프로세스 Pi가 자원 유형 Rj 중 k개 할당을 요청하고 있음

 

 

// 아래 첨자를 쓸 수 없어서 벡터.i로 표기함

Work = Available;
Finish[i] = (Allocation.i != 0) ? false : true;

for (j = 0; j < n; j++) {
    for (i = 0; i < n; i++) {
        if (Finish[i] == false && Request.i <= Work) // 교착상태 탐지
            break;
    }
    Work = Work + Allocation.i; // 프로세스 Pi는 수행 완료 후 현재 갖고 있는 자원을 반납, 시스템을 떠난다고 가정
    Finish[i] = true;
}
// 임의 i에 대하여 Finish[i] = false면 시스템이 교착상태에 있다는 것이다. (Pi가 deadlock 되어 있음)

 "회피"는 할당을 가정하고 안정 순열 존재 여부를 통해 교착상태를 예측해보는 것이고,
 "탐지"는 가능한 모든 할당 순열을 조사하여 현재의 Allocation과 Request 간에 교착상태가 있는지를 확인하는 것이다.

 

 

(예시 1)

다섯 개의 프로세스 {P0, P1, ... , P4}와 자원 {A, B, C}를 가진 시스템이 있으며, 자원 유형 A는 7개, B는 2개, C는 6개가 있다.

시간 T0에서 시스템은 아래와 같은 상태에 있다.

 

	Allocation			Request			Work = Available
	A (총합 7)	B (총합 2)	C (총합 5)	A	B	C	A	B	C
P0	0	1	0	0	0	0	7-7 = 0	2-2 = 0	6-5  = 1
P1	2	0	0	2	0	2
P2	3	0	2	0	0	0
P3	2	1	1	1	0	0
P4	0	0	2	0	0	2

* Banker's 알고리즘에서 Allocation은 가정치였지만, 지금은 현재의 자원 할당치이다.

* 프로세스들의 Request을 모두 할당해줄 수 있는 순열이 있는지를 확인해야 하는 것이다.

 

Request 행렬을 위에서부터 쭉 훑어보았을 때 Need <= Work을 만족하는 첫 프로세스는 P0이다.

P0 실행 후 Work = Work + Allocation = (0+0, 0+1, 1+0) = (0, 1, 1)

 

그다음, 자원 (0, 1, 1)로 Need <= Work를 만족하는 프로세스는 P2이다.

P2 실행 후 Work = Work + Allocation = (0+3, 1+0, 1+2) = (3, 1, 3)

 

그 다음, 자원 (3, 1, 3)으로 Need <= Work를 만족하는 프로세스는 P1이다.

P1 실행 후 Work = Work + Allocation = (3+2, 1+0, 3+0) = (5, 1, 3)

 

...

 

이렇게 해서 교착상태가 일어나지 않는 프로세스 순열 <P0, P2, P1, P3, P4>를 확인할 수 있다.

 

 

(예시 2)

예시 1에서 만약 프로세스 P2가 자원 유형 C의 자원을 2개 더 요구했었더라면 어떻게 되는가?

 

	Allocation			Request			Work = Available
	A (총합 7)	B (총합 2)	C (총합 5)	A	B	C	A	B	C
P0	0	1	0	0	0	0	7-7 = 0	2-2 = 0	6-5  = 1
P1	2	0	0	2	0	2
P2	3	0	2	0	0	2
P3	2	1	1	1	0	0
P4	0	0	2	0	0	2

 

우선 예시 1과 동일하게 Need <= Work을 만족하는 첫 프로세스는 P0이다.

P0 실행 후 Work = Work + Allocation = (0+0, 0+1, 1+0) = (0, 1, 1)

 

하지만 그 다음, 자원 (0, 1, 1)로 Need <= Work를 만족하는 프로세스는 없다.

 

즉, P0가 갖고 있던 자원을 반환하여도 유용한 자원의 수가 다른 모든 프로세스의 요구를 만족하지 못하므로

시스템은 교착상태에 빠지게 된다.

 

교착상태 복구(recovery)

---

탐지 알고리즘이 교착상태가 존재한다고 결정한다면 이 교착상태를 깨뜨리기 위한 방법에는 두 가지가 존재한다.

 

1. 순환(환형) 대기를 깨뜨리기 위해 한 개 이상의 프로세스를 중지(abort)하고 자원을 회수 (프로세스 종료)

2. 교착 상태에 있는 하나 이상의 프로세스들로부터 자원을 선점(preempt)

 

프로세스 종료 (Process Termination)

프로세스를 종료시킴으로 교착상태를 제거하기 위해서는 두 방법 중 하나를 사용한다.

두 방법 모두 종료된 프로세스에게 할당되었던 자원들을 시스템이 회수한다.

 

1. 교착상태에 빠진 프로세스들을 모두 중지

가장 확실한 방법이지만 비용이 너무 많이 드는 방법이다.

계산했던 내용들은 모두 무용지물이 되며, 처음부터 다시 수행해야 하기 때문이다.

 

2. 교착상태가 제거될 때까지 한 프로세스씩 중지

이때는 교착상태에 빠진 프로세스들 중 어느 것을 선택하여 종료시켜야 할지를 결정해야 한다.

종료시킬 프로세스를 선정하기 위한 고려 요소들에는 다음의 것들이 있다.

 

• 프로세스 우선순위
• 얼마나 오랫동안 수행된 프로세스이며, 얼마나 더 오래 수행될 것인가?
• 프로세스가 사용한 자원 타입과 수 (자원들을 선점하기가 수월한지에 대한 여부)
• 작업을 끝내기 위해 얼마나 더 많은 자원을 필요로 하는가?
• 복귀하는데 얼마나 많은 프로세스가 포함되어 있는가?
• 프로세스가 대화형(interactive)인지 일괄처리(batch)인지의 여부

 

해당 방법은 각 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출해

아직도 프로세스들이 교착상태에 빠져있는지를 확인해야 하기 때문에 상당한 오버헤드를 유발한다.

 

자원 선점 (Resource Preemption)

교착상태에서 벗어날 때까지

교착상태에 빠져있는 프로세스로부터 자원을 계속적으로 선점해, 다른 프로세스에게 주는 방식이다.

 

이 방식을 위해서 고려해야 하는 사항들은 다음과 같다.

 

1. 희생자 선택

프로세스 종료에서와 같이, 어느 자원과 어느 프로세스들이 선점될 것인지 그 순서를 결정해야 한다.

 

2. 후퇴(rollback)

교착상태를 해결하기 위해서는 안정 상태로 후퇴시키고 그 상태로부터 다시 시작해야 한다.

하지만 일반적으로 안정 상태가 어떤 것인지 결정하기 어렵기 때문에 각 프로세스의 상태 정보를 더 많이 관리해야 한다.

 

가장 단순한 해결책은 완전히 후퇴시키는 것(total rollback - abort & restart)이다.

 

3. 기아 상태(starvation)

특정 프로세스의 자원만 계속 선점하지 않는다는 보장은 어떻게 할 수 있을까?

희생할 프로세스를 선택할 때 비용에 근거하여 선정하게 된다면 동일 프로세스가 항상 선택될 가능성이 있다.

 

일반적인 해결 방법은

각 프로세스가 작은 유한한 횟수만 희생자로 선정되도록 하고, 희생 횟수를 비용 요소에 반영하는 것이다.