데드락 (Deadlock)

교착상태라고도 불리는 데드락을 알아보도록 하겠습니다.

 

데드락은 어느 프로세스도 일을 할 수 없는 상태를 말합니다.

 

Process 상태
Blocked/Asleep state : 프로세스가 특정 이벤트를 기다리는 상태

 

Deadlock 상태
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우입니다.

 

그렇다면 여기서 궁금한게 생깁니다. 기아 상태도 이벤트를 기다리는 경우인데 Deadlock과 무슨 차이가 있을까요?

 

Deadlock과 Starvation의 차이
Deadlock은 asleep 상태에서 자원이나 이벤트를 기다리는데 일어날 가능성이 없는 것을 기다리는 경우입니다.
Starvation은 ready 상태에서 CPU를 기다리는데 발생할 수 있는데, 계속해서 새치기를 당하는 경우입니다.

 

Deadlock은 자원과 가장 밀접한 관계를 가집니다. 그렇다면 자원을 더 알아보도록 하겠습니다.

 

자원의 일반적 분류
Hardware resources vs software resources

자원의 다른 분류 법
- 선점 가능 여부에 따른 분류
- 할당 단위에 따른 분류
- 동시 사용 가능 여부에 따른 분류
- 재사용 가능 여부에 따른 분류

선점 가능 여부에 따른 분류

• Preemptible resources
  • 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  • Processor, memory 등
• Non-preemptible resources
  • 선점 당하면, 이후 진행에 문제가 발생하는 자원
  • dist, drive (데이터 기록을 하다가 뺏어가서 그 데이터를 수정해버리면 데이터에 문제가 생기기 때문입니다)

할당 단위에 따른 분류

• Total allocation resources
  • 자원 전체를 프로세스에게 할당
  • Processor, disk drive 등
• Partitioned allocation resources
  • 하나의 자원을 여러 조작으로 나누어, 여러 프로세스들에게 할당
  • Memory 등

동시 사용 가능 여부에 따른 분류

• Exclusive allocation resources
  • 한 순간에 한 프로세스만 사용 가능한 자원
  • Processor, memory (한 프로세스 만을 위한 메모리니까요), disk drvie 등
• Shared allocation resource
  • 여러 프로세스가 동시에 사용 가능한 자원
  • Program (크롬을 동시에 5개 띄울 수 있는 것과 똑같이 생각하면 됩니다), shared data 등

재사용 가능 여부에 따른 분류

• SR (Serially-reusable Resources)
  • 시스템 내에 항상 존재 하는 자원
  • 사용이 끝나면, 다른 프로세스가 사용 가능
  • Processor, memory, disk, program
• CR (Consumable Resources)
  • 한 프로세스가 사용한 후에 사라지는 자원
  • signal, message

---

Deadlock을 발생시킬 수 있는 자원의 형태

• Non-preemptible resources => 절대 안 뺏기니까요.
• Exclusive allocation resources => 절대 혼자 쓰니까요.
• Total, partitioned allocation => 사실 크게 관리가 없습니다.
• SR, CR은 좀 어려워서 고려하지 않습니다.

---

Deadlock 발생의 예

• 2개의 프로세스와 2개의 자원을 가지고 있습니다. (P1, P2, R1, R2)
• P1이 R2를 가지고 R1을 요청하고, P2는 R1을 가지고 R2를 요청하는 경우에 발생합니다. 서로가 가진 걸 원하고, 그게 사이클이 생성이 되면 데드락이 발생합니다.

Deadlock Model(표현법)

• Graph Model
  • Node => 프로세스 노드, 자원 노드 (P1, P2, R1, R2)
  • Edge
    • Rj => Pi : 자원 Rj이 프로세스 Pi에 할당 됨
    • Pi => Rj : 프로세스 Pi가 자원 Rj를 요청 함
• State Transition Model

Deadlock 발생 필요 조건 (밑의 4개가 모두 성립해야 Deadlock이 발생 !!!)

