[OS] - DeadLock

DeadLock

---

2개 이상의 Process 혹은 Thread가 서로 Resource를 얻지 못하여 다음 처리를 하지 못하는 상태

 

• 무한히 Resource를 기다리게 되는 상태 ( Wait )
• System 한정된 Resource가 여러 곳에서 사용되면 발생한다.
• 하나의 Process에서 Resource를 요청하였을 때, 동시에 Resource를 사용할 수 없는 상황이 발생 -> Process는 Wait State

 

Starvation = 식사하는 철학자

링크

 

DeadLock 발생 조건

• 4가지 모두 필수조건

1. Mutual Exclusion ( 상호 배제 )

Resource는 하나의 Process에서만 사용 할 수 있다.

 

2. Hold and wait ( 점유 대기 )

최소한 하나의 Resource를 점유, 다른 Process에 할당되어 사용하고 있는 Resource를 추가로 점유하기 위해 대기하는 Process가 존재

 

3. Non Preemptive ( 비선점 )

다른 Process에 할당된 Resource는 사용이 끝날 때까지 빼앗을 수 없다.

 

4. Circular wait ( 순환 대기 )

Process 집합에서 순환 형태의 Resource를 대기하고 있어야 한다.

 

Deadlock 처리

1. Prevention

• DeadLock 발생 조건 중 하나를 제거하여 해결 (Resource 낭비가 심각하다)
  • Mutual Exclusion 부정 = 여러 Process가 Resource 사용
  • Hold and Wait 부정 = Process 실행 전 모든 Resource를 할당
  • Non Preemptive 부정 = Resource를 다른 Process가 요구한다면 Resource 반납
  • Circular Wait 부정 = Resource에 고유 번호 할당

 

2. Avoidance

• 교착 상태 발생 시 피해나가는 방법
  • Banker's Algorithm
  • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
  • Process가 Resource를 요구 할 때, Resource를 할당한 후에도 Safe State로 남아 있는지 사전에 검사한다.
  • Safe State라면 Resource 할당 / Unsafe State 시 Process Resource 해지 대기
  • 아래의 예시에서 2개의 Resource가 남아있다면? -> p1에게 할당 후 다음 단계를 진행 할 수 없다.(Unsafe State)
  • 3개의 Resource가 남아있다면, p1에게 할당 후 p0 -> p2 순으로 Safe state 유지 가능
  • 사용자 수가 일정해야하며, Resource 수가 일정해야 합니다.
  • Unsafe state를 방지하기 위해서 Resource이용도가 낮기 때문에 실제로 사용 X

 

탐지 및 회복

• DeadLock 허용 후 발생 시 회복 시킨다.

1. Detection

• Resource 할당 그래프를 통해 Deadlock 탐지
• Resource 요청 시, 탐지 알고리즘을 실행 시켜 Overhead 발생

 

2. Recovery

Deadlock 유발한 Process 종료

• Deadlock Process 모두 중지
• Deadlock 상태가 제거 될 때까지 순차적으로 중지

Resource Premmptive

• Deadlock 상태의 Process가 점유하고 있는 Resource를 선점하여 다른 Process에게 할당( Process 일시 중지 )
• 우선 순위가 낮은 Process 혹은 수행횟수가 적은 Process 위주로 자원 선점