[2019.06.28] Concurrency : Deadlock and Starvation

Deadlock : 두개 이상의 process가 자원을 기다리는 데 일어나는 충돌. 각자 자원을 가지고 있는 상태에서 다른 거 요청할 때 일어난다.

 - Reusable Resources : 한번에 하나의 프로세스에만 사용되며 그 사용으로 고갈되지 않는다. ex. Processor, I/O channels, main memory, semaphore ...
    예제. memory 공간에 200KB의 가용 공간이 있다. 
     P1에는 80KB 다음 60KB를 요구하는 statement가 있다. P1에서 80KB를 요구하는 statement를 실행하고 (남은 메모리 120) context switch 일어나서 P2를 실행한다. P2에는 70KB 다음 80KB를 요구하는 statement가 있다. 70KB를 할당해주고 (남은 메모리 50) 80 할당하려니 못해주니까 P2는 blocked queue로 들어간다. 그리고 다시 P1으로 왔지만 여기도 60을 할당하지 못한다. 그래서 P1도 blocked queue로 들어간다. P2는 P1의 80이 풀어지길, P1은 P2의 자원이 풀어지길 계속 기다린다.
 - Consumable Resources : 한번 소비하면 없어지는 자원 ex. Interrupts, signals, messages ...
    Receive message가 blocking되면 Deadlock 발생 -> 서로 상대방이 자신들에게 신호를 주길 기다리는 상황.

자원이 요구될 때는 process -> resource, 자원이 할당될 때는 resource -> process.

Deadlock의 발생조건 (동시에 만족되어야 함)
1. Mutual exlusion => 오로지 자원은 프로세스 하나에만 배정되어야 한다.
2. Hold-and-Wait
3. No preemption => 남의 자원을 뺏으면 안된다. 우선순위가 높은 프로세스여도 뺏으면 안된다. 우선순위는 오로지 CPU 자원만 뺏을 수 있다.
4. Circular Wait => P1 -> Resource a -> P2 -> Resource b -> P1 ... 이런식으로 요구, 할당 관계가 circular 하게 연결된 경우.

Deadlock 다루는 방법
1. deadlock 에 들어가지 않게끔 사전에 방지 => process가 4가지 조건을 충족하지 않도록 한다. OS 입장에성 일하는 것이다.
2. deadlock에 들어가 recover
3. 아무것도 하지말고 내버려두기 (OS가)

Deadlock 예방 => 4가지 조건을 깨트린다.
 Hold and Wait  X : 처음부터 한꺼번에 자원을 받게 한다. 하지만 너무 가지게 되어 자원 낭비가 된다.
 Circular Wait X : 자원에 일련의 순서를 매겨서 낮은 자원이 높은 것을 요구할 수 없게 하는 것

Deadlock 회피 : 알고리즘을 돌려 자원을 파악한다. deadlock을 발생시킬 문제가 있다면 시작하지 않는다. (banker's algorithm)

Deadlock 발견 후 전략 : 다 죽이거나 하나씩 죽여보자.