데드락

교착상태(Deadlock)

정의

✨ 데드락이란? → 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 되어 더 이상 진행이 될 수 없는 상태

✨ Resource (자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• (예) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  ✓ Request, Allocate, Use, Release

✨ Deadlock Example 1

• 시스템에 2개의 tape drive가 있다.
• 프로세스 P과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다

✨ Deadlock Example 2

• Binary semaphores A and B

   P₀                P₁
  P(A);             P(B);
  P(B);             P(A);

Deadlock 발생의 4가지 조건

✨ Mutual exclusion(상호 배제)

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• Critical Section Problem을 해결하기 위해서는 반드시 만족해야 하는 조건. 공유자원이 존재한다면 이 조건은 만족시킬 수밖에 없다.

✨ No preemption(비선점)

• 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

✨ Hold and wait(보유 대기)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

✨ Circular wait(순환 대기)

• 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
• 프로세스 P₀ , P₁...... Pₙ 이 있을 때

    P₀은 P₁이 가진 자원을 기다림
    P₁은 P₂가 가진 자원을 기다림
    Pₙ₋₁은 Pₙ 이 가진 자원을 기다림
    Pₙ은 P₀ 이 가진 자원을 기다림

💡 4가지 조건을 모두 만족해야 데드락이 생긴다

Resource-Allocation Graph(자원 할당 그래프)

• 프로세스 간의 관계를 그래프로 도식화해 보면 데드락이 발생할지 예상할 수 있다. 이 그래프를 Resource-Allocation Graph(자원 할당 그래프)라고 한다. 예시를 하나 살펴보자.

  

R = 리소스 P는 프로세스 R 내의 동그라미는 인스턴스의 개수

💡 그림 1,2 는 데드락일까 아닐까?
Answer
→ 그림1은 R2의 인스턴스 두개가 전부 사이클을 형성되서 데드락이 걸린다.
→ 그림2는 P1과 P3가 사이클을 이루었지만 R2와 R1에서 다른 각각의 인스턴스가 할당된 P4, P2의 작업이 끝이나면 사이클이 풀리기 때문에 데드락이 이니다.

• 그래프에 cycle이 없으면 deadlock이 아니다
• 그래프에 cycle이 있으면
  ✓ if only one instance per resource type, then deadlock
  ✓ if several instances per resource type, possibility of deadlock

Deadlock의 처리 방법

💡 위의 두가지 방법은 데드락을 방지 한다. 밑의 두가지 방법은 데드락을 나둠

✨ Deadlock Prevention (데드락 방지)

• 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

✨ Deadlock Avoidance (데드락 회피)

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

✨ Deadlock Detection and recovery (데드락 감지 및 복구)

• Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

✨ Deadlock Ignorance (데드락 무시)

• Deadlock을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention (데드락 방지)

1. Mutual Exclusion
→ Critical Section Problem을 해결하기 위해서는 이 조건은 반드시 만족해야 하므로 공유자원이 존재한다면 이 조건을 방지할 수 없다.
→ 공유해서는 안되는 자원의 경우 반드시 성립해야 함.

2. Hold and Wait
→ 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 해야 한다.
방법 1. 따라서 프로세스를 시작할 때 모든 필요한 자원을 할당받게 하거나,
방법 2. 자원이 필요한 경우 보유하고 있던 자원을 모두 반납하고 다시 요청하는 방식을 이용할 수 있다.

3. No preemption
→ process가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 선점된다.
→ 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
→ State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)

4. Circular wait
→ 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

🏴 하지만 이 방법은 Utilization(효율성) 저하, throughput(처리량) 감소, starvation문제를 가짐.

Deadlock Avoidance (데드락 회피)

✨ 정의

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당. 즉 Deadlock이 발생할 가능성이 있는 경우엔 자원을 할당하지 않는 방식

• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임

📌 safe state

• 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

📌 safe sequence

• 프로세스의 sequence<P₁, P₂.....Pₙ>이 safe하려면 Pᵢ(1<=i<=n)의 자원 요청이
  "가용 자원 + 모든 Pj( j < i )의 보유 자원" 에 의해 충족되는 경우 sequence를 safe하다고 말한다.
• 현재가 안전하다

✨ 시스템이 safe state에 있으면 → no deadlock

✨ 시스템이 unsafe state에 있으면 → possibility of deadlock

✨ Deadlock Avoidance

• 시스템이 unsafe state에 들어가지 않는 것을 보장

✨ 2가지 경우의 avoidance 알고리즘

• Single instance per resource types
  ✓ Resource Allocation Graph algorithm 사용
• Multiple instances per resource types
  ✓ Banker's Algorithm 사용

