# 교착상태

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

💡 여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가, 아무도 작업을 진행하지 못하는 상태이다. 즉, 교착상태는 공유자원 때문에 일어나는 현상이다. (특정 자원을 여러 프로세스가 공유하지 않는다면, 교착상태는 발생하지 않는다.)

### 교착상태의 예시

* 원형 탁자에 세 개의 음식과, 세 개의 포크, 세 명의 사람이 있다. 음식을 먹기 위해서는 반드시 포크 두 개를 사용해야한다.
* 이런 상황에서 세 명의 사람이 각자 포크를 하나씩 들어서 아무도 음식을 먹지 못하는 상태를 교착상태라고 한다.

### 교착상태의 필요조건

💡 필요 조건 중 한 가지라도 충족되지 않으면, 교착상태는 발생하지 않는다. 이에 필요 조건을 활용해 교착상태를 “예방”하려고 하였으나, 제약이 많고 비효율적이었다. 이에 교착상태에 빠진 후 해결하는 방법을 사용하게 되었다.

1. 상호배제
   * 어떤 프로세스가 하나의 리소스를 점유했다면, 다른 프로세스와 공유할 수 없다.

     (내가 집은 포크는 다른 사람이 쓸 수 없다)
2. 비선점
   * 프로세스 A가 자원을 점유했을 때, 프로세스 B가 해당 자원을 뺏을 수 없다.

     (내가 먼저 든 포크는, 다른 사람이 뺏어갈 수 없다)
3. 점유와 대기
   * 프로세스가 리소스A를 가진 상황에서, 또 다른 리소스B를 기다리는 상태여야한다.

     (하나의 포크가 더 필요한 상황)
4. 원형 대기
   * 점유와 대기를 하는 프로세스들이 원형을 이루고 있어야한다.

     (서로가 서로의 포크를 원하고 있어야한다.)

***

### 교착상태의 해결 방법

1. 교착상태의 예방
2. 교착상태 검출 후 해결

### 교착상태 예방 (deadlock avoidance)

* 은행원 알고리즘 등을 사용하여 교착상태가 발생하지 않는 수준만 자원을 할당하는 방식이다.
  * 프로세스가 요청하는 프로세스의 수 뿐만 아니라, 최대 요청 수 및 운영체제가 가지고 있는 자원의 수를 비교하며 안정상태, 불안정상태로 분류한다.
  * 운영체제는 최대한 안정상태로 유지하고자 한다.
  * 불안정상태에 있더라도, 무조건 교착상태에 빠지는 것이 아니라 단순히 확률이 높아지는 것이다. (최대 요청개수를 요청하지 않을 가능성이 존재하기 때문이다) =
* 운영체제는 위 방법을 위해 다음과 같은 정보를 알고 있어야한다.

  * 시스템의 총 자원 (전체 자원의 수)
  * 프로세스의 최대 요구자원
  * 프로세스의 요구자원

  ⇒ 남은 자원을 가지고 교착상태에 빠지지 않을 수 있을지 판단하는것이다.
* 교착상태를 회피하기는 적절하지만, 오버헤드가 발생하므로 비싸고 비효율적이다. (불안정상태라고 항상 교착상태가 발생하는 것은 아니므로)

### 교착상태 검출 방법

💡 \*\*교착상태 해결 방법 :\*\* 일정 시점마다 체크포인트를 만들어 작업을 저장하고, 교착상태가 발생한다면 해당 체크포인트로 롤백하여 교착상태를 해결한다.

1. 가벼운 교착상태 검출
   * 타이머를 이용한다.
   * 프로세스가 일정시간동안 작업을 하지 않는다면, 교착상태라고 판단한다.
2. 무거운 교착상태 검출
   * 자원 할당 그래프를 이용한다.
   * 운영체제는 프로세스가 어떤 자원을 사용하는지, 요청하는지 확인하며, 해당 그래프에 순환구조가 생긴다면 교착상태를 일으킨 프로세스를 종료시킨다. (체크포인트로 롤백)
   * 해당 방법은 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야하는 오버헤드가 발생하지만, 가벼운 교착 상태 검출에서 발생하는 억울하게 종료되는 프로세스는 발생하지 않는다.