1. 교착상태(DeadLock)

---

교착상태란 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하여 무한적 기다리게 되는 현상을 교착상태(DeadLock) 이라고 합니다.

여러개의 작업이 동시에 실행되는 멀티 프로세스, 멀티 스레드 프로그래밍 환경에서 발생할 수 있는 이슈입니다.

교착상태를 쉽게 설명할 수 있는 쉬운 '식사하는 철학자들' 예제를 통해 알아볼 수 있습니다.

1. 왼쪽 포크가 사용가능해질 때까지 생각을 하다가, 사용이 가능해지면 바로 왼쪽 포크를 집어든다.
2. 오른쪽 포크가 사용가능해질 때까지 생각을 하다가, 사용이 가능해지면 바로 오른쪽 포크를 집어든다.
3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사한다.
4. 오른쪽 포크를 내려놓는다.
5. 왼쪽 포크를 내려놓는다.
6. 다시 1번으로 돌아간다.

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 집어든다면, 모든 철학자들이 자기 오른쪽 포크가 사용 가능해 질때까지 기다리게 됩니다. 그렇게 되면 모든 철학자들은 영원히 오른쪽 포크를 사용할 수 있을 때 까지 기다리게 되는데, 이것이 바로 교착상태 입니다.

2. 교착상태 발생 조건

---

교착상태는 아래 4가지 조건이 모두 만족하게 되면 발생합니다.

1. 상호 배제 (Mutual Exclusion)

프로세스 간의 공유 자원은 한 번에 한 개의 프로세스에만 할당 됩니다. 여러 프로세스가 동시에 공유 자원을 사용할 수 없습니다.

2. 점유와 대기 (Hold and Wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가적으로 점유하기 위해 대기하는 상태입니다.
프로세스 A가 자원 a를 점유하고 있고 b를 사용하기 위해 대기중입니다. 이 때, 다른 프로세스 C는 자원 a를 사용하기 위해 대기할 경우 프로세스 A의 작업이 끝날 때까지 대기하게 됩니다.

3. 비선점 - 선취 불가능 (Non-preemption)

프로세스가 어떤 자원을 점유하고 있을 때, 이 자원을 다른 프로세스가 강제로 빼앗을 수 없습니다.

4. 순환 대기 (Circular Wait)

공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있다고 할 때, 자신에게 할당된 자원을 점유하고 있으면서 앞이나 뒤에 있는 프로세스의 자원을 요구하는 상황입니다.

한 마디로 두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재하는 경우입니다.

3. 교착상태 해결하기

---

1. 상호 배제를 제거하는 기법
   여러 프로세스가 동시에 공유자원을 사용할 수 있도록 한다.

   공유 자원 중 대부분이 한 번에 한 프로세스에만 사용할 수 있기 때문에 상호 
   배제조건은 제거하기 어렵다

2. 점유 및 대기 제거
   프로세스가 실행되기 전에 모든 자원을 할당하여 프로세스 대기를 제거하거나 어떠한 자원도 점유하고 있지 않은 상태에서만 자원을 요구하도록 한다.

   한 번에 모든 자원을 요구하고 할당받는 것은 비효율적이며 기아현상(Starvatio
   n) 이 발생할 수 있다.

3. 비선점 제거
   다른 프로세스가 점유하고 있던 자원을 뺏어서 사용함을 허용한다.

   여러 오류를 초래할 수 있는 위험한 방법이다.

4. 순환 대기 제거
   자원을 선형적인 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원이 고유번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하여 순환 대기를 제거한다.

   대부분의 교착상태 방지 알고리즘은 4번조건, 즉 순환 대기 상태의 사이클이 발생하는 일을 막는데 초점이 
   맞춰져 있다.

[참고문헌]
https://beenii.tistory.com/116
https://github.com/WeareSoft/tech-interview/blob/master/contents/os.md#thread-safe