Deadlock(교착 상태)
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- I/O device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
- Request → Allocate → Use → Release (요청 → 할당 → 사용 → 반납)
Deadlock 발생의 4가지 조건(필요충분)
- Mutual Execlusive
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
- No preemption
- 자원을 빼앗을 수 없음
- Hold and Wait
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
- Circular Wait
- 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
- 그래프에 cycle이 없으면 deadlock이 아니다
- 그래프에 cycle이 있으면
- if only one instance per resource type then deadlock
- if several instances per resource type, possibility of deadlock
Deadlock 처리 방법
1. Deadlock Prevention
- Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립
- Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
- No Preemption
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 프로세스가 다시 시작
- state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용
- Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
→ Utilization 저하, Throughput 감소, starvation 문제
2. Deadlock Avoidance
- 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 할당.
-
Resource Allocation Graph Algorithm
-
점선(미래에 자원을 요청할 수 있음을 뜻함)에 해당하는 것을 통해 Cycle이 생기면 자원을 할당해주지 않는다.
- Deadlock의 위험성이 생기는 사이클이 아예 발생하지 않도록 한다.
-
-
Banker’s Algorithm
- 최대 요청을 해버리면 줄 수 있는 자원이 없기 때문에 이런 경우에는 자원을 할당해주지 않는다.
