Handling Deadlocks

Deadlock Characterization

4가지 조건을 모두 동시에 만족할 경우 Deadlock 발생

1. Mutual Exclusion (상호 배제): 자원이 공유 불가능(Non-sharable)하고 한 번에 하나의 프로세스만 사용 할 수 있음.
2. Hold and Wait (점유와 대기): Processes hold and request resources. 프로세스가 이미 자원을 점유한 상태에서 추가 자원을 요청하며 대기
3. No Preemption (비선점): Resources can't be forcibly reclaimed. 자원을 강제로 회수할 수 없으며, 프로세스가 자발적으로 해제해야 함.
4. Circular Wait (순환 대기): Circular chain of processes waiting. 프로세스 간 순환적으로 자원 요청하며 대기 상태 형성

 

---

Deadlock Prevention

Characterization별로 해결 방법이다.

1. Mutual Exclusion (상호 배제)
   • Allow resources to be sharable (e.g., read-only files).
   • 읽기 전용 파일처럼 공유 불가능한 자원보다 공유 가능한 자원을 사용한다.
   • Non-sharable resources like printers cannot eliminate this condition.
   • 프린터와 같은 리소스는 상호 배제 해소를 못 해준다.
2. Hold and Wait (점유와 대기)
   • Require processes to request all resources at once before execution.
   • 자원을 요청하기 전에 필요한 모든 자원을 한 번에 요청
   • Alternatively, ensure a process holds no resources while waiting for additional ones
   • 추가 자원을 요청하기 전에 현재 점유 중인 자원을 해제
3. No Preemption (비선점)
   • Allow resources to be forcibly preempted if the requested resource is unavailable.
   • Applicable to resources that can be saved and restored (e.g., CPU registers).
   • 자원을 강제로 회수 가능하도록 설계.
4. Circular Wait (순환 대기)
   • Impose an ordering on resource types.
   • Processes must request resources in an increasing order of precedence.
   • 자원에 우선순위를 부여하고 항상 정해진 순서대로 요청

Prevention은 간단하고 빠르게 외우자

Mutual Exclusion : Non-sharable Resource때문임 -> sharable resource 사용

Hold and Wait : Hold(자원 점유 상태)에서 추가 자원 요청하며 Wait ->
자원 요청 전 필요한 모든 자원 한 번에 요청(재요청 할 필요 없이 원인 자체를 원천봉쇄)
그러지 못 할 경우 : 추가 자원 요청 전에 현재 점유 중인 자원 해제

No Preemption : 자원이 점유 중일 때 강제로 회수 안 됨 -> 자원을 강제로 회수 하도록 설계

Circular Wait : 프로세스들이 순환적으로 기다림 -> 자원에 우선순위 부여

 

---

Deadlock Avoidance

Safe State

• A state where all processes can finish execution without entering a deadlock.
• 모든 프로세스가 교착상태 없이 실행 완료가 가능한 상태

Unsafe State:

• A state where there is a possibility of deadlock, though deadlock may not have occurred yet.
• 교착상태가 발생할 가능성이 있는 상태

If a system is in safe state -> no deadlocks
if a system is in unsafe state -> possibility of deadlock
avoidance -> ensure that a system will never enter an unsafe state.

 

Avoidance : Banker's Algorithm

Single instance of a resource type : resource-allocation graph

Multiple instance of a resource type : Banker's Algorithm

• Check if resource allocation leads to a safe sequence where all processes can complete.
• 자원을 할당하기 전에 요청이 안전 상태를 유지하는지 확인

 

* instance : 프로그램이나 프로세스의 개별적인 실행 단위이다. 

 

1. 프로세스가 자원을 요청하면, Resource Request Algorithm으로 요청 검증
2. 요청이 승인되면 Safety Algorithm으로 상태 검증
3. 안전 상태면 요청을 허용, 그렇지 않으면 요청 거부

 

예시보기

초기 데이터

R1, R2, R3

Avaliable: [3, 3, 2]

 

MAX
P0: [7, 5, 3]
P1: [3, 2, 2]
P2: [9, 0, 2]
P3: [2, 2, 2]
P4: [4, 3, 3]

Allocation
P0: [0, 1, 0]
P1: [2, 0, 0]
P2: [3, 0, 2]
P3: [2, 1, 1]
P4: [0, 0, 2]

 

Safety Algorithm 실행

1. Work = Avaliable = [3, 3, 2]
2. P1 실행 가능 ( Need[1] = [1, 2, 2] <= Work)
   • Work = Work + Allocation[1] = [5, 3, 2]
   • Finish[1] = true.
3. 반복하여 모든 프로세스 완료 가능 -> 안전 상태

Resource Request Algorithm

P1이 Request[1] = [1, 0, 2] 요청

• Request[1] <= Need[1] 확인 -> 요청 가능
• Request[1] <= Available 확인 -> 요청 가능

자원 임시 할당 후 Safety Algorithm 실행 -> 안전 상태 유지 -> 요청 승인

Banker's Algorithm은 deadlock prevention이 효과적이지만, 자원 요청 정보를 미리 알아야 하므로 모든 환경에 적합하진 않다.

 

---

Deadlock Detection

single instace : Wait-For Graph(Resource Allocation Graph의 변형)를 통해 deadlock detection

several instances : 자원 상태를 확인하며 deadlock dection (using time-varying data structures)

	Single Instance	Serveral Instance
