운영체제 정리 - Deadlocks
System Model
- 시스템은 한정된 자원으로 이루어져 있다. ex) CPU cycles, files, memory space, I/O devices…
- 이러한 Resorce Type을 R로 나타내고 R에 해당하는 인스턴스를 W라 한다 ex) 4개의 CPU가 시스템안에 있으면, CPU Type의 인스턴스가 4개임
- 스레드는 request, use, release를 통해 리소스를 사용하고 request와 release는 시스템 콜을 이용한다.
Deadlock with Multithreaded Applications
Deadlock은 Multithreaded에서만?
- deadlock이 multithreaded환경에서만 발생하는지가 궁금해져서 ChatGPT한테 물어보았다. 
스레드 범위가 아닌 프로세스단에서 발생하기도 하고 앞에서 보았던 프로세스간 통신에서 blocking방법을 써도 일어날 수 있는 것 같다. 또는 네트워크 환경에서도 일어날 수 있다고 한다.
Multithreaded Application의 Deadlock 예시
- 위 프로그램의 코드가 1->2->3->4 순서대로 실행 될 경우 왼쪽 코드를 실행하는 스레드는 오른쪽 코드를 실행하는 스레드에서 점유하고 있는 second_mutex에 의해 무한 대기
- 오른쪽 코드를 실행하는 스레드는 왼쪽 코드를 실행하는 스레드가 first_mutex를 통해 점유하고 있어 무한대기
- 항상 이런 deadlock이 일어나는 것은 아니지만 일어날 가능성이 존재
Deadlock Characterization
4가지 필요 조건
- 아래 네 가지 특성이 모두 충족될 때 deadlock이 생길 수 있다.
Mutual Exclusion: 한번에 하나의 스레드만 자원을 사용
Hold and wait: 스레드가 하나를 점유하는 동시에 자원요청을 하고 기다림
No Preemption: 선점이 불가능
Circular Wait: 점유와 요청이 하나의 순환 구조를 이룸
Resource-Allocation Graph
그래프로는 아래와 같이 나타낸다 
그래프의 3가지 예시
-> cycle이 존재하고 자원이 충분하지 않으면 Deadlock
Deadlock을 다루는 방법
- 대부분의 시스템에서는 비용이 많이 들기 때문에 deadlock을 예방하지는 않는다
Deadlock prevention: 4가지 특성 중 하나를 근본적으로 차단
Deadlock avoidance: 미래를 예측하여 deadlock이 일어날 상황을 차단
Deadlock detection: 현재 상태를 보고 deadlock을 판단
Recovery from Deadlock: 빠르게 deadlock으로 부터 회복
Deadlock Prevention
- 4가지 특성 중 Circular Wait를 제외하고 근본적으로 차단하기 어려움(비용, 복잡성 증가)
- Circular Wait를 Lock Ordering방법으로 차단하고 Deadlock을 방지할 수 있음
- 하지만 Lock order가 프로그램의 동작에 따라 동적으로 변경되는 상황이라면 이를 적용하기는 어렵다.
계좌이체 시스템에서는 lock을 걸 순서가 유동적이기 때문에 Lock ordering의 적용이 어려움
Deadlock Avoidance
Safe state
- ** unsafe state일 때 deadlock이 발생할 수 있다.**
- 리소스 타입에 대해 Single instance이면 그래프를 통해 예측하고 safe state로 유지할 수 있다.
- Multiple instances이면 banker’s algorithm을 통해 자원 할당 상태를 예측하고 safe state로 유지할 수 있다.
Resouce-Allocation Graph Algorithm
claim edge: 미래에 T가 R에 요청을 할 것을 나타냄, R이 T에 할당될 때 safe여부에 따라 요청을 수락/거부 할 수 있음
- T1과 T2간의 circular wait가 생길 수 있으므로 unsafe state
방법: 각 스레드에 필요한 자원을 추가로 할당하여 스레드의 작업을 끝내 사용할 수 있는 작업을 점점 늘린다.
- 처음에 Work가 3 3 2 이므로 필요한 자원을 충족시켜 줄 수 있는 스레드는 T1, T3
- 임의로 T1에 자원을 할당해주고 작업이 끝나면 사용할 수 있는 자원은 5(3+2) 3 2
- 같은 방법으로 T3, T4, T2, T0순으로 할당
만약 Need를 충족시켜 줄 Work가 어떤 할당 순서로도 존재하지 않는다면 Unsafe 한 것이다.
여기서 추가적으로 어떤 스레드가 자원을 요청할 때 이것이 safe 한지를 판단하면 된다.
예시를 하나만 들자면 만약 T1이 (1,0,2)를 요청했을 때 
- (1,0,2) 만큼 work에서 빼주고 T1의 Allocation에는 더해준다.
- 그 상태에서 다시 순서가 존재하는지를 판단한다
결론적으로 unsafe가 되는 상황은
- 요청자체가 work를 넘을 때
- 요청이 work를 넘지 않지만 모두 할당해줄 수 있는 순서가 존재하지 않을 때
이런 상황에는 할당을 해주지 않는 것이 Banker’s Algorithm을 이용한 deadlock avoidance다
Deadlock Detection
- detection도 avoidance와 비슷하게 그래프를 이용한 방법과 현재의 자원할당 상태를 이용하는 방법이 있다
detection은 현재를 기준으로 하기 때문에 미래에 필요할 Need가 아닌 현재의 Request를 기준으로 Work를 계산하여 Deadlock을 탐지한다. 위의 경우에는 deadlock이 탐지되지 않는다.
위처럼 T2에 c자원에 1이 추가 요청된 경우에는 모든 요청에 할당해 줄 수 있는 순서가 없어 자원이 더 필요하지 않은 T0를 제외한 T1,T2,T3,T4에서 Deadlock이 일어난다.