[OS-반효경] Deadlock

이전 글인 Process Synchronization에서 Deadlock을 간단히 소개했는데, 본 포스팅에서는 Deadlock(교착상태)에 대해 자세히 알아보겠습니다.

Deadlock은 일련의 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태입니다. 프로세스가 자원을 사용하는 과정은 보통 Request(요청) → Allocate(획득) → Use(사용) → Release(반납)로 이루어집니다. Deadlock은 일부 프로세스가 자원을 획득한 채로 다른 자원을 요청하고, 그 요청이 서로 얽히면서 자원을 반납하지 못할 때 발생합니다.

Deadlock 조건

Deadlock이 발생하려면 Mutual exclusion, No preemption, Hold and wait, Circular wait이 모두 만족해야 합니다.

Mutual exclusion(상호배타성): 매 순간 하나의 프로세스만이 자원을 독점적으로 사용할 수 있음
No preemption(비선점): 자원을 빼앗기지 않음
Hold and wait: 자신이 가진 자원을 반납하지 않고 계속 갖고 있음
Circular wait: 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

위 조건 중 하나라도 만족하지 않는다면 Deadlock은 발생하지 않습니다.

Deadlock 처리 방법

Deadlock을 처리 방법은 Deadlock Prevention, Deadlock Avoidance, Deadlock Detection and Recovery, Deadlock Ignorance가 있습니다.

Deadlock Prevention: Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance: 시스템의 State가 원래의 State로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and Recovery: Deadlock 발생은 허용하되 그에 대한 Detection 루틴을 두어 Deadlock 발견시 Recovery
Deadlock Ignorance: Deadlock을 시스템이 책임지지 않음. → 사용자가 Deadlock 해결

Deadlock 처리 방법의 강도는 Prevention > Avoidance > Detection and Recovery > Ignorance로 Prevention이 가장 강하게 처리됩니다. 또한 Prevention과 Avoidance는 Deadlock을 사전에 예방하는 것이지만, Detection and Recovery와 Ignorance는 Deadlock을 허용합니다.

Deadlock Prevention

Deadlock Prevention은 Deadlock 처리 방법 중에서 가장 강한 처리 방법으로, Deadlock의 4가지 조건 중 어느 하나가 만족되지 않도록 하면 됩니다.

Mutual exclusion

이 조건은 대부분의 경우 만족하기 때문에, Prevention에서 고려 대상이 아닙니다.

No preemption

프로세스가 어떤 자원을 기다려야 한다면, 이미 보유한 자원을 모두 반납(preemption)시킵니다. 이후 필요한 자원을 모두 얻을 수 있을 때 다시 실행한다면 No preemption 조건을 만족시키지 않게 됩니다.

Hold and wait

Hold and wait 조건을 깨는 방법은 프로세스 시작 시 필요한 자원을 한 번에 모두 할당받고, 프로세스 종료때 자원을 반납하면 해당 조건을 만족시키지 않습니다. 하지만 이 방법은 매 시점 필요한 자원을 알아야 하기 때문에 비효율적입니다.

또 다른 Hold and wait 조건을 깨는 방법은 추가 자원이 필요하면, 보유 중인 자원을 모두 반납한 뒤 다시 요청하면 됩니다.

Circular wait

모든 자원 유형에 전역적인 할당 순서를 정하여 프로세스가 정해진 순서대로만 자원을 요청하면 해당 조건은 만족하지 않습니다.

위와 같은 Prevention 방법을 사용하면 Deadlock을 원칙적으로 막을 수 있지만, 자원 활용률이 떨어지고 처리량이 감소하며 Starvation 문제가 발생할 수 있어 비효율적입니다.

Deadlock Avoidance

Deadlock Avoidance는 Deadlock이 발생할 수 있는 상태로 시스템이 들어가지 않도록, 자원 할당 시점에 시스템이 안전한지(Safe) 동적으로 검사한 뒤 안전한 경우에만 자원을 할당하는 방법입니다.

Safe,unsafe,deadlocked_state_spaces

가장 일반적인 모델은 각 프로세스가 ‘각 자원별 최대 사용량’을 미리 선언하도록 하는 방식입니다. 최대 사용량 정보를 이용하여 운영체제는 현재 상태에서 safe sequence가 존재하는지 확인합니다. safe sequence가 하나라도 존재한다면, 안전한 상태(safe state)로 간주되어 Deadlock이 발생하지 않습니다.

safe sequence는 현재 가용 자원과 앞선 프로세스들이 반납한 자원만으로, 모든 프로세스를 Deadlock 없이 완료할 수 있는 실행 순서입니다.

Deadlock Avoidance는 2가지 경우일 때, 대표적인 알고리즘이 있습니다.

자원이 한 개인 경우 → Resource Allocation Graph Algorithm
자원이 여러개인 경우 → Banker’s Algorithm

Resource Allocation Graph Algorithm

RAG_Algorithm

Resource Allocation Graph 알고리즘은 앞으로 해당 자원을 요청할 가능성을 그래프에 미리 표시(점선)해두고, 실제 요청이 들어왔을 때 Cycle이 생기는지를 검사하여 unsafe state를로 진입하는 것을 막습니다.

