저번 시간에는 세마포어에 대해 알아봤었다. 세마포어는 Block & Wakeup 구조를 통해 spinlock 문제를 해결했지만 이로 인해 또 다른 문제가 발생한다고 했었다. 그 중 하나가 Deadlock and Starvation 문제다. 데드락은 아래 그림과 같이 서로 다른 두 프로세스가 wait 상태에 있는 자원을 요청하는 경우 발생한다. 만약이 이 문장을 이해했다면 데드락의 개념은 이해한 것이다. 이번 글에서는 데드락이 정확하게 무엇인지, 어떤 상황에서 발생하는지 알아볼 것이다.
데드락(Deadlock)의 개념 - 식사하는 철학자 문제
'식사하는 철학자 문제'는 데드락의 개념을 설명할 때 정말 많이 사용되는 예시다. 아래의 상황을 가정하고 시작한다. 좀 말이 안 되기는 하지만 개념 설명을 위한 가정이기 때문에 그냥 그러려니 하고 넘어가자.
다섯 명의 철학자가 한 자리씩 차지한다. 식탁은 위와 같이 원형이고, 철학자 양 옆에 포크가 하나씩 놓여있다(철학자 수 = 포크의 수). 철학자는 프로세스에 대응하고 포크는 자원에 대응한다. 따라서 위 그림은 세마포어의 integer 변수가 5인 경우라고 할 수 있다. 식사 규칙은 아래와 같다.
1. 철학자는 식사를 하거나 안 하거나 둘 중 하나의 액션만 취한다.
2. 식사를 할 때는 양쪽 포크를 사용하는데, 왼쪽포크 → 오른쪽포크 순서로 사용한다.
3. 다 먹으면 포크를 내려 놓는데, 왼쪽포크 → 오른쪽포크 순서로 내려 놓는다.
4. 포크는 같이 사용할 수 없다. 한 명이 사용중이면 다 사용할때까지 기다려야한다.
코드로 살펴보면 아래와 같다.
do{
wait(forks[i]);
wait(forks [(i + 1) % 5]);
// eat
signal(forks[i]);
signal(forks[(i + 1) % 5]);
// think
} while(True);
식사를 한 명씩만 하면 문제될 것이 전혀 없다. 한 명이 포크를 사용하고 내려놓은 뒤에 다른 한 명이 식사하면 포크가 겹칠 일이 없기 때문이다. 문제가 발생하는 경우는 다섯 명 모두 동시에 포크를 집을 때 발생한다.
아래의 그림과 같은 상황이다. 빨간색 화살표가 왼쪽 포크를 집는 액션이고, 남색 화살표가 오른쪽 포크를 집는 액션이다. 모두 동시에 배가 고파 각자 왼쪽의 포크를 집었다. 오른쪽 포크를 집으려는데 다른 사람이 이미 가지고 있어서 식사를 못하고 있다. 어느 한 명이 식사를 완료해야 포크를 내려놓는데 식사는 오른쪽 포크까지 집어야 가능하기 때문에 다섯 명의 철학자는 영원히 식사를 하지 못한다. 이러한 상황을 바로 '데드락'이라고 한다.
식사하는 철학자 문제로 얻을 수 있는 아주 중요한 포인트가 하나 있다. 위에 코드를 다시 한번 보고 온 뒤에 아래 질문에 답해보기를 바란다.
데드락은 어떤 상태(state)에서 발생할까?
데드락이 발생한 이유는 프로세스가 자원을 해제하지 못했기 때문이다. 그러면 이렇게 생각할 수 있다. 데드락은 자원을 공유하고 있는 모든 프로세스가 wait 상태일 때 발생한다. 전부 wait 상태에 있기 때문에 모두 영원히 기다리기만 하는 것이다.
참고로 데드락은 프로세스 관점과 시스템 관점에서 볼때 약간의 의미 차이가 있다. 시스템이 데드락에 빠졌다는 것은 시스템 내의 프로세스가 하나 이상 데드락 상태에 빠졌다는 것을 의미하고, 프로세스가 데드락에 빠졌다는 것은 프로세스가 wait 상태에 있고 자원을 절대 받을 수 없는 상황을 의미한다. 프로세스 여러 개의 입장이냐, 하나의 입장이냐 차이다. 크게 중요한 것은 아니다.
데드락(Deadlock) 시스템 모델
데드락의 발생 조건을 설명하기 전에 용어 정리를 먼저 하자. 앞으로 자주 쓰이게 될 용어 두 개를 소개한다. 바로 resource type과 instance다.
- Resource type : 인스턴스를 담는 컨테이너. ex) 프린터, LAN 카드
- Instance : 자원의 개체 ex) 프린터1, 프린터2, 프린터3 ...
크게 어렵지 않은 개념이니 더이상 설명하지 않겠다. 아마 위 그림으로 딱 감 잡았을 것이다. 단, 같은 자원이라도 다른 resource type으로 설정할 수 있음에 유의하자. 여러 대의 프린터를 두 개의 컨테이너에 담아 type1, type2로 분류할 수 있다는 말이다.
앞으로 데드락을 설명할 때 방향 그래프 모델을 사용할 것이다. 그래프이기 때문에 노드와 간선을 가진다. 노드와 간선의 종류는 두 가지이며 각각 아래와 같다.
1) Process Node, Resource Node
2) Request Edge(P_i → R_j), Assignment Edge(R_j → P_i)
- Request Edge
- Assignment Edge
데드락(Deadlock) 발생 조건
프로세스는 어떤 자원을 사용하려고 할 때 아래의 순서로 동작한다.
1. request : 자원 요청. 가용 자원이 없으면 계속 대기
2. use : 프로세스가 자원 사용중
3. release : 프로세스가 자원을 다 쓰고 해제
위와 같은 프로세스 실행 순서에서 데드락은 다음의 네 가지 조건이 모두 만족되어야 발생한다.
1. Mutual Exclusion : 하나의 자원을 두 개의 프로세스가 점유할 수 없다. 프로세스와 자원을 일대일 대응 관계다.
2. Hold and wait : 프로세스가 자원을 점유하고 있는 상태에서 다른 자원을 요청할 수 있다.
3. No preemption : 프로세스는 자원을 강제로 빼앗을 수 없다. 자원이 해제돼야 사용할 수 있다.
4. Circular wait : 식사하는 철학자 문제처럼 wait 상태의 프로세스들끼리 cycle이 발생한 경우. P0 → P1 → P2 → P0
이제 몇 가지 예시를 살펴보자.
Case 1 - 세 가지 조건 만족
- Mutual Exclusion : 두 개의 프로세스가 하나의 인스턴스를 차지하는 경우는 없다
- Hold and wiat : P1, P2는 자원을 할당받은 상태에서 요청하고 있다
- No preemption : YES (가정)
- Circular wait : 순환 구조 없음
위 예시는 데드락에 빠질까? 데드락의 네 가지 조건 중 Circular wait 하나만 만족하지 않고 있다. 아래와 같은 순서로 진행하면 모든 간선을 제거할 수 있다. 따라서 이 예시는 데드락에 빠지지 않았다.
Case 2 - 네 가지 조건 모두 만족
- Mutual Exclusion : 두 개의 프로세스가 하나의 인스턴스를 차지하는 경우는 없다
- Hold and wiat : P1, P2, P3은 자원을 할당받은 상태에서 요청하고 있다
- No preemption : YES (가정)
- Circular wait : 두 개의 cycle 있다
위 예시는 데드락에 빠질까? 데드락의 네 가지 조건을 모두 만족하고 있다. 해보면 알겠지만 모든 간선을 제거할 수 있는 경우의 수는 없다. 따라서 이 예시는 데드락에 빠졌다.
Case3 - 네 가지 조건 모두 만족 (특수 케이스)
- Mutual Exclusion : 두 개의 프로세스가 하나의 인스턴스를 차지하는 경우는 없다
- Hold and wiat : P1, P3은 자원을 할당받은 상태에서 요청하고 있다
- No preemption : YES (가정)
- Circular wait : 한 개의 cycle 있다
위 예시는 데드락에 빠질까? 데드락의 네 가지 조건을 모두 만족하고 있다. 아래와 같은 순서로 진행하면 모든 간선을 제거할 수 있다. 따라서 이 예시는 데드락에 빠지지 않았다.
데드락의 네 가지 조건을 모두 만족하는데 데드락에 빠지지 않은 이유는 뭘까? Case2와의 차이점이 뭘까? 가장 큰 차이는 자원 R_1에 있다. 자원 R_1은 순환에 빠졌지만 할당 가능한 인스턴스에 여유가 있다. 이게 어떤 상황이냐 하면, 식사하는 철학자 문제에서 한쪽에 포크가 두 개 놓여 있는 경우다. 포크에 여유가 있기 때문에 철학자 한 명이 식사를 할 수 있게 되고 식사 완료 후 포크를 내려 놓으면 다른 철학자들도 식사를 할 수 있게 된다. 즉 특수 케이스는 아래와 같이 정리할 수 있다.
순환에 빠진 자원의 인스턴스에 여유가 있으면 데드락에 안 빠질 수 있다!!!
따라서 아까 위에서 데드락의 네 가지 조건을 모두 만족하면 데드락이 발생한다고 했는데, 정확하게 말하면 아래와 같이 수정할 수 있다.
네 가지 조건을 모두 만족하면 데드락이 발생할 가능성이 생긴다.
따라서 아래의 명제는 거짓이 됨을 알 수 있다.
데드락 조건을 모두 만족 → 데드락 발생
데드락(Deadlock) 해결 방법
지금까지는 데드락이 어떤 경우에 발생하는지에 대해 살펴봤다. 그러면 반대로 데드락이 발생하지 않게 하려면 어떻게 해야 할까? 내용이 길기 때문에 이는 다음 시간에 살펴보도록 하자.
'CS > 운영체제' 카테고리의 다른 글
| [ 운영체제 ] Banker's Algorithm (0) | 2022.01.31 |
|---|---|
| [ 운영체제 ] 데드락(Deadlock) 해결 방법 (0) | 2022.01.31 |
| [ 운영체제 ] 동기화 방법3 - Semaphores (0) | 2022.01.26 |
| [ 운영체제 ] 동기화 방법2 - TestAndSet(), Mutex Locks (0) | 2022.01.25 |
| [ 운영체제 ] 동기화 방법1 - Peterson's Solution (0) | 2022.01.25 |
