[OS] 데드락 (Deadlock)

1. 데드락이란?

---

데드락이란 둘 이상의 프로세스 혹은 스레드가 서로 상대방의 작업이 끝나기를 기다려 결국 이러지도 저러지도 못하고 무한정 기다리고만 있는 상태를 말합니다. 동시에 접근하면 안되는 공유자원에 접근할때 스레드는 Lock 기법을 이용합니다. 그러고 공유 자원의 사용이 끝났을 때 UnLock을 하는데, UnLock을 하기 전 교착 상태가 발생해 UnLock을 영원히 하지 못하는 상태를 보고 이름을 데드락으로 지은게 아닌가 생각해봅니다.. 🤔

[그림 1] 데드락(Deadlock)

2. 데드락 발생 조건

---

데드락은 아래 4가지 조건이 모두 만족될 시 발생합니다.

1. 상호 배제 (Mutual Exclusion) - 공유 자원에 여러 프로세스가 동시에 접근할 수 없다.
2. 점유 상태로 대기 (Hold and Wait) - 자원을 가지고 있는 상태에서 다음 자원의 획득을 위해 대기한다.
3. 선점 불가 (Non Preemptive) - 다른 프로세스가 점유 중인 자원을 강제로 가져올 수 없다.
4. 순환성 대기 (Circle wait) - 둘 이상의 프로세스가 자원에 접근하기 위해 기다리는데, 이 관계에 사이클이 존재한다.

3. 데드락 해결 방법

---

데드락에 대해 4가지 종류의 해결 방안이 있습니다.

1. 예방 (Prevention)
   데드락이 발생하기 위해선 위의 발생 조건 4가지를 모두 만족해야 합니다. 다른 말로, 위 4가지 조건 중 하나라도 만족하지 않으면 발생하지 않습니다. 즉, 발생 조건 4가지 중 1가지를 불만족시킴으로써 데드락을 미리 예방하는 방법입니다.
   이 방법은 애플리케이션을 만드는 개발자의 몫입니다. (그러니까 앱이 데드락 안 걸리게 개발자가 코드 잘 짜야된다는 말이죠.. 😅 )
2. 회피 (Avoidance)
   프로세스가 자원을 요청하면 OS는 이 자원을 줬을 때 데드락이 발생하는지 여부를 확인한 후, 괜찮을 경우만 자원을 할당시킴으로써 문제 발생을 회피하는 전략입니다. 자원할당 그래프 알고리즘, 은행원 알고리즘 두 가지가 대표적입니다.
3. 회복 (Recovery)
   OS는 프로세스가 달라는 자원을 그냥 다 주고, 주기적으로 데드락에 걸렸는지 검사합니다. 이때, 데드락에 걸렸다면 이전 상태로 회복시키는 방법입니다. 데드락에 걸린 프로세스를 모두 중지하거나, 데드락이 해결될 때까지 프로세스를 하나씩 중지합니다.
   희생자 선택의 원칙: 최소 비용으로 프로세스를 중지시키는 방법을 찾기.
4. 무시 (Ignore)
   데드락을 해결하기 위한 비용이 데드락에 의해 발생하는 비용보다 더 클 때 무시해버리는 방법입니다.(해결 비용>데드락에 의한 비용)
   현대의 OS는 이 방법을 채택하기 때문에 개발자가 Prevention 방법을 통해 데드락이 발생하지 않도록 코드를 짜야합니다. 

4. 참고자료

---

[1] https://junsday.tistory.com/32

[2] https://namu.wiki/w/Deadlock

[3] https://jhnyang.tistory.com/4