교착상태 (Deadlock)

교착상태란 각 구성원이 메시지를 보내거나 더 일반적으로 잠금을 해제하는 등의 조치를 취하기 위해 자신을 포함한 다른 구성원이 대기하는 상태를 말한다. 교착상태는 다중 처리 시스템, 병렬 컴퓨팅 및 분산 시스템에서 공통적인 문제로, 소프트웨어와 하드웨어 잠금을 사용하여 공유 자원을 중재하고 프로세스 동기화를 구현한다. 운영 체제에서는 요청된 시스템 자원이 다른 대기 프로세스에 의해 유지되기 때문에 프로세스나 스레드가 대기 상태에 들어갈 때 교착 상태가 발생하며, 이는 다시 다른 대기 프로세스에 의해 보유되는 다른 자원을 기다리고 있다. 만약 프로세스가 요청한 자원이 다른 대기 과정에 의해 사용되고 있기 때문에 무한정 상태를 변경할 수 없다면, 시스템은 교착상태에 있다고 한다. 통신 시스템에서 교착상태는 주로 자원 경합보다는 손실되거나 손상된 신호 때문에 발생한다.

교착 처리
대부분의 현재 운영체제는 교착상태를 예방할 수 없다. 교착 상태가 발생할 때 서로 다른 운영 체제는 표준이 아닌 다른 방식으로 대응한다. 대부분 접근방식은 네 가지 코프만 조건, 특히 네 번째 조건 중 하나가 발생하는 것을 방지함으로써 작용한다. 주요 접근방식은 다음과 같다.

예방 (Prevention)
교착 방지 기능은 네 가지 코프만 조건 중 하나가 발생하는 것을 방지함으로써 효과가 있다.
상호 배제 조건을 제거한다는 것은 어떤 프로세스도 자원에 대한 독점적 접근권을 갖지 못한다는 것을 의미한다. 이것은 스풀할 수 없는 자원에 대해서는 불가능하다는 것을 증명한다. 그러나 스풀 자원이 있더라도 교착상태는 여전히 발생할 수 있다. 상호 배제를 회피하는 알고리즘을 비차단 동기화 알고리즘이라고 한다.
보류 및 대기 또는 자원 보유 조건은 시작 전(또는 특정 작업에 착수하기 전) 필요한 모든 자원을 요청하도록 프로세스를 요구함으로써 제거할 수 있다. 이러한 사전 지식은 종종 만족하기 어렵고 어떤 경우에도 자원을 비효율적으로 사용하는 것이다. 또 다른 방법은 없는 경우에만 자원을 요청하는 프로세스를 요구하는 것이다. 그러므로, 그들은 그들이 필요로 할 모든 자원을 처음부터 요청하기 전에 먼저 현재 보유하고 있는 모든 자원을 방출해야 한다. 이것 또한 종종 비현실적이다. 그것은 자원을 배분할 수 있고 오랫동안 사용하지 않고 있을 수 있기 때문이다. 또한, 인기 있는 자원을 필요로 하는 프로세스는 무한정 기다려야 할 수 있다. 그러한 자원은 항상 어떤 프로세스에 할당되어 자원이 고갈될 수 있기 때문이다.
또한 공정이 일정 시간 동안 자원을 가질 수 있어야 하거나 처리 결과가 일관되지 않거나 박살이 날 수 있기 때문에 선처 없음 조건은 피하기 어렵거나 불가능할 수 있다. 그러나 선처를 시행할 수 없는 것은 우선순위 알고리즘을 방해할 수 있다. "잠긴" 자원의 선정은 일반적으로 롤백을 의미하며, 오버헤드가 매우 비싸기 때문에 피해야 한다. 선처할 수 있는 알고리즘에는 잠김 없는 알고리즘과 대기 없는 알고리즘과 낙관적인 동시성 제어가 포함된다.
일부 자원과 즉시 할당할 수 없는 다른 자원에 대한 요청이 있는 프로세스가 있는 경우, 해당 프로세스의 현재 보유 중인 모든 자원을 해제하여 조건을 제거할 수 있다.
최종 조건은 원형 대기 조건이다. 순환 대기 시간을 피하는 접근방식은 중요한 섹션 동안 인터럽트를 비활성화하고 리소스의 부분적 순서를 결정하는 계층을 사용하는 것을 포함한다. 명확한 계층 구조가 존재하지 않는 경우, 자원의 메모리 주소조차 순서를 결정하는 데 사용되었고, 열거 순서가 증가함에 따라 자원이 요청된다.

교착 상태 무시(Ignoring deadlock)
이 접근법에서는 교착 상태가 절대 발생하지 않을 것으로 가정한다. 이것은 또한 오스트리치 알고리즘의 응용이다. 이는 교착상태 발생 사이의 시간 간격이 크고 매번 발생하는 데이터 손실을 견딜 수 있을 때 사용된다.

탐지 (Detection)
교착상태를 감지하면 교착상태가 발생할 수 있다. 그런 다음 시스템 상태를 검사하여 교착 상태가 발생했음을 감지한 후 수정한다. 자원 할당 및 프로세스 상태를 추적하는 알고리즘이 사용되며, 감지된 교착 상태를 제거하기 위해 하나 이상의 프로세스를 롤백하고 재시작한다. 각 프로세스가 잠겼거나 현재 요청된 자원이 운영 체제의 자원 스케줄러에 알려지기 때문에 이미 발생한 교착 상태를 쉽게 감지할 수 있다. 교착 상태가 감지된 후에는 다음 방법 중 하나를 사용하여 교정할 수 있다.
- 자원 선점: 다양한 프로세스에 할당된 자원은 교착 상태가 깨질 때까지 연속적으로 선점하여 다른 프로세스에 할당할 수 있다.
- 프로세스 종료: 교착 상태에 관련된 하나 이상의 프로세스가 중단될 수 있음 교착상태에 빠진 모든 경쟁 과정을 중단할 수도 있다. 이것은 교착 상태가 확실하고 빠르게 해결되도록 보장한다. 그러나 부분 연산이 손실되기 때문에 비용이 많이 든다. 또는 교착 상태가 해결될 때까지 한 번에 한 가지 프로세스를 중단할 수도 있다. 이 접근방식은 각 중단 후 알고리즘이 시스템이 여전히 교착 상태에 있는지 여부를 결정해야 하기 때문에 높은 오버헤드를 가지고 있다. 프로세스의 우선 순위 및 나이와 같은 몇 가지 요소를 임기 만료 후보를 선택하는 동안 고려해야 한다.

분산 교착 상태 (Distributed deadlock)
산 교착 상태는 교착 검출기의 로컬 대기 그래프에서 전역 대기 그래프를 구성하거나 에지 추적과 같은 분산 알고리즘을 통해 탐지할 수 있다. 분산된 교착상태는 분산된 거래나 동시통제가 사용될 때 분산된 시스템에서 발생할 수 있다. 분 팬텀 교착상태란 시스템 내부 지연으로 인해 분산 시스템에서 거짓으로 감지되지만 실제로는 존재하지 않는 교착상태를 말한다.