Resource Allocation Graph algorithm

• Claim edge Pᵢ → Rj
  ✓ 프로세스 Pᵢ 가 자원 Rj 를 미래에 요청할 수 있음을 뜻함 (점선으로 표시)
  ✓ 프로세스가 해당 자원 요청시 request edge로 바뀜 (실선)
  ✓ 프로세스가 해당 자원을 받으면 assignment edge(실선)로 바귐
  ✓ Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다.
  assignment edge : 프로세스가 자원을 다시 돌려주는 방향
request edge : 프로세스가 자원을 요청하는 방향
Claim edge : 미래에 이 프로세스가 자원을 요청할 수 있음

• request edge의 assignment edge 변경시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.

• Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n²) 시간이 걸린다

그림의 상황은 unsafe한 상황이다.

Banker's Algorithm

• 비록 리소스의 여유가 있다 하더라도, Process가 요청할 수 있는 최대 요청 자원이 available resource보다 많다면 할당하지 않는다.
• Available resource가 process의 최대 요청 자원보다 클때 자원을 할당해준다.

Deadlock Detection and recovery (데드락 감지 및 복구)

✨ Deadlock Detection

• Deadlock이 발생했는지는 Deadlock을 미리 회피하는 방법과 유사하게 확인할 수 있다.

• Resource type 당 single instance인 경우
  ✓ 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  ✓ 그래프를 통해서 사이클이 생겼는지를 확인

• Resource type 당 multiple instance인 경우
  ✓ Banker's algorithm 과 유사한 방법 활용
  ✓ 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스가 존재하지 않는다는 것을 이용

✨ 데드락 Recovery 방법

1. Process termination(프로세스 종료)

• Abort all deadlocked processes (프로세스를 한번에 다 죽이는 방법)

• Aobrt one process at a time until the deadlock cycle is eliminated (데드락이 해결될 때 까지 프로세스를 하나씩 죽이는 방법)

• Deadlock을 해결하기 위해 어떤 프로세스를 종료시켜야 할까?
  여기에는 몇 가지 판단 기준이 있다.

 1. 프로세스의 중요도
 2. 프로세스가 얼마나 오래 실행됐는가
 3. 얼마나 많은 자원을 사용했는가
 4. 프로세스가 작업을 마치기 위해 얼마나 많은 자원이 필요한가
 5. 프로세스가 종료되기 위해 얼마나 많은 자원이 필요한가
 6. 프로세스가 batch인가 interactive인가

2. Resource Preemption(자원을 빼앗는 방법)

• 비용을 최소화할 victim의 선정
• 안전한 상태(Deadlock이 발생하기 전)으로 rollback 후 process restart
• 이때 Starvation 문제가 생길 수 있다.
  ✓ 동일한 프로세스가 계속해서 victim으로 선정되는 경우
  ✓ cost factor에 rollback 횟수도 같이 고려

✨ Wait-for graph 알고리즘

• Resource type single instance인 경우

• Wait-for graph
  ✓ 자원할당 그래프의 변형
  ✓ 프로세스만으로 node 구성
  ✓ Pᵢ가 가지고 있는 자원을 Pₓ가 기다리는 경우 Pₓ→ Pᵢ

• Algorithm
  ✓ Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  ✓ O(n²)

Single Instance에서의 데드락 확인

• 리소스를 빼버리고 Process로만 자원의 이동을 간략하게 나타낸 Wait-for 그래프를 만들어 데드락 디텍션에서는 확인을 한다.
• 데드락 디텍션은 자원이 나중에 요청할 것을 알 필요가 없다. 왜냐면 데드락이 걸리는것을 방지하지 않기 때문이다. 걸리면 걸리는데로 나두기 때문에 현재의 상태만을 체크할 뿐이다.

Multi Instance에서의 데드락 확인

• 데드락 디텍션에서는 프로세스의 최대 요청량을 알 필요가 없다.
• 이 방법은 현재 데드락인가 아닌가를 확인한다.
• 밑의 그림은 데드락이 아닌데, P₀나 P₂가 일을 끝내서 자원을 반납하면 가용 자원으로 모든 일을 처리 할 수 있기 때문이다.
• 만약 P₂가 C를 하나 필요로 한다면? 그것은 데드락이 된다. 그렇다면 Recovery 시스템이 작동할 것이다.
  

Deadlock Ignorance(데드락 무시)

✨ Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음.
• 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
• UNIX, Windows 등 대부분의 범용 OS가 채택

결론

📌 데드락은 굉장히 고전적인 문제이다. 현재는 점점 중요도가 줄어 드는 문제. 따라서 현대의 범용체제는 대부분 Deadlock을 Ignorance하고 있다.