Deadlock 이란?)
어떤 스레드가 필요로 하는 자원을 다른 대기 스레드에서 점유하고 있고, 대기 스레드 역시 다른 스레드가 작업을 끝내기를 기다리고 있기 때문에 대기상태가 영원히 끝나지 않는 현상이다. 즉 교착상태에 빠져서 아무것도 못하는 경우를 의미한다.
여러 개의 자원이 있는 시스템에서 동기화가 필요한 스레드들끼리 자원을 공유한다. 이러한 자원을 하나의 type으로 묶을 수 있는데, 내부에는 여러 identical instance로 이루어져 있다.
request(요청) -> use(사용) -> release(반납)의 순서로 자원을 사용하는 데 사용 단계에서 여러 자원을 사용할 수 있다.
자원에 포함되는 인스턴스의 갯수는 중요하지 않고 type이 중요하다.
Deadlock의 특징)
아래 4가지 조건을 모두 만족해야만 Deadlock에 빠질 수 있다.
- Mutal Exclusion(상호 배제): 적어도 1개이상의 자원이 공유 불가능해야 한다.
- Hold and Wait(점유 대기): 스레드가 적어도 1개 이상의 리소스를 점유하고 있는 상태로 대기하고 있어야 한다.
- No Preemption(비선점): 자원은 선점이 불가능해야 한다.
- Circular Wait(순환 대기): 대기중인 스레드들이 필요로 하는 다른 스레드들을 이어 보면 순환 구조를 가져야 한다.
이것이 뭘 의미하는지 정리해 볼 필요가 있다.
교착상태(Deadlock)에 빠지기 위해서는 1개 이상의 자원이 공유가 불가능하면서, 해당 자원을 점유하고 대기하는 스레드가 존재하고 이러한 자원들은 선점이 불가능해야 한다. 만약 선점이 가능하면 다른 스레드의 자원을 뺏어 오면 되기에 교착상태가 발생하지 않는다. 또한 위 그림처럼 스레드들 간에 서로를 필요로 하는 순환 구조를 가져야 한다. 즉, 거의 Worst Case 들만 모아놔야 교착 상태에 빠지기 때문에 확률상 흔하게 겪을 수 있는 문제는 아니다.
Resorce Allocation Graph(자원 할당 그래프))
해당 그래프는 방향성을 갖는 그래프다.
자원 할당 그래프의 정점 (vertex) 집합은 두 가지로 나뉨.
- -> 활성화된 모든 스레드의 집합
- -> 모든 자원들의 집합
각 정점들을 잇는 간선 (edge)은 다음과 같음.
- (request edge): 스레드가 자원을 요청하였음.
- (assignment edge): 자원이 스레드에 할당되었음.
위 그림을 살펴보면 first_mutex 자원은 thread_one에 할당 되어 있고 second_mutex 자원은 thread_two에 할당되어 있다.
thread_one 은 second_mutex를 thread_two는 first_mutex 자원을 요청하면 cycle이 형성되고 데드락 상황이 된다.
<예시>
정점 내부에 점은 해당 자원에 존재하는 Instance를 의미한다.
1)
R2의 모든 instance를 스레드들이 사용하고 있지만 순환구조가 아니다. 따라서 Deadlock 상태에 빠지지 않는다.
만약 여기서 T3가 R2에 자원을 요청한다면 순환구조가 만들어져서 Deadlock 상태에 빠질 것이다.
2)
위 그림과 동일하지만 T3가 R2에 자원을 요청하고 있다.
R2의 인스턴스들이 모두 스레드들에 할당되어 있고 2개의 순환구조가 만들어졌기에 데드락이 발생한다.
3)
1개의 순환구조가 만들어졌고 모든 인스턴스 들이 스레드에 할당 되어 있지만 만약에 T2 or T4가 자원을 다 쓰고 반납한다면 T3나 T1은 자원을 할당받는 것이 가능하다. 따라서 Deadlock 상태가 발생하지 않는다.
정리: 순환구조가 존재하지 않으면 절대 Deadlock이 발생하지 않는다, 순환구조가 존재할 경우 Deadlock의 발생 가능성이 존재한다.
Deadlock Prevntion(데드락 방지))
- Mutal Exclusion(상호 배제): 모든 자원이 공유 가능하도록 하면 된다(?) 이러면 뮤 텍스 락을 쓰는 게 무슨 의미가 있나..
- Hold and Wait(점유 대기): 스레드가 자원을 요청할 때 본인이 점유하고 있는 자원을 반납하고 요청하도록 함. But, 매우 비효율적인 방법 만약 스레드가 엄청 많은 개수의 자원을 점유할 때 1개의 자원을 얻기 위해 그 많은 수의 자원을 다 반납해버리고 할당받은 1개의 자원을 사용한 후에 다시 그 수많은 자원을 회수하려면 매우 비효율적..
- No Preemption(비선점): 다른 스레드의 자원을 선점하여 주도권을 뺏는 것. 그러나 이전에 자원을 갖고 있던 스레드가 무엇을 하고 있는지 신경 쓰지 않고 뺏기 때문에 예상치 못한 문제가 발생할 수 있다.
- Circular Wait(순환 대기): 각 리소스마다 순서를 배정하여 자원을 요청할 때 기존에 점유하고 있던 자원보다 낮은 순서의 자원은 요청할 수 없도록 하여 순환구조의 발생을 막는 것. 우선순위 개념이 들어왔기 때문에 Starvation이 발생할 위험도 있다.
그리고 완벽하게 deadlock을 피할 수 있는 것도 아니다.
T1과 T2가 서로 동시에 송금하려고 하는 상황에서 문제가 발생한다.
T1이 lock1을 획득한 상황에서 T2가 lock2를 획득하려고 하면 T1이 lock1을 반납할 수 없다. 따라서 순환구조가 생긴다.
결론은 위의 방법으로도 완벽하게 Deadlock을 방지할 수 없다는 것이다.
Deadlock Avoidance(데드락 회피))
필요한 자원의 최대 개수와 이미 할당되어 있는 자원이나 앞으로 요구할 자원의 수를 알고 있고 이를 활용해 알고리즘을 통해 Deadlock 상태에 빠지는 것을 확실히 막을 수 있다.
<안전상태(safe state)>
안정상태는 데드락이 발생하지 않는다. 스레드를 최대한 안전상태에 있게 한다.
시스템 초기에는 안전상태에서 점유 대기를 수행한다. 이후 자원 요청이 들어올 때마다 상태를 판단하여 자원의 할당 여부를 결정한다.
안전상태일 경우 = 할당, 안전상태가 아닐 경우 = 거절
데드락 회피를 위해 claim edge를 추가할 수 있다.
claim edge는 미래에 해당 자원을 요청했을 때 순환구조가 발생하는지 확인해 볼 수 있는 역할을 한다.
claim edge를 추가했을 때 순환구조가 없다면 안전 상태에 있다는 뜻으로 추후 요청이 들어오면 허용 가능하다.
다만 claim edge는 자원의 instance가 1개일 때만 유효하다.
앞서 순환구조가 존재해도 데드락이 발생하지 않는 경우를 봤다.
인스턴스를 여러 개 가진 자원의 데드락을 미리 확인해 보는 방법은 은행원 알고리즘이다.
'Computer Science > 운영체제' 카테고리의 다른 글
| Chapter 10. Virtual Memory (0) | 2022.06.10 |
|---|---|
| chapter 09. Main Memory (0) | 2022.06.04 |
| Chapter 07-2. Windows API (0) | 2022.06.02 |
| Chapter 07-1. Synchronization Examples (0) | 2022.06.02 |
| Chapter 06. Synchronization Tools (0) | 2022.06.01 |
