[OS][운영체제] 7. Deadlocks / 데드락

1. The Deadlock 문제
2. Deadlock Characterization (빠지기 위한 4가지 조건)
3. 시스템 모델
4. 데드락 Handling 방법
5. 데드락 Prevention
6. 데드락 Avoidance
7. 데드락 Detection
8. 데드락 Recovery

---

1. The Deadlock 문제

The Deadlock: 각각 하나의 자원을 가지고 있고, 상대의 자원을 기다리고 있는 상황을 말한다.

이는 서로 양보를 하지 않아 계속 기다리는 상황이다.

[사진 1] Deadlock

- Bridge Crossing: 누군가 후진을 해야 (preempt resources and rollback) 풀리는 문제 상황이다.

[사진 2] Bridge Crossing

-> Starvation 문제도 생길 수 있다

2. Deadlock Characterization (4가지 조건)

• Mutual Exclusion
  • : 한 자원을 한 시에 한 프로세스가 사용할 수 있다
• Hold and Wait
  • : 최소 하나의 자원을 잡고 있는 프로세스가 다른 프로세스의 자원을 얻기 위해 기다린다
• No Preemption
  • : 프로세스가 작업을 끝낸 뒤에 released 된다
• Circular Wait
  • : P1은 P6의 자원을 요청, P6는 P3의 자원을 요청, P3는 P4의 자원을 요청, P4는 P1의 자원을 요청하여 기다리는 상태

[사진 3] Circular Wait

3. 시스템 모델

- 자원 유형: CPU, 메모리, I/O, 파일 등

- 한 자원(R)의 유형에는 여러 인스턴스(W)가 있다.

- 프로세스는 자원을

1. Request
2. Use
3. Release

한다.

 

- 프로세스 P와, 자원의 유형 R을 점으로 표현하고(그 안에 인스턴스 표현),

‘어느 프로세스가 어느 자원을 요청하는가’ / ‘어느 자원이 어느 프로세스에 할당 되어 있는가’는 화살표로 표현한다.

 

ex1)

[사진 4] System Model 예시

빨간색 선 - Loop

파란색 선 - P2 P3 closed Loop

• 상호 배제
  • : 한 시에 한 자원을 한 프로세스가 사용한다
• Hold N Wait
  • : 이미 갖고 있는 자원과, 요청한 자원을 기다린다
• No Preemption
  • : O
• Circular Wait
  • : 빨간색, 파란색 closed loop

 

ex2)

[사진 5] System Model 예시

• Hold N Wait: 필요한 자원을 모두 확보한 P2와 P4에 의해 만족이 안 된다.

(P2가 반납하면 P1이 가져가 쓰고, P4가 반납하면 P3가 가져가 쓴다.)

-> No Deadlock

4. 데드락 Handling 방법

• Prevention & Avoidance (5)
  • : deadlock state에 들어가지 못하도록 한다
• Detect then Recovery (6)
  • : deadlock state에 들어가지 못하게 하는 방법은 많은 오버헤드를 발생시킨다
  • : 중요한 어플리케이션을 돌린다면 최소의 하나 방법을 이용하고,
  • : 그게 아니라면 deadlock state를 허용하고 recover한다 

5. 데드락 Prevention

4가지 조건 중 하나를 깨준다

• 상호 배제
  • : 공유할 수 없는 자원이라면 가능하다
• Hold N Wait
  • : 할당한 자원이 없을 때 자원을 요청할 수 있도록 한다
  • : or 어떤 프로세스가 실행하기 전에 모든 자원을 확보하고 실행한다
  • -> 자원 활용도가 낮고, starvation 문제가 생길 수 있다
• No Preemptive
  • : 프로세스가 자원을 요청할 때 할당이 안 된다면, 할당된 모든 자원을 놔준다(released)
• Circular Wait
  • : 모든 유형의 자원에 할당된 번호의 순서대로 자원을 요청할 수 있다

6. 데드락 Avoidance

가장 간단하고 많이 쓰이는 모델은 자원을 최대 몇 개까지 쓸 것인지 정하는 모델이다.

Deadlock-Avoidance 알고리즘은 주기적으로 자원 할당 상태를 체크하여 Circular-Wait에 빠지지 않게 한다.

사용 가능한 자원, 할당된 자원, 최대 몇 개까지의 자원인지에 대해 자원 할당 상태가 정의된다.

Safe State

모든 프로세스들을 처리해줄 수 있는 Safe sequence가 있으면 Safe state이다.

 

Pi 입장에서 처리 sequence가 safe하다는 ‘시스템에 여유 있는 자원’ + ‘먼저 처리되는 프로세스들에 의해 요청하는 자원’을 만족시킬 수 있음을 말한다.

unsafe state이면 데드락에 빠질 가능성이 있음을 의미한다.

-> Avoidance: unsafe state가 안 되도록 함

[사진 6] unsafe/safe state

Resource-Allocation Graph 알고리즘

자원을 요청할 것 같다는 Claim edge로, 점선으로 표시한다.

-> 실선 -> 반대 실선 -> 점선 복원

[사진 7] Claim edge

- 만약 그래프가 cycle을 포함한다면 Unsafe State에 들어가게 된다.

[사진 8] cycle graph

