Deadlock

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

The Deadlock Problem

• Resource
• 하드웨어, 소프트웨어 등을 포함하는 개념
• I/O Device, CPU Cycle, Memory Space, Semaphore 등
• 프로세스가 자원을 사용하는 절차
• Request, Allocate, Use, Release

• Deadlock Ex1
• 시스템에 2개의 Tape Drive가 있다.
• P1과 P2 각각이 하나의 Tape Drive를 보유한 채 다른 하나를 기다리고 있다.

• Deadlock Ex2
• Binary Semaphores A and B

Deadlock의 발생 조건 4가지

• Mutual Exclusion
• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

• No Preemption
• 프로세스는 자원을 강제로 빼앗기지 않음

• Hold and Wait
• 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있는다.

• Circular Wait
• 자원을 기다리는 프로세스 간 사이클이 형성됨

Resource-Allocation Graph

• Vertex
• Process P
• Resource R

• Edge
• Request Edge P → R
• Assignment Edge R → P

확인하는 방법

• 그래프에 Cycle이 없으면, Deadlock이 아니다.

• Cycle이 있으면,
• 자원당 인스턴스가 하나씩밖에 없으면, Deadlock
• 자원당 몇 개의 인스턴스가 있으면, Deadlock의 가능성이 있음

Deadlock 처리 방법

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

• Avoidance
• 자원 요청에 대한 부가적인 정보를 이용해서, Deadlock의 가능성을 없는 경우에만 자원을 할당
• System State가 원래 State로 돌아올 수 있는 경우에만 자원 할당

• Detection and Recovery
• Deadlock 발생은 허용하되, 그에 대한 Detection 루틴을 두어 Deadlock 발견시 Recover

• Ignorance
• Deadlock을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택
• 현대적인 시스템에서는 Deadlock이 많이 발생하지 않기 때문에, 평소에 Overhead를 감수하면서 처리하지 않는 것

Prevention

• Mutual Exclusion
• 굥유해서는 안되는 자원의 경우, 반드시 성립해야함

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

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

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

단점

• Utilization 저하

• Throughput 감소

• Starvation 문제

Avoidance

• 자원 요청에 대한 부가 정보를 이용해서, 자원 할당이 Deadlock으로 부터 안전한지를 동적으로 조사
• 안전한 경우에만 할당

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

• 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

• Avoidance는 시스템이 Unsafe State에 들어가지 않는 것을 보장

• 2가지 경우의 알고리즘
• Single Instance per Resource Types
• Resource Allocation Graph Algorithm 사용
• Multiple Instances per Resource Types
• Banker’s Algorithm 사용

Resource Allocation Graph Algorithm

• Claim Edge Pi → Rj
• 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함(점선)
• 프로세스가 해당 자원 요청시 Request Edge로 바뀜(실선)
• Rj가 Release되면, Assignment Edge는 다시 Claim Edge로 바뀐다.

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

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

Banker’s Algorithm

• 가정
• 모든 프로세스는 자원의 최대 사용량을 미리 명시
• 프로세스가 요청 자원을 모두 할당받은 경우, 유한 시간 안에 이들 자원을 다시 반납한다.

• 방법
• 기본 개념
• 자원 요청 시, Safe 상태를 유지할 경우에만 할당
• 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택
• 그런 프로세스가 없으면 Unsafe 상태
• 그런 프로세스가 있으면, 그 프로세스에게 자원을 할당
• 할당받은 프로세스가 종료되면, 모든 자원을 반납
• 모든 프로세스가 종료될 때까지 이러한 과정을 반복

Example of Banker’s Algorithm

• P1 Request (1, 0, 2)

Detection and Recovery

• Detection
• Resource type당 Single Instance인 경우
• 자원할당 그래프에서의 Cycle이 곧 Deadlock을 의미
• Resource type당 Multi 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)

• Recovery
• Process Termination
• Abort all Deadlocked Processes
• Abort one process at a time until the Deadlock Cycle is eliminated
• Resource Preemption
• 비용을 최소화할 victim의 선정
• Safe State로 Rollback하여 Process를 Restart
• Starvation 문제
• 동일한 프로세스가 계속해서 victim으로 선정되는 경우
• Cost Factor에 Rollback 횟수도 같이 고려

Ignorance

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

출처