> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/operating-system/deadlock.md).

# Deadlock

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라고 한다. 만약 프로세스 A는 자원 a를 점유한 채 자원 b를 기다리고, 프로세스 B는 자원 b를 점유한 채 자원 a를 기다리는 상대방이 가진 자원을 기다리기만하다가 실행 한번 못하는 상황을 말한다.

#### 자원할당그래프(Resource Allocation Graph)

교착 상태를 표현하는 방법으로, 어떤 프로세스가 어떤 자원을 사용하고 기다리는지를 표현하는 그래프이다. 프로세스는 원으로, 자원의 종류는 사각형으로 표현하며, 사용할 수 있는 자원의 개수는 사각형 내에 점으로 표현한다. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시하고, 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

### 필요조건 4가지

* 상호배제: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우
* 점유와 대기: 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 경우
* 비선점: 해당 자원을 이용하는 프로세스의 작업이 끝나아만 비로소 이용할 수 있는, 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우
* 원형 대기: 자원 할당 그래프에서 프로세스들과 자원이 원의 형태를 이루는 경우\\

### **예방**

교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방식

* 상호 배제를 없애는 경우: 모든 자원을 공유 가능하게 만듬 -> 이론적으로만 가능하며 현실적으로 무리
* 점유와 대기를 없애는 경우: 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분함 -> 자원의 활용률이 낮아질 우려, 자원을 많이 사용하는 프로세스는 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기 어려움
* 비선점 조건을 없애는 경우: 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있게 만듬 -> 모든 자원이 선점 가능한 것이 아니므로 범용성이 떨어짐
* 원형 대기 조건을 없애는 경우: 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당(=식사하는 철학자 문제에서 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황) -> 수많은 자원에 번호를 붙이는 일은 어려우며, 각 자원에 어떤 번호를 붙이는지에 따라 자원의 활용률이 떨어질 수 있음

교착 상태의 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 발생!

### **회피**

교착 상태가 발생하지 않을 정도로만 조심하게 자원을 할당하는 방식

* 안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
* 안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태(안전 순서열대로 프로세스에 자원을 배분하여 교착 상태가 발생하지 않음)
* 불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상황(안전 순서열이 없음)
* Banker’s Algorithm: allocation, max, needs, available한 자원의 개수를 표로 나타내고, 가능한 프로세스 먼저 완료해 안전한 상태로 만들어주는 것이다. 모든 프로세스가 안전 상태로 완료되면 교착 상태가 발생하지 않으며, 불안전 상태가 있다면 교착 상태가 발생한다.

### **회복**

예방과 회피는 교착 상태 발생을 막기 위한 노력이라면, 이는 교착 상태 발생을 인정하고 사후에 조치하는 방식

* 선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
* 프로세스 강제 종료를 통한 회복: 교착 상태에 놓인 프로세스를 모두 강제 종료할 수 있고(프로세스들 작업 내용 잃음), 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있음(오버헤드 문제 발생)