• Exclusive use of resources => 자원의 특성
• Non-preemptible resources => 자원의 특성
• Hold and wait (Partial allocation) => 프로세스의특성
  • 자원 하나 hold하고 다른 자원 요청
• Circular wait => 프로세스의특성
  • 사이클이 생길 때

 

위 4가지가 모두 만족해야 데드락이 발생합니다. 꼭, 꼭 기억합시다 !!

---

Deadlock 해결 방법

저희는 앞서 Deadlock 발생 필요 조건을 4가지 말했습니다. 저 4가지가 모두 성립해야 Deadlock이 발생한다면 그 중 하나만 제거하면, Deadlock을 해결 할 수 있다는 말입니다.

• Deadlock prevention methods
  • 교착상태 예방
• Deadlock avoidance methods
  • 교착상태 회피
• Deadlock detection and deadlock recovery methods
  • 교착상태 탐지 및 복구

Deadlock Prevention (교착상태 예방)

• 4개의 deadlock 발생 중 필요 조건 중 하나를 제거
  • Exclusive use of resources
  • Non-preemptible resources
  • Hold and wait
  • Circular wait
• Deadlock이 절대 발생하지 않습니다.
• 모든 자원을 공유 허용
  • Exclusvie of resrouces 조건 제거
  • 현실적으로 불가능
• 모든 자원에 대해 선점 허용
  • Non-preemptible resources 조건 제거, 모든 자원에 선점을 허용하는 것입니다.
  • 현실적으로 불가능, 많은 문제가 발생할 수 있습니다.
  • 유사한 방법으론 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소하는 방법이 있습니다. 단, 이렇게 하면 일하던 것들을 전부 포기하는 것이기 때문에 일한다고 사용한 자원들이 모두 아깝게 버려지는 것입니다.
• 필요 자원을 한번에 모두 할당 받자 (Total allocation)
  • Hold and wait 조건 제거
  • 자원 낭비 발생
    • 필요하지 않은 순간에도 가지고 있습니다.
  • 나머지 애들이 무한 대기 현상 발생 가능
• Circular wait 조건 제거
  • Totally allocation을 일반화 한 방법
  • 자원들에게 순서를 부여
  • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
    • R1, R2, R3, R4
    • P1 (1, 2, 4 모두 필요)
    • P2 (1, 3 모두 필요)
    • P1이 먼저 하면 P2는 P1이 쓰고 있는 1을 못 쓰기 때문에 P2가 실행이 안됩니다. 그렇다면 놀고 먹는 자원인 3은 어떻게 될까요?? 그냥 놀게 됩니다.
  • 자원 낭비 발생
• Deadlock prevention은 비현실적이고 자원 낭비가 심합니다. 그렇기에 자원을 아끼면서 Deadlock을 해결하는 방법을 아래에서 다뤄봅시다.

Deadlock avoidance method (교착상태 회피)

• 시스템의 상태를 계속 감시
• 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state로 유지

Safe state

• 모든 프로세스가 정상적으로 종료 가능한 상태
• Safe sequence가 존재하느냐? 존재해야 Safe state입니다.
  • Deadlock 상태가 되지 않을 수 있음을 보장

Unsafe state

• Deadlock 상태가 될 가능성이 있음 (반드시 되는건 아님)

가정

• 프로세스의 수가 고정된다.
• 자원의 종류와 수가 고정된다.
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있다.
• 프로세스는 자원을 사용 후 반드시 반납한다.
• (사실 비현실적인 가정입니다)

Deadlock Avoidance 방법

• Dijkstra's algorithm (Banker's algorithm)
  • Deadlock avoidance를 위한 간단한 이론적 기법
  • 가정
    • 한 종류(resource type)의 자원이 여러 개(unit)
  • 시스템을 항상 safe state로 유지
  • 제가 10만원을 가지고 있고, 친구 3명이 이미 돈을 빌린 상태에서 또 돈을 빌릴려고 합니다. 이러한 상황에서 누가한테 빌려줄까요? 가 Banker's algorithm 입니다.
