OS 6. Deadlock

출처 : KOCW 운영체제-반효경

Deadlock

일련의 프로세스들이 서로 가진 자원을 기다리며 block된 상태이다. 여기서 자원은 하드웨어(I/O device, CPU cycle, memory space ...), 소프트웨어(공유데이터, semaphore…) 등을 포함하는 개념이다.

프로세스가 자원을 사용하는 절차는 총 4 단계이다. 자원을 요창하는 단계인 Request, 자원을 받는 단계인 Allocate, 사용하는 단계인 Use, 마지막으로 반납하는 단계인 Release가 있다.

Deadlock 발생의 조건은 4가지가 있다. 이 중 하나라도 해당되지 않는다면 Deadlock이 발생하지 않는다. 이 것을 해결하게 되면 Deadlock을 해결할 수 있다.

1. Mutual exclusion : Deadlock 이 발생하는 가장 근본적인 원인이라고 할 수 있다. 하지만 보통 Mutual exclusion을 만족하기 위해서 lock을 사용하기 때문에 이것을 해결한다는 것은 목적으로 발생한 문제를 해결하기위해 목적을 제거하는 것과 같기 때문에 말이 안된다.

2. No preemption : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다. (=강제로 빼앗기지 않는다.)

3. Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.(=쓰지도 않는데 쓸데없이 들고있다.)

4. Circular wait : 자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.

Resource-Allocation Graph

자원 할당 그래프는 프로세스와 자원의 종류와 각 자원의 개수를 나타내며 각 프로세스가 어떤 자원을 요청하는지 어떤 자원을 가지고 있는지를 나타낸 그래프다. 프로세스가 자원을 가리키는 것은 해당 자원을 요청하고 있다는 것이고 그 반대는 해당 프로세스가 그 자원을 가지고 있다는 것을 의미한다.

자원 할당 그래프에서 cycle이 없다는 것은 현재 deadlock이 발생하지 않았다는 이야기이고 cycle이 존재한다면 deadlock 의 가능성이 있다는 것이다. 각 자원의 종류에 오직 하나의 인스턴스만 있을땐 cycle이 존재한다는 것은 deadlock이 발생했다는 것이다. 위의 두 경우 모두 cycle이 생겼지만 deadlock이 발생하지 않은 예이다.

Deadlock의 처리 방법

순서가 낮을 수록 더 강한 deadlock 처리방법이다. 1,2는 deadlock의 발생을 미연에 방지하는 방법이고 3,4는 deadlock의 발생을 일단 허용하는 방법이다.

1. Deadlock prevention
   자원 할당시 deadlock의 4가지 필요 충분 조건 중 어느 하나가 만족되지 않도록 하는 것이다.

2. Deadlock avoidance
   자원 요청에 대해 부가적인 정보를 이용해 deadlock의 가능성이 없는 경우 또는 시스템 state가 원래 state로 돌아올 수 있는 경우에만 장원을 할당하는 방법이다.

3. Deadlock detection and recovery
   Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 이 발견되면 recover하는 방식이다.

4. Deadlock ignorance
   Deadlock을 시스템이 책임지지 않은 않는 방법으로 UNIX를 포함한 대부분의 OS가 채택하고 있다.

해결법 1. Deadlock prevention

1. Hold and wait
   프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
   방법 1: 프로세스가 시작 시 모든 필요한 자원을 할당받게 하는 방법 -> 너무 비효율적
   방법 2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

2. No preemption
   CPU 와 memory와 같은 자원은 preemptive하기 때문에 deadlock 이 생기지 않는다. 그렇다고 무작정 빼앗아 오게 되면 문제가 될 수 있다. CPU와 memory와 같은 state를 쉽게 저장하고 restore할 수 있는 자원에 주로 사용한다.

3. Circular wait
   자원에 순서를 정해서 해결할 수 있다. 예를들어 순서가 3인 자원을 보유중인 프로세스는 순서가 1인 자원을 얻기위해선 3인 자원을 release 해야한다.

=> Deadlock 은 그리 흔하게 발생하는 현상이 아니다. Deadlock prevention 방법은 deadlock을 원천 봉쇄할 수 있지만 utilization 저하, throughput 감소, starvation 문제 등의 커다란 단점을 가지고 있어 효율적인 방법이 아니다.

해결법 2. Deadlock avoidance

Deadlock avoidance는 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당한다. 가장 일반적이고 간단한 방법은 프로세스들이 필요로 하는 각 자원의 최대 사용량을 미리 선언하도록 하는 방법이다.

