7장 Deadlock

blocked 프로세스가 서로 필요로 하는 자원을 가지고 있을 때.

System Model
시스템은 자원(씨피유 사이클, 메모리 공간, I/O 디바이스 등)들로 이루어져 있다. 
각각의 자원은 여러개의 인스턴스가 있다.
프로세스가 한 자원 type의 인스턴스를 요구하면 그 타입의 어떤 인스턴스라도 그 요청을 수행할 수 있다.
자원을 사용하고 나서는 반드시 반환해야 한다.

Deadlock Characterization
네가지 조건이 동시에 발생했을 때 Deadlock이 발생할 수 있다.
1. Mutual exclusion(리소스가 여러 프로세스에 의해 공유될 수 없다.)
2. Hold and wait (하나 이상의 리소스를 가지고 있는 채로 다른 자원을 획득하기를 기다리는 것)
3. No preemption (중간에 리소스를 뺏기지 않는 것. 작업을 마치고 내놓는 것)
4. 기다리는 프로세스들이 사이클을 이룰 때. p0는 p1이 가지고 있는 리소스를 원하고, p1은 p2, p2는 p0.

일반적으로 사이클이 없으면 데드락이 없다. 사이클이 있으면 데드락 가능성이 있다. 하지만 있어도 반드시는 아니다. 하나의 자원 type에 여러개 인스턴스가 있는 경우 데드락이 생기지 않을 수도 있다.

Methods for Handling Deadlocks
시스템이 데드락 상태에 빠지는 것을 허용하지 않도록 하는 것.
시스템이 데드락 상태에 빠지는 것을 허용하나, 그것을 감지하고 회복하는 것.
데드락 상태에 빠지면 그 문제를 무시하고 데드락이 발생하지 않은 것처럼 행동하는 것.

Deadlock Prevention

4가지 데드락 발생 조건 중에 최소한 하나라도 성립하지 않게 하기.
mutual exclusion
read-only 파일은 프로세스 여러개가 동시에 접근해도 상관없다.
하지만 원래 공유가 불가능한 자원들이 있다.

Hold and wait
프로세스가 어떤 자원을 요청하기 전, 아무 자원도 가지지 않은 상태가 되도록 한다.
낮은 자원 이용률, starvation 가능성이 있다.

No preemption
프로세스가 어떤 자원을 요청했으나 받지 못하고 기다려야 한다면 지금 가진 모든 자원을 버리고 wait 상태가 된다.
모든 필요한 자원을 얻었을 때 다시 시작된다.

Circular wait
모든 자원에 순서를 매긴다. 높은 숫자의 자원을 가지고 있는 프로세스가 낮은 숫자의 자원을 가지지 못하도록 한다.

Deadlock Avoidance

어떤 리소스를 할당하고 해제하는지 순서를 안다면, 즉 리소스가 어떻게 요청되는지 추가적인 정보를 안다면
미래에 발생할 수 있는 deadlock문제를 사전에 방지할 수 있다.
가장 간단하고 효과적인 방법은 프로세스가  각 type별 최대로 필요한 리소스의 수를 정하는 것이다.
리소스 할당 상태를 조사하여 circular-wait condition이 발생하는지를 알아본다.
리소스 할당 상태는 이용가능한 자원의 수, 할당된 자원의 수, 프로세스의 최대 요구 자원의 수로 정의된다.

Safe state
데드락을 피하도록 자원을 할당받는 프로세스순서 정하기.
이러한 순서를 safe sequence라고 하고
safe sequence에서 한 프로세스가 요구하는 리소스가 (1)현재 이용가능한 리소스와 (2)이전 순서의 프로세스가 가진 리소스의 합보다 작으면 그 프로세스는 요구하는 리소스를 모두 받을 수 있음을 의미한다. 이전 순서의 프로세스는 작업이 끝난뒤 리소스를 반환할 것이기 때문이다.

시스템이 safe state에 있으면 데드락이 발생하지 않을 것이고, unsafe state에 있으면 데드락 가능성이 있지만 반드시 발생하지는 않는다.
따라서 Deadlock Avoidance는 시스템을 항상 safe state한 상태로 유지시키는 것이다.

Resource-Allocation Graph Algorithm
리소스와 프로세스의 관계를 그래프로 표현.

출처 : vidyaprasar.dei.ac.in

점선은 프로세스가 자원을 요청한 상태이다.
할당할 때 cycle이 되는지 조사한다.

Banker's Algorithm
각 리소스 타입마다 인스턴스가 여러개 일때의 알고리즘.
1. 각 프로세스는 각 리소스 타입별로 최대 필요한 인스턴스 수를 가지고 있어야 한다.
2. 이 숫자는 시스템의 전체 자원의 수를 넘지 않아야 한다.
3. 프로세스가 리소스들을 요청할 때, 시스템은 이 자원 할당이 시스템을 safe state하게 하는지 조사해야 한다.
4. 조사 결과 safe state이면 할당
5. unsafe state이면 다른 프로세스가 자원을 방출할 때까지 기다린다.

Safety Algorithm
모든 프로세스의 현재 필요한 자원을 현재 이용가능한 자원으로 처리할 수 있는지 조사.
Dijktra

Deadlock Detection

시스템이 데드락 prevention이나 avoidance한 알고리즘을 제공하지 않으면 detection이라도 제공해야.
wait-for graph

출처 : academic.udayton.edu
resource allocation graph에서 리소스 타입만 제거한 것.
사이클이 생기는지 조사.

Detection algorithm
모든 프로세스에 대해서 현재 이용가능한 자원으로 요청된 자원을 처리할 수 있는지 조사.
하나라도 처리못하는 프로세스가 있으면 그 프로세스는 데드락에 빠진 것. 다른 프로세스들이 완료해서 충분한 리소스를 반환해서 데드락이 깨질 때까지 대기상태에 들어감.
데드락이 자주 발생하면 자주 detection 알고리즘을 수행해 주어야 한다.

자원 할당 요청이 들어오고 즉시 처리할 수 없는 경우마다 이 알고리즘이 호출 될 수 있다.
성능우려 때문에 한시간마다 한번씩, 또는 CPU 이용률이 40퍼센트 이하로 떨어졌을 때 호출하는 방법이 있다.

Recovery from Deadlock 
모든 deadlock 된 프로세스들을 죽이는 방법 - 많은 비용.
사이클이 제거될 때까지 한번에 한 프로세스만 죽이기 - 하나 죽일때마다 detection 알고리즘 호출해야 되서 성능 저하. 그리고 죽이는 것도 어렵다. 그 프로세스가 파일을 수정중이었다면?
그래서 이 방법을 쓴다면 잘 선택하는 것이 중요. 최소비용을 선택
프로세스 우선순위, 프로세스 진행율, 얼마나 많은 혹은 어떤 타입의 리소스가 사용되었는지, 완료하려면 얼마나 많은 리소스가 필요한지, 얼마나 많은 프로세스가 종료될 것인지,  프로세스가 interactive인지 batch인지.
Recovery의 세가지 이슈
죽일 프로세스 선택, Rollback(현재 실행중인 프로세스들의 상태 정보를 다 기억해줘야 되는지), Starvation(한 프로세스만 자꾸 리소스를 뺏겨서 victim이 될 때)