Deadlock이란?

쓰레드 T1이 할당해달라 요청한 자원이 현재 남아있지 않다면(다른 쓰레드가 사용하고 있어서) 쓰레드 T1는 wait 상태가 된다.
이때, 이 쓰레드 T1이 요청했던 자원이 다른 wait 쓰레드에게 할당되어 있는 상태라면 쓰레드 T1은 영원히 wait 상태에서 변경되지 못한다.
이러한 상황이 데드락이다.

Deadlock의 발생 조건

데드락은 다음 네 가지 조건을 모두 만족해야 발생한다.
1. Mutual exclusion
2. Hold & wait
3. No preemption
4. Circular wait

데드락을 해결하는 방법은 다음 세 가지 중 하나다.
- 데드락이 발생하는 경우, 문제 상황을 무시하고 데드락이 시스템에서 발생한적이 없는 것처럼 행동한다.
- 데드락 상황을 예방, 회피하는 방법을 사용해서 시스템이 데드락에 절대 빠지지 않도록 한다.
- 시스템이 데드락 상황에 빠지는 것을 허용하되, 데드락 상황에 빠진 것을 감지하고 회복시킨다.

기본 아이디어는 데드락의 발생 조건들 중 하나라도 일어나지 않게 하는 것이다.
하지만 이 방법을 쓰게 되면 CPU 이용량, 처리량이 낮아진다.
Mutual exclusion이 일어나지 않게 하는 경우
- 하나의 자원을 여러 쓰레드가 사용할 수 있게 한다.
- 단, 동기화 문제가 일어날 수 있다.
Hold & wait이 일어나지 않게 하는 경우
- 쓰레드가 시작되기 전에 필요한 자원을 한꺼번에 할당해서 wait를 하지 못하게 한다.
No preemption이 일어나지 않게 하는 경우
- 시스템 내부적으로 정해놓은 우선순위에 따라 우선순위가 높은 쓰레드가 자원을 할당 받기를 request하는 경우 해당 자원을 뺏어서 할당한다.
Circular wait이 일어나지 않게 하는 경우
- 일정한 순서로 자원을 요청, 할당받을 수 있게 한다.

자원 할당 요청이 들어왔을 때, 자원을 할당해줘도 safe state를 유지할 수 있는지 확인하고 자원을 할당한다.
이 방식을 사용하기 위해서는 쓰레드가 실행 전에 자신이 실행되는 동안 필요한 모든 자원에 대한 정보를 사전에 제공해야한다.
safe state란 safe sequence가 존재하는 것이다.
safe sequence: 쓰레드의 sqeuncne <T1, T2, ..., Tn>이 있을 때, Ti의 자원 요청이 '가용 자원 + 모든 Pj (j < i)의 보유 자원'에 의해 충족되는 경우 sequence를 safe 하다고 말한다.
만약 시스템이 Safe state에 있으면 Deadlock이 발생하지 않는다. 하지만 Unsafe state에 있으면 Deadlock이 발생할 수 있다. 따라서, Deadlock Avoidance는 시스템이 Unsafe state에 들어가지 않는 것을 보장하는 것이다.
두 경우의 Avoidance 알고리즘이 있는데, 각 자원 타입마다 하나의 인스턴스가 존재하는 경우 자원 할당 그래프 알고리즘을 사용하고, 여러 인스턴스가 존재하는 경우 Banker's 알고리즘을 사용한다.

회복 방법에는 크게 두 가지가 있다.
1. 쓰레드 종료(termination)
2. Resource preemption
쓰레드 종료
- 데드락이 사라질 때까지 데드락에 연관된 쓰레드를 하나씩 종료시킨다.
- 또는, 데드락 상황에 연관된 모든 쓰레드를 한꺼번에 종료시킨다.
Resource preemption
- 데드락이 사라질 때까지 연관된 쓰레드에게서 자원을 뺏어서 요청한 다른 쓰레드에게 할당한다.