Safe state 는 프로세스들에 대한 safe sequence가 존재하는 상태를 말한다. safe sequence는 process 의 처리 흐름<P1,P2,…Pn>에 있어 매 process가 이전의 process가 쓰던 자원과 가용자원을 모두 합한 것 보다 작거나 같으면 그 process의 처리 흐름은 safe sequence 라고 한다.

조건을 만족하면 다음과 같은 방법으로 모든 프로세스의 수행을 보장할 수 있다.

• Pi 의 자원요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.

• Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

  Avoidance 알고리즘

1. Single instance per resource types : Resource Allocation graph algorithm
   Resource Allocation graph algorithm : cycle 을 확인 (BFS,DFS) * O(n^2)

점선(claim edge)은 프로세스가 해당 자원을 미래에 요청할 수 있다는 것을 의미하고 프로세스가 해당 자원을 요청할때 request edge로 바뀐다. 자원이 release되면 assignement edge는 다시 claim edge로 바뀐다.
Request edge의 assignment edge 변경시 (점선을 포함하여) cycle이 생기지 않는 경우에만 자원을 할당하게 된다.
deadlock이 발생할 가능성이 있다면 자원할당을 하지 않는다는 점에서 이 알고리즘은 최악의 상황을 가정한 것이다. 그렇기 때문에 굉장히 비효율적이다.

2. Multiple instances per resource types: Banker’s Algorithm
   Banker’s Algorithm 은 각 프로세스가 각 자원의 최대 할당량을 알고있고 각 프로세스는 요청 자원을 모두 할당받은 다음 유한시간 내에 해당 자원을 다시 반납하는 상황을 가정한다.
   

기본적으로 1번의 경우와 동일하게 safe 상태를 유지할 경우에만 할당한다. 최대 자원 사용량까지 필요한 자원이 가용 자원 수보다 적거나 같은 프로세스에게 자원을 할당하고 그렇지 않은 프로세스의 요청은 block한다. 할당받은 프로세스가 종료되면 모든 자원을 반납한다. 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다.
마찬가지로 Banker’s Algorithm도 deadlock이 발생할 가능성이 있다면 자원할당을 하지 않는다는 점에서 이 알고리즘은 최악의 상황을 가정한 것이다. 그렇기 때문에 굉장히 비효율적이다.

해결법 3. Deadlock Detection and Recovery

Deadlock 이 의심되는 상황에 Deadlock 을 detection 하고 deadlock 이 발견되면 recovery 한다.
Deadlock detection은 avoidance에서 활용한 방법과 거의 동일하다.

Single instance의 경우 위와 같이 resource allocation graph를 wait for graph로 바꿀 수 있다. 그리고 wait for graph에서 BFS/DFS 알고리즘을 통해 cycle을 확인하고 cycle이 확인되면 deadlock 이 발생하였다고 볼 수 있다.

Multiple instance 상황의 경우 banker’s algorithm과 유사하다. 다른점은 최대 사용량을 모르고 있어도 된다는 점이다. 왜냐하면 detection의 경우가 현재 상태자체가 deadlock 인지 판단하면 되기 때문이다.(이 상황이 deadlock이라고 확신해?)
어떤 특정 상황을 놔두고 request를 하지 않고 있는 프로세스가 가지고 있는 자원은 모두 반납한다고 했을때 safe state 인지 판단하면된다. 만약 unsafe state라면 deadlock이라고 확신할 수 있다. Banker’s algorithm은 deadlock을 완전히 막아야 하기 때문에 최악의 상황을 가정하지만 detection인 경우 무죄 추정의 원칙과 유사하게 deadlock이 될 가능성이 있는 상황을 최대한 배제하고 최상의 상황을 가정한다.

Detection 을 통해 deadlock이 확인이 된다면 recovery를 해야한다. recovery에는 크게 2가지 방법이 있다.
1. Process termination

• Deadlocked processes 모두 죽이는 방법
• deadlock cycle이 제거 될때까지 Deadlocked processes 중 하나씩 죽이는 방법

2. Resource preemption

• 비용을 최소화할 희생양(victim)을 선정
• safe state로 rollback 하여 process를 restart
• Starvation 문제
  - 동일한 프로세스가 계속해서 victim으로 선정
  - cost factor에 rollback 횟수도 같이 고려

해결법 4. Deadlock ignorance

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