[OS 기초] Deadlock

# Race condition의 방지

- 하드웨어적 매커니즘 : 인터럽트 enable/disable, 버스의 트랜잭션 기법들

- 소프트웨어 매커니즘 : semaphores, monitors

# Deadlock

: 여러 프로세스들이 concurrent하게 수행할 때 발생. 

<해결방법>

- prevention. 예방하는 방법

- detection and recovery. 증상을 최소화하는 방법

* Resource Allocation Graph : 프로세스와 자원사이의 관계를 나타내는데 사용하는 자료구조

box : 프로세스

rounded box : 자원

자원-> 프로세스 : 자원이 프로세스에 할당

프로세스->자원 : 프로세스가 자원을 사용하기를원하는 상황

- Resource Allocation Graph를 이용한 Deadlock 탐지 : Cycle이 존재하는 경우 Deadlock이 발생한 상황임을 알 수 있음.
        단, 자원을 관리하는 세마포어가 바이너리 세마포어인 경우만 반드시 Deadlock 발생

# Deadlock의 사촌들

- Deadlock : 리소스를 공유하는 프로세스들이 서로가 원하는 리소스를 분점하고 있기 때문에 더 진행하지 못하는 것. 리소스를 기다리면서 wating상태에 빠지므로 CPU 관점에서의 리소스를 낭비하는 경우는 없음. 

- Livelock : CPU 리소스를 계속적으로 사용하지만 아무일도 하지 못하는 상황   

ex. router나 DB Server등에서의 Receive Live Lock. 

* interrupt coalescing : 인터럽트발생 빈도를 줄이기 위해 여러번의 입력을 모아하서 한번에 인터럽트를 발생시키거나 일정 시간마다 한번씩 인터럽트를 발생

* 패킷의 우선순위 매기기

- Indefinite postponement : 프로세스 하나 혼자서 주로 발생. 절대 일어날 수 없는 이벤트를 기다리는 상황

# Deadlock의 발생

<필요조건 4가지>

1. Mutual exclusion : 리소스를 공유할 수 없음

2. No preemption : preemption(자신의 리소스를 포기하고 리소스를 전달해 주기)을 할수없는 상황

=> 1,2번은 resource의 특징이므로 어쩔 수 없음

3. Hold and wait : 자신의 리소스는 점유하고 있으면서 다른 리소스를 또 원하는 상황

=> 프로세스가 수행을 시작할 때 해당 프로세스가 필요한 리소스를 한번에 다 받게 하기

=> 현실성이 없음. 어떤 프로세스가 어떤 리소스를 얼마나 필요로 할 지 프로그램 수행전 알기가 어렵고, 안다고 하더라도 비 경제적 임(한번에 많이 할당)

4. Circular wait : 원하는 리소스의 패턴이 Circular하는 상황

=> 역시나 비현실적임. 프로세스들이 사용할 수 있는 시스템의 리소스들을 넘버링하여 한방향으로 리소스를 할당시킴

 

# Prevention and Detection

1. Banker's Algorithm

: 어떤 프로세스들이 리소스를 점유하고 있을 때의 상태를 2가지로 분류

- safe state : 시스템이 Deadlock 상태에 빠지지 앟는 상태

- unsafe state : 시스템이 Deadlock 상태에 빠질 가능성이 있는 상태

ex. 1997년 12월 24일 우리나라의 IMF 상황

- 새로운 프로세스는 자신의 최대의 resource need를 선언해야 함 (단점이기도 함)

- 어떤 프로세스가 리소스를 요청하면 safe state와 unsafe state를 판단하여 리소스를 할당하거나 wait state로 진행

- Notations

* n : 시스템에 존재하는 프로세스의 갯수

* m : 시스템에 존재하는 리소스의 갯수

- Available[1:m] : 어떤 리소스 i가 몇개있는지 표현

- Max[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 최대 몇개까지 원하는지 표현

- Allocation[1:n, 1:m] : 프로세스 i가 j타입의 리소스를 몇개 받아서 있는지를 표현

- Need[1:n, 1:m] : Max - Allocation. 향후 몇개를 더 할당 받을 수 있는지를 표현

- vectors X, Y

- work array : 어떤 자원의 중간 계산 결과를 저장하고 있는 array

- finish array : 어떤 프로세스가 종료되었는지를 나타내는 boolean array

- Safety Check

step 1. work에 현재 사용가능한 리소스를 asign. finish array의 모든 값을 false로 설정(아직 어떤 프로세스도 끝나지 않음을 의미)

step 2. 현재 수행을 끝내지 않았고, 최대로 필요로하는 리소스를 모두 만족해 줄 수 있는 어떤 프로세스 i를 찾음

step 3. 프로세스를 terminate시키고 finish로 리소스를 반납하는 과정을 모든 해당되는 프로세스만큼 반복하여 수행

step 4. 모든 finish[] 엔트리 값이 true가 되면 끝

- Safety Check를 사용해서 resource grant을 수행하는 방법

step 1. Request array에 각 프로세스의 새로 요청하는 request를 기록

step 2. 어떤 프로세스의 request가 Maximum보다 더 많은 요구를 하게되면 요청을 받아주지 않음

step 3. Maximum 값보다 적은 상태라면 일단 satety check 알고리즘을 수행한 후 safe하면 요청을 들어줌 

=> banker's algorithm은 satety하게 구현하며 deadlock avoidance를 수행. 

=> 프로세스가 maximum request를 각 타입별로 관리해야하고 그걸 수행하기 위해 비용이 비싼 의사결정이 필요하고 deadlock avoidance를 할 수 없는 상황도 있음.

=> Deadlock Detection!!

# Banker's Algorithm을 변형

step 1. 현재 리소스 상태가 주어지면 termination이 가능한 프로세스들을 termination시키기

step 2. 남은 리소스들을 보고, 데드락 때문에 종료되지 못한 리소스들을 발견할 수 있음  

* Deadlock Detection 기법이 큰 주목을 받지 못한 이유

Personal Computer에서는 사용자들이 임의로 종료시키기 때문에 큰 문제가 되지않음.

Server에서는 일종의 watch dog을 사용하여 termination 시킴

* 경우에 따라서는 termination이 비용이 굉장히 비싼 경우가 있음

이럴때, CPR(check point resume)이라는 응용이 동작 중에 일정 시간 간격으로 응용의 모든 상태를 디스크에 저장하고 문제가 발생했을 때 저장된 응용의 상태를 사용해 응용의 수행을 재개하는 기법