Ch.7 Deadlocks

CS/Operation System

Ch.7 Deadlocks

아헿헿헿 2022. 6. 18. 01:22

교착상태(Deadlock)은 프로세스가 리소스를 점유하고 놓아주지 않거나, 어떠한 프로세스도 리소스를 점유하지 못하는 상태가 되어 프로그램이 멈추는 현상을 말합니다. 많은 개수의 프로세스, 다중 스레드 프로그램, 많은 자원을 사용하고 있기에 발생할 가능성이 더 높아지는 교착 상태를 예방하거나 회피 하는 방법을 알아보고자 합니다.

7.1. System Model

프로세스는 유한한 자원과 한정된 조건 속에서 다음과 같은 흐름으로 리소스를 이용합니다.

요청(Request): 리소스를 요청한다. 만약 다른 프로세스가 리소스를 사용중이라서 리소스를 받을 수 없다면 대기합니다.
사용(Use): 프로세스는 리소스 위에서 수행됩니다.
방출(Release): 프로세스가 리소스를 놓아줍니다.

시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 resource로 구성된다. 정상적인 작동 모드이면, 프로세스는 다음 순서로만 resource를 사용할 수 있습니다. 한 프로세스 집합 내의 모든 프로세스가 집합 내의 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면, 그 프로세스 집합은 교착상태(Deadlock)에 있습니다.

7.2. Deadlock Charcterization

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

필요조건들(Necessary Conditions)

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

상호 배제(Mutual Exclusion) : 최소한 하나의 리소스가 비공유 모드로 점유되어야 합니다. 비공유 모드에서는 한 번에 하나의 프로세스만이 해당 resource를 사용할 수 있습니다.
점유하며 대기(Hold-and-wait) : 프로세스는 최소한 하나의 resource를 점유한 채, 현재 다른 프로세스에 의해 점유된 resource를 추가로 얻기 위해 반드시 대기해야 합니다.
비선점(No preemption) : resource들을 선점할 수 없어야 합니다. 즉, resource가 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 task를 종료한 후, 그 프로세스에 의해서만 resource가 자발적으로 방출될 수 있습니다.
순환 대기(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)입니다.

7.3. Methods for Handling Deadlocks

데드락을 제어하는 데는 크게 3가지 방법이 존재합니다.

교착상태을 예방하거나 회피
교착상태 예방은 앞서 언급한 4가지 조건 중 적어도 하나가 성립하지 않도록 하는 방법입니다. 교착상태 회피는 프로세스가 일생 동안 요구하고 사용할 resource에 대한 부가적인 정보를 얻은 뒤 그 정보를 바탕으로 프로세스를 기다려야 할지 결정할 수 있습니다.
시스템이 교착상태가 허용 후 회복
교착상태 예방이나 회피를 사용하지 않으면, 교착상태가 발생할 수 있습니다. 이에 교착상태가 진짜로 발생했는지에 대한 여부를 조사하는 알고리즘과 교착상태 복구 알고리즘을 사용할 수 있습니다.
문제를 무시하고, 교착상태이 시스템에서 절대 발생하지 않는 척한다.
오히려 발생한 교착상태를 해결하는 데 더 비용이 많이 들 수 있으므로, 무시해버릴 수도 있습니다. 이 경우, 계속된 교착상태로 시스템 성능을 저하시킬 가능성도 있기 때문에, 수작업으로 다시 시작할 필요가 있습니다.

7.4. Deadlock Prevention

데드락을 방치하는 것은 시스템 효율에 큰 영향을 줍니다. 따라서 데드락을 방지하는 것이 중요한데, 데드락을 방지한다는 것은 데드락 발생 조건 중 하나를 만족시키지 않음으로써 데드락이 발생을 막는 것입니다.

▶ 상호 배제(Mutual Exclusion)

상호 배제는 적어도 하나의 resource는 공유 불가능한 resource 여야 한다는 조건입니다. 이에 공유 가능한 resource에 대해서는 교착상태(Deadlock)이 일어나지 않습니다. (ex) 읽기-전용 파일. 하지만 일반적으로 상호 배제 조건을 거부하는 것으로 교착 상태 예방은 일부 자원들이 근본적으로 공유가 불가능하기 때문에 불가능합니다.

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

프로세스가 resource를 요청할 때, 다른 resource들을 점유하지 않을 것을 보장하면 교착상태 예방이 가능합니다. 이를 위해 두가지 방법이 존재합니다.

프로세스가 전혀 resource를 갖고 있지 않을 때만, resource을 요청하도록 허용하면 됩니다. 이 방법에서 다른 추가 resource를 요청하려면, 현재 자신에게 할당된 resource를 모두 방출해야 합니다.
각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당받을 것을 요구합니다.

이 두가지 방법에는 두가지의 단점이 존재합니다.

