데드락(Deadlock)이란? 🔍
교착상태라고도 불리며, 프로세스들이 서로가 가진 자원을 요구하며 뒤엉킨 상태입니다. 프로세스들은 자원을 얻지 못하여 다음 상태로 넘어가지 못하게 됩니다.
프로세스가 R1과 R2를 모두 얻어야 동작하는 상황일 때
위의 그림과 같이 프로세스 P1이 리소스 R1을 점유한채로 R2를 요청하고,
P2는 R2를 점유한 채로 R1을 요청하는 상태일 경우
서로가 상대의 자원을 무한정으로 기다리는 상황이 발생합니다. 이것을 교착상태(Deadlock)이라고 합니다.
- 위와 같은 그림을 그리는 이유는? 🧐
- Resource Allocation Graph(RAG)를 그리는 이유는 사이클의 유무를 효과적으로 탐지하기(Detection) 위해서 입니다. 보통 프로세스를 동그라미, 리소스를 네모로 표현합니다.
데드락의 필요조건 4가지 🔑
아래 4가지가 전부 충족되어야 데드락이 발생할"수도" 있는 것입니다.
1. 상호 배제 (Mutual Exclusion)
- 리소스 하나는 한 번에 한 프로세스만이 사용할 수 있어야 합니다.
2. 점유 대기 (Hold and Wait)
- 이미 하나 이상의 자원을 가지고 있는 동시에 다른 자원을 사용하기 위해 대기하고 있는 프로세스가 있어야 합니다.
3. 비선점 (No Preemption)
- 이미 다른 프로세스가 가지고 있는 자원은 해당 프로세스가 끝날 때 까지 빼앗을 수 없습니다.
4. 순환 대기 (Circular Wait)
- 여러 개의 프로세스가 서로가 가지고 있는 자원을 요청하는 상황입니다. 위의 그림과 같은 상황이 순환 대기의 대표적인 예시입니다.
- 리소스 하나당 인스턴스가 하나일 경우에는 사이클이 데드락의 필요충분조건이 되지만, 인스턴스가 여러 개일 경우에는 사이클이 필요조건이 됩니다.
데드락의 해결 방법 💡
데드락을 예방(Prevention)하거나, 회피(avoidance)해야합니다. 혹은 데드락이 발생하도록 놔두다가 발생했을 경우 탐지하고 회복(Detection and Recovery)해야 합니다.
1. 데드락 예방 (Prevention)
- 상호 배제(Mutual Exclusion)
- 해당 조건을 없애려면 한 자원을 여러 프로세스가 공유해야합니다.
- 일반적인 경우 여러 프로세스가 한 자원을 공유한다는 것이 불가능합니다.
- 점유 대기 (Hold and Wait)
- 자원을 아무것도 소유하지 않을 때만 자원을 요청해야 합니다.
- 또는 모든 리소스가 사용가능한 조건에서만 실행을 하게 해야 합니다.
- 가능은 하나 리소스 utilization이 낮다는 부작용이 있습니다.
- starvation(프로세스가 필요한 리소스를 끊임없이 가져오지 못하는 상황)이 발생할 수 있습니다.
- 비선점 (No Preemption)
- 어떤 프로세스가 리소스를 가지고 있는 상태에서 지금 당장 할당받을 수 없는 리소스를 요청할 경우, 가지고 있던 리소스도 release한 후 wait 상태로 돌아갑니다.
- CPU 에서는 가능하지만 프린터와 같이 중간에 wait 상태로 다시 돌아갈 수 없는 경우 불가능합니다.
- 순환 대기 (Circular Wait)
- 모든 리소스 타입에 우선순위를 매겨 어떤 리소스를 할당받았을 경우 해당 리소스보다 번호가 작은 리소스는 요청할 수 없게 합니다.
- Ex) tape = 1, printer = 12 라고 할 때, tape -> printer 는 가능하지만 printer -> tape 는 불가능합니다.
- 리소스 utilization 이 낮다는 부작용이 있습니다.
2. 데드락 회피 (Avoidance)
절대 데드락이 발생하지 않는 조건 : Available Resource >= Need
Banker's Algorithm의 핵심
- Safe state 예시 (12개의 인스턴스를 가진 리소스라고 했을 때)
| Maximum Needs | Current Use(Allocation) | Needs(Demand) | |
|---|---|---|---|
| P0 | 10 | 5 | 5 |
| P1 | 4 | 2 | 2 |
| P2 | 9 | 2 | 7 |
처음 상황에서는 남아있는 인스턴스가 3개이고, safe sequence는 P1, P0, P2 입니다.
- P1 : 5 + 2 + 2 + (4 - 2) = 11 <= 12
- P1 이 종료되었을 경우 : 4개의 인스턴스 반환 => 5개의 인스턴스 사용 가능
- P0 : 5 + 2 + (10 - 5) = 12 <= 12
- P0 이 종료되었을 경우 : 10개의 인스턴스 반환 => 10개의 인스턴스 사용 가능
- P2 : 2 + (9 - 2) = 9 <= 12
=> 자원을 많이 요청하는 프로세스가 뒤에 수행됩니다.
- Needs <= Available 를 매번 체크해서 safe sequence를 찾는 것이 Banker's Algorithm의 기본 정리 입니다.
데드락 탐지와 회복 (Detection and Recovery)
- Single Instance의 경우
- Resource Allocation Graph(RAG)를 이용하여 cycle을 탐지합니다.
- Multiple Instance의 경우
- Banker's Algorithm의 Needs를 Request로 바꾸어 Needs 가 더 많을 경우 데드락이 발생한 것이므로 해당 원리를 이용하여 탐지합니다.
- 회복 방법
- Kill
- 모든 데드락과 연관된 프로세스를 종료합니다.
- cycle 이 제거될 때까지 프로세스를 하나씩 종료합니다.
- 리소스를 많이 요구하는 것부터 종료합니다.
- Rollback
- safe state로 가서 프로세스를 재수행합니다.
- context 값(registers, stack...)이 보존되어있어야 재수행이 가능한데, 이 값들은 check point 에 저장해둡니다.
- 그러므로 check point에서만 재수행이 가능합니다.
- Kill
위 3가지 방법 중 가장 많이 사용되는 해결 방법은 3번째 방법이라고 합니다.
Backend Developer