자원 특징	각 자원 유형이 단일 인스턴스를 가짐	각 자원 유형이 여러 인스턴스를 가짐
탐지 방법	Wait-for Graph	Request, Allocation 상태 확인
판단	Cycle	Finish[i]
시간 복잡도	O(n^2)	O(m x n^2)
예시	단일 프린터, 네트워크 포트	다수의 프린터, 디스크 드라이브

 

1. Overhead : 탐지 알고리즘 실행이 자주 필요하면 성능 저하
2. 복구 비용 : 탐지 후 교착 상태 복구에는 높은 비용(프로세스 종료, 자원 선점 등) 발생
3. Deadlock 지속 시간 : Detection 이후 즉시 복구하지 않으면 Deadlock 장기화

Single Instance

Wait-for Graph에 Cycle이 포함된 경우 Deadlock 존재

 

(a) T1은 T2가 점유 중인 R1을 요청하고 있다.

(b) T1은 T2가 R1을 해제할 때까지 기다린다.

      T2는 T3가 R4를 해제할 때까지 기다린다.

      T3은 T4가 R5을 해제할 때까지 기다린다.

 

Deadlock Case1 : T1 -> T2 -> T4 -> T1

Deadlock Case2 : T1 -> T2 -> T3 -> T4 -> T1

 

Several Instance

Available	사용 가능한 자원
Allocation	각 프로세스가 점유한 자원
Request	각 프로세스가 요청 중인 자원

 

초기화

• Work = Available
• Finish[i] = false for all processes Pi (초기에는 완료되지 않은 상태)

프로세스 탐색

• Finish[i] = false이고, Request[i] <= Work인 프로세스 Pi를 찾음. (실행 가능한 프로세스)
  
  • Work = Work + Allocation[i] -> 자원 반환
  • Finish[i] = true -> 완료 상태로 업데이트

모든 프로세스에 대해 위 과정 반복

 

Finish[i] = false 인 프로세스가 있다면 해당 프로세스는 Deadlock 상태

 

더 자세히 공부하기 (클릭)

Simple Detection Algorithm

 

T0부터 T4까지 5개의 스레드, 3개의 Resource A, B, C = [7, 2, 6]

Sequence : <T0, T2, T3, T1, T4>로 가정

 

 

Sequence[0] : T0 실행 가능 여부

Request[0] = [0, 0, 0] <= Available = [0, 0, 0]

T0은 요청없이 실행 가능

 

Available += Allocation[0] = [0, 1, 0]
Finish[0] = true

 

Squence[1] : T2 실행 가능 여부

Request[2] = [0, 0, 0] <= Available = [0, 1, 0]

T2은 요청없이 실행 가능

Available += Allocation[2] = [3, 1, 3]
Finish[2] = true

 

Squence[2] : T3 실행 가능 여부

Request[3] = [1, 0, 0] <= Available = [3, 1, 3]

T3은 실행 가능

Available += Allocation[3] = [5, 2, 4]
Finish[3] = true

 

Squence[3] : T1 실행 가능 여부

Request[1] = [2, 0, 2] <= Available = [5, 2, 4]

T1은 실행 가능

Available += Allocation[1] = [7, 2, 4]
Finish[1] = true

 

Squence[4] : T4 실행 가능 여부

Request[4] = [0, 0, 2] <= Available = [7, 2, 4]

T4는 실행 가능

Available += Allocation[4] = [7, 2, 6]
Finish[4] = true

 

 Safe Squence

<T0, T2, T3, T1, T4>은 Safe State이며, 모든 프로세스가 실행을 완료할 수 있으므로, Deadlock이 없다. 

 

---

 

Deadlock Recovery

Deadlock 복구 방법은 아주 간단하다. 자원을 가지거나, 가지지 못하면 프로세스가 죽으면 된다.

 

1. Process Termination
   • Abort All Deadlocked Processes: Ensures quick recovery but at a high cost (loss of progress).
   • 모든 교착 프로세스를 종료하면 되지만, 높은 비용이 든다.
   • Abort One Process at a Time: Iteratively terminate one process and re-run the detection algorithm. Higher overhead but minimizes loss.
   • 한 번에 하나의 프로세스를 종료하며 교착 상태 탐지를 반복하면 비용은 적게 들겠지만, 오버헤드가 발생
2. Resource Preemption
   • Select a vitcim: Choose a process to preempt resources from, minimizing overall cost.
   • 교착 상태를 해소하기 위해 자원을 강제로 회수
   • Rollback: Return the process to a safe state, restarting if necessary.
   • 프로세스를 이전 안전 상태로 복구
   • Starvation Avoidance: Prevent selecting the same process repeatedly by considering the number of rollbacks.
   • 동일한 프로세스가 반복적으로 선택되지 않도록 설정

Some factors that affect which threads are chosen to be aborted:

In which order should we choose to abort?

1. Priority of the thread

2. How long has the thread computed, and how much longer to

completion

3. Resources that the thread has used

4. Resources that the thread needs to complete

5. How many threads will need to be terminated

6. Is the thread interactive or batch?

---

 

aspect	avoidance	detection	recovery
when	system dynamically avoids unsafe states	deadlock may occur; need detection	after detecting deadlock
mechanism	Banker's Algorithm	Wait-for Graph or resource tracking	Terminate process or Preempt resources
outcome	No deadlocks	Detects deadlocks	Resolves deadlocks

 

HAND~