Deadlock - 정의, 발생 조건, Resource Allocation Graph, Prevention, Avoidance, Detection, Recovery

Deadlock

Deadlock

Defintion : 각각의 프로세스가 자원을 하나씩 가지고 있는 상태에서 서로의 자원을 기다리는 상태

-> 서로 필요한 자원을 사용중이기 때문에 더 이상 진행되지 않는 데 이것을 Deadlock이라고 한다.

Process 1은 R1을 가지고 있고 R2를 요청하는 상태이고, Process 2는 R2를 가지고 R1을 기다리는 상태이다.

이러한 경우에 서로의 자원을 기다리지만 절대 받을 수 없는 상태가 된다. 이러한 상태를 Deadlock이라고 한다.

Deadlock 발생 조건

1) Mutual Exclusion(상호 배제)

- 한번에 1개의 프로세스만이 자원에 접근할 수 있음

2) Hold and wait

- 한개이상의 자원을 가지고 있는 프로세스가 다른 자원을 기다리는 상태

3) No preemption 

- 해당 작업이 완료될때까지 가지고 있는 자원을 놓지 않음

4) Circular wait

- 연쇄적으로 자원을 기다리는 상태. 위 그림처럼 서로가 연쇄적으로 기다리고 있음(Resource와 Process 사이의 cycle이 존재)

-> 4가지 조건을 모두 만족하게 되면 Deadlock이 발생한다.

Resource Allocation Graph

- 그래프처럼 Vertex와 Edge로 이루어져있음

- Process를 나타내는 P vertex와 Resource를 나타내는 R vertex가 있음

- Request edge : P -> R, Assignment edge : R -> P

Process는 Resource에 request를 하고 Resource에서는 Instance중 하나를 allocation 해준다.

이러한 과정에서 여러 프로세스와 여러 Resource사이에 Cycle이 생기게 되면 Circular wait 조건을 만족하게 된다.

Cycle이 존재하더라도 위처럼 multiple instance를 가진다면 deadlock이 무조건 발생하지는 않는다.

Deadlock Prevention

- Deadlock이 발생하는 조건 4가지 필요조건을 하나 제거해 deadlock을 예방하는 방법

1) Mutual Exclusion

- Mutual Exclusion을 없앤다는 것은 자원 공유의 개념을 없앤다는 것을 의미한다. 즉 자원 공유가 불가능하게 되므로 Mutual Exclusion을 없앤다는 것을 불가능하다

2) Hold and Wait

- 한 자원을 가지고 있는 것을 막고, 여러 자원을 필요로 할 때 모든 자원이 사용 가능할 때 할당받도록 하는 방법

- 프로세스 실행 전 모든 자원을 할당받기 때문에 Resource Utilzation이 감소할 수 있다.

- 요청하는 모든 리소스가 존재할 때 할당받기 때문에 Starvation이 발생할 수 있다.

3) No preemption

- Preemption을 허용할 경우 절대로 Deadlock은 발생하지 않는다.

- 어떤 자원을 요청하는 경우, 이미 보유하고 있던 자원이 선점되고 모든 자원을 얻을 수 있을 때 재시작하는 방법

4) Circular wait

- 각 리소스의 타입에 따라 순서를 정하는 방법

- 리소스의 할당은 정해진 순서대로만 할당하게 된다.

Deadlock Avoidance

- Deadlock 발생 가능성을 모두 제거하는 것이 아닌, deadlock이 발생하려 할 때 이를 회피하는 방법을 말함

- OS가 process가 실행되기 위한 자원의 양을 알고 deadlock이 일어날 수 있는 상태를 회피한다.

Safe State

- 여러 개의 프로세스가 있을 때, 프로세스가 자원을 요청할 때 아무런 문제없이 자원을 할당받을 수 있는 경우의 상태를 의미

- safe sequence : 사용가능한 자원을 특정 process에게 주고 그 프로세스가 끝난 후 해당 자원을 받은 후 모든 프로세스가 무사히 작업을 마칠 수 있는 경우의 Sequence를 의미함

Avoidance Alogrithm

1) Single-Instance (Resource Allocation Graph Algorithm)

- Resource Allocation Graph를 사용해 Process의 수행 순서를 결정함

- 미래에 사용할 자원을 나타내는 Claim Edge를 사용한다. (점선)

-> 요청할 때 점선이 실선으로 바뀜. 이 때 cycle이 생기지 않으면 자원을 할당함

- 위와 같은 상황에서 P2가 R2를 요청해 할당받게 되면 Cycle이 생기게 된다. 이러한 경우 Resource를 할당받지 않고 P1이 끝나기를 기다린다.

2) Multiple instances (Banker's Algorithm)

- 가진 자원 정보를 가지고 safe state가 존재하는지 확인하고 하나의 경우라도 존재하는지 확인하여 deadlock을 회피할 수 있는 알고리즘

- 프로세스가 사용할 자원들을 미리 보고 Safe sequence를 찾는 알고리즘이다.

사용되는 변수

① Available : 각 Resource 별로 할당할 수 있는 남은 인스턴스 수

② Max : Process가 하나의 타입의 resource에 최대로 요구하는 인스턴스 수

③ Allocation : Process에 할당된 resource의  인스턴스 수

④ Need : Process가 필요로 하는 resource의 인스턴스 수

Example) Banker's Algorithm

프로세스 4개와 Resource 3개가 있다. Allocation은 현재 할당 받은 양, Need는 추가로 필요한 양, MAX는 총 합쳐서 필요한 양, Available은 현재 할당할 수 있는 Resource의 양이다.

Need를 보면 현재는 P2와 P3중에 선택하여 할당할 수 있다.

P3에게 할당한 후 P3은 종료하여 자원을 반환한다. 반환한 후 남은 자원은 R1(2), R2(3), R3(1)이다. 이 자원을 가지고 다음으로 할당할 수 있는 프로세스는 P2와 P3이다.

P2를 선택하여 할당한 후 P2는 종료하여 자원을 반환한다. 남은 프로세스중 할당할 수 있는 것은 P4밖에 없기 때문에 P4를 선택하여 할당한다.

P4 프로세스는 종료 후 할당받았던 resource를 모두 반환한다. 반환한 후 P1에게 할당할 수 있는 자원이 된다. P1에게 자원을 할당한다.

P1은 자원을 할당받고 작업을 시작한다. 종료후에는 위와 마찬가지로 반환하게 될 것이다.

Deadlock Detection

- Detection은 Prevention과 거의 같은 방식을 이용한다.

- Detection도 single Instance와 multiple Instance로 나누어지는데 single instance는 회피와 마찬가지로 Resource Allocation Graph를 활용한다.

- multiple instance의 경우, Banker's Algorithm과 거의 비슷한 알고리즘을 사용한다.

-> Need 대신 Request 사용

-> 미래에 필요한 정보가 아닌 현재의 Request 사용

Deadlock Recovery

- Deadlock이 발생한 상황에서 복구하는 방법

1) Process Termination

- Deadlock이 일어난 모든 프로세스를 종료시키는 방법

- 하나의 프로세스씩 종료시키며 deadlock cycle이 없어질때까지 반복한다.

2) Check & Rollback

- 비용을 최소화할 victim process를 선정한다.

- safe state로 return하고 프로세스를 재시작한다.