[OS] Deadlock

1. Deadlock이란?

2개 이상의 프로세스간에 자원에 대한 요청이 뒤엉켜있어서 서로 무한히 대기하고 있는 현상

 

※ Starvation과의 차이

Starvation : Ready 상태에서 대기, 발생 가능성이 있는 이벤트를 대기

Deadlock : Asleep 상태에서 대기, 발생 가능성이 없는 이벤트를 대기

 

 

2. 자원의 분류

1) 하드웨어 vs 소프트웨어

2) 선점 자원 vs 비선점 자원 : 선점 당해도 문제 없음(CPU, memory) vs 선점 당하면 문제 발생(disk drive)

3) 전체를 한 프로세스에게 할당(CPU, disk drive) vs 부분을 여러 프로세스들에게 할당(memory)

4) 동시에 사용 가능(SW program) vs 동시에 사용 불가능(CPU, memory, disk drive)

   : Shared allocation resources vs Exclusive allocation resources

5) 재사용 가능(CPU, memory, disk drive, program) vs 재사용 불가능(signal, message)

   : SR(Serially-reusable Resources) vs CR(Consumable Resources)

 

여기서 비선점 자원, 동시에 사용 불가능한 자원, 재사용 가능한 자원은 Deadlock를 발생시킬 수 있으며, 할당 단위는 영향을 미치지 않는다.

 

 

3. Deadlock Model

1) Graph Model

 

2) State Transition Model(상태 변환 모델)

아래의 예제에서는 상태 경우의 수가 25임(5x5)

 

 

4. Deadlock 발생 필요 조건

1) 상호 배제(Mutual exclusion)

2) 비선점(Non-preemptible)

3) 점유와 대기(Hold and wait)

4) 환형 대기(Circular wait) : 프로세스들이 Circle 관계일 경우

 

여기서 조건 한가지를 깨뜨리면 Deadlock을 풀 수 있다.

 

 

5. Deadlock 해결 방법

1) 예방

Deadlock의 발생 조건중 하나 이상을 제거하는 방법

 

(1) 상호 배제 조건 제거 : 모든 자원을 공유 허용 -> 비현실적

(2) 선점 허용 : 모든 자원에 대해 선점 허용 -> 비현실적

(3) 점유와 대기 조건 제거 : 필요 자원을 한번에 모두 할당 -> 자원 낭비, 무한 대기 가능성 존재

(4) 환형 대기 조건 제거 : 프로세스는 순서의 증가 방향으로만 자원 요청 -> 자원 낭비

※ (3), (4) : 현재 필요하지 않은 자원도 소유중이기 때문에 자원이 낭비됨

 

 

2) 회피

시스템의 상태를 계속 감시하여 Deadlock 상태가 될 가능성이 있는 자원 할당 요청을 보류하는 방법이며, 시스템은 항상 Safe state로 유지함

 

(1) Safe/Unsafe state이란?

<1> Safe state

- 모든 프로세스가 정상적으로 종료가 가능한 상태

- 안전 순서(Safe sequence)가 존재하기 때문에 Deadlock 상태가 되지 않음

- Unsafe state로 변할 수 있음

※ 안전 순서 : 모든 프로세스가 작업을 마칠 수 있는 경우에 해당하는, 프로세스의 실행 종료 순서

<2> Unsafe state

- 안전 순서가 존재하지 않는 상태

- Deadlock 상태가 될 가능성이 있음(Deadlock은 Unsafe state에서 발생함★)

 

(2) 조건

<1> 프로세스의 수가 고정됨 -> 비현실적

<2> 자원의 종류와 수가 고정됨 -> 비현실적

<3> 프로세스가 요구하는 자원 및 최대 수량을 알고 있음 -> 비현실적

<4> 프로세스는 자원 사용 후 반드시 반납함

 

(3) 해결 방안

<1> Dijkstra의 banker 알고리즘

① 소개

- 자원의 종류가 하나일 경우를 다룸

- 시스템을 항상 Safe state로 유지함

 

② 예시

현재 할당 중인 총 자원 수는 1+5+2=8개이다. 즉 추가로 할당해줄 수 있는 자원의 수는 2개이다.

이 2개의 자원을 P1에 추가 할당해주면 P1은 정상적으로 작업을 마칠 수 있으며, 자원 3개를 돌려받을 수 있다.

이 3개의 자원을 P3에 추가 할당해주면 P3은 정상적으로 작업을 마칠 수 있으며, 자원 5개를 돌려받을 수 있다.

이 5개의 자원 중 4개의 자원을 P2에 추가 할당해주면 P2까지 정상적으로 작업을 마칠 수 있다.

즉, 위의 예시는 Safe State이며, Safe sequence는 P1->P3->P2이다.

만약, 처음 상태에서 모든 프로세스의 필요 자원 수가 3이상이었다면 Safe sequence가 존재하지 않으므로 Unsafe State였을 것이다.

 

