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

# 데드락 (DeadLock, 교착 상태)

* 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
* 무한히 다음 자원을 기다리게 되는 상태
  * 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
* 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

<br>

### 주로 발생하는 경우

* 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
  * A 프로세스가 자원A 요청 → 동시에 자원A 사용 불가 한 상태 → A프로세스가 대기 상태로 들어감
  * 이때 `대기상태`로 들어간 프로세스들이 `실행상태`로 변경될 수 없을 때 교착 상태 발생

<br>

## 데드락 발생 조건

> 4가지 모두 성립해야 발생 (하나라도 성립하지 않을 경우 데드락 해결 가능)

<br>

#### ✔️ 상호 배제 (Mutual exclusion)

: 자원은 한번에 한 프로세스만 사용 가능

<br>

#### ✔️ 점유 대기 (Hold and wait)

: 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스 존재

<br>

#### ✔️ 비선점(No preemption)

: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없음

<br>

#### ✔️ 순환 대기(Circular wait)

: 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

\ <br>

## 데드락 처리

### ✔️ 예방(prevention)

> 교착 상태 발생 조건 중 하나를 제거하면서 해결

<br>

**방법**

* `상호배제 부정` : 여러 프로세스가 공유 자원 사용
  * 현실적으로 불가능
* `점유대기 부정` : 프로세스 실행전 모든 자원을 할당
  * 자원 낭비 발생
    * 필요하지 않은 순간에도 가지고 있음
  * 무한대기 현상 발생 가능
* `비선점 부정` : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
  * 현실적으로 불가능
* `순환대기 부정` : 자원에 고유번호 할당 후 순서대로 자원 요구
  * 자원들에게 순서 부여
  * 프로세스는 순서의 증가 방향으로만 자원 요청 가능
  * 자원 낭비 발생

<br>

**특징**

* 4개의 데드락 발생 필요 조건 중 하나를 제거한다면, 절대 발생하지 않음
* 심각한 자원 낭비 발생
* 비현실적

\ <br>

### ✔️ 회피(avoidance)

**개념**

* 시스템의 상태를 계속 감시
* 시스템이 데드락 상태가 될 가능성이 있는 자원 할당 요청 보류
* 시스템을 항상 `Safe state`로 유지
  * `Safe state` : 모든 프로세스가 정상적으로 종료 가능한 상태

<br>

**방법**

* `은행원 알고리즘 (Banker's algorithm)`
  * 다익스트라가 제안한 기법
  * 어떤 자원의 할당의 할당허용 여부를 결정하기 전, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 진행하여 `safe state`에 들 수 있는 여부 검사
  * 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
  * 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
  * 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

<br>

**특징**

* 데드락의 발생을 막을 수 있음
* 높은 오버헤드
  * 항상 시스템을 감시하고 있어야 함
* Safe state 유지를 위해 사용되지 않는 자원 존재
* 실용적이지 못함
  * 가정이 필요함
    * 프로세스, 자원 수 고정
    * 필요한 최대 자원 수를 알고 있음

\ <br>

### ✔️ 탐지(detection)

**개념**

* 데드락 방지를 위한 사전 작업을 하지 않음
  * 데드락 발생 가능
* 주기적으로 데드락 발생 확인
  * `시스템`이 데드락 상태인지 확인
  * 어떤 `프로세스`가 데드락 상태인지 확인
* `Resource Allocation Graph (RAG)` 사용

<br>

**Resource Allocation Graph (RAG)**

* 데드락 검출을 위해 사용
* 방향성(directed)을 가지고 이분 그래프(bipatite graph) 사용
* `Graph Reduction` 으로 데드락 판별
  * 주어진 RAG에서 edge를 하나씩 지워감
  * `Complete reduced` : 모든 edge가 제거 되었다면 데드락 X
  * `Irrducible` : 지울 수 없는 edge가 존재한다면 데드락 O
* RAG는 높은 오버헤드를 가짐
  * 주기적인 검사 필요로, 검사 주기에 영향을 받음
  * 노드 수가 많은 경우 오버헤드 증가

\ <br>

**데드락 회피(avoidance)와 탐지(detection)**

