공룡책으로 정리하는 운영체제 - CHAPTER 7. 교착상태(Deadlocks)

CHAPTER 7 - 교착상태(Deadlocks)
CH 7에서는,
- 첫째로, 교착상태(Deadlock)에 대해서 알 수 있다.
- 둘째로, 교착상태(Deadlock)을 예방하거나 회피하는 방법에 대해서 알 수 있다.

​- 대기 중인 프로세스들이 다시는 그 상태를 변경시킬 수 없는 상황을 교착상태(Deadlock)이라고 한다.

---

7.1 시스템 모델(System Model)

- 시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 resource로 구성된다.​

- 정상적인 작동 모드이면, 프로세스는 다음 순서로만 resource를 사용할 수 있다.
1. 요청(Request) : 프로세스가 resource을 요청한다. 만약 얻지 못하면, resource을 얻을 때까지 대기해야 한다.
2. 사용(Use) : 프로세스가 resource에 대해 작업을 수행할 수 있다.
3. 방출(Release) : 프로세스가 resource를 방출한다.

- 한 프로세스 집합 내의 모든 프로세스가 집합 내의 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면,
  그 프로세스 집합은 교착상태(Deadlock)에 있다.

 

---

7.2 교착상태의 특징(Deadlock Charcterization)

- 교착상태(Deadlock)에 있는 프로세스들은 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어서 다른 작업을 시작하는 것도 불가능하다.

​

* 필요조건들(Necessary Conditions)

- 교착상태(Deadlock)은 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생​할 수 있다.

1. 상호 배제(Mutual Exclusion) : 최소한 하나의 resource는 nonsharable mode로 점유되어야 한다.
nonsharable mode에서는 한 번에 하나의 프로세스만이 해당 resource를 사용할 수 있다.

2. 점유하며 대기(Hold-and-wait) : 프로세스는 최소한 하나의 resource를 점유한 채, 현재 다른 프로세스에
의해 점유된 resource를 추가로 얻기 위해 반드시 대기해야 한다.

3. 비선점(No preemption) : resource들을 선점할 수 없어야 한다. 즉, resource가 강제적으로 방출될 수 없고,
점유하고 있는 프로세스가 task를 종료한 후, 그 프로세스에 의해서만 resource가 자발적으로 방출될 수 있다.

4. 순환 대기(Circular wait) : 대기하고 있는 프로세스의 집합 {P(0), P(1), ... , P(n)}에서 P(0)는 P(1)이 점유한
resource를 대기하고, P(1)은 P(2)가 점유한 resource을 대기하고, .... , P(n)은 P(0) 가진 resource을 대기한다.

​

* 자원 할당 그래프(Resource-Allocation Graph)

- deadlock은 시스템 자원 할당 그래프(system resource-allocation graph)로 보다 정확하게 기술될 수 있다.
- P(i) → R(j)는 요청 간선(Request Edge)이고, R(j) → P(i)는 할당 간선(Assignment Edge)이다.

- 자원 할당 그래프에서 사이클(Cycle)을 포함하지 않으면, 시스템 내에 어느 프로세스도 교착상태(Deadlock)이
  아니라는 것을 보일 수 있다.

- 하지만, 만일 각 resource type이 여러 개의 instance를 가지면, cycle이 반드시 교착상태(Deadlock)이 발생했음을
  의미하지는 않는다.

- 요약하자면, 자원 할당 그래프에서 사이클이 없다면 시스템은 교착상태(Deadlock)이 100% 아니다.
- 반면에, 사이클이 있다면 시스템은 교착상태에 있을 확률이 있는 상태이다.

 

---

7.3 교착상태 처리 방법(Methods for Handling Deadlocks)

- 원칙적으로 교착상태(Deadlock) 문제를 처리하는데 다음과 같은 세 가지 방법이 있다.

​

(1) 교착상태(Deadlock)을 예방하거나 회피하는 protocol을 사용한다.
- 교착상태(Deadlock) 예방은 앞서 언급한 4가지 조건 중 적어도 하나가 성립하지 않도록 하는 방법이다.
- 교착상태(Deadlock) 회피는 프로세스가 일생 동안 요구하고 사용할 resource에 대한 부가적인 정보를 얻은 뒤
  그 정보를 바탕으로 프로세스를 기다려야 할지 결정할 수 있다.​

(2) 시스템이 교착상태(Deadlock)가 가능하도록 허용한 다음에 회복시키는 방법이 있다.
- 교착상태(Deadlock) 예방이나 회피를 사용하지 않으면, 교착상태가 발생할 수 있다. 이에 교착상태가 진짜로
발생했는지에 대한 여부를 조사하는 알고리즘과 교착상태 복구 알고리즘을 사용할 수 있다.

