[운영체제] DeadLock과 그 해결방법

목차

1. 데드락

2. DeadLock 해결 방법

3. Resource-Allocation Graph

 

 

 

 

데드락

교착상태

 

 

개념

둘 이상의 프로세스가, 각각 점유하고 있는 자원을 놓치않고 서로 기다릴 때 무한 대기에 빠지는 상태를 의미한다.

 

발생 조건

1. 상호 배제

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

 

2. 비선점

프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏기지 않는다.

 

3. 보유대기

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

 

4. 순환대기

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

 

P0는 P1의 자원을 기다림

P1는 P2의 자원을 기다림

..

Pn은 P0의 자원을 기다림 

 

 

DeadLock 해결 방법

1. DeadLock Prevention

deadlock의 발생조건들을 발생하지 않도록 막아 문제를 해결하는 방법이다. 

 

1. 상호 배제

이 것은 막을 수 있는 조건은 아니다. 

 

2. 비선점

필요한 경우 자원을 선점할 수 있게 함으로써 문제를 해결한다. 하지만 빼앗기는 경우 큰 문제가 발생하는 리소스의 경우 이런 방법을 사용하기 어렵다. 

 

3. 보유대기

프로그램 시작 시 필요한 모든 자원을 할당받게 하거나, 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청하게 함으로써 해결할 수 있다. 하지만 resource 측면에서 비효율적임.

 

4. 순환대기

자원 할당에 순서를 정해 문제를 해결한다.  예를 들어 순서 3인 자원을 보유중인 프로세스가 1인 자원을 할당받기 위해서는 우선 R을 release 해야한다.

 

-> Utilization 저하 ,Throughput 감소, starvation 문제 등이 발생할 수 있으며, 흔하지 않은 현상인 DeadLock을 미리 생각해 이렇게 하는 것은 비효율적이다. 

 

2. DeadLock Avoidance

프로세스의 자원 요청이 데드락을 발생시키지 않는 경우에만 허락되도록 하는 것이다. 

 

자원 사용

 

예를 들어 Type1...Type4가 각각 7 6 8 4개만큼의 자원이 있다고 해보자.

지금 각 프로세스에 할당된 총 개수는 6 2 8 3 개이다.  따라서 이 둘의 차이인 1 4 0 1 만큼의 자원이 남아 있을 것이다.

A는 1 1 0 0 을 필요로 하는데, 이는 현재 남아있는 리소스로 fullfill 할 수 있으므로, 요청이 허락된다. 

하지만 D의 요청 2 1 1 2는 현재 남아있는 리소스로 만족시킬 수 없으므로, 요청이 거절되게 하는 것이다.

 

 

3. DeadLock Detection and Recovery

일단 놔두고, 데드락이 생기는지를 탐지해서 데드락이 생기는 경우 데드락을 해결하는 방식

Detection

DeadLock Detection

 

Request가 없는 프로세스는 P0 하나이므로 P0이 자원을 돌려주면 남은 자원은 0 1 0 이 된다. 하지만 이 자원으로는 요청을 만족시켜줄 프로세스가 없으므로 데드락 상태가 된다. 

Recovery

데드락과 관련된 프로세스를 죽이거나, 비용을 최소화할 victim을 선정해 자원을 빼앗음으로써 문제를 해결한다.

 

 

4. Deadlock Ignorance

데드락이 일어나도 아무런 조치를 취하지 않는 방법. DeadLock을 해결하기 위한 방법들이 모두 비효율적이므로, 가만히 놔두는 전략이다. 사용자가 직접 Process를 죽이든 해서 해결하고, OS는 관여하지 않는다.

 

 

 

Resource-Allocation Graph

Resource-Allocation Graph

 

그래프에 cycle이 없으면 deadlock이 아니다.

그래프에 cycle이 있고, 각 자원이 하나씩이면 데드락이고, 여러개이면 데드락 가능성이 존재한다.

왼쪽의 그래프의 경우 어떨까?  

사이클이 2개가 있기 때문에, 자원이 둘이 있지만, 진행이 불가능해 데드락이 된다.

 

오른쪽의 그래프 경우 어떨까?

오른 쪽의 경우 사이클은 하나이지만, 자원이 두개라 데드락이 아니다. 사이클과 관련없는 P2나 P4가 자원을 할당하면

프로세스가 진행될 수 있기 때문이다.