Deadlock (교착상태)
프로세스 집합의 모든 프로세스가 해당 집합 내의 다른 프로세스만이 일으킬 수 있는 이벤트를 기다리고 있어 프로세스가 진행되지 않는 상태
Liveness failure(무한 대기)의 한 형태
- 특정 스레드 또는 프로세스가 요청한 자원이
다른 대기 중인 스레드 또는 프로세스에 의해 보유되어 있어대기 중인 스레드가 다시 상태를 변경할 수 없는 상황
- 이 상황은 대개
서로가 서로의 자원을 기다리는프로세스들 사이에 발생함
System Model
자원과 프로세스, 그리고 그들 사이의 상호작용을 표현
- 시스템은 한정된 수의 자원으로 구성되어 있음
- 자원: CPU 사이클, 메모리 공간, I/O 장치 등
- 이러한 각각의 자원 유형을 R₁, R₂, ..., R𝗇과 같이 나타냄
- 각 자원 유형 R𝑖는 W𝑖개의 인스턴스를 가지고 있음
인스턴스는 동일한 유형의 특정 자원을 나타냄
- 각 프로세스는 다음과 같은 순서로 자원을 사용합니다:
요청(Request): 프로세스는 필요한 자원을 시스템에 요청함사용(Use): 요청된 자원이 할당되면, 해당 자원을 사용하여 작업을 수행함해제(Release): 작업이 완료되면 자원을 해제하고 시스템에 반환함
프로세스가 요청한 자원이 다른 프로세스에 의해 보유되고 있어 사용할 수 없는 경우, 요청한 프로세스는 대기 상태로 전환됩니다. 만약 프로세스들이 서로의 진행을 막는 방식으로 자원을 보유하고 있다면, 이는 deadlock 상태로 이어질 수 있습니다.
이러한 시스템 모델은 deadlock의 발생 원인을 이해하고, 이를 해결하거나 피하는 방법을 설계하는 데 도움이 됩니다.
Deadlock with Semaphores
- 이 예제에서는 세마포어 S와 Q가 있으며, 두 개의 스레드 T1과 T2가 각각 이 세마포어를 사용하여 리소스에 대한 접근을 동기화하려고 합니다.
- 스레드 T1은 먼저 세마포어 S를 대기(wait)하고, 다음으로 세마포어 Q를 대기합니다.
- 스레드 T2는 반대 순서로 세마포어 Q를 먼저 대기하고, 다음으로 세마포어 S를 대기합니다.
이 상황에서 deadlock이 발생할 수 있는 상황은 다음과 같습니다:
- T1이 S를 대기하고 성공하며, 동시에 T2가 Q를 대기하고 성공합니다.
- 이 상태에서 T1은 Q를 대기하려 시도하고, T2는 S를 대기하려 시도합니다.
- 하지만, 각각의 세마포어는 이미 다른 스레드에 의해 보유되고 있으므로 두 스레드 모두 대기 상태로 전환됩니다.
- 따라서, 두 스레드 모두 signal 연산을 수행할 수 없게 되어 deadlock 상태에 빠집니다.
이러한 상황은 세마포어를 이용한 동기화에서 자주 발생하는 문제로, 스레드들이 세마포어를 요청하는 순서를 잘못 관리하면 발생할 수 있습니다. 따라서, 세마포어를 사용할 때는 스레드간의 상호작용과 세마포어의 사용 순서를 신중하게 고려해야 합니다.
Deadlock Characterization
Deadlock은 일반적으로 아래 네 가지 조건이 동시에 유지되어야 발생함
1. 상호 배제(Mutual Exclusion):
하나의 자원을 동시에 하나의 스레드만이 사용할 수 있다는 조건
즉, 한 스레드가 자원을 사용 중이면, 다른 스레드는 그 자원을 사용할 수 없다.
2. 보유 및 대기(Hold and Wait):
스레드가 이미 하나 이상의 자원을 보유하면서 다른 스레드가 보유한 추가적인 자원을 기다리고 있는 상태
3. 비선점(No Preemption):
자원이 강제로 회수될 수 없다는 조건
즉, 자원은 해당 자원을 보유한 스레드가 자신의 작업을 완료한 후에만 자발적으로 해제할 수 있다.
4. 순환 대기(Circular Wait):
스레드 집합 {T₀, T₁, ..., T𝗇}이 존재하며, T₀이 T₁이 보유한 자원을, T₁이 T₂가 보유한 자원을, ..., T𝗇이 T₀가 보유한 자원을 대기하는 순환 구조가 있는 상태
이 네 가지 조건이 동시에 충족될 때, 시스템은 Deadlock 상태에 빠질 수 있다.
Resource Allocation Graph
프로세스와 자원 사이의 할당 상태를 시각화하는 도구
시스템의 deadlock 상태를 분석하고 이해하는 데 유용함
- Vertex
- 동그라미나 네모로 표현
- 동그라미는 쓰레드 : {T₁, T₂, ... ,T𝑛}
- 네모는 자원(Resource) : {R₁, R₂, ... ,R𝑛}
- Edge
- 화살표로 표현
- Request Edge: T→R, 쓰레드가 해당 자원을 요청하고 있음을 나타냄
- Allocation Edge: R→T, 자원이 쓰레드에 할당되었음을 나타냄
Deadlock이 있는 Resource Allocation Graph
이렇게 지들끼리 빙글빙글 돌고 있으면(cycle이 생기면) 데드락 발생한다
cycle이 있는 경우에도
1) 하나의 자원에 하나의 인스턴스 밖에 없으면, 무조건 데드락
2) 하나의 자원에 다수의 인스턴스 있으면, 데드락 발생할 수도 있음
라고 한다.
Deadlock이 없는 Resource Allocation Graph
T₄는 R₂를 release시켜줄 수 있기 때문에 cycle을 깰 수 있다.
(R₁ → T₂도 마찬가지 인듯?)
Methods for Handling Deadlocks
데드락을 처리하는 세 가지 방법
- 무시하기:
- Deadlock이 시스템에서
발생하지 않는다고 가정하고, 이에 대해 아무런 조치도 취하지 않는 것
- Deadlock이 시스템에서
- 시스템이 Deadlock 상태에 들어가지 않도록 보장하기:
- Deadlock 예방(Deadlock Prevention)
- Deadlock 회피(Deadlock Avoidance)
- 시스템이 Deadlock 상태에 들어가게 한 후 복구하기:
- Recovery from deadlock
아래에서 마저 배움
Deadlock Prevention
Deadlock의 네 가지 필요 조건 중 적어도 하나를 항상 부정하여 Deadlock이 발생하지 않도록 하여 예방함
1. 상호 배제 (Mutual Exclusion) 부정
원래 조건: 한 번에 하나의 스레드만이 자원을 사용할 수 있음
부정: 공유 가능한 자원에 대해서는
상호 배제를 요구하지 않아야 함예) 읽기 전용 파일과 같은 공유 가능한 리소스는 동시에 여러 스레드에 의해 사용될 수 있습니다. 그러나 비공유 자원에 대해서는 상호 배제 조건이 유지되어야 합니다.
2. 보유 및 대기(Hold and Wait) 부정
원래 조건: 스레드가 이미 하나 이상의 자원을 보유하면서 다른 스레드가 보유한 추가적인 자원을 기다리고 있는 상태
부정: 스레드가 자원을 요청할 때
다른 자원을 보유하고 있지 않아야 함방법1: 스레드가 실행을 시작하기 전에 필요한 모든 자원을 요청하고 할당받도록 함
이 방식은 한 번에 모든 필요 자원을 얻지 못하면 스레드가 시작되지 않으므로 deadlock을 예방할 수 있지만,자원 활용률(Resource Utilization)이 떨어질 수 있음방법2: 스레드가 자원을 보유하고 있지 않을 때만 자원을 요청하도록 함
이 방식 역시 deadlock을 예방할 수 있지만, 모든 자원이 한 번에 사용 가능하도록 조정되어야 하며, 그렇지 않으면 스레드가기아 상태(Starvation)에 빠질 수 있음
3. 비선점(No Preemption) 부정
원래 조건: 자원이 강제로 회수될 수 없다
- 만약 어떤 스레드가 자원을 보유하고 있으면서 동시에 즉시 할당받을 수 없는 다른 자원을 요청하면,
현재 보유하고 있는 모든 자원을 방출해야 한다. 이러한 동작은 선점(preemption)을 허용함으로써 가능해짐- 선점된 자원들은 스레드가 대기 중인 자원 목록에 추가됨
- 스레드는 이전에 가지고 있던 자원과 요청한 새 자원을 모두 다시 얻을 수 있을 때만 재시작
선점에 따른 오버헤드 발생 가능성 존재함
4. 순환 대기(Circular Wait) 부정
원래 조건: 스레드 집합 {T₀, T₁, ..., T𝗇}에서 T₀이 T₁이 보유한 자원을, T₁이 T₂가 보유한 자원을 기다리고, ..., T𝗇이 T₀이 보유한 자원을 기다리 순환적인 대기 상태
부정: 모든 자원 유형에 대해
총 주문(total ordering)을 부과하고, 각 스레드가 열거 순서가 증가하는 방식으로 자원을 요청하도록 요구즉, 각 자원 유형에 고유한 번호를 할당하고, 스레드가 번호 순서대로 자원을 요청하도록 만드는 것입니다. 이를 통해 순환 대기를 방지할 수 있습니다. 예를 들어, 스레드가 5번 자원을 보유하고 있다면 그보다 높은 번호인 6번, 7번, 등의 자원만 요청할 수 있습니다. 이런 방식으로 스레드가 낮은 번호의 자원을 요청하며 순환 대기 상태에 빠지는 것을 방지할 수 있습니다.
Deadlock Avoidance
- 시스템이 Deadlock 상태에 들어가지 않도록 동적으로 자원 할당 상태를 검사하고 조절하는 방식
- 이를 위해서는 시스템이
사전에일부 정보를 가지고 있어야 함
Deadlock avoidance에 대한 기본적인 모델
-
각 스레드가 필요로 하는 각 유형의
자원의 최대 수량을 선언해야 함
이는 시스템이 각 스레드에 의해요청될 수 있는 자원의 최대 양을 알 수 있게 하여, 더 안전하게 자원을 할당할 수 있게 함 -
자원 할당 상태를 동적으로 검사하여 순환 대기 상태가 발생할 수 없도록 함
이 알고리즘은 현재 사용 가능한 자원의 수, 이미 할당된 자원의 수, 그리고 프로세스들이 요구하는 자원의 최대 수량에 기반하여 작동함
Safe State (안전 상태)
시스템이 Deadlock에 빠지지 않고 모든 스레드를 성공적으로 실행 완료할 수 있는 상태
안전 상태에 대한 정의와 그 조건:
-
스레드가 사용 가능한 자원을 요청할 때 시스템은 즉시 할당이 시스템을 안전한 상태로 유지할지 여부를 결정해야 함
-
시스템은 모든 스레드 <T₁, T₂, ..., T𝗇>의 순서가 존재하고, 각 스레드 Ti에 대해
Ti가 아직 요청할 수 있는 자원이현재 사용 가능한 자원+j < i인 모든 Tj가 보유한 자원에 의해 만족시킬 수 있을 때 안전 상태에 있음 -
만약 Ti의 자원 요구가 즉시 충족되지 않는다면, Ti는 모든 Tj가 완료될 때까지 기다릴 수 있음
-
Tj가 완료되면, Ti는 필요한 자원을 얻을 수 있으며, 그런 다음 실행, 할당된 자원 반환, 종료를 진행할 수 있음
-
Ti가 종료되면, Ti + 1이 필요한 자원을 얻을 수 있고, 이 과정이 반복됨
- 시스템이
safe state에 있는 경우 → Deadlock 없음- 시스템이
unsafe state에 있는 경우 → Deadlock 가능성 있음- Deadlock avoidance 알고리즘을 통해 시스템이 unsafe state에 들어가지 않도록 보장함
Deadlock Avoidance Algorithms
- 데드락 피하기 알고리즘의 일환으로 Resource Allocation Graph가 사용될 수 있다.
- 이 방법은 각 자원 유형에 대해
단일 인스턴스가 존재할 때 사용할 수 있다.
- Request Edge
- 프로세스가 자원을 요청하였으나
아직 할당받지 못했을 때- Ti → Rj 형태로 표현
- 프로세스가 자원을 할당받을 때
Assignment Edge로 변환됨
- Assignment Edge
- 프로세스가 자원을 할당받았을 때
- Rj → Ti 형태로 표현
- 프로세스가 자원을 해제(release)하면 다시
Request Edge로 변환됨
- Claim Edge
- 프로세스가 사용할 수 있는 자원을 사전에 선언할 때
- 일반적으로 점선으로 표시
- 프로세스가 특정 자원을 요청하면 Request Edge로 변환됨
- 자원을 할당받으면 Assignment Edge로 변환됨
Resource allocation graph scheme
위 경우 R₂는 자유로운 상태이지만 T₂에 할당될 경우 cycle이 생기기 때문에, 데드락 발생 가능성이 생겨 할당할 수 없다.
이처럼, Request Edge에서 Assignment Edge로 전환될 때 cycle이 생기는 지 잘 살펴봐야함
Banker's Algorithm
- Edsger Dijkstra가 개발
- 자원 할당 및 데드락 회피를 위한 알고리즘
- 안전 상태를 유지하면서 자원을 할당하는 것이목표
모든 자원의 할당을 시뮬레이션하여 안전성을 테스트한 다음,
할당이 허용되어야 하는지 여부를 결정하기 전에 가능한 교착 상태 상태를 테스트한다.
-
다중 인스턴스의 자원: 자원의 각 유형은 여러 인스턴스를 가질 수 있다.
-
최대 사용량 사전 요구: 각 스레드는 사전에 최대 사용량을 주장해야 한다. 즉, 스레드가 실행 중에 필요로 할 가능성이 있는 모든 자원을 사전에 요구해야 한다.
-
안전 알고리즘: 시스템이 자원 요청을 받으면, Banker's Algorithm은 '안전 알고리즘'을 실행하여 요청을 승인하는 것이 안전한지 결정한다. 안전 알고리즘은 시스템이 안전 상태에 있는지를 판단하는데, 이는 모든 스레드가 자신의 최대 요구량을 만족시키면서 실행을 완료할 수 있는 상태를 의미한다.
-
요청의 거부 또는 연기: 시스템은 불가능하거나 안전하지 않은 요청을 거부하거나 연기한다.
Banker's Algorithm 자료구조
- Available:
- 길이가 m인 벡터 (m은 자원 유형의 수)
- Available [j] = k라면, 현재 자원 유형 Rj의 k개 인스턴스가 사용 가능하다는 뜻
- Max:
- n x m 행렬 (n은 프로세스의 수, m은 자원 유형의 수)
- Max [i, j] = k라면, 프로세스 Ti는 최대 k개의 자원 유형 Rj를 요청할 수 있다는 뜻
- Allocation:
- n x m 행렬
- Allocation [i, j] = k라면, Ti 프로세스에 현재 자원 유형 Rj의 k개 인스턴스가 할당되어 있다는 뜻
- Need:
- n x m 행렬
- Need [i, j] = k라면, Ti 프로세스는 작업을 완료하기 위해 추가로 Rj 유형의 k개 인스턴스를 더 필요로 한다는 뜻
- Need는 Max와 Allocation의 차이로 계산
즉, Need [i, j] = Max [i, j] – Allocation [i, j].
Banker's Algorithm - Safe State
Safe State (안전 상태) : 모든 프로세스들이 실행을 완료하고 종료할 수 있는 상태
-
시스템은 모든 프로세스가 결국에는 그들이 필요로 하는 최대한의 자원을 획득하고, 그 이후에는 곧바로 종료하면서 그 자원을 시스템에 반환하려 할 것이라고 가정함
-
Banker's Algorithm은 이러한 안전 상태를 판별하기 위해
가상의 프로세스 요청 집합을 찾음 -
이런 요청 집합을 찾을 수 없는 상태는
안전하지 않은 상태로 판단함 (데드락 가능성이 있는 상태)
Banker's Algorithm
- Banker's Algorithm psuedo code
- Time Complexity = O(m × n²)
- Let Work and Finish be vectors of length m and n, respectively
/* initialize */ Work = Available Finish[i] = false for i=0,1,...,n-1
Work와 Finish라는 두 개의 벡터 선언한다
- Work는
사용 가능한 자원의 수를 나타내는 길이 m의 벡터- Work 벡터는 사용 가능한 모든 자원(Available)으로 설정
- Finish는 각 프로세스가
자신이 필요로 하는 자원을 모두 얻었는 지를 나타내는 길이 n의 벡터- Finish 벡터의 모든 요소는 false로 설정
- Find an i such that both:
( Finish[i] == false) AND (Need[i] ≤ Work) If no such i exists, GO TO step 4
- Finish[i]가 false이고 Need[i]가 Work보다 작거나 같은 인덱스 i를 탐색
- 이는 아직 자신이 필요로 하는 모든 자원을 얻지 못한 프로세스(i)가 현재 사용 가능한 자원(Work)으로 그 요구를 충족시킬 수 있음을 의미
- 만약 그런 i가 존재하지 않는다면, step 4로 넘어감
Work = Work + Allocation[i] Finish[i] = true GO TO step 2
- 이러한 프로세스 i가 있다면, 그 프로세스가 현재 보유하고 있는 자원(Allocation[i])을 시스템에 반환한다고 가정하고, 이 반환된 자원을 사용 가능한 자원(Work)에 더한다.
- 그리고 Finish[i]를 true로 설정하여 이 프로세스가 필요한 모든 자원을 얻었음을 나타낸다.
- 그런 다음 step 2로 돌아간다.
If Finish[i] == true for all i, then the system is in a safe state
- 모든 프로세스에 대해 Finish[i]가 true라면, 이는 모든 프로세스가 자신이 필요로 하는 모든 자원을 얻을 수 있다는 것을 의미하므로, 시스템은 안전한 상태에 있다고 결론지은다.
Banker's Algorithm Example
- 5개의 쓰레드: T₀ ~ T₄
- 3개의 자원(인스턴스): A(10), B(5), C(7)
- 초기 상태
Allocation Max Need Work A B C A B C A B C A B C T₀ 0 1 0 7 5 3 7 4 3 3 3 2 T₁ 2 0 0 3 2 2 1 2 2 T₂ 3 0 2 9 0 2 6 0 0 T₃ 2 1 1 2 2 2 0 1 1 T₄ 0 0 2 4 3 3 4 3 1
Banker's Algorithm의 안전 기준을 만족시키는 순서 <T₁,T₃,T₄,T₂,T₀>이 존재하기 때문에 해당 시스템은 안전상태이다.
Deadlock Detection
시스템이 데드락 상태로 진입하는 것을 허용하고, 데드락이 발생한 경우에 감지하여 복구하는 접근 방식
- 데드락 감지 알고리즘 :
- 정기적으로 또는 특정 조건 하에 데드락을 감지하기 위해 실행
- 자원 유형의
단일 인스턴스 또는 다중 인스턴스에 대해 사용될 수 있음 - 주로 사용되는 방법은 자원 할당 그래프를 검사하여 순환이 존재하는지 확인하는 것
순환이 발견되면 데드락이 존재한다고 판단
- 복구 스킴 :
- 데드락이 감지되면 시스템은 데드락을 해결하기 위해 복구 스킴을 실행해야함.
Wait-for-graph scheme
자원 유형의
단일 인스턴스에 대한 데드락 감지 방법
- Resource Allocation Graph와 달리 자원 vertex가 없음
- Ti → Tj: 스레드 Ti가 스레드 Tj에 의해 보유된 자원을 기다리고 있다는 뜻
- 이런 방식으로 그래프를 구성한 뒤, 주기적으로 알고리즘을 호출하여 그래프에 순환(cycle)이 있는지 검사
- 순환이 존재한다면 그것은 데드락이 발생했음을 의미
- 그래프 내에서 순환을 감지하는 알고리즘은 일반적으로 시간복잡도 O(n²)
(n은 vertex 수)
Detection Algorithm
자원 유형의
다수 인스턴스에 대한 데드락 감지 방법
Time Complexity = O(m × n²)
- Let Work and Finish be vectors of length m and n, respectively
/* initialize */ Work = Available For i = 0, 1, ... , n – 1, if Allocation[i] ≠ 0, Finish[i] = false; otherwise Finish[i] = true
Work와Finish라는 두 개의 벡터를 초기화Work는 현재 사용 가능한 모든 자원Finish는 각 프로세스가 요구를 완료했는지 (더 이상 필요한 자원이 없는지)- 각 프로세스에 대해 할당된 자원이 있다면
Finish벡터의 해당 위치는false로 설정되고, 그렇지 않으면true로 설정
- Find an i such that both:
(Finish[i] == false) AND (Request[i] ≤ Work) If no such i exists, GO TO step 4
Finish[i]가false이며Request[i]가Work벡터보다 작거나 같은 프로세스 i를 탐색
즉, 아직 요구를 완료하지 못했지만, 현재 사용 가능한 자원으로 요구를 충족시킬 수 있는 프로세스 탐색- 만약 그러한 프로세스가 없다면 4단계로 이동
Work = Work + Allocation[i] Finish[i] = true /* assume Ti will finish with no more request */ GO TO step 2
- 프로세스 i의 요구가 충족되면,
Work벡터에 프로세스 i에게 할당된 자원을 추가하고,Finish[i]를true로 설정- 즉, 프로세스 i가 요구를 완료하고 자원을 반환했다고 가정함
- 그런 다음 2단계로 되돌아감
- If Finish[i] == false for some i , then the system is in a deadlock state, and Ti is deadlocked
Finish[i]가false인 프로세스가 있으면, 시스템이 데드락 상태에 있음을 의미- 즉, 이 프로세스는 요구를 충족시킬 수 있는 충분한 자원을 얻지 못했음
Detection Algorithm Example - No deadlock
- 5개의 쓰레드: T₀ ~ T₄
- 3개의 자원(인스턴스): A(7), B(2), C(6)
- 초기 상태
Allocation Request Available A B C A B C A B C T₀ 0 1 0 0 0 0 0 0 0 T₁ 2 0 0 2 0 2 T₂ 3 0 3 0 0 0 T₃ 2 1 1 1 0 0 T₄ 0 0 2 0 0 2
모든 i에 대해 Finish[i] == True를 만족시키는 순서 <T₀,T₂,T₃,T₁,T₄>가 존재하기 때문에 해당 시스템은 안전상태이다.
Detection Algorithm Example - With Deadlock
- 5개의 쓰레드: T₀ ~ T₄
- 3개의 자원(인스턴스): A(7), B(2), C(6)
- 초기 상태
Allocation Request Available A B C A B C A B C T₀ 0 1 0 0 0 0 0 0 0 T₁ 2 0 0 2 0 2 T₂ 3 0 3 0 0 1 T₃ 2 1 1 1 0 0 T₄ 0 0 2 0 0 2
T₀ 이후 (0, 1, 0)상태에서 만족시킬 수 있는 Request가 없기 때문에 데드락 상태에 빠질 수 있다.
Recovery from Deadlock
데드락 상태에서 회복하는 방법1 : 쓰레드 or 프로세스 종료
- 모든 데드락 프로세스 종료
- 데드락 상태에 있는
모든 프로세스를 즉시 중단하는 방법- 이 방법은 가장 간단하지만, 작업의 손실이 크고 중단된 프로세스들이 필요로 하는 작업을 다시 시작해야 하는 비용이 발생할 수 있음
- 한 번에 하나의 프로세스만 종료
- 데드락 상태가 해결될 때까지
한 번에 하나의 프로세스만을 종료하는 방법- 이 경우에는 어떤 프로세스를 종료할지 결정해야 함
- 고려 요인:
- 스레드의 우선 순위
우선 순위가 낮은 스레드를 먼저 종료할 수 있습니다.
- 스레드가 얼마나 계산하였는지, 완료하기 위해 얼마나 더 필요한지
이미 많은 작업을 완료한 스레드를 종료하면 많은 작업이 손실될 수 있으므로, 계산량이 적은 스레드를 먼저 종료하는 것이 좋을 수 있음
- 스레드가 사용한 자원
많은 자원을 소비한 스레드를 종료하면 그 자원들을 재사용할 수 있게
- 스레드가 완료하기 위해 필요한 자원
완료하기 위해 많은 추가 자원을 필요로 하는 스레드를 종료하면, 이 후보자원들을 다른 스레드들이 사용할 수 있게 됨
- 종료해야 하는 스레드의 수
가능한 적은 수의 스레드를 종료하는 것이 좋음
- 스레드가 대화형인지 배치형인지
대화형 스레드는 사용자와 상호작용하므로 종료하면 사용자에게 불편을 줄 수 있으므로, 배치형 스레드를 먼저 종료하는 것이 좋음
데드락 상태에서 회복하는 방법 2 : 자원 선점
데드락 상태에 있는 프로세스로부터
필요한 자원을 강제로 회수하는 방식
이 방법은 세 가지 주요 단계를 포함합니다:
- 희생자 선택(Selecting a victim)
- 어떤 프로세스로부터 자원을 회수할지 결정하는 단계
- 비용을 최소화하는 방식으로 진행됨
- 롤백(Rollback)
- 프로세스를 안전한 상태로 되돌림
- 이후, 프로세스 재시작
- 기아 상태(Starvation)
- 동일한 프로세스가 항상 희생자로 선택될 수도 있음
- 이 경우, 해당 프로세스는 계속해서 롤백되고 결국 작업을 완료하지 못하는 기아 상태에 빠질 수 있음
- 이를 방지하기 위해, 롤백 횟수를 비용 요소에 포함하여 프로세스 선택을 조정