​
(3) 문제를 무시하고, 교착상태(Deadlock)이 시스템에서 절대 발생하지 않는 척한다.
- 오히려 발생한 교착상태를 해결하는 데 더 비용이 많이 들 수 있으므로, 무시해버릴 수도 있다.
- 이 경우, 계속된 교착상태로 시스템 성능을 저하시킬 가능성도 있기 때문에, 수작업으로 다시 시작할 필요가 있다.

 

---

7.4 교착상태 예방(Deadlock Prevention)

- 앞서 언급한 4가지 교착상태 발생 조건들 중에 적어도 하나가 성립하지 않도록 하여 교착상태를 예방할 수 있다.

​

* 상호 배제(Mutual Exclusion)

- 상호 배제는 적어도 하나의 resource는 공유 불가능한 resource 여야 한다는 조건이다. 이에 공유 가능한 resource에 대해서는 교착상태(Deadlock)이 일어나지 않는다. (ex) 읽기-전용 파일

​

* 점유하며 대기(Hold and Wait)

- 프로세스가 resource를 요청할 때, 다른 resource들을 점유하지 않을 것을 보장하면 교착상태 예방이 가능하다.

​- 첫 번째 방법은 프로세스가 전혀 resource를 갖고 있지 않을 때만, resource을 요청하도록 허용하면 된다.

- 위 방법에서 다른 추가 resource를 요청하려면, 현재 자신에게 할당된 resource를 모두 방출해야 한다.

​- 두 번째 방법은 프로세스가 초기에는 DVD drive와 Disk file만 요청하도록 허용하는 방법이다.

​

- 이 두 protocol에는 2가지 단점이 있다.

(1) 많은 resource들이 할당된 후 오랫동안 사용되지 않기 때문에, resource의 이용도가 낮을 수 있다.

(2) 기아(Starvation) 문제가 발생할 수 있다. (특정 프로세스는 무한정 대기하는 상황이 나올 수 있다.)

​

* 비선점(No Preemption)

- 교착상태(Deadlock)을 보장하는 세 번째 조건은 할당된 resource이 선점되지 않아야 한다는 점이다.

- 이 조건을 성립하지 않게 하기 위해, 어떤 resource을 점유하고 있는 프로세스가 즉시 할당할 수 없는

다른 resource을 요청하면, 현재 점유하고 있는 모든 resource들이 선점되게 할 수 있다.

​

* 순환 대기(Circular Wait)

- 교착상태(Deadlock)을 보장하는 네 번째 조건은 순환 대기(Circular wait) 조건이다.

- 이 조건을 성립하지 않게 하기 위해, 모든 resource type에 대해 전체적인 순서를 부여하여,

각 프로세스가 열거된 순서대로, 오름차순으로 resource을 요청하도록 요구하게 할 수 있다.

 

---

7.5 교착상태 회피(Deadlock Avoidance)

- 교착상태 예방 방법을 쓰면, 장치의 이용률이 저하되고 시스템 처리율(Throughput)이 감소될 수 있다.

- 교착상태 회피는 resource가 어떻게 될지 추가 정보를 통해서 이루어진다.

​

* 안전 상태(Safe State)

- 시스템 상태가 안전(Safe) 하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 resource를
교착상태(Deadlock)을 발생시키지 않고, 차례로 모두 할당해 줄 수 있다는 것을 의미한다.

- 시스템이 안전 순서(Safe Sequnece)를 찾을 수 있다면 시스템은 안전(safe) 하다고 말할 수 있다.
- 시스템이 안전하다는 것은 교착상태(Deadlock)가 발생하지 않는다는 것을 의미한다.

- 시스템이 안전 순서(Safe Sequence)를 찾을 수 없다면 시스템은 불안전(unsafe) 한 상태에 있다.
- 시스템이 불안전하다는 것은 반드시 교착상태(Deadlock)으로 간다는 것을 의미하지 않는다.
- 대신, 시스템이 불안전하다는 말은 "앞으로 교착상태로 갈 확률이 있다."라는 뜻을 의미한다.​

- 예를 들어, 시스템에는 12개의 tape가 있고 세 개의 프로세스 상황은 아래와 같을 때,

	최대 소요량	현재 사용량
P(0)	10	5
P(1)	4	2
P(2)	9	2

 

