[OS] 7. Deadlock

Chapter 7. Deadlock

교착상태.

일련의 프로세스들이 서로가 가진 자원을 요청하고 기다리며 blocked 된 상태를 말한다.

자원(리소스)에 대한 개념을 다시 한 번 짚고 가자면,

하드웨어와 소프트웨어 등을 포괄하는 개념이다.

예를 들면, I/O space, CPU cycle, memory space, semaphore 등이 있다.

그리고 프로세스가 자원을 사용하는 절차에는 Request, Allocate, Use, Release 단계가 존재한다.

즉, Deadlock 이란,

프로세스 P1과 P2가

P1(a); P2(b); // 각각 a,b라는 자원을 할당받은 상태에서

P1(b) request, P2(a) request // b를 요청하고 a를 요청한 상태를 말한다.

Deadlock이 형성되기 위한 4가지의 조건이 존재한다.

Mutual Exclusion

매 순간 하나의 프로세스 만이 자원을 사용할 수 있다.

(당연하게 느껴지는 조건이다.)

No Preemption

프로세스는 자원을 스스로 내어놓을 뿐, interrupt 등에 의해서 강제로 반환되지 않는다.

자원이 강제로 반환된다면, 데드락이 발생할 가능성은 없다,

Hold and wait

자원을 갖고 있는 프로세스가 다른 자원을 기다릴 때, 보유 자원을 반환하지 않고 계속 보유하고 있어야 한다.

내놓지 않은 상태에서 추가적인 요청을 해야 데드락이 발생한다.

Circular wait

위 조건들을 만족하면서 서로가 가진 자원을 서로가 기다리는 프로세스가 존재해야 한다.

즉 프로세스간의 사이클이 형성되어야 한다.

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

그래프에 cycle이 존재하지 않으면 Deadlock이라고 할 수 없다.

자원에 인스턴스가 여러 개일 경우, (cycle에 포함되지 않는 인스턴스가 존재하더라도,)

데드락 일 수도 있고, 아닐 수도 있는 것이다.

자원 내의 모든 인스턴스에 해당하는 cycle이 형성되어야 데드락이 성립된다.

Deadlock 처리 방법

Deadlock Prevention

자원 할당 시 Deadlock의 필요조건 중 어느 하나를 미리 차단하여 방지하는 방법

1) Mutual Exclusion  차단

자원을 공유시키는 방법이다. 공유해서는 안되는 자원의 경우에서는 불가능 하다.

2) Hold and wait 차단

프로세스가 자원을 요청할 때 다른 어떠한 자원도 갖고 있지 않게 하는 방법이다.

HOW?

How 1> 프로세스 시작 시 필요한 모든 자원을 할당받게 한다.

프로세스는 매 시점마다 필요로 하는 자원이 다르다.

필요하지 않은 시점에 자원을 갖고 있으면 그 만큼 비효율성이 높아지게 된다.

How 2> 자원이 필요한 경우 보유하고 있던 자원을 모두 반환시킨다.

3) No Preemption 차단

프로세스가 어떤 자원을 요청해야 하는 경우, 이미 보유하고 있던 자원이 선점된다.

모든 필요한 자원을 얻을 수 있을 때, 그 때가 되서야 프로세스가 다시 시작된다.

프로세스의 State를 쉽게 저장하고 복구할 수 있는 자원에서만 가능한 방법이다. (ex. CPU, memory)

4) Circular wait 차단

모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당하는 방법이다.

자원에 순서를 할당하여 (1,2,3, ...) 3번 자원을 할당하기 위해서는 1과 2를 보유한 상태이어야 하고,

2를 획득하기 위해서는 1을 보유한 상태이어야 획득할 수 있도록 하는 방법이다.

Dead lock Prevention 방법은 Utilization 저하, Throughtput감소, Starvation 문제들이 발생하게 된다.

어쩌다 한 번 발생할 Deadlock을 미연에 방지하다가 막대한 비효율이 발생하는 것이다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만,

즉 Deadlock으로부터 safe한 지를 동적으로 점검하여 safe한 경우에만 자원을 할당해주는 방법이다.

*Safe State

시스템 state가 원래의 state로 돌아올 수 있는 sequence가 존재하면 safe state라고 한다.

unsafe state가 데드락의 상태를 의미하는 것은 아니고, 그럴 가능성이 존재한다는 것을 의미한다.

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

이 방법에는 2가지 알고리즘이 존재한다.

Single Instance pre resource types - Resource Allocation Graph Algorithm

Claim edge를 사용한다.

프로세스가 자원을 미래에 요청할 수도 있음을 뜻하는 점선을 의미한다.

실제로 자원을 요청하게 되면 그 점선이 실선으로 바뀌는 것이다.

실선으로 cycle이 생기지 않는 경우에만 요청한 자원을 할당한다.

하지만 이 Cycle 생성 여부를 조사하는데 프로세스의 개수가 n개 일 때, Order of n^2의 time complexity가 발생한다.

Multiple instances per resource types - Banker's Algorithm

프로세스가 평생 사용할 자원들(자원값이 될 수 있는 최대값)을 미리 선언한다.

현재 할당 된 자원의 양(Allocation)을 계산하고

프로세스에게 최대로 할당될 수 있는 자원의 양(MAX)을 계산하고

두 데이터를 통해

추가로 할당해줄 수 있는 자원의 양(Need)를 계산한다.(Need = MAX - Allocation)

그리고 하나의 데이터가 더 존재하게 되는데, 현재 가용할 수 있는 자원의 양(Available)이다.

프로세스의 Need수치가 Available의 수치보다 높으면 할당해주지 않고

또 Need에 있는 양을 최악의 상황으로 생각하여 요청한 정도가 Need보다 낮더라도 할당해주지 않는다.

낮은 양을 먼저 요청하게 되면 나중에 또 요청하게 될 것이고, 그 때 Deadlock이 발생할 수도 있기 때문이다.

이 경우에는 최종적으로 요청한 자원의 양이 커져서 Need의 값이 될 때까지 대기해야 한다.

즉, 자원을 요청하는 프로세스의 MAX값을 Available의 양이 커버할 수 있다면 그 프로세스의 요청에 응답하는 방법인 것이다,

문제는,

Need의 자원의 양이 언제 필요한지 모르는 것이다.

다음 두 가지 방법은 데드락이 발생하도록 그냥 두는 방법이다.

Deadlock Detection and Recovery

데드락을 탐색하고 그 상황을 복구하는 방법이다.

Recovery 1. Process Termination

프로세스를 종료한다.

Recovery 2. Resource Preemption

비용을 최소화할 victim process를 선정하여 자원을 뺏어 데드락을 해제한다.

하지만 이 방법은 Starvation 문제가 발생한다.

victim process가 극단적으로 한 프로세스에게만 해당된다면, 그 프로세스는 계속해서 자원을 뺏기게 되는 상황이 발생한다.

Deadlock Ignorance

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

만약 데드락이 발생하게 되면 사용자가 프로세스를 죽이는 방법으로 대처한다.

데드락 자체가 매우 드물게 발생하므로 조치 자체가 더 큰 overhead가 될 수 있다는 점에서

현재 대부분의 운영체제들이 채택하고 있는 방법이다.

Chapter 7. 끝 

이 포스팅은 이화여대 반효경 교수님 강의를 듣고 요약한 내용을 담고 있습니다.