교착 상태 회복

탐지 알고리즘으로 교착 상태를 확인한 후 처리에 대한 방법을 생각해야한다. 여러 방법 중 하나는 교착 상태 발생을 운영자에게 통지하여 운영자가 직접 처리하는 방법이고, 다른 방법은 시스템이 자동으로 회복하는 것이다.
교착 상태를 회복하는 방법은 순환 대기에 포함된 하나의 스레드를 중지시키거나, 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점하는 방법이있다.

프로세스와 스레드 종료

프로세스나 스레드를 중지하여 할당된 자원을 회수한다.

교착 상태 프로세스를 모두 중지

교착 상태 사이클을 확실히 끊어낼 수 있지만 비용이 크다. 어느 지점까지 연산을 한 시점에서 종료가 된다면 프로세스가 재실행될 때 이 연산들을 다시 해야하기 때문이다.

교착 상태가 제거될 때까지 한 프로세스씩 중지

프로세스가 중지될 때마다 교착 상태 알고리즘을 호출하여 교착 상태를 확인해야하므로 상당한 오버헤드가 발생한다.

문제점

만약 프로세스가 파일을 갱신하는 도중 종료된다면 그 파일은 부정확한 상태가 된다. 다른 예로 mutex 락을 점유한 상태로 공유 데이터를 갱신하는 중 종료된다면 락이 반납되면서 공유 데이터의 무결성을 보장할 수 없다.
부분 종료 방식을 사용한다면 교착 상태를 해결하기 위한 스레드를 정해야한다. 특정 프로세스를 중지시켰을 때 발생하는 비용이 가장 적은 프로세스를 선택해야한다. 이때 계산된 최소 비용이 항상 최소라는것을 보장하는것은 쉽지않다.(CPU 스케쥴링과 유사한 문제라고 생각하면된다.) 종료될 프로세스를 선택하기 위해선 아래와 같은 요인을 고려해야한다

1. 프로세스의 우선순위
2. 지금까지 프로세스가 수행된 시간과 종료까지 필요한 시간
3. 프로세스가 사용한 자원의 유형과 수
4. 프로세스가 종료하기 위해 더 필요한 자원의 수
5. 얼마나 많은 수의 프로세스가 종료되어야 하는지

자원 선점

자원 선점을 이용하여 교착 상태를 제거하려면 교착 상태가 제거될 때까지 계속해서 프로세스로부터 자원을 선점하여 다른 프로세스에게 자원을 점유하도록 해야한다. 자원을 선점할 때 아래와 같은 요인을 고려해야 한다.

1. 희생자 선택 (selection of a victim)
   어떤 자원과 어떤 스레드가 선점했을때 최소 비용이 드는지 선점의 순서를 결정해야한다. 비용 요인으로는 교착 상태 프로세스가 점유한 자원의 수, 교착 상태 프로세스가 지금까지 실행하는 데 소요한 시간 등 여러가지가 있다.

2. 후퇴 (rollback)
   프로세스로부터 자원을 선점하려면 이 프로세스를 안전한 상태로 후퇴시키고 다시 시작해야한다(교착 상태에 처한 프로세스는 정상적으로 실행될 수 없기에). 안전 상태가 어떤것인지 결정하기 어렵기 때문에, 간단한 방법으로는 프로세스를 중지한 후 재시작하여 완전히 후퇴시킨다. 더 좋은 방법으로는 교착 상태를 해결할 수 있을 정도로 후퇴하는 것이다.(완전한 정지가 아닌 특정 자원을 반납하는 수준을 말하는것 같음). 이러한 방식은 시스템이 실행하는 모든 프로세스에 더 많은 정보를 유지하여야 한다.

3. 기아상태 (starvation)
   자원들이 동일한 프로세스로부터 항상 선점되지 않도록 보장해야한다. 1번에서 고려한 희생자 선택시 계산한 비용에 의해 완료되지 못하는 기아 상태가 발생할 수 있다. 대부분의 해결 방법은 비용 요소에 후퇴 횟수를 포함하는 것이다.