[OS] DeadLock

What is DeadLock?

---

교착상태라고 하는 DeadLock은 두 개 이상의 프로세스(혹은 쓰레드)가 서로 끝나기를 기다리는 상태, 보충하자면 대기 상태로 들어간 프로세스들이 실행 상태로 변경 될 수 없을 경우

선생님이 철수랑 영희한테 청소를 시켰다.
철수는 청소도구함에서 빗자루를 챙기고, 영희는 쓰레받기를 챙겼다.
이제 청소를 시작하자.
철수가 빗자루질을 하고 그걸 담으려고 하는데 쓰레받기가 없다. 영희가 다 쓰길 기다려야겠네?라고 생각하며 기다린다.
영희는 영희대로 철수가 빗자루질을 다 해야 내가 청소를 마칠 수 있겠구나?라고 철수가 빗자루를 다 쓰길 기다린다. 쓰레받기를 손에 꼭 쥔 채 말이다.

Background of The DeadLock

---

           초기                                                         현재
  CPU하나에 프로세스 하나           🔜    CPU 하나에 프로세스 여러개(멀티프로세싱) 또는 프로세스 안의 여러 개의 쓰레드(멀티쓰레딩)

How Do DeadLock Occur?

---

1. Mutual Exclusion(뮤텍스 - 자원에 대한 동시 접근 불가, 상호 배제) - 한 번에 여러 프로세스가 동시에 한 자원에 접근을 막음
2. Hold and Wait(점유하고 기다리기, 점유 대기) - 접근해야하는 자원이 다른 프로세스가 접근 중일 경우 대기 상태로 빠짐
3. No Preemption(자원을 뺏어오지 못함, 비선점) - 다른 프로세스가 점유한 자원을 뺏어오지 못함
4. Circular Wait(순환 대기) - 철수&영희 예제
   
   

How To Solve DeadLock?

Prevention(예방)

---

위 4가지 조건이 충족해야 DeadLock이 발생하는데, 사전에 하나라도 발생하지 않도록 막는것
그러나, 이 방법은 자원이 낭비되는 경향이 있음(?)
성능이 나빠지거나, 다른 문제를 발생시킬 수 있는 여지가 있음

Avoidance(회피) - DeadLock이 발생하면 피해가는 방법

---

은행원 알고리즘(Banker’s Algorithm)

E.J.Dijkstra가 제안한 방법으로 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 DeadLock을 회피하는

Detection and Recovery(탐지 & 회복) - 자원 할당 그래프를 통해 DeadLock 탐지

---

[Detection] 자원 할당 그래프

자원을 요청할 때마다 자원 할당 그래프를 탐색하면 오버헤드가 발생함

• 프로세스 Pi로부터 자원 Rj로의 방향은 Pi → Rj로 표현하며 이것은 프로세스 Pi가 자원 Rj을 요청하는 것으로 자원 Rj을 기다리는 상태
• 자원 Rj로부터 프로세스 Pi로의 방향은 Rj → Pi로 표현하며 이것은 자원 Rj가 프로세스 Pi에 할당된 것을 의미

[Recovery]

DeadLock을 일으킨 프로세스를 종료시키거나, 할당된 자원을 해제

프로세스를 종료하는 방법

1. DeadLock의 프로세스 모두 중지
2. DeadLock이 없어질 때까지 한 프로세스씩 중지

자원을 선점하는 방법

1. DeadLock의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당, 해당 프로세스를 일시 정지 시키는 방법
2. 우선 순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점
   
   

Ignore(무시)

---

무시해도 괜찮을 확률로 DeadLock이 발생한다고 판단되면 무시함
그러나, 이 방법은 성능상 손해를 볼 수 있어서 안정성과 성능을 고려해야함

Reference

---

교착상태(deadlock)와 그 해결방안을 알아보자. :: webie's blog
[운영체제] 데드락, 교착상태 해결 (Dead lock)