detection 알고리즘이 deadlock이 존재한다고 판단하면, 여러 대안을 사용할 수 있다. 한 가지 가능성은 deadlock이 발생한 것을 운영자에게 알라고, 운영자가 데드락을 수동으로 처리하도록 하는 것이다. 다른 가능성은 시스템이 데드락에서 자동으로 recover(복구)하도록 하는 것이다. 데드락을 깨는 두 가지 옵션이 있다. 하나는 단순히 하나 이상의 스레드를 중단하여 순환 대기를 깨는 것이다. 다른 하나는 데드락에 빠진 하나 이상의 스레드에서 일부 리소스를 선점하는 것이다.
8.8.1 Process and Thread Termination
프로세스나 스레드를 중단하여 데드락을 제거하기 위해, 두 방법 중 하나를 사용한다. 두 방법 모두, 시스템은 종료된 프로세스에 할당된 모든 리소스를 회수한다.
-
Abort all deadlocked processes(모든 데드락 프로세스 중단):
이 방법은 데드락 사이클을 분명히 깰 것이지만, 많은 비용이 든다. 데드락 프로세스는 긴 시간동안 계산을 했을 수 있고, 이 부분 계산 결과는 버려야하고 아마도 나중에 다시 계산해야 할 것이다. -
Abort one process at a time until the deadlock cycle is eliminated(데드락 사이클이 제거될 때까지 한 번에 한 프로세스 중단):
이 방법은 상당한 오버헤드를 초래한다. 각 프로세스가 중단된 후, deadlock-detection 알고리즘을 호출하여 프로세스가 여전히 데드락인지 확인해야하기 때문이다.
프로세스를 중단하는 것은 쉽지 않을 수 있다. 프로세스가 파일을 업데이트하는 중에, 종료하면 해당 파일이 잘못된 상태로 남을 수 있다. 마찬가지로, 프로세스가 뮤텍스 락을 가지고 있는 동안, 공유 데이터를 업데이트하는 중이었다면, 시스템은 lock을 사용가능한 상태로 복원해야 하지만, 공유 데이터의 무결성에 대해서는 보장할 수 없다.
부분 종료 방법을 사용하면, 어떤 데드락 프로세스를 종료해야 하는지 결정해야 한다. 이 결정은 CPU-sheculing 결정과 유사한 정책 결정이다. 이 질문은 기본적으로 경제적인 것인데, 종료 시 최소 비용이 발생하는 프로세스를 중단해야 한다. 불행히도, minimum cost(최소 비용)정확한 용어가 아니다. 다음을 포함하여, 많은 요소가 어떤 프로세스를 선택할지에 영향을 미칠 수 있다.
- 프로세스의 우선순위
- 프로세스가 계산한 시간과, 지정된 task를 완료하기 전에 계산할 시간
- 프로세스가 사용한 리소스의 수와 유형
- 프로세스를 완료하기 위해 필요한 리소스 수
- 종료해야 하는 프로세스 수
8.8.2 Resource Preemption
리소스 선점을 사용하여 데드락을 제거하려면, 프로세스에서 일부 리소스를 순차적으로 선점하고, deadlock cycle이 깨질 때까지 이 리소스를 다른 프로세스에 제공한다.
데드락을 처리하기 위해 선점이 필요하다면, 세 가지 문제를 해결해야 한다:
-
Selecting a victim. 프로세스 종료에서와 마찬가지로 비용을 최소화하기 위해 선점 순서를 결정해야 한다. 비용 요인에는 다음과 같은 프로세스가 포함될 수 있다. 데드락 프로세스가 보유한 리소스 수와 프로세스가 지금까지 소비한 시간 등.
-
Rollback. 프로세스에서 리소스를 선점하면, 해당 프로세스는 정상적인 실행을 계속할 수 없다. 필요한 리소스가 없어졌기 때문이다. 프로세스를 안전한 상태로 롤백하고 해당 상태에서 다시 시작해야 한다.
일반적으로, 안전한 상태가 무엇인지 판단하기 어렵기 때문에, 가장 간단한 솔루션은 롤백이다: 프로세스를 중단한 다음 다시 시작한다. 데드락을 깨는 데 필요한 범위내에서 롤백하는 것이 더 효과적이지만, 이 방법은 시스템이, 실행 중인 프로세스에 대한 정보를 더 많이 보관해야 한다. -
Starvation. 희생자 선택이 주로 비용 요인에 기반하는 시스템에서는, 항상 동일한 프로세스가 희생자로 선택될 수 있다. 결과적으로, 이 프로세스는 지정된 task를 완료하지 못하고, 이는 모든 실용적인 시스템이 해결해야하는 기사 상태이다. 프로세스가 (작은) 유한한 횟수만큼만 선택될 수 있도록 해야 한다. 가장 일반적인 솔루션은 비용 요인에 롤백 횟수를 포함시키는 것이다.
