Deadlocks

Deadlock

데드락은 4가지 조건을 만족시킬 때 발생한다.

 

Mutual Exclusion(상호배제)

한 프로세스 자원을 얻으면 해당 자원을 독점적으로 사용한다.

 

No preemption (비선점)

자원을 가지면 빼앗기지 않음 

 

Hold and wait

다른 자원을 점유하기 위해 기다릴 때는 내가 들고 있는 자원을 점유한 상태에서 기다린다.

 

Circular wait

자원을 기다리는 프로세스끼리 참조순환이 되어야만함

사각형R은 자원, 동그라미P는 프로세스이다. 작은 점은 자원의 인스턴스 갯수를 의미한다. 화살표를 따라갔을 때 만약 사이클이 형성이 안된다면 데드락이 아니다. 만약 사이클이 있고, 자원당 인스턴스가 하나만 있으면 데드락, 자원당 인스턴스가 여러개라면 데드락 가능성이 있는 상태이다.(만약 자원당 인스턴스수만큼 사이클 횟수가 돈다면 데드락)

---

데드락 해결방법

데드락을 해결하는데는 크게 4가지 방법이 있다. 

 

Deadlock Prevention

앞서 배웠던 4가지 조건 중 어느하나가 발생하지 못하게하여 데드락을 미리 막는 것

-> 프로세스가 자원을 요청할 때(기다릴 떄)는 다른 어떤 자원도 가지지 못하게 한다.

-> 모든 자원에 할당순서를 매겨 정해진 순서대로 자원을 할당하면 사이클이 생기지 않는다. 

 

Deadlock Avoidance

프로세스가 시작될 때 해당 프로세스가 사용할 자원의 정보를 미리 알고 있다고 가정하고 자원할당하기 전에 데드락 발생여부를 확인뒤 할당. 할당 자원이 한 개라면 앞선 그래프를 통해, 자원이 2개 이상이면 Banker's Algorithm(자원이 남아돔에도 할당하지 않는 문제 발생가능)을 통해 데드락을 피해간다. Deadlock avoidance 가 되면 언제나 데드락으로부터 세이프한 환경을 보장할 수 있으나 자원이 남아돔에도 혹시모를 데드락 상태를 방지하기 위해 할당하지 않아 리소스가 낭비된다는 단점이 있다.

 

Deadlock Detection and recovery

데드락은 드물게 발생하는 문제이기 때문에 앞선 방법은 낭비가 너무 심했다. 따라서 일단 데드락이 발생하면 빠르게 발견해서 복구시키는 방법이 고안되었다. 즉 데드락 발생은 허용하되 그에대한 detection루틴을 두어 빠르게 발견후 복구라는 메커니즘을 사용하는 것이다. 복구할 때는 데드락 연관 프로세스를 모두 죽인후 다시 실행시키는 방법 혹은 데드락에 연관된 프로세스를 하나씩 죽여보는 방법이 있다.

 

Deadlock Ignorance

하지만 앞서 데드락 디텍션도 조금만 늦게 발견하더라도 버벅임 현상이 나타날 수 있다. 따라서 마지막 방법으로는 애초에 데드락이 발생하지 않는다 가정하는 것이다. OS단에서는 데드락에 관여하지 않고 만약 데드락이 발생하면 사용자에게 직접 프로세스를 죽일 수 있는 안내창을 띄워 해결한다. 현대 OS(유닉스, 윈도우등)가 이 방법을 채택하고 있다.

---

https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f

반효경 [운영체제] 17. Deadlocks 2