• Habermann's algorithm
  • Dijkstra's algorithm의 확장
  • 한 종류의 자원이 아닌 여러 종류의 자원이 존재합니다.
  • 시스템을 항상 safe state로 유지합니다.
• Deadlock의 발생을 막을 수 있습니다.
• High overhead
  • 항상 시스템을 감시하고 있어야 합니다.
• Low resource utilization
  • safe state 유지를 위해, 사용 되지 않는 자원이 존재합니다.
• 비현실적인 방법입니다. (가정을 해야하니까요)

그럼 이제는 데드락을 허용하고 탐지하고 복구하는 방법은 어떨까요?

---

Deadlock detection and deadlock recovery methods

• Deadlock 방지를 위한 사전 작업을 하지 않습니다.
• 주기적으로 deadlock 발생 확인합니다.
  • Resource Allocation Graph(RAG)를 사용합니다.
  • RAG란?
    • 방향성이 있는 그래프입니다.
    • 프로세스와 자원으로 나눈 그래프입니다. 프로세스와 프로세스끼리는 연결 안됩니다. 물론 자원도 마찬가지입니다.
    • G = {N, E}
      • N은 노드를 가진 집합입니다. {P1, P2, P3 .... }, {R1, R2, R3 ... }
      • Edge는 Np 와 Nr 사이에만 존재합니다. e = (P, R) : 자원 요청 / e = (R, P) : 자원 할당
      • Rk는 k type의 자원, tk는 k 자원이 몇 개 있는지를 나타냅니다.
• Graph Reduction
  • 주어진 RAG에서 edge를 하나씩 지워가는 방법
  • Edge가 다 지워지면 Deadlock이 아닙니다.
  • 지울 수 없는 edge가 존재하면 Deadlock 입니다.
• 어떤 Edge를 지울까요?
  • Unblocked Process에 연결된 Edge를 지우면 됩니다.
    • Unblocked Process : 필요한 자원을 모두 할당 받을 수 있는 프로세스
• GrapheReduction은 검사 주기에 영향을 받고 Node의 수가 많은 경우엔 High Overhead가 발생합니다.
• Deadlock avoidance
  • 최악의 경우를 생각
    • 앞으로 일어날 일을 고려
  • Deadlock이 발생 하지 않음
• Deadlock detection
  • 최선의 경우를 생각
    • 현재 상태만 고려
  • Deadlock 발생 시 Recovery 과정이 필요합니다.
• Deadlock Recovery
  • Deadlock 상태인 프로세스 중 일부 종료 => Deadlock termination
    • 누굴 죽일까요..? 기준이 있습니다. 그 기준을 cost model이라고 하고, 그 기준은 다양합니다
      • 종류가 될 수 있고, 우선순위가 될 수 있고, 총 수행 시간, 남은 시간이 있습니다.
    • Lowest termination cost process first
      • 비용이 적은 애를 죽입니다.
      • 한 번만 찾아서 비용이 낮은 애를 골라서 죽이면 되니 그닥 오버헤드가 크지 않습니다.
      • 불필요한 프로세스들이 종료될 가능성이 있습니다.
    • Minimum cost recovery
      • 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택
        • 모든 경우의 수를 고려 해야 합니다.
      • 복잡하고, 오버헤드가 큽니다. 죽이고 살리고 하니 O(n^2)입니다.
  • Rescource preemption
    • Deadlock 상태 해결을 위해 선점할 자원 선택
    • 해당 자원을 가지고 있는 프로세스를 종료 시킵니다.
      • Deadlock 상태가 아닌 프로세스가 종료 될 수 있습니다.
      • 해당 프로세스는 이후 재시작 됩니다.
      • 억울합니다.
    • 선점할 자원을 선택
      • preemption cost model이 필요
      • minimum cost recovery method 사용
        • O(r) => 하나씩 빼서 보면 되기 때문입니다.
  • Checkpoint-restart method
    
    • 프로세스의 수행 중 특정 지점마다 저장을 하는 것입니다. (Context를)
    • Rollback을 위해 사용합니다.
      • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작합니다.

---

이상 데드락 (Deadlock)였습니다. ^_^