Cycle 여부를 검사하는 데는 프로세스 수가 n일 때, 보통 $O(n^2)$ 시간이 걸릴 수 있습니다.

Banker’s Algorithm

Banker’s 알고리즘은 자원 요청이 들어올 때마다 시스템 safe state를 유지할 수 있는지 검사한 뒤, safe한 경우에만 자원을 할당합니다. Banker’s 알고리즘을 사용하기 위한 가정은 다음과 같습니다.

모든 프로세스는 각 자원에 대한 최대 사용량을 미리 선언
자원을 할당받은 프로세스는 유한한 시간 안에 작업을 끝내고 자원을 반납

Banker's_Algorithm

A는 10개, B는 5개, C는 7개가 존재합니다. 사용할 수 있는 자원은 $(3, 3, 2)$ 입니다. $P_0$ 는 $(7, 4, 3)$ 이 필요한데, 부족하여 $P_1$ 를 살펴 봅니다. $P_1$ 은 $(1, 2, 2)$ 가 필요한데, $(3, 3, 2)$ 보다 작거나 같으므로 처리가 가능합니다. $P_1$ 에게 자원을 빌려주고 작업을 마쳤다면, $P_1$ 이 반납하는 자원 $(2, 0, 0)$ 은 새로운 가용 자원인 $(3, 3, 2) + (2, 0, 0) = \mathbf{(5, 3, 2)}$ 가 됩니다.

$P_1$ 가 끝나고 남은 프로세스( $P_0, P_2, P_3, P_4$ ) 중 가능한 곳을 찾습니다. $P_0$ 은 $(7, 4, 3)$ 가 필요한데, A가 부족합니다. $P_2$ 은 $(6, 0, 0)$ 가 필요한데, A가 부족합니다. $P_3$ 은 $(0, 1, 1)$ 가 필요한데, $(5, 3, 2)$ 보다 필요 자원이 작으므로 가능합니다. $P_3$ 에게 자원을 빌려주고 작업을 마쳤다면, $P_3$ 의 반납 자원 $(2, 1, 1)$ 은 새로운 가용 자원인 $(5, 3, 2) + (2, 1, 1) = \mathbf{(7, 4, 3)}$ 가 됩니다.

위와 같은 과정을 반복하면 $\langle P_1, P_3, P_4, P_2, P_0 \rangle$ 로 safe sequence가 완성됩니다. 즉 시스템은 안전하기 때문에 Deadlock이 발생하지 않습니다.

Deadlock Detection and Recovery

Deadlock Detection and Recovery는 Deadlock 발생을 허용하되, 주기적으로 Deadlock을 탐지하고 Deadlock이 발견되면 이를 복구(Recovery)합니다. Prevention/Avoidance처럼 사전에 Deadlock을 막지 않기 때문에 자원 활용률은 높을 수 있지만, Deadlock이 발생하면 탐지 비용과 복구 비용이 추가로 발생합니다.

Detection

Deadlock 탐지는 현재 시스템 상태에서 Deadlock이 발생했는지를 검사하는 과정입니다.

Detection 자원이 1개인 경우에는 현재의 Resource Allocation Graph를 Wait-for Graph로 변환해서 Cycle을 검사합니다. Cycle이 발견된다면 Deadlock 상태입니다.

자원이 여러개인 경우에는 Banker’s Algorithm과 유사하게, Available, Allocation, Request 정보를 이용해 ‘종료 가능한 프로세스가 남아있는지’를 반복적으로 확인합니다. 끝까지 종료되지 못하는 프로세스가 남는다면 Deadlock으로 판단합니다.

Deadlock을 언제 검사할지는 정책에 따라 달라집니다.

일정 시간마다 주기적으로 검사
자원 요청이 계속 실패하는 경우에만 검사
CPU/IO 사용량이 비정상적으로 떨어질 때 검사

Recovery

Deadlock이 탐지되면, Cycle을 끊기 위해 프로세스나 자원을 대상으로 복구(Recovery)를 수행합니다. 복구는 프로세스를 종료하거나 자원을 선점하여 복구할 수 있습니다.

Deadlock Ignorance

Deadlock Ignorance는 운영체제가 Deadlock을 ‘드물게 발생하는 문제’라고 취급합니다. 또한, Deadlock에 대한 조치가 더 큰 오버헤드라고 생각하여 탐지나 예방 로직을 두지 않습니다.

그래서 만약 Deadlock이 발생하면 사용자가 직접 프로세스를 kill합니다. Deadlock Ignorance은 UNIX나 Windows 등 대부분의 범용 운영체제가 채택하는 방법입니다.

Conclusion

이번 포스팅에서는 Deadlock의 조건, Deadlock의 처리 방식 등 Deadlock에 대해 자세히 알아보았습니다. 다음에는 메모리 관리에 대해 알아보겠습니다.

References

[1] KCOW 운영체제 반효경 강의

[2] Operating System Concepts(Silberschatz, Galvin and Gagne)