운영체제 18. Deadlock을 어떻게 해결할까
교착상태를 어떻게 해결하는가?
교착 상태가 뭔데?
두 프로세스 \(T_{0}, T_{1}\)이 있다. \(T_{0}\) 프로세스가 필요한 자원을 \(T_{1}\)가 갖고있고, \(T_{1}\)이 반납해줄 때가지 대기중이다. 그러나 \(T_{1}\)가 필요한 자원은 \(T_{0}\)이 갖고있고, 똑같이 상대가 반납해줄 때까지 대기하고 있다. 이 대기는 영원히 끝나지 않는다. 이런 환형 대기 구조를 Deadlock라고 한다.
교착 상태는 언제 발생할까?
Deadlock는 다음 네 조건이 동시에 만족되면 발생한다. 하나라도 충족되지 않으면 Deadlock가 일어나지 않는다.
- 상호 배제가 이루어져야 한다. 상호 배제가 없다면, 그냥 남이 자원을 쓰고있던 말던 접근할 수 있으므로 Deadlock이 발생할 수 없다.
Mutual Exclusion - 상호 배제를 통해 대기 상태일 때, 내가 가지고 있는 자원을 뱉지 않아야 한다.
Hold and wait - 다른 프로세스의 자원을 뺏을 수 없어야 한다.
비선점, No preemption - 마지막으로 대기하는 프로세스들이 대기하며 환형 구조를 이루어야 한다. 즉, \(P_{0}\)은 \(P_{1}\)이 가진 자원을, \(P_{1}\)은 \(P_{2}\)가 가진 자원을, …, \(P_{n}\)은 \(P_{0}\)이 가진 자원을 기다리는 구조다.
Circular wait
그렇다면, 위 조건을 깨면 Deadlock은 발생 안하겠네?
맞다. 네 조건 중 하나를 깨면 Deadlock은 발생하지 않는다.
Mutual Exclusion 부정
이를 부정하는 것은, Deadlock을 막고자 동기화를 포기하는 것과 다름없다.
Hold and wait 부정
자원을 가지고 대기하는 상태를 막으면 된다. 즉, (1)모든 자원을 한꺼번에 다 쓸 수 있을 때까지 아에 작업을 시작하지 않거나, (2)대기 상태로 진입할 때 갖고있던 자원을 다 반납하고 다시 할당받으면 된다.
(1)번 방법은 당장에 필요없는 자원까지 한번에 할당받아야 하므로 자원 낭비다. 또, 많은 자원을 필요로하는 프로세스라면 기아 상태에 빠질 수 있다.
(2)번 방법은 사소한 자원 하나 얻는데 실패해도 기존의 갖고있던 모든 자원을 반납하는 상황이 벌어진다. 즉, 오버헤드가 크다. 또 기아 상태에 빠지기 쉽다.
따라서 사용하지 않는다.
[!NOTE] Dining Philosophers Problem에서의 Hold and wait 부정{title} 자원을 둘다 잡을 수 있을때만 집는다. 그렇지 않으면 아에 집지 않는다. AND 동기화라고 한다.
No preemption 부정
비선점 조건을 부정한다는 것은, 자원을 선점할 수 있다는 것이다. 즉 다른 프로세스가 가지고 있던 자원을 뺏어와야 하고, 그럼 남이 실행하던 작업이 엉망이 되어버릴 수 있다.
즉, 선점당한 프로세스가 원하던 작업 흐름이 있을 것이다. 이 작업 흐름을 끊고 다른 프로세스가 자원을 잠깐 사용해서 다시 되돌려 놓으면? 기존의 원하던 결과와 다른 결과를 야기할 수 있다. 이것 자체가 간섭이다. 우리는 간섭을 막기 위해 동기화를 구현했지 않는가?
따라서 현실적으로 적용하기 어렵다.
Circular wait 부정
Dining Philosophers Problem을 살펴보자.
환형 대기 조건을 깨는 아이디어는 다음과 같다. 위 환영 대기에서 자원을 요청하는 것 하나만 끊으면 된다. 만약 프로세스가 필요한 자원은 번호가 증가하는 순서대로 자원을 요청한다. 라는 규칙을 만든다. 따라서 자원에는 번호가 부여되어야 한다. 이 규칙을 통해 환영 대기가 자연스럽게 깨진다.
위 그림에서 갈색 철학자가 5번부터 집기 때문에 문제가 발생한다. 만약 자원의 번호가 증가하는, 1번 포크부터 집게하면 1번은 이미 파랑색이 가지고 있으므로 대기한다. 따라서 5번을 빨간색이 집을 수 있게 된다. 이후 빨간색이 모든 자원을 반납하면서 차례대로 대기 상태가 풀린다. 마지막으로 파랑색이 1번을 반납하면 갈색이 1, 5번을 차례로 집으며 자원을 사용할 수 있다.
문제가 있다. 항상 갈색이 꼴등으로 자원을 쓰게 된다. 따라서 평등하지 않다. 또는 기아상태에 빠질 수도 있다.
대안으로 번호가 역전되는 곳을 여러군데 만들어둘 수도 있다. 또는 홀수 철학자와 짝수 철학자는 포크 집는 순서를 달리 하는 방법도 존재한다. 기아 문제는 완전히 해결할 수 없다.
교착 상태가 될지 안될지 미리 알 수 있을까?
예방 방법은 자원 활용도를 낮추거나, 기아 문제를 발생시킨다. 그렇다면, Deadlock의 조건을 깨지 않되 교착 상태가 될지 안될지 미리 알 수 있다면? 잠시 자원 할당을 안하면 되잖아. 이것이 교착상태 회피(Deadlock Avoidance) 개념이다.
어떻게 Deadlock 발생 가능성을 예측할까? 안정 순열(safe sequence) 라는 가상의 개념을 도입한다. 어떤 프로세스들 사이의 안정 순열이 하나라도 존재하면 안정 상태이고, 그렇지 않으면 불안정 상태라고 한다. 불안정 상태라는 것은, Deadlock가 발생할 수 있는 가능성이 존재하는 상태와 같다. 즉 시스템은 초기에 안정 상태로 존재한다. 임의의 프로세스가 자원 할당을 요청한다. 요청 이후 시스템이 불안정 상태로 진입한다는 것을 파악하면, 자원 할당을 보류한다. 이로써 Deadlock을 회피한다. 즉 당장 가용할 자원이 있어도 대기한다는 측면에서 시스템 이용도는 떨어진다.
안정 순열이 무엇인가? 임의의 프로세스 순열 \(\langle P_{1}, P_{2}, \dots, P_{n}\rangle\)을 가정한다. \(P_{i}\)가 현재 필요한 자원량(a)이 있을 것이다. 그 필요한 자원이 시스템의 현재 남은 자원 갯수(b) + \(P_{1}, P_{2}, \dots, P_{i-1}\)가 가지고 있는 자원의 총합(c)보다 항상 작거나 같으면 이를 안정 순열이라 한다.
\[a \leq b + c\]회피 알고리즘에는 Banker’s 알고리즘이 있다. Banker’s 알고리즘은 어떤 프로세스가 자원을 요청했을 때, 일단 자원을 할당해주는 척 한다. Safety 알고리즘으로 시뮬레이션 돌려보고, 시스템이 불안정 상태가 되면 값들을 원상복구 시키고 자원을 할당해주지 않는다. 즉, Wait 상태로 만든다.
다음 상황을 가정한다.
- 프로세스 집합과 자원 유형 집합이 존재한다.
- 하나의 자원 유형의 개수는 여러개일 수 있다.
- 각 프로세스는 자원 갯수가 m개라면, 다음과 같은 차원이 m인 벡터 필드를 갖는다.
- Max: 최대치로 요청할 자원 개수. ‘최대 이만큼은 써야한다’
- Allocation: 할당 받은 자원 개수.
- Need: 필요한 자원 개수. \(\text{Max} - \text{Allocation}\)
- 시스템은 다음 정보를 가지고 있다.
- 초기 자원 개수
- Available: 현재 가용 가능한 자원 개수
- 프로세스가 요청한 자원 개수를 다음과 같은 차원 m인 벡터로 생각한다.
- Request: 프로세스가 임의의 시점에서 요청한 자원 갯수
Banker’s 알고리즘은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
만약 Request_i <= Need_i이고
만약 Request_i <= Available이면
먼저 자원을 준 척 한다.
Available -= Request_i
Allocation_i += Request_i
Need_i -= Request_i
Safety 알고리즘을 돌려본다.
불안정 상태라면
롤백 후 Wait()
안정 상태라면
그대로 할당
아니면
자원이 반납될 때까지 대기한다. Wait().
아니면
Request_i는 과도한 요청이다. Error.
}
어떻게 불안정 상태라는 것을 탐지할까? 모든 순열의 경우의 수를 체크해보면서, 안정 상태가 하나라도 존재하면 안정 상태다. 그러나 이는 비효율적이다. 효율적인 Safery 알고리즘이 존재한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
Work = Available;
Finish[n] = false;
for (j = 0; j < n; j++)
{
for (i = 0; i < n; i++) {
// 수행되지 않은 프로세스 중 바로 할당 가능한 프로세스를 아무거나 찾는다.
if (Finish[i] == false && Need[i] <= Work) {
Work = Work + Allocation[i];
Finish[i] = true;
}
}
}
핵심 아이디어는 다음과 같다. Work Vector는 항상 증가 또는 유지된다. 위 알고리즘은 자원을 할당할 수 있는 프로세스 \(i\)를 찾아내고, 그 프로세스에 자원을 할당 후 자원을 반납받는 상황을 가정한다. 그러면 \(i\)가 가지고 있던 자원 수 Allocation만큼 반납받게 되어 가용 가능한 자원 Work가 증가한다.
교착 상태를 탐지할 수 있을까?
만약 교착 상태를 탐지할 수 있다면, 탐지 알고리즘을 주기적으로 수행해서 교착 상태를 풀어버리면 된다. 어떻게 탐지할까?
(1) 자원 할당 그래프
프로세스를 원, 자원을 네모, 네모 안은 자원의 개수다. 프로세스 -> 자원은 자원 요청, 자원 -> 프로세스는 자원 할당이다. 이 상태는 시스템의 한 순간을 포착한 스냅샷이다.
사이클이 없다면 교착 상태가 발생하지 않는다. 사이클이 있고, 자원이 하나밖에 없다면 교착 상태가 반드시 발생한다. 사이클이 있고, 자원이 여러개 있다면 교착 상태가 발생할 수도 있다.
즉, 자원 유형당 자원이 하나씩만 존재하는 경우 자원 할당 그래프를 통해 교착 상태 여부를 바로 탐지할 수 있다.
(2) 탐지 알고리즘 프로세스들이 요구하는 자원들이 존재한다. 이를 \(\text{Request}_{i}\)라 하자. 어떤 프로세스가 요청한 자원을 할당해줬을 때, 그 프로세스가 잘 수행되어 자원을 반납한다고 가정한다. 이 가정을 계속 반복했을 때 모순이 발생한다면 가정이 틀렸음을 증명한다. 즉, 자원 \(\text{Request}_{i}\)를 해결해주지 못함이 증명된다. 따라서 교착 상태에 빠진 것과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Work = Available;
// 자원을 갖고있지 않은 프로세스는 탐지에서 고려하지 않아도 된다.
// 교착 상태는 교착 상태 사이클 내의 프로세스가 자원을 hold and wait 해야하기 때문이다.
Finish[i] = (Allocation[i] != 0) ? false : true;
for (j = 0; j < n; j++)
{
for (i = 0; i < n; i++) {
if (Finish[i] == false && Request[i] <= Work) {
Work += Allocation[i];
Finish[i] = true;
}
}
}
교착 상태를 강제로 풀어버릴 수 있을까?
가장 단순한 방법은, 교착 상태에 빠진 모든 프로세스를 다 종료시키는 것이다. 너무 무식한 방법이다.
그러면, 하나 종료시켜보고, 탐지 알고리즘으로 데드락 검사하는걸 반복해서 데드락 풀릴때까지 반복하자. 그러면 덜 종료시켜도 되잖아. 이 방법도 문제다. 탐지 알고리즘의 오버헤드가 존재하고, 종료시킬 희생양 프로세스를 선택해야 한다.
어떤 프로세스를 희생양 삼는게 좋을까?
- 프로세스의 우선순위가 낮은 것부터 종료하는게 좋을 것이다.
- 수행 시간이 짧은 것부터 종료하는게 좋을 것이다.
- 점유한 자원이 많은 프로세스를 종료하는게 효과적이다.
- 사용자와 상호작용하는 대화성 프로세스보다 백그라운드에서 실행되는 일괄 프로세스를 종료시키는 것이 낫다.
종료시키지 말고, 자원을 뺏어서 해결할 수는 없을까? 이 또한 고려해야 하는 부분이 많다. 어떤 프로세스의 자원을 뺏을 것인지 희생양을 또 정해야 한다. 그리고 자원을 할당하기 전으로 Rollback해야 한다. Rollback하기 위해 이전 상태를 기록해야 한다. 메모리 오버헤드가 발생한다. 구현도 복잡하다. 그리고 특정 프로세스가 계속 희생양으로 선택하면 기아 상태에 빠질 수 있다. 기아 상태를 해결하기 위해 희생자 선택 횟수에 제한을 걸어야 한다.
실제로 대부분의 범용 운영체제(Windows, macOS, Linux 등)는 교착상태가 매우 드물게 발생한다고 가정하고, 탐지 및 회복에 드는 비용이 더 크다고 판단하여 교착상태를 무시하는(Ignorance) 전략을 사용한다.