교착 상태(Deadlock)는 멀티프로세스나 멀티스레드 환경에서 발생하는 문제로, 각각의 프로세스나 스레드가 서로가 가진 자원을 점유하면서 상대방의 자원이 해제되기를 기다리는 상황에서 무한정 기다리는 현상을 말한다.
교착 상태는 두 개 이상의 작업이 동시에 이루어지는 경우에 발생할 수 있는데, 이때 각 작업이 서로가 가진 자원을 요청하고 점유하며, 자원의 해제를 서로가 기다리는 상황에서 더 이상 작업을 진행할 수 없게 된다.
컴퓨터 시스템에서 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다.
자원 활당 그래프에서 프로세스는 원으로, 자원은 사각형으로 표현한다. 자원을 사용하는 경우(할당된 경우)는 자원에서 프로세스로 향하는 화살표로 표시하고, 프로세스가 자원을 기다리는 경우(대기하는 경우)는 프로세스에서 자원으로 향하는 화살표로 표시한다.
자원이 2개 이상의 프로세스를 동시에 허용할 수 있다. 여러 프로세스가 동시에 사용하는 자원을 다중 자원(multiple resource)라고 한다. 프로세스 수를 사각형 안에 원으로 표현된다.
교착 상태는 일반적으로 다음과 같은 4가지 조건이 동시에 성립할 때 발생한다.
교착 상태를 해결하기 위해서는 위 조건 중 하나를 제거해야 한다. 예를 들어, 상호 배제 조건을 제거하여 여러 개의 프로세스나 스레드가 동시에 자원을 사용할 수 있도록 하는 방법이 있다. 하지만, 이는 일반적으로 복잡하고 어려운 문제로, 보통은 교착 상태가 발생하지 않도록 시스템 설계 및 운영 체제에서 교착 상태를 해결하기 위한 대표적인 방법으로는 다음과 같은 것들이 있다.
예방(Prevention): 교착 상태가 발생할 수 있는 조건 중 하나를 제거하여 교착 상태를 예방하는 방법이다. 예를 들어, 상호 배제 조건 중 하나를 제거하거나, 순환 대기 조건을 제거하는 것이다.
회피(Avoidance): 교착 상태가 발생할 가능성이 있는 자원 요청을 할 때, 시스템이 자원 할당을 결정하는데 있어 안전한 상태에서만 자원을 할당하도록 하는 방법이다. 이를 위해 자원 할당 상태를 추적하고, 안전 상태인 경우에만 자원을 할당하도록 하는 알고리즘이 사용된다.
검출(Detection): 교착 상태가 발생하는 것을 감지하여, 교착 상태가 발생하면 그 상황을 해결하는 방법이다. 이를 위해 시스템에서는 일정 주기마다 자원 할당 상태를 체크하고, 교착 상태가 발생하는지 여부를 검사한다.
회복(Recovery): 교착 상태가 발생한 경우, 교착 상태를 해결하고 시스템을 정상 상태로 복구하는 방법이다. 이를 위해 자원을 해제하거나, 프로세스나 스레드를 강제로 중지시키는 등의 방법이 사용된다.
교차 상태 회피에서는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태로 유지하도록 한다.
할당된 자원이 적으면 안정상태, 많으면 불안정 상태이다.
은행이 대출해 주는 방식이다. 즉 대출 금액이 가능한 범위 내이면(안정 상태이면) 대출이 허용되지만 그렇지 않으면 거부되는 것과 유사하다.
은행원 알고리즘은 최악의 경우를 기준으로 삼음으로써 문제 상황을 철저히 피하여 교착 상태를 막는다.
안정상태: 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우
타임아웃을 이용한 교착상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. ( 교착 상태가 자주 발생하지 않을 것이라고 간주)
자원 할당 그래프가 교착 상태인지 판단하는 방법은 사이클 존재 여부이다. 존재하면 교착 상태가 있다고 판단한다. (단 자원의 수가 하나이면 교착 상태이고 여러 개일 경우 모두 교착 상태라고 판단 할 수 없다.)
교착 상태 회복에서는 종료하는 일뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템으로 복구하는 일도 해야 한다. (체크포인트)