Deadlock
Deadlock 이란 2개 이상의 Thread가 task를 수행하는 과정에서 특정 공유 Resource에 접근하기 위해 서로 circular하게 대기하고 있는 상황을 의미한다.
여기서 중요한 것은 `Circular`하게 대기한다는 점으로, 단순히 자원을 기다리는 것과는 차이가 있다.
아래는 간단한 예시 시나리오이다.
Thread 1:
1. 리소스 A를 요청
2. 리소스 A 획득 대기
Thread 2:
1. 리소스 B를 요청
2. 리소스 B 획득 대기
(Thread 1과 Thread 2는 각자의 리소스를 대기하고 있음)
Thread 1:
3. 리소스 B를 기다림 (리소스 B는 Thread 2가 가지고 있음)
Thread 2:
3. 리소스 A를 기다림 (리소스 A는 Thread 1이 가지고 있음)
(Thread 1과 Thread 2는 서로의 리소스를 기다리면서 무한히 대기하며 데드락 상황에 빠짐)
즉 서로 상대방이 가지고 있는 자원을 얻기 위해 대기하는 상황을 Circular하게 대기하고 있다고 말하고,
이를 Deadlock이라고 한다.
종종 `Starvation`이라는 용어와 혼용해서 쓰이는데, `Starvation`이란 Process 혹은 Thread가 무한하게 대기하고 있는 상태를 말하는 것으로 Deadlock은 Starvation의 일종이라고 할 수 있다.
https://simple-coding-place.tistory.com/25
에서 살펴보았던 Semaphore를 사용한 시나리오도 간단하게 살펴보자
P0: P(S)->P(Q)-> -------------- -> V(S)->V(Q)
P1: P(Q)->P(S)-> -------------- -> V(Q)->V(S)
위 시나리오에서, P0는 semaphore S를, P1은 semaphore Q를 습득하였다.
이후 각각 Semaphore Q, S를 습득해야 다음 로직을 수행할 수 있는데, 서로 다른 프로세스가 각 자원을 이미 가져간 상태이므로 서로 진행되지 못하고 무한히 대기해야 하는 Deadlock 상황이 발생한다.
Deadlock의 조건
Deadlock이 발생하기 위해서는 4가지 조건이 만족되어야하며, 하나의 조건이라도 만족되지않으면 Deadlock 상황은 발생하지 않는다.
1. Mutual Exclusion (상호 배제)
특정 자원에 대해, 한 번에 하나의 Process, 혹은 하나의 Thread만이 이용 가능해야 한다.
2. Hold and Wait (점유 대기)
하나의 자원을 이미 가지고 있으면서, 다른 Process나 Thread에 할당된 자원을 얻기 위해 대기하고 있는 프로세스가 존재해야 한다.
3. No Preemption (비선점)
다른 Process나 Thread가 이미 할당받은 자원은 작업이 종료될 때 까지 다른 Process나 Thread가 강제로 빼앗을 수 없어야 한다.
4. Circular Wait (순환 대기)
자원을 가지고 대기하고 있는 Process나 Thread들이 순환하는 형태로 대기하고 있어야 한다.
Deadlock의 해결방법
Deadlock을 해결하는 방법은 위에서 언급한 Deadlock의 조건 중 하나를 충족하기 않게 만들어주기만 하면 된다.
Deadlock 처리 유형에는 크게 3가지가 존재하는데,
`Prevent`, `Avoid`, `Detect and Recover` 방식이 있다.
Prevent
말 그대로 Deadlock 조건이 발생하지 않도록 미리 예방하는 방법을 말한다.
1. 여러 프로세스가 공유 자원을 사용 가능하도록 한다 (Mutual Exclusion을 충족하지 못하도록 하는 방식)
2. 프로세스 실행 전에 모든 자원을 할당하고 시작한다 (Hold and Wait를 충족하지 못하도록 하는 방식)
3. 자원을 이미 가지고 있는 프로세스가 다른 프로세스로부터 자원 점유 요청을 받을 경우 해당 자원을 반납한다. (Preemptive 방식)
4. 자원에 고유 번호를 할당하고 순서대로 자원을 요구하게 한다. 우선순위가 높은 자원을 위해 낮은 자원을 해제할 수 있도록 하는 방식이다. (Circular Wait를 충족하지 못하게 하는 방식)
Avoid
Deadlock을 위한 4가지 조건을 불충족시키는 방식은 아니지만, 최대한 Deadlock이 발생하지 않도록 조절하는 방식을 Avoid라고 한다.
Avoid를 구현한 대표적인 예시는 `Banker's Algorithm`과 `Resource Allocation Graph Algorithm` 이 있다.
Banker's Algorithm
Banker's Algorithm은 다음과 같은 4가지의 개념을 기반으로 동작한다.
1. Available Resources: 현재 시스템에서 사용 가능한 모든 리소스의 수를 나타낸다.
2. Maximum Request: 각 프로세스가 어떤 종류의 리소스를 얼마나 요청할 수 있는지를 나타내는 Matrix로, 각 프로세스가 필요로 하는 최대 리소스 양을 의미한다.
3. Allocation: 각 프로세스가 현재 얼마나 많은 리소스를 할당 받았는지를 나타내는 Matrix이다.
4. Need: 각 프로세스가 작업을 마치기 위해 추가로 필요로하는 리소스의 양을 나타내는 Matrix로,
Maximum Request - Allocation으로 계산할 수 있다.
`Available Resources`는 1차원 배열로 관리한다. 예를 들어, `Available[i] = k ` 라고 하면 Resource i에 k만큼의 자원이 남아 있다는 뜻이다.
`Maximum Request`는 2차원 배열로 관리하며, `Maximum[i][j] = k` 라고 하면 Process i가 Resource j를 최대 k개 요청할 것임을 의미한다.
`Allocation`는 2차원 배열로 관리하며, `Allocation[i][j] = k` 라고 하면 Process i가 Resource j 를 k만큼 할당받은 상태임을 의미한다.
`Need` 또한 Maximum Request, Allocation과 동일하게 해석해주면 된다.
위 정보들을 바탕으로 Banker's Algorithm은 다음과 같이 동작한다.
1. Process가 리소스를 요청하면, 요청한 리소스가 Need Matrix와 Available Matrix보다 작은지 검사한다.
2. 1번 조건을 통과할 경우, 임시로 리소스를 할당해 본 후 시스템이 Safe State에 도달하는지 검사한다.
이 Safe State는 모든 프로세스가 리소스를 원활하게 사용할 수 있는 상태, 즉 Deadlock이 발생하지 않는 상태를 의미한다.
프로세스의 동작 순서에 관계 없이 Safe State가 유지될 수 있어야하기 때문에, 자원 할당의 순서를 바꿔가며 시뮬레이션이 진행되고, 문제가 감지되면 리소스를 할당하지 않고 대기한다.
3. 2번 조건까지 만족할 경우, 실제로 리소스를 할당하고 Allocation matrix와 Need Matrix를 업데이트 한다.
간단한 수도코드는 아래와 같다.
Initialize:
Available: 현재 사용 가능한 각 리소스의 수 (벡터)
Max: 각 프로세스가 최대로 요청할 수 있는 리소스의 수 (매트릭스)
Allocation: 각 프로세스에게 현재 할당된 리소스의 수 (매트릭스)
Need: 각 프로세스가 추가로 필요로 하는 리소스의 수 (Need = Max - Allocation)
Request(Resource, Process):
if Request <= Need[Process] and Request <= Available then
임시로 리소스를 할당받아보고 안전한 상태인지 확인
if SafetyCheck() then
Allocate Resource to Process
Available -= Request
Allocation[Process] += Request
Need[Process] -= Request
else
대기 // Request의 할당이 불가능
else
대기 // Request가 현재 필요한 양보다 크거나 사용 가능한 양보다 큼
Release(Resource, Process):
Deallocate Resource from Process
Available += Resource
Allocation[Process] -= Resource
Need[Process] += Resource
SafetyCheck():
Work = Available
Finish[1..n] = false (n은 프로세스의 수)
while(true){
j = (Finish[j] == false 이고, 모든 i에 대해 need[j][i] <= Available[j][i] 를 만족하는 Thread의 랜덤한 ID)
if(위 조건을 만족하는 j가 더이상 존재하지 않는 경우){
if(Finish 배열의 모든 값이 true이면)
return true
else
return false
}
else{
Finish[j] = true;
모든 i에 대해 Available[i] = Available[i] - alloc[j][i]
}
}
Resource Allocation Graph Algorithm
그래프형태로 프로세스와 자원의 할당 관계를 표현하면서 Deadlock을 감지하는 방식이다.
위 그림에서 Process는 원형의 노드로 표현되었으며, Resource는 네모난 노드로 표현되었다.
Resource 내부의 동그란 노드들은 해당 자원이 총 몇개 할당될 수 있는지를 나타낸다.
화살표가 자원에서 프로세스로 이어지는 경우는 할당된 상태를 의미하며, 그 반대 방향은 자원 할당을 요청하는 상태를 의미한다.
즉 할당 요청과 할당된 상태에 따라 아래와 같은 그래프 모양이 생성될 수 있다.
그림을 보면 P2-P3 간에 Cycle이 생성된 것을 확인할 수 있다
프로세스와 자원 간 할당 관계를 이렇게 그래프로 나타내었을 때 Cycle이 없다면 Deadlock이 발생하지 않음을 보장할 수 있다.
그러나 Cycle이 있다고 해서 무조건 Deadlock을 의미하는 것은 아니다.
resource type당 1개 씩의 자원만이 존재한다면 Deadlock 상황임을 확정할 수 있으나, 여러 개인 경우는 case를 모두 따져 확인해보아야 한다.
다만 위 예시에서는 P2, P3가 데드락을 생성하고 있다.
'OS' 카테고리의 다른 글
[OS] 8. Virtual Memory (0) | 2023.10.03 |
---|---|
[OS] 7. Address Translation (0) | 2023.10.03 |
[OS] 4. Process Scheduling (0) | 2023.10.02 |
[OS] 5. Synchronization(동기화) (0) | 2023.09.21 |
[OS] 3. Thread (0) | 2023.09.17 |