8.1. 시스템 모델
데드락 (deadlock)
한 프로세스의 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 일어날 수 있는 event를 기다리는 상태
즉, 어떤 스레드 (or 프로세스)가 필요로 하는 자원을 다른 waiting 스레드에서 점유하고 있는 상태
(모든 프로세스가 waiting 상태 ⇒ waiting 상태가 영원히 끝나지 않는다.)
시스템을 고려해보자
시스템은 경쟁하는 스레드들 사이에 분배 되어야 할 유한한 수의 자원들로 구성된다.
이러한 자원들은 하나의 타입 (type)으로 분할된다..
→ 여러 개의 identical instance를 하나의 Resource type으로 정의한다.
ex) 한 시스템이 4개의 CPU를 가진다면, Recource type CPU는 4개의 인스턴스를 가진다.
만약 스레드가 어떤 Resource type의 한 인스턴스를 요청하면, 동일한 Resource type의 “임의의” 인스턴스를 할당함으로써 요청이 충족된다.
스레드는 주로 요청 (request) - 사용 (use) - 반납 (release)의 순서로 자원을 사용하는데, '사용' 단계에서 한 번에 여러 자원을 사용할 수 있다.
8.2. 다중 스레드 응용에서의 교착 상태
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);
//1번 스레드 함수//
void* do_work_one(void* param)
{
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/* 작업 수행 */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
//2번 스레드 함수//
void* do_work_two(void* param)
{
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/* 작업 수행 */
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
}만약 1번 스레드가 first_mutex의 lock을 획득하고, 2번 스레드가 second_mutex의 lock을 획득한 상태라면
→ 1번 스레드는 second_mutex의 lock을 획득하기 위해 대기하고, 2번 스레드는 first_mutex의 lock을 획득하기 위해 대기하게되면서 DeadLock이 발생할 수 있다.
8.3. 교착 상태 특성(Deadlock Characterization)
Deadlock이 발생할 수 있는 네 가지 필요조건
-
Mutual Exclusion(상호 배제)
최소한 하나의 자원이 비공유(non-sharable) 모드로 점유되어야 한다.ex) 여러개의 reader + 하나의 writer가 필요하다.
-
Hold-and-wait(점유하며 대기)
스레드가 최소한 하나의 리소스를 점유하고 있는 상태로 ,다른 스레드가 점유하고 있는 자원을 획득하기 위해 대기하고 있어야 한다.(아무 자원도 점유하지 않고 대기 중이면 데드락이 발생하지 않는다.)
-
No preemption(선점불가)
자원들을 선점할 수 없어야 한다.자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드 종료 후 자발적으로 방출되어야 한다.
-
Circular Wait(순환 대기)
대기 중인 스레드의 집합{T0,T1…Tn}에서 T0은 T1이 점유한 자원을 대기, T1은 T2가 점유한 자원을 대기, … , Tn-1은 Tn이 점유한 자원을 대기한다.
자원 할당 그래프(Resource-Allocation Graph)
자원 할당 그래프는 방향 그래프 (directed graph, digraph)이다.
방향 그래프는 정점(vertex) 집합, 간선(Edge)의 집합으로 구성된다.
정점의 집합
- T={T1,T2,⋯Tn} -> 시스템 내의 모든 활성 스레드의 집합
- R={R1,R2,⋯Rn} -> 모든 Resource Type의 집합
간선의 집합
- Ti→Rj 요청 간선(request edge): Ti 스레드가 Rj 자원을 요청
- Rj→Ti 할당 간선(assignment edge): Rj 자원이 Ti 스레드에 할당
(mutex는 자원으로 생각하면 된다.)
1. first_mutex가 thread_one에 할당된다.
2. thread_one이 second_mutex를 요청한다.
3. 하지만 second_mutex는 thread_two에 할당된다.
4. thread_two가 first_mutex를 요청한다.
5. 하지만 first_mutex는 이미 thread_one에 할당되었다.
… 위 과정이 계속 반복된다.그래프가 순환하는 것을 확인할 수 있다.
자원 할당 그래프 예시
자원 할당 그래프의 정의로부터, 그래프가 사이클(cycle)을 포함하지 않으면 시스템 내 어느 스레드도 DeadLock이 발생하지 않는다.
R2 자원에 인스턴스가 두 개가 있지만, 사이클이 두 개가 만들어졌으므로, Deadlock 발생
사이클이 있음에도 불구하고, P2와 P4가 자원을 반납하면 DeadLock 문제가 해결될 수 있다.
Note:
- 자원 할당 그래프에 사이클이 없다면, DeadLock이 발생하지 않는다.
- 사이클이 있다면 DeadLock이 발생할 수도 있고, 발생하지 않을 수도 있다.
8.4. 교착 상태(DeadLock) 처리 방법
- 문제를 무시하고, 교착 상태가 시스템에서 발생하지 않는 척 한다.
- 절대 교착 상태가 되지 않도록, 예방(prevent)하거나 회피(avoid)하는 프로토콜을 사용한다.
- 시스템이 교착 상태가 되도록 허용한 다음 탐지(detect) 후 회복(recover)한다.
8.5. 교착 상태 예방
DeadLock이 발생하려면 네 가지의 필요조건이 각각 성립해야 한다.
이들 조건 중에서 최소한 하나가 성립하지 않도록 하여 교착 상태를 예방한다.
상호 배제(Mutual Exclution)
최소 1개 이상의 자원이 공유가 불가능해야 한다는 조건이다.
만약 모든 자원이 공유 가능하다면 어떨까?
→ 현실적으로 불가능하다.
본질적으로 공유가 불가능한 자원이 존재한다.
ex) mutex 락은 동시에 여러 스레드가 공유할 수 없다.
(Shared Data에 다른 스레드가 접근하지 못하도록 하기 위한 것이니까)
점유하며 대기(Hold and Wait)
스레드가 자원을 점유한 상태로 대기하고 있기 때문에 발생하는 문제
→ 프로세스가 자원을 요청할 때, 다른 어떤 자원도 가지고 있지 않아야 한다.
방법 1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하자
- 자원 이용률이 낮다. 자원이 할당되었지만 장기간 사용되지 않을 수 있다.
- 기아가 발생한다. 인기있는 여러 개의 자원이 필요한 스레드는, 적어도 하나의 자원이 다른 스레드에 항상 할당되므로 무한정 대기를 해야한다.
방법 2. 자원이 필요할 경우, 보유한 자원을 모두 놓고 다시 요청하자
- 매우 비효율적인 시스템이다. ex) 여러개의 파일을 open하고 있는 스레드가 있다. 1개의 새로운 파일 Open시모든 파일을 close 후, 다시 파일을 open해야 한다.
비선점(No Preemption)
이미 할당된 자원이 선점되지 않아야하기 때문에 발생하는 문제
→ 모든 자원에 대한 선점을 허용한다.
→ 프로세스가 할당 받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기한다.
(자원 낭비 발생 )
순환 대기(Circular Wait)
4가지 해법 중 그나마 실용적인 해법
모든 Resource type에 순서를 부여한다. 각 프로세스가 반드시 오름차순으로 자원을 요청하도록 한다.
증명
{T0, T1 … Tn}의 스레드가 있다. Ti는 Ri를 대기하고있고, Ti+1은 Ri를 가지고 있다.
그러면 Ti+1이 Ri를 가지고있으면서 Ri+1을 요청하기 때문에 F(Ri) < F(Ri+1)이 만족한다.
하지만 이 조건은 F(R0) < F(R1) < … < R(Rn) < R(R0)을 의미한다.
F(R0) < F(R0)은 성립하지 않기 때문에, 오름차순으로 자원을 요청할 경우 순환 대기 조건이 성립할 수 없다.
하지만 DeadLock을 예방이 보장되지는 않는다.
순환 대기 조건을 예방하기 위해 순서를 부여해서
Lock1 획득 후 Lock2를 획득하도록 구현했지만, DeadLock이 발생할 수 있다.
두 계좌 A, B가 있다고 할 때, A→B & B→A 동시에 송금이 발생한다면?
Thread1이 lock1을 획득 한 상태에서, Thread2가 lock2를 획득한다면
Thread1이 lock1을 반납할 수 없기 때문에 Cycle이 발생한다.
참고 :
Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.