많은 resource들이 할당된 후 오랫동안 사용되지 않기 때문에, resource의 이용도가 낮을 수 있습니다.
기아(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

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

이에 안전 순서<P(1), P(0), P(2)>가 있으므로, 위 시스템은 안전하다고 할 수 있습니다. 하지만, 위의 시스템에서 P(2)의 현재 사용량이 3이었다면 시스템은 불안전한 상태로 변경됩니다. 시스템을 항상 안전한 상태로 유지하게 하여 교착상태을 회피할 수 있습니다. 하지만, 이 방법은 프로세스가 요청한 resource보다 시스템이 더 많은 resource을 갖고 있더라도 때에 따라 그 프로세스를 기다리게 할 수 있으므로, resource의 utilization이 더 낮아질 수 있습니다.

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

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

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

자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없습니다. 은행원 알고리즘(Banker's Algorithm)에서는 자원이 여러 개씩 있더라도 사용할 수 있습니다. 은행원 알고리즘에서는 아래와 같은 자료구조를 사용합니다. (n : 프로세스의 수, m : resource의 수)

Available : 각 종류 별로 available 한 resource의 개수를 나타내는 벡터입니다. Available[j] = k 이면, 현재 R(j)를 k 개 사용할 수 있다는 뜻입니다.
Max : 각 프로세스가 최대로 필요로 하는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다. Max[i][j] = k 이면, P(i)가 R(j)를 최대 k 개까지 요청할 수 있음을 나타냅니다.
Allocation : 각 프로세스에게 현재 나가있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다. Allocation[i][j] = k 이면, 현재 P(i)가 R(j)를 k 개 사용 중임을 나타냅니다.
Need : 각 프로세스가 이후 요청할 수 있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다. Need[i][j] = k라면, 이후 R(j)를 k개까지 더 요청할 수 있음을 나타냅니다.

이들 간에는 Need[i][j] = Max[i][j] - Allocation[i][j]의 관계가 있습니다.

안전성 알고리즘(Safety Algorithm)

Work와 Finish는 각각 크기가 m과 n인 vector입니다. Work를 Available 값으로 초기화해주고, i = 0, 1, ... , n-1에 대하여 Finish[i] = false를 초깃값으로 줍니다.
아래 두 조건을 만족하는 i 값을 찾습니다.
a. Finish[i] == false
b. Need(i) <= Work
Work = Work + Allocation_i, Finish[i] = true로 한 뒤에 두 번째 단계로 갑니다
모든 i 값에 대해 Finish[i] = true 이면, 이 시스템은 안전 상태에 있습니다.

자원 요청 알고리즘(Resource-Request Algorithm)

만약 Request_i <= Need_i이면, 두 번째 단계로 가고, 아니면 오류로 처리합니다.
만약 Request_i <= Available이면, 세 번째 단계로 가고, 아니면 프로세스는 기다려야 합니다.
마치 시스템이 P(i)에게 resource를 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꿉니다.

$$ Available = Available+Request_i $$

$$Allocation_i = Allocation_i + Request_i $$

$$ Need_i = Need_i - Request_i $$

예시 (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) 예방이나 회피 알고리즘을 사용하지 않는다면, 교착상태가 발생할 수 있습니다. 이러한 환경에서는 시스템이 아래 알고리즘들을 반드시 지원해야 합니다.

교착상태(Deadlock)이 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
교착상태(Deadlock)으로부터 회복하는 알고리즘

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

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

(a)는 자원 할당 그래프이며 (b)는 a에 대응되는 대기 그래프에 해당합니다. 교착상태(Deadlock)을 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 그래프에서 cycle을 탐지하는 알고리즘을 호출합니다.

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

대기 그래프(Wait-for graph)는 각 종류마다 resource가 여러 개씩 존재하는 상황에서는 사용할 수 없습니다. 따라서, 은행원 알고리즘과 유사하게 자료구조를 사용해야 합니다.

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

탐지 알고리즘(Detection-Algorithm)은 언제 돌려야 하는지에 대해서는 두 가지를 살펴봐야 합니다

교착상태(Deadlock)가 얼마나 자주 일어나는가?
교착상태(Deadlock)이 일어나면, 통상 몇 개의 프로세스가 거기에 연루되는가?

교착 상태가 자주 일어난다면, 탐지 알고리즘(Detection Algorithm)도 자주 돌려아 합니다. 교착상태(Deadlock)이 일어나는 시점은 "어떤 프로세스가 resource를 요청했는데, 그것이 즉시 만족되지 못하는 시점"입니다.

7.7. Recovery from Deadlock

만약 시스템이 데드락을 방지하거나 회피하지 못했고, 데드락이 발생하여 이를 탐지하였다면, 데드락으로부터 복구되어야 합니다. 이를 operator가 운영자가 수작업으로 처리하게 하는 것입니다.

▶ 프로세스 종료(Process Termination)

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

교착상태(Deadlock) 프로세스를 모두 중지 : 이 방법은 확실하게 교착상태(Deadlock)의 cycle을 깨트리지만, 관련된 모든 프로세스를 중지시키므로 비용이 커집니다.
교착상태(Deadlock)가 제거될 때까지 한 프로세스 씩 중지 : 각 프로세스가 중지될 때마다, 탐지 알고리즘을 통해 교착상태(Deadlock)이 존재하는지를 확인해야 하므로, 상당한 overhead를 유발할 수 있습니다.

어떤 프로세스를 먼저 중지시켜야 하는가는 아래와 같은 기준들이 있을 수 있습니다.

프로세스의 우선순위가 어떠한지
지금까지 프로세스가 수행된 시간과 종료하는 데까지 더 필요한 시간
프로세스가 사용한 자원 타입과 수
프로세스가 작업을 마치기 위해 얼마나 많은 리소스가 필요한가
얼마나 많은 수의 프로세스가 종료되어야 하는가
프로세스가 일괄처리(batch)인가 대화형(interactive)한가

▶ Resource Preemption

교착상태(Deadlock)을 해결하기 위해 리소스 선점(Preemption) 방식을 사용할 때는 다음의 세 가지 사항을 고려해야 합니다.

희생자 선택(Selection of a victim) : 어느 resource와 process가 선점될 것인가?
후퇴(Rollback) : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
기아 상태(Starvation) : 기아(Starvation) 상태가 발생하지 않는다는 것을 어떻게 보장해야 하는가?

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