Deadlock-데드락

Deadlock (=교착상태)

• 더 이상 방법이 없는 상황
• 일련의 프로세스들이 각자 갖고 있는 자원을 놓지 않고 상대방이 가진 자원을 요구하는 상태

 

The Deadlock Problem

• Deadlock
  • 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
• Resource(자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) I/O device, CPU cycle, memory space, semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request, Allocate, Use, Release
• Deadlock Example 1
  • 시스템에 2개의 tape drive가 있다.
  • 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.
• Deadlock Example 2
  • Binary semaphores A and B
  

 

Deadlock 발생의 4가지 조건

• Mutual exclusion (상호배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption (비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait (보유 대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait(순환 대기)
  • 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
  • 예를 들어
    1. 프로세스 P0, P1,... Pn이 있을 때
    2. P0은 P1이 가진 자원을 기다림
    3. P1은 P2가 가진 자원을 기다림
    4. Pn-1은 Pn이 가진 자원을 기다림
    5. Pn은 P0이 가진 자원을 기다림

 

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

• Vertex
  • Process P = {P1, P2,..., n}
  • Resource R = {R1, R2,..., Rm}
• Edge
  • request edge Pi → Rj
  • assignment edge Rj → Pi
  
• 그래프에 cycle이 없으면 deadlock이 아니다
• 그래프에 cycle이 있으면
  • if only one instance per resource type, then deadlock
    • 오른쪽 위와 같은 경우, instance는 하나가 아니지만 모든 instance가 cycle을 갖고 있으므로 deadlock이라고 볼 수 있다.
  • if several instances per resource type, possibility of deadlock
  
  
  • 위 경우는 여분의 자원이 있고, P2, P4는 cycle에 속해있지 않기 때문에 deadlock이 아니다.

 

Deadlock의 처리 방법

위에 있을수록 더 강한 방법이다.

1. Deadlock이 생기기 전에 방지
   1. Deadlock Prevention
      • 자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
   2. Deadlock Avoidance
      • 자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원을 할당
      • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
2. Deadlock이 생긴 후 조치
   1. Deadlock Detection and recovery
      • 시스템이 느려지거나 이상이 발생했다고 판단되면 Deadlock을 찾고 recovery
      • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두고 deadlock 발견 시 recover
   2. Deadlock Ignorance
      • Deadlock이 생겨도 어떠한 조치도 하지 않음
      • Deadlock을 시스템이 책임지지 않음, 사람이 프로세스를 죽이거나 하는 등의 조치
      • UNIX를 포함한 대부분의 OS가 채택

 

Deadlock Prevention

• Utilization 저하, Throughput 감소, Starvation 문제 발생 가능
• 생기지도 않은 Deadlock을 미연에 방지하기 위해 설정한 제약조건 인해 비효율적임
• 4가지 조건의 처리
  • Mutual Exclusion
    • 공유해서는 안 되는 자원의 경우 반드시 성립해야 함
    • 처리할 수 있는 조건이 아님.
  • Hold and Wait
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
    • 처리방법
      1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 (자원에 대한 비효율성 높음)
      2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
  • No Preemption
    • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
    • State를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용 (CPU, memory)
    • 중간에 자원을 뺏기면 작업이 엉망이 되는 프로세스에는 처리방법을 적용할 수 없음
    • 처리방법
      1. Preemption을 가능하게 함. 대신, save와 restore를 용이하게 해야 함.
  • Circular Wait
    • 필요한 자원들이 꼬리에 꼬리를 물고 cycle을 형성한 경우
    • 처리방법
      1. 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
         • 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 위해서는 우선 Ri를 release 해야 함.

 

Deadlock Avoidance

• 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전한 지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• 시스템이 unsafe state에 들어가지 않는 것을 보장
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence <P1, P2,... , Pn>이 safe 하려면 Pi(1 ≤ i ≤ n)의 자원 요청이 “가용 자원 + 모든 Pj ( j < i )의 보유 자원”에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi의 자원 요청이 즉시 충족될 수 없으면 Pj( j <i )가 종료될 때까지 기다린다.
    • Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다.
• 시스템이 safe state에 있으면 → no deadlock
• 시스템이 unsafe state에 있으면 → possibility of deadlock
• 2가지 알고리즘
  1. Single instance per resource types → Resource Allocation Graph algorithm 사용
  2. Multiple instances per resource types → Banker’s Algorithm 사용

 

Resource Allocation Graph algorithm

• Claimn edge Pi → Rj
  • 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함 (점선)
  • 프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
  • Rj가 release 되면 assignment edge는 다시 claim edge로 바뀐다.
• request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
• Cycle 생성 여부 조사 시 프로세스의 수가 n일 때 O(n^2)의 시간이 걸린다.

*두 번째 그림의 경우 P2는 R2에게 requests를 하지만 cycle이 생길 우려가 있기 때문에 할당되지 않음

**제일 오른쪽의 경우, P1 → R2가 실선이 될 수도 있기 때문에 unsafe지만 deadlock은 아님.

***만약 P1→R2가 실선으로 변한다면 그 시점부터 deadlock 발생

 

Example of Banker’s Algorithm

• Allocation : 이미 할당된 자원의 양
• Max : Proces가 최대 필요로 하는 양
• Available : 전체 resource (A:10, B:5, C:7) - Allocation( A:(0+2+3+2+0), B:(1+0+0+1+0), C:(0+0+2+1+2))
• Need : 추가로 필요한 양 (Max - Allocation)
• Available이 있다고 무조건 할당받는 것은 아님. 가용자원으로 최대 필요한 양을 충족시키지 못하면 자원을 나누어주지 않음. 항상 최악의 경우를 고려하기 때문
  • 예를 들어, P0가 (A:0 B:2 C:0)을 요청하였을 때, Available 하지만 Need에는 부족하기 때문에 다른 프로세스가 Available로 작업을 완수하고 자원을 추가로 반납할 때까지 기다리게 됨

 

Deadlock Detection and Recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • Banker’s algorithm과 유사한 방법 활용
    
  • Graph
  
  • (a) : Resource-Allocation Graph
  • (b) : Corresponding wait-for grpah
  • 자원의 최대 사용량을 미리 알릴 필요 없음 → 그래프에 점선이 없음
• Wait-for graph 알고리즘
  • Resource type 당 single instance인 경우
    • Wait-for graph
      • 자원할당 그래프의 변형
      • 프로세스만으로 node 구성
      • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk→Pj
    • Algorithm
      • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
      • O(n^2)
• Recovery 2 way
  • Process termination (프로세스 종료)
    • Abort all deadlocked processes → deadlock이 걸린 프로세스들을 전부 죽임
    • Abort one process at a time until the deadlock cycle is eliminate → deadlock cycle에 속한 프로세스를 하나씩 죽임
  • Resource Preemption (자원 빼앗기)
    • 비용을 최소화 할 victim의 선정
    • safe state로 rollback 하여 process를 restart
    • Starvation 문제
      • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려
      • Starvation문제를 해결하기 위해 자원을 뺏는 루틴도 중요

 

Deadlock Ignorance

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

 

 

 

 

 

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>

•