> For the complete documentation index, see [llms.txt](https://real-dev.gitbook.io/real-library/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://real-dev.gitbook.io/real-library/os_with_joonion/17-18-.-deadlock.md).

# 17\~18강. Deadlock

*2개 이상의 프로세스(혹은 쓰레드) 쌍이 서로가 점유한 자원을 계속 기다리는 상황*

#### 데드락이 발생하는 조건

* 데드락은 아래 조건들이 모두 만족될 때 발생한다.
* 상호배제 → 하나의 자원이 단 하나의 주체에 의해서만 점유될때
  * 모든 리소스를 공유 자원으로 둘 수 없기에 현실적으로 사용 불가
* 점유 대기 → 특정 리소스를 점유하고 계속 대기중
* 비선점 → 자원을 외부에서 뺏을 수 없음
* 원형 대기 → 자원에 대한 상호 참조가 발생하는 상황
  * lock ordering을 통해 어느정도 방지할 수 있지만 100%는 아니다.
  *

<br>

### 특징

* 자원 참조/할당 그래프에서 사이클이 없다면 따로 데드락이 발생하지 않지만, 사이클이 존재한다면 데드락이 발생할 수도 있다.

<br>

### Handling

* 데드락이 발생하지 않을 것이라고 치고 무시하기
* 데드락을 원천적으로 방지해버리기
  * 일반적인 시스템엔 적용되지 않고, 아주 고가의 시스템에 적용할 수도 있음
  * Multi Thread 환경으로 이뤄낸 이점들을 대부분 잃게되는 결과를 야기하게 됨. 따라서 원천 방지은 좋은 방법이 아니게 됨
* 데드락을 회피해버리기
  * 대표적인 사례가 은행권 알고리즘
* 데드락이 발생하도록 두고, 감지/회복 시스템을 구성 - 실질적으로 많이 사용됨
  * 데드락을 주기적으로 확인하여 이를 감지하는 시스템을 구성
  * 데드락 자체가 많이 일어나는 현상이 아니라서…
  * 데드락을 감지했을 때 정상화하기 위해선 두 가지 방법이 있는데,

1. 데드락을 일으킨 쓰레드 집합을 모두 Restart
2. 데드락 사이클에서 하나씩 쓰레드를 정지 시켜보기
3. Resource를 해소해버리기 - Victim을 선정하여 죽여버리기. → 단, 이 경우 기아가 발생할 수 있으므로 선정 횟수를 저장하여 계속 죽지 않도록 구성

<br>

### Deadlock 회피

#### Safe State

* 모든 리소스를 쓰레드에 할당할 수 있는 순서가 존재할 때.
  * 즉, 순서만 따르면 데드락을 피할 수 있는 상태
* 따라서 이 안전 구역에 계속 머무를 수 있도록 데드락 회피 전략을 구성한다.
* \*\*RAG - \*\*따라서 어떤 요청이 들어왔을 떄, 해당 요청이 안정 상태를 깨트릴 수 있다면 요청을 거부하고, 상태를 유지할 수 있을 때만 요청을 수락한다.

<br>

#### Bankers Algorithm

* RAG보다 훨씬 복잡하다.
* 쓰레드가 N개, 리소스가 M개
* Max : 앞으로 쓰레드가 요청할 최대 자원 수
* allcation: 이미 할당된 자원 수
* need: 앞으로 요청할 리소스

…

~~이정도면 내가 이해 못하고 넘어가는게 큰 죄악은 아닐거야…~~

* 결국 중요한 점은 정해진 순서대로 작업을 수행했을 때, 모든 작업을 종료할 때까지 특정 자원의 갯수가 0 이하로 내려가지 않는 작업순서를 고르거나, 존재하지 않을 때 요청을 기각한다면 데드락을 확실히 회피할 수 있다는 의미