* 데드락 회피
  * 최악의 경우를 생각
    * 데드락이 일어날 경우를 고려하여 회피
  * 데드락이 발생하지 않음
* 데드락 탐지
  * 최선의 경우를 생각
    * 현재 상태만 고려해 데드락이 발생하는가를 파악
  * 데드락이 발생할 수 있음
  * 데드락 발생 시 Recovery과정이 필요

\ <br>

### ✔️ 복구(recovery)

**개념**

* 데드락을 검출한 후 해결하는 과정

**방법**

* `Process terminate`
  * 데드락 상태에 있는 프로세스를 종료시킴
  * 강제 종료된 프로세스는 이후 재시작 됨
  * 종료 방법
    1. 데드락의 원인이 되는 프로세스를 모두 종료
    2. 한번에 하나의 프로세스만 종료시키면서 데드락이 풀리는지 확인 (높은 오버헤드)
  * 종료시킬 프로세스 선택 요인
    1. 프로세스 우선순위
    2. 프로세스 수행 시간, 일을 끝마치기까지 남은 시간
    3. 프로세스가 점유하고있는 자원 타입과 양 (회복하기 쉬운 자원인지)
    4. 프로세스가 종료하기까지 남은 자원의 수
    5. 얼마나 많은 수의 프로세스를 같이 종료시켜야하는지
    6. 프로세스가 interactive인지 bath형태인지
* `Resource preemption`
  * 데드락 상태 해결을 위해 프로세스의 자원을 선점하는 방법
    1. 희생 프로세스 선정
       * 희생 비용을 최소화하기위해 어느 프로세스의 어떤 자원을 뺏을지 결정
    2. 롤백
       * 어떤 프로세스로부터 자원을 뺏어오면 자원을 뺏긴 프로세스는 나중에 safe state로 롤백하고 다시 재실행 해줘야함
       * 혹은 처음 상태로 되돌림
       * `Checkpoint-restart method`
         * 프로세스의 수행 중 특정 지점(check point)마다 context 저장
         * 롤백을 위해 사용
           * 프로세스 강제 종료 후, 가장 최근의 check point에서 재시작
    3. 기아현상
       * 선점횟수에 가중치를 부여해 선점이 많이된 프로세스에게 우선권을 줘 기아현상 방지

\
\ <br>

## Wait free 와 Lock free

> Wait-free와 Lock-free는 모두 멀티스레딩 환경에서 공유 자원에 대한 동시 접근을 처리하는 기술
>
> Wait-free는 모든 스레드가 동시에 진행될 수 있는 것에 비해, Lock-free는 일부 스레드가 블로킹될 가능성이 있지만, 구현이 더 쉽고 성능이 높은 경우가 많음.

<br>

**공통점**

* 스레드가 락을 획득하거나 해제하는 데 소비되는 시간이 줄어듦
* 락 경쟁으로 인한 병목 현상이 줄어들어 여러 스레드가 효율적으로 동시에 실행될 수 있음
* 무한 대기 상황을 방지함으로써 데드락 문제 해결

<br>

### Wait free

* 개념
  * 모든 스레드가 동시에 진행
  * 하나의 스레드가 멈춰도 다른 스레드는 계속 진행 가능
* 특징
  * 어떤 스레드도 블로킹되지 않음
* 단점
  * 구현이 복잡하고 어려움
    * 복잡성으로 인해 정확성을 증명하는 것이 어려움
  * Lock-Free에 비해 더 많은 오버헤드 발생 가능
* 장점
  * 모든 스레드가 한정된 시간 내에 진행 가능

<br>

### Lock free

* 개념
  * 항상 하나 이상의 스레드가 진행할 수 있음을 보장
* 특징
  * 공유 자원에 대한 동시 접근을 락 없이 원자적 연산으로 처리
* 단점
  * 일부 스레드가 블로킹될 가능성 있어 높은 지연시간 발생 가능
* 장점
  * 비교적 쉬운 구현
  * 하나 이상의 스레드가 진행 가능함을 보장
  * 스레드 간 상호작용 없이 안전하게 공유 자원 사용 가능