Deadlock
Deadlock이란 무엇일까? 우선 이런 그림을 생각해놓자
데드락이란 운영체제 또는 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로세스 또는 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황을 말한다.
전에 기아(Starvation)라는 상태와 비슷한 것 같은데...
Deadlock VS Starvation
Deadlock은 asleep상태에서 자원, Event를 기다리는데 일어날 가능성이 없음
Starvation은 ready상태에서 CPU를 기다리는 것 (우선순위에 밀려서)
자원의 분류
일반적 분류 : Hardware resource, Software resource
데드락 관점에서 자원을 바라보면...
- 선점 가능 여부에 따른 분류
- 할당 단위에 따른 분류
- 동시 사용 가능 여부에 따른 분류
- 재사용 가능 여부에 따른 분류
1. 선점 가능 여부에 따른 분류
Preemptible resources
선점 당한 후 돌아와도 문제가 발생하지 않는 자원
ex) Processor, Memory 등
Non - Preemptible resources
선점 당하면 이후 진행에 문제가 발생하는 자원
ex) disk drive 등
2. 할당 단위에 따른 분류
Total allocation resources
자원 전체를 프로세스에게 할당
ex) Processor, disk drive
Partitioned allocation resources
하나의 자원을 여러 조각으로 나누어 여러 프로세스들에게 할당
ex) Memory
3. 동시 사용 가능 여부에 따른 분류
Exclusive allocation resources
한 순간에 한 프로세스만 사용 가능한 자원
ex) Processor, disk drive, Memory
Shared allocation resources
여러 프로세스가 동시에 사용 가능한 자원
Program(sw), Shared data
4. 재사용 가능 여부에 따른 분류
SR
시스템 내에 항상 존재하는 자원
사용이 끝나면 다른 프로세스가 사용 가능
ex) Processor, disk drive, Memory, Program
CR
한 프로세스가 사용한 후에 사라지는 자원
ex) signal, message
Deadlock을 발생시킬 수 있는 자원의 형태
Non - Preemptible resources
-> 한번 할당받으면 끝날때까지 쓰기 떄문에 요청을 해도 못 주기 때문에 데드락 발생
Exclusive allocation resources
-> 나눠쓰는건(Shared allocation) 그냥 나눠쓰면 되는데
얘는 아님 -> 데드락 발생
SR(Serially reusable resources) / CR
할당 단위는 딱히 문제 없음
Deadlock 발생의 예
2개의 프로세스(P1, P2)
2개의 자원(R1, R2) 를 가지고 있다고 가정
P1이 R2 요청
P2가 R1 요청
이 상태에서
P1이 R1 요청 -> 아직 데드락 아님
P2가 R2 요청 -> 서로가진걸 요청 -> 데드락
Deadlock Model
- Graph Model
Node : 프로세스 노드(P1, P2), 자원 노드(R1, R2)
Edge :
Rj -> Pi : 자원 Rj이 프로세스 Pi에 할당됨
Pi -> Rj : 프로세스 Pi가 자원 Rj을 요청(대기중)
- State Transition Model
ex) 2개의 프로세스와 A type의 자원 2개(unit) 존재
프로세스는 한번에 자원 하나만 요청/반납 가능
Deadlock 발생 필요 조건
자원의 특성
1. Non - Preemptible resources
2. Exclusive allocation resources
프로세스의 특성
3. Hold and Wait : 자원을 하나 hold하고 다른 자원 요청
4. Circular wait
4가지 모두 성립해야 데드락 발생!!
Deadlock 해결 방법
Deadlock Prevention
4가지 모두 성립해야 데드락이 발생한다고 했으니 4가지 중 하나를 제거하면
데드락이 절대 발생하지 않는다!!
1. Non - Preemptible resources
2. Exclusive allocation resources
3. Hold and Wait
4. Circular wait
모든 자원을 공유 허용
Exclusive allocation resources 조건 제거
하지만 현실적으로 불가능하다.
모든 자원에 대해 선점 허용
Non - Preemptible resources 조건 제거
모든 자원에 대해 선점을 허용한다는 것 또한 현실적으로 불가능하다.
하지만 유사한 방법으로 프로세스가 할당 받을 수 없는 자원을 요청한 경우,
기존에 가지고 있던 자원을 모두 반납하고 작업 취소하는 방법이 있다.
심각한 자원 낭비가 발생하긴한다..
필요한 자원 한번에 모두 할당
Hold and Wait
필요한 자원 한번에 모두 할당하고 필요 없어져도 반납 X
자원 낭비 발생 -> 필요하지 않은 순간에도 가지고 있기 때문
무한 대기 현상 발생 가능
Circular wait 조건 제거
Total allocation을 일반화 한 방법
자원들에게 순서 부여
프로세스는 순서의 증가 방향으로만 자원 요청 가능 (Circular이 만들어질수없다.)
자원 낭비 발생
Prevention은 자원 낭비가 너무 심하고 비현실적이다...
Deadlock Avoidance
앞에서 Prevention은 너무 자원낭비가 심했다.
회피(Avoidance)방법을 알아보자.
Deadlock Avoidance은 시스템의 상태를 계속 감시한다.
Deadlock이 될 가능성이 있는 자원 할당 요청을 보류한다.
즉 시스템을 항상 safe state로 유지하는 방법이다.
Safe state
모든 프로세스가 정상적 종료 가능한 상태
Safe sequence가 존재 -> Deadlock 상태가 되지 않을 수 있음을 보장Unsafe state
Deadlock 상태가 될 가능성이 있음 (반드시 발생X)
Deadlock Avoidance 가정
- 프로세스의 수가 고정됨
- 자원의 종류와 수가 고정됨
- 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
- 프로세스는 자원을 사용 후 반드시 반납한다
-> Not practical 하긴 함 ㅎㅎ..
Deadlock Avoidance 알고리즘
1. Dijkstra's algorithm
Banker's algorithm
2. Habermann's algorithm
Dijkstra) Banker's algorithm
한 종류의 자원이 여러개, 시스템을 항상 safe state로 유지한다고 가정
예시1) 1 resource type R, 10 resource units, 3 processes
Max. Claim : 요구한 최대 자원의 수
Cur. Alloc : 현재 할당 받은 자원의 수
Additional Need : 추가로 필요한 자원의 수
쉽게 생각해서 내가 10만원을 가지고 있다.
친구 3명이 돈을 빌림
P1은 만원 빌렸고, 2만원이 더 필요함
P2는 5만원 빌렸고, 4만원이 더 필요함
P3는 2만원 빌렸고, 3만원이 더 필요함
나는 총 8만원을 빌려줬고 2만원이 남은 상태
친구들은 반드시 돈을 갚는 친구들임!!
남은 금액 빌려주는 순서는? P1 - P3 - P2
P1에게 빌려주면 3만원 돌려받음! 그럼 P3에게 빌려줄 수 있다.
P3에게 빌려주고 5만원 받으면 P2에게 빌려줄수있음!
이게 Safe sequence이다.
예시2) 1 resource type R, 10 resource units, 3 processes
아까와 동일한 상태에서 추가로 필요한 자원의 수만 달라졌다.
2만원 밖에 없기때문에 돈을 빌려줄수없음!!
이게 Unsafe sequence이다.
Dijkstra's algorithm
P1이 R하나를 요청 -> P1 - P3 - P2 순서로 빌려주면
Safe sequence 존재함
P2가 R 하나 요청 -> 남은 자원이 하나뿐이라 Unsafe sequence
즉, 어떤 상태에서 자원 요청이 들어왔을때 자원을 주었다고 "가정"해보고
Safe sequence가 있으면 OK 없으면 X
이게 Banker's algorithm
Habermann's algorithm
자원이 A, B, C 3개가 각각 10, 5, 7개 존재
5개의 Processes
A 3개, B 3개, C 2개 더 빌려줄 수 있음
P2 → P4 → P1 → P3 → P5 순서로 빌려주면 Safe sequence 존재
Banker's algorithm에서 자원의 개수만 늘어난게 Habermann's algorithm
Deadlock의 발생을 막을 수 있지만...
1. High overhead : 항상 시스템을 감시하고 있어야함
2. Low resource utilization : Safe state 유지를 위해, 사용되지않는 자원이 존재함
3. Not practical : 프로세스 수와 자원 수가 고정, 필요한 최대 자원 수를 알고있어야함
Deadlock Detection and Recovery
Deadlock Detection
Deadlock 방지를 위한 사전 작업 X 즉, 데드락이 발생해도 피하지 않음
주기적으로 Deadlock 발생 확인
✅ 시스템이 Deadlock 상태인가?
✅ 어떤 프로세스가 Deadlock 상태인가?
Resource Allocation Graph를 사용해서 Deadlock을 찾아냄
Resource Allocation Graph (RAG)
Deadlock 검출을 위해 사용
Directed(방향성), bipartite Graph
그래프는 "노드"와 "엣지"로 구성 G = (N, E)
Node
프로세스의 노드들(P1, P2, ... Pn)과 리소스 노드들(R1, R2, ... Rn)의 집합으로 구성
Edge
엣지는 Np와 Nr사이에만 존재
프로세스에서 리소스, 리소스에서 프로세스로만 연결 가능
• e = (Pi, Rj) : 자원 요청
예) P1 → R1 프로세스 : 프로세스 P1이 자원 R1을 요청중
• e = (Rj, Pi) : 자원 할당
예) R2 → P2 프로세스 : 자원 R2가 프로세스 P2에 할당됨
Rk : k type의 자원
Tk : Rk의 단위 자원 수
|(a, b)| : (a, b) edge의 수
RAG Example
Graph reduction
데드락을 쉽게 판단할수있는 알고리즘!!
주어진 RAG에서 edge를 하나씩 지워가는 방법이다.
Completely reduced → 다 지워짐, 데드락 X
Irreducible → 지울 수 없는 엣지 존재, 데드락 O
Unbloked process 엣지를 지운다.
→ 필요한 자원을 모두 할당 받을 수 있는 프로세스Graph reduction procedure
- Unblocked process에 연결 된 모든 edge wprj
- 더 이상 unblocked process가 없을 때 까지 1 반복
최종 Graph에서
• 모든 edge가 제거됨 → Completely reduced
• 일부 edge가 남음 → Irreducible
Graph reduction example 1
모든 엣지가 지워짐 → 데드락 X
Deadlock Avoidance VS Deadlock Detection
Deadlock Avoidance
• 최악의 경우를 생각
• 데드락이 발생하지 않음
Deadlock Detection
•최선의 경우를 생각
•Deadlock 발생 시 Recovery 과정이 필요
Deadlock Recovery
Deadlock을 검출 한 후 해결하는 과정
Deadlock Recovery Method
1. Process termination
• Deadlock 상태에 있는 프로세스를 종료 시킴
• 강제 종료 된 프로세스는 이후 재시작 됨
termination cost model
종료 시킬 deadlock 상태의 프로세스 선택
• 우선순위
• 종류
• 총 수행 시간
• 남은 수행 시간
• 종료 비용
...
2. Resouce preemption
• Deadlock 상태 해결을 위해 선점할 자원 선택
• 자원을 빼앗긴 프로세스는 강제 종료 됨