Banker’s 알고리즘

인스턴스가 여러 개일 때 적용하는 알고리즘이다.

각 프로세스들은 자원을 최대 몇 개 사용할 건지(Max) 사전에 알려야 한다.

또, 프로세스들은 자원을 얻기 전에 기다리고, 정해진 시간 내에 반납(Allocation 반납)해야 한다.

 

데이터 구조는 다음과 같다.

• Available (Available[j] = k)
  • : 자원의 여유분 / j의 유형을 k 만큼 여유로 가지고 있음
• Max (Max[I, j] = k)
  • : Pi가 Rj 유형을 최대 k개까지 요청한다
• Allocation (Allocation[i, j] = k)
  • : Pi가 Rj를 k개 할당 받는다
• Need (Need[i, j] = k)
  • : Pi가 작업을 완료하는 데에 Rj를 k개 필요로 한다
  • : Need = Max - Allocation

Banker's Safety 알고리즘

1. 초기화
   1. Work = Available
   2. Finish[i] = false
2. 조건
   1. Finish[i] = false && Need (i) <= Work
3. 실행
   1. Work += Allocation (i)
   2. Finish[i] = true
4. 끝
   1. 모든 i에 대해 Finish[i] == true이라면, 시스템 in Safe state

 

예시는 다음 사진을 보자.

[사진 9] Safety 알고리즘

T0의 한 snapshot이 빨간 점선 박스라고 하자.

Max - Allocation으로 Need 값을 구한다.

->

P0) Available 자원 수는 3 3 2이고, 이는 P0 Need를 충족시키지 못한다

P1) P1의 Need는 충족시켜 Need만큼의 자원을 사용하고 반납한다. 할당되었던 자원을 모두 반납하여 Available 자원 수는 5 3 2이다

P2) P2 Need를 충족시키지 못한다

P3, P4) P1과 같은 방법으로 프로세스 처리 -> Available 자원 수는 7 4 5이다

P0, P2) 프로세스 처리

->

시스템은 1 - 3 - 4 - 2 - 0 혹은 1- 3 - 4 - 0 - 2 sequence에서 Safe state에 있다.

이는 순서보다 모든 프로세스가 처리된다는 것이 중요하다.

Banker's Resource-Request 알고리즘

1. 프로세스 i의 Request <= Need?
2. Request <= Available?
3. 할당했다고 Pretend(가정) 후에 1. Safety 알고리즘 적용
   1. : unsafe면 wait 하고 옛날 값으로 다시 복원시킴

Pretend는 다음과 같다.

• Available -= Request;
• Allocation += Request ;
• Need -= Request;

 

예시로 P1이 (1, 0, 2)를 Request 할 때, 다음 사진을 보자.

 

[사진 10] Resource Requset 알고리즘

1. (1, 0, 2) <= (1, 2, 2)
2. (1, 0, 2) <= (3, 3, 2)
3. Available -= Request, Allocation += Request, Need -= Request 한 후,
4. Safety 알고리즘 진행

7. 데드락 Detection

데드락 Prevention & Avoidance와 달리 데드락 상태를 허용한다.

Wait-for Grapg를 유지하고,

주기적으로 알고리즘을 돌려 cycle이 존재하면 데드락 상태에 빠짐

노드(프로세스)의 개수 n일 때 알고리즘을 돌릴 때 O(n^2)의 오버헤드를 발생시킨다.

[사진 11] Resource-Allocation/Wait-for Gpaph

(a): Resource-Allocation Graph

(b): Wait-for Graph

위 사진은 인스턴스의 개수가 각 하나일 때, cycle로 인해 deadlock 상태이다.

인스턴스가 여러 개일 때 Detection 알고리즘

1. 초기화
   1. : 길이 m의 Work = Available
   2. : 길이 n의 Finish[i] = false (Allocation != 0), Finish[i] = ture (Allocation == 0)
2. 조건
   1. : Request <= Work
   2. : Finish[i] == false
3. 실행
   1. : Work += Allocation
   2. : Finish[i] = true
4. 끝
   1. : If (Finish[i] == false), then Pi는 데드락 상태이다

이는 O(m * n^2)의 오버헤드를 발생시킨다.

 

예시로는 다음 사진과 같다.

[사진 12] Deadlock Detection 알고리즘

이 때, P2의 Request가 0 0 1이라면, 이는 데드락이 발생한다. (P1, P2, P3, P4)

 

- 데드락이 얼마나 일어나는지, 프로세스가 얼만큼 관여됐는지에 따라 Detection 알고리즘 사용이 달라진다.

8. 데드락 Recovery

1. Process Termination

• 모든 데드락 프로세스 종료
• 프로세스를 하나씩 종료(abort)
  • : Priority / 작업 기간 / Resource를 얼마나 사용하는지 / need Resource / 얼마나 많은 프로세스를 종료해야 하는지 / interactive or batch 프로세스 인지
  • : 등을 고려하여 종료할 프로세스를 선택

2. Preemption

자원을 빼앗아 오는 방법

• Selecting a victim
  • : cost(희생)을 최소화
• Rollback
  • : safe state로 돌아가 재시작
• Starvation
  • : 동일한 프로세스의 희생양으로 선택될 수 있는 횟수를 정해줄 수 있음