Deadlock

교착상태(deadlock)

각자 일부 자원을 가지고 있으면서 상대방의 자원을 내놓길 원하는 현상

The Deadlock Problem

데드락

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource

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

Deadlock Example 1

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

Deadlock 발생의 4가지 조건

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

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

데드락이 발생했는지 자원 할당 그래프를 사용하여 확인

위 그림같은 경우 사이클이 없기 때문에 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

Mutual Exclusion

• 공유해서는 안되는 자원의 경우 반드시 성립해야 함

Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
• 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
• 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

No Preemption

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

Circular Wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release해야 한다.

이 Deadlock prevention은 원천적으로 데드락을 막을 수 있지만, Utilization 저하, throughput 감소, starvation 문제가 생길 수 있다!

Deadlock Avoidance

Deadlock avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(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 Algoritm의 예

위 그림에서 점선은 프로세스에서 자원으로만 가며, 요청할 여지가 있다는 의미이고 점선은 요청한다는 의미이다.

마지막 그림에서 unsafe한 상황이 발생하는데, deadlock avoidance는 저런 상황을 발생시키지 않도록 자원을 주지 않는다.(데드락 발생 위험이 있으면 자원을 주지 않음)

Banker's Algorithm의 예

위와 같은 상황에서 Available보다 Need가 높은 프로세스가 자원을 요청하면 최대를 요청할 수 있으므로(데드락 발생) 요청을 받아들이지 않음

최악의 상황에서 데드락이 발생하는지 확인

sequence(P1, P3, P4, P2, P0)가 존재하므로 시스템은 safe state

그러나 Deadlock avoidance 방법은 비효율적임(자원이 남았는데도 프로세스에게 자원을 주지 않으므로)

Deadlock Detection and Recovery

Deadlock Detection

• Resource type당 single instance인 경우
  • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
• Resource type당 multiple instance인 경우
  • Banker's algorithm과 유사한 방법 활용

Wait-for graph 알고리즘

• Resource type 당 single instance인 경우
• Wait-for graph
  • 자원할당 그래프의 변형
  • 프로세스만으로 node구성
  • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk → Pj
• Algorithm
  • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  • O(n^2)

자원의 최대 사용량을 미리 알릴 필요 없음 -> 그래프에 점선이 없음(deadlock avoidance와 다르게)

Resource type당 multiple instance인 경우

Request는 추가요청가능량이 아니라 현재 실제로 요청한 자원량을 나타냄
최선의 상황에서 데드락이 발생하는지 확인

그러나 위의 그림에서 P2가 자원 하나(C)를 요청하는 경우 데드락 발생!

Recovery

• Process termination
  • 데드락된 모든 프로세스 중단
  • 데드락이 제거될 때까지 한번에 하나의 프로세스만 중단
• Resource Preemption
  • 비용을 최소화할 victim의 선정
  • safe state로 rollback하여 process를 restart
  • Starvation 문제
    • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
    • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

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

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

참고사이트

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09