(1) 먼저 tape 3개(12 - (5+2+2)) 중 2개를 P(1)에 할당하여 P(1)을 완료시킨 뒤, tape 4개를 돌려받는다.
(2) 이제 여분의 5개의 tape를 P(0)에 모두 할당하여, P(0)를 완료시키고 tape 10개를 돌려받는다.
(3) P(2)를 완료시킨다.

- 이에 안전 순서(Safe Sequence) <P(1), P(0), P(2)>가 있으므로, 위 시스템은 안전(safe) 하다고 할 수 있다.
- 하지만, 위의 시스템에서 P(2)의 현재 사용량이 3이었다면 시스템은 불안전(unsafe) 한 상태로 변경된다.

- 시스템을 항상 안전(Safe) 한 상태로 유지하게 하여 교착상태(Deadlock)을 회피할 수 있다.
- 하지만, 이 방법은 프로세스가 요청한 resource보다 시스템이 더 많은 resource을 갖고 있더라도 때에 따라
  그 프로세스를 기다리게 할 수 있으므로, resource의 utilization이 더 낮아질 수 있다.

 

* 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

- 자원 할당 그래프를 그려보면서 cycle이 안 생기게 하여 교착상태(Deadlock)을 회피할 수 있다.
- 요청 간선, 할당 간선과 함께 점선으로 예약 간선을 사용할 수 있다.
- 그래프에서 cycle이 없다면, resource를 할당해도 시스템은 안전 상태가 된다.
- cycle이 발생하게 되면, 시스템은 불안전한 상태가 되므로 교착상태를 회피할 수 없게 된다.

 

 