③ 원리

어떤 프로세스가 급하게 n개의 자원이 더 필요하다고 요청이 들어왔을 때, 이 프로세스에게 n개의 자원을 할당한 이후에 안전 순서가 존재한다면 자원을 할당해주고, 안전 순서가 존재하지 않는다면 요청을 거절한다.

 

<2> Habermann 알고리즘

① 소개

- Dijkstra 알고리즘의 확장

- 자원의 종류가 여러 개일 경우를 다룸

- 시스템을 항상 Safe state로 유지함

 

② 예시

가정 : 자원a 10개, 자원b 5개, 자원c 7개, 프로세스 5개

 

③ 원리

Dijkstra 알고리즘과 유사한 원리이며, 중요한 점은 여러 자원을 한 쌍으로 묶어 한 프로세스씩 할당해준다는 것이다.

 

(4) 단점

- 항상 시스템을 감시하고 있어야 하기 때문에 Overhead가 큼

- Safe state를 유지하기 위해, 사용되지 않는 자원이 존재함

- 프로세스와 자원의 개수가 고정되어 있고 각 프로세스의 최대 필요 자원수를 알고 있다는 것을 가정하에 진행되기 때문에 실용적이지 않음

 

 

3) 탐지 및 복구

Deadlock을 피하지 않고 주기적으로 탐지해서, Deadlock 발생이 확인되었다면 복구시킴

 

(1) 탐지(Detection) 방법

<1> RAG란?

- 자원 할당 그래프

- 방향성이 있는 그래프

- Deadlock 검출을 위해 사용됨

 

<2> RAG의 구성

 

<3> RAG로 Deadlock을 판단하는 방법

Unblocked 프로세스의 모든 Edge들을 지워나가서 그래프의 모든 edge들이 말끔히 제거된다면 Deadlock인 프로세스가 없다고 판단하면 된다.

Unblocked 프로세스는 필요한 자원을 모두 할당 받을 수 있는 프로세스(요청 수<=남은 자원 수)이다.

그렇다면 아래 그림에 나와있는 RAG는 Deadlock 상태인지 판별해보자.

P1 : R1(요청 0개<=남은 자원 0개), R2(요청 1개<=남은 자원 1개) 모두 만족 -> Unblocked

즉, P1에 연결된 모든 Edge를 지웠으며 그 결과는 아래와 같다.

P2 : R1(요청 1개<=남은 자원 2개), R2(요청 1개<=남은 자원 1개) 모두 만족 -> Unblocked

이렇게 되면 P2에 연결된 모든 Edge도 지워짐으로써 그래프의 모든 Edge가 지워진다.

즉, 이 예제는 Deadlock 상태가 아니라고 판단할 수 있는 것이다.

 

※ 또 다른 예제

P3 : R1(요청 0개<=남은 자원 0개), R2(요청 0개<=남은 자원 0개), R3(요청 1개<=남은 자원 1개) 모두 만족 -> Unblocked

P1, P2 모두 Blocked 상태이므로 이 예제는 Deadlock 상태이다.

P1 : R1(요청 1개>남은 자원 0개) 불만족, R2(요청 1개<=남은 자원 1개) 만족, R3(요청 0개<=남은 자원 2개) 만족

-> R1 때문에 Blocked

P2 : R1(요청 0개<=남은 자원 0개) 만족, R2(요청 2개>남은 자원 1개) 불만족, R3(요청 1개<=남은 자원 2개) 만족

-> R2 때문에 Blocked

 

이 탐지 방법에서 발생하는 Overhead의 크기는 검사 주기와 Node 개수에 영향을 받는다.

 

(2) 복구(Recovery) 방법

<1> 프로세스 종료

- Deadlock 상태인 프로세스들 중 일부를 종료했다가 나중에 재시작 시키는 방법

- 프로세스의 우선 순위, 종류, 총 수행 시간, 남은 수행 시간, 종료 비용 등 여러 요소들을 고려할 수 있음

 

<2> 자원 선점

- 선점할 자원을 선택해서 그 자원을 가지고 있는 프로세스를 종료하고 나중에 재시작 시키는 방법

- Deadlock 상태가 아닌 프로세스가 종료될 수도 있다는 단점이 있음

- 선점할 자원을 선택하기 위해 Cost model이 필요함

- 최소 비용 복구 방법을 사용함

 

<3> Checkpoint

위에서 살펴본 <1>, <2> 2가지 방법의 공통점은 프로세스를 종료하고 그 프로세스를 나중에 재시작 시킨다는 점이다.

프로세스를 재시작 시킬 때 작업을 처음부터 다시 진행하는 것 보다는 특정 지점마다 context를 저장해두고 최근에 저장한 Checkpoint로 돌려보내는 것(Rollback)이 리스크가 적기 때문에 Checkpoint를 사용해야 한다.

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN