운영체제 - 데드락(Dead Lock)
Definition
1. Dead Lock
- 자원을 공유하는 프로세스들이 서로가 원하는 자원을 분점하고 있기 때문에 프로세스가 더 진행하지 못하는 현상.
- CPU 낭비는 없음
2. Live Lock
- 자원을 계속적으로 사용하지만 아무런 생산적인 일을 하지 못하는 상황
- 예를들어, 라우터에 지나치게 많은 패킷(packet)이 도착하여 큐(queue)가 꽉 차 기존의 old packet를 지속적으로 버리게 되는 상황
- 혹은 지나치게 많은 interrupt request로 인한 실질적인 job이 수행될 수 없는 상황
* Interrupt Coalescing
- Interrupt 발생 빈도를 줄이기 위해서, 여러 번의 입력을 모아서 한번에 interrupt를 발생시키거나 일정 시간마다 한번씩 interrupt를 발생시키는 기법
3. Indefinite postponement
- 절대 일어날 수 없는 이벤트(event)를 기다리는 상황
Resource Allocation Graph
1. 사각형 : 프로세스(process)
2. 원 : 자원(resource)
3. 실선(resource->process) : 이미 프로세스에 할당된 자원
4. 점선(process->resource) : 프로세스가 그 자원을 원하는 상황
- 그래프에 cycle이 존재하면 deadlock이 있는 것이다.
- cycle이 존재하는 경우 deadlock이 발생한 상황임을 알 수 있음. 단, 위 상황에서는 자원을 관리하는 Semaphore가 Binary Semaphore인 경우에만 발생.
데드락(Dead lock)의 필요 조건
1. Mutual exclusion (limited access)
- Resources cannot be shared
- 한개의 자원이 점유가 되면 절대 공유가 안 됨.
2. No preemption
- Once given, a resource cannot be taken away
- 상대방이 자원을 원해도 절대 양보하지 않음
3. Hold and wait (multiple independent requests)
- Processes don’t ask for resources all at once
- 프로세스가 다른 자원을 원할 때도 기존에 가지고 있는 자원을 계속 hold 시킴.
4. Circular wait
- There is a circularity in the graph of who has what and who wants what
- Resource Allocation Graph의 cycle과 같은 상황
데드락 해결책
1. Dead Lock Prevention(=Avoidance)
- 데드락 상황이 애초에 발생하지 않게 미리미리 예방하는 방법
- 예방하는 데 CPU자원이 매우 많이 필요
- ex. Banker's algorithm
2. Dead Lock Detection and Recovery
- 데드락 상황이 발생하지 않게끔 예방하지는 않음
- 단, 데드락이 발생하면 데드락이 발생했다는 사실을 탐지(detection)하고 그에 따른 조치(Recovery)를 취함