* 은행원 알고리즘(Banker's Algoirthm)

- 자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.
- 은행원 알고리즘(Banker's Algorithm)에서는 자원이 여러 개씩 있더라도 사용할 수 있다.

- 은행원 알고리즘에서는 아래와 같은 자료구조를 사용한다. (n : 프로세스의 수, m : resource의 수)

(1) Available : 각 종류 별로 available 한 resource의 개수를 나타내는 벡터이다. Available[j] = k 이면,
현재 R(j)를 k 개 사용할 수 있다는 뜻이다.

​(2) Max : 각 프로세스가 최대로 필요로 하는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Max[i][j] = k 이면, P(i)가 R(j)를 최대 k 개까지 요청할 수 있음을 나타낸다.

​(3) Allocation : 각 프로세스에게 현재 나가있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Allocation[i][j] = k 이면, 현재 P(i)가 R(j)를 k 개 사용 중임을 나타낸다.

​(4) Need : 각 프로세스가 이후 요청할 수 있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Need[i][j] = k라면, 이후 R(j)를 k 개까지 더 요청할 수 있음을 나타낸다.

​- Need[i][j] = Max[i][j] - Allocation[i][j]의 관계가 있다.

- 안전성 알고리즘(Safety Algorithm)
(1) Work와 Finish는 각각 크기가 m과 n인 vector이다. Work를 Available 값으로 초기화해주고,
i = 0, 1, ... , n-1에 대하여 Finish[i] = false를 초깃값으로 준다.

(2) 다음 두 조건을 만족하는 i 값을 찾는다.  (a . Finish[i] == false b. Need(i) <= Work)

(3) Work = Work + Allocation(i) Finish[i] = true로 한 뒤에 두 번째 단계로 간다.

(4) 모든 i 값에 대해 Finish[i] = true 이면, 이 시스템은 안전 상태에 있다.

- 자원 요청 알고리즘(Resource-Request Algorithm)
(1) 만약 Request(i) <= Need(i)이면, 두 번째 단계로 가고, 아니면 오류로 처리한다.

(2) 만약 Request(i) <= Available 이면, 세 번째 단계로 가고, 아니면 프로세스는 기다려야 한다.

(3) 마치 시스템이 P(i)에게 resource를 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꾼다.

Available = Available - Request;

Allocation_i = Allocation_i + Request;

Need_i = Need_i - Request;

 

- 예시 (Example)

​Allocation, Max, Available 배열이 아래와 같을 때,

	Allocation (A B C)	Max (A B C)	Available (A B C)
	A B C	A B C	A B C
P(0)	0 1 0	7 5 3	3 3 2
P(1)	2 0 0	3 2 2
P(2)	3 0 2	9 0 2
P(3)	2 1 1	2 2 2
P(4)	0 0 2	4 3 3

 

Need 배열은 아래와 같다. (Max - Allocation = Need)

	Need (A B C)
	A B C
P(0)	7 4 3
P(1)	1 2 2
P(2)	6 0 0
P(3)	0 1 1
P(4)	4 3 1

 

- 위의 시스템은 안전하다(Safe)라고 할 수 있는데, <P(1), P(3), P(4), P(2), P(0)>의 sequence가 있기 때문이다.

---

7.6 교착상태 탐지(Deadlock Detection)

- 만약 시스템이 교착상태(Deadlock) 예방이나 회피 알고리즘을 사용하지 않는다면, 교착상태가 발생할 수 있다.
- 이러한 환경에서는 시스템이 아래 알고리즘들을 반드시 지원해야 한다.
  (1) 교착상태(Deadlock)이 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
  (2) 교착상태(Deadlock)으로부터 회복하는 알고리즘

​

* 각 자원 타입이 한 개씩 있는 경우(Single Instance of Each Resource Type)

- 모든 자원들이 한 개의 instance만 있다면, 대기 그래프(wait-for graph)를 이용하여 교착상태(Deadlock) 탐지 알고리즘을 정의할 수 있다.

(a) 자원 할당 그래프&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (b) a에 대응되는 대기 그래프

 

- 교착상태(Deadlock)을 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 그래프에서
  cycle을 탐지하는 알고리즘을 호출한다.

​

* 각 타입의 자원을 여러 개 가진 경우(Several Instances of a Resource Type)

- 대기 그래프(Wait-for graph)는 각 종류마다 resource가 여러 개씩 존재하는 상황에서는 사용할 수 없다.

- 따라서, 은행원 알고리즘과 유사하게 자료구조를 사용해야 한다.

​

* 탐지 알고리즘 사용(Detection-Algorithm Usage)

- 탐지 알고리즘(Detection-Algorithm)은 언제 돌려야 하는지에 대해서는 두 가지를 살펴봐야 한다.
  (1) 교착상태(Deadlock)가 얼마나 자주 일어나는가?
  (2) 교착상태(Deadlock)이 일어나면, 통상 몇 개의 프로세스가 거기에 연루되는가?

- 교착 상태가 자주 일어난다면, 탐지 알고리즘(Detection Algorithm)도 자주 돌려아 한다.

- 교착상태(Deadlock)이 일어나는 시점은 "어떤 프로세스가 resource를 요청했는데, 그것이 즉시 만족되지 못하는 시점"이다.

 

---

7.7 교착상태 회복(Deadlock Recovery)

- 탐지 알고리즘을 통해 교착상태(Deadlock)이 존재한다고 결정되면, 운영자가 수작업으로 처리하는 것이
  한 가지 방법이 될 수 있다.

- 또 다른 방법은, 자동적으로 교착상태(Deadlock)로부터 회복(Recovery) 하게 하는 것이다.

- 자동적인 회복을 위해 프로세스를 종료시키는 것과 자원을 선점하는 것 두 가지 종류가 있을 수 있다.

​

* 프로세스 종료(Process Termination)

- 종료된 프로세스로부터 할당되었던 모든 자원을 회수하게 한다.

(1) 교착상태(Deadlock) 프로세스를 모두 중지 : 이 방법은 확실하게 교착상태(Deadlock)의 cycle을 깨트리지만, 관련된 모든 프로세스를 중지시키므로 비용이 커진다.

(2) 교착상태(Deadlock)가 제거될 때까지 한 프로세스 씩 중지 : 각 프로세스가 중지될 때마다, 탐지 알고리즘을 통해 교착상태(Deadlock)이 존재하는지를 확인해야 하므로, 상당한 overhead를 유발할 수 있다.

​
- 어떤 프로세스를 먼저 중지시켜야 하는가는 아래와 같은 기준들이 있을 수 있다.
(1) 프로세스의 우선순위가 어떠한지
(2) 지금까지 프로세스가 수행된 시간과 종료하는 데까지 더 필요한 시간
(3) 프로세스가 종료하기 위해 필요한 추가 resource의 수
(4) 프로세스가 사용한 resource type과 수

​

* 자원 선점(Resource Preemption)

- 자원 선점(Resource Preemption)을 이용하여 교착상태(Deadlock)을 제거하려면, 교착상태가 깨어질 때까지 프로세스로부터 Resource을 계속적으로 선점해 이들을 다른 프로세스에게 주어야 한다.​

- 교착상태(Deadlock)을 해결하기 위해 선점이 필요하다면, 다음의 세 가지 사항을 고려해야 한다.
(1) 희생자 선택(Selection of a victim) : 어느 resource와 process가 선점될 것인가?
(2) 후퇴(Rollback) : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
(3) 기아 상태(Starvation) : 기아(Starvation) 상태가 발생하지 않는다는 것을 어떻게 보장해야 하는가?

 

---

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』