DeadLock

https://core.ewha.ac.kr/publicview/C0101020140411151510275738?vmode=f

반효경 [운영체제] 16. Deadlock 1

 

DeadLock

DeadLock = 교착상태

DeadLock

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

Resource = 자원 

- 자원은 HW 자원일수도, SW 자원일수도 있다

- 프로세스가 하나의 tape drive에서 읽어서 다른 tape drive에 copy 하는 작업을 한다고 생각해보자 

프로세스가 tape 2개를 다 점유해야 가능하다 

P1, P2가 각각 하나의 tape을 가지고 다른 tape을 얻기를 기다린다면 deadlock이 발생한다 

이 경우 HW 자원 때문에 deadlock이 걸린 것이다. 

 - 프로세스가 semaphore 2개를 획득해야 하는 상황을 가정해보자 

이런 경우 SW에 의해 deadlock이 발생한 것이다

- 프로세스가 자원을 사용하는 절차는 크게 4단계를 거친다. 

Request : 요청, Allocate : 획득, Use : 사용, Release : 반납 

 

Deadlock이 발생하는 조건 

1. Mutual Exclusion 상호 배제 

매 순간 하나의 프로세스만이 자원을 사용할 수 있음 (독점적으로 사용)

2. No Preemption 비선점 

프로세스는 자원을 스스로 내어놓을 뿐 뺏기지 않음 

3. Hold and wait 보유대기 

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

4. Circular wait 순환대기 

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

P0은 P1이 가진 자원을 기다림 

P1은 P2가 가진 자원을 기다림  ... 

Pn-1은 Pn이 가진 자원을 기다림 

Pn은 P0이 가진 자원을 기다림 

 

자원할당그래프

Resource allocation graph 

데드락이 발생했는지 알아보기 위해 그린다

동그라미 : 프로세스 , 사각형 : 자원 

사각형 안의 점 : 자원 인스턴스의 개수

 

엣지 

1. 자원 -> 프로세스 : assignment edge 

자원이 프로세스에 속해 있다 

2. 프로세스 -> 자원 : request edge

프로세스가 자원을 요청했다 (아직 획득은 못함)

 

 

그래프를 가지고 데드락인지 아닌지 어케아냐 ??

 

1. 그래프 안에 cycle이 없다 : deadlock이 아니다 

왼쪽 그래프의 경우 2개의 cycle이 있다 

첫번째 그래프 (위 위 사진) 은 cycle이 없다 : deadlock이 아님! 

cycle이 있다고 무조건 데드락은 아님! 

2. cycle이 있으면 

- 만약 자원 당 인스턴스(점)이 하나씩만 있다 : 데드락 

- 자원에 인스턴스가 여러개 있으면 : 데드락 일수도 아닐수도

왼쪽 그림 : 데드락

자원에 인스턴스가 2개지만, 자원에 걸린 cycle이 2개다

오른쪽 그림 : 데드락 X

자원에 인스턴스 2개씩 있다.

2번, 4번 프로세스가 cycle에 연루되지 않았다 

2번 또는 4번이 자원을 쓰고 나서 반납하면 1번 또는 3번이 자원을 먹으면서 cycle을 해소할 수 있다

 

DeadLock을 처리하는 방법 

4가지 방법이 있다 

1 ~ 4번 순으로 강한 방법이다 

1,2번 : 데드락이 생기기 전에 방지

3,4번 : 데드락이 생기는 건 놔두고 추후에 처리

현대의 운영체제는 대부분 4번을 채택 (데드락이 생기던 말던 관여 X)

 

1. Deadlock Prevention

- 자원 할당 시 데드락의 4가지 조건 중 하나가 만족되지 않도록 하는 것 

2. Deadlock Avoidance

- 자원 요청에 대한 부가정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당 

- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당 

3. Deadlock Detection and Recovery 

- DeadLock 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발생 시 recover 

4. Deadlock Ignorance 

- 시스템이 데드락을 책임지지 않음 

- 대부분의 OS가 채택 

- 사람이 알아서 프로세스를 죽이던지.. 해서 해결

- 데드락은 빈번히 발생하는 이벤트가 아니기 때문에 미리 방지하려고 overhead를 들이는 것이 비효율적이라 이 방법을 주로 사용함  

 

deadlock prevention

데드락의 4가지 성립조건 중 하나를 차단해서 데드락에 들어가지 못하도록 원천차단 하는 방법 

Mutual Exclusion

- 매 순간 하나의 프로세스만이 자원을 사용해야 한다는 조건 

- 이건 어쩔 수 없다. 공유해서는 안되는 자원이기 때문. 이걸 배제할 수 있으면 애초에 데드락이 발생하지 않을 것 

Hold and Wait

- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다는 조건 

-> 자원을 기다려야 하는 상황에서는 자원을 보유하고 있지 않게 만들어야 한다 

방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 한다 (프로세스가 평생 필요로 하는 자원을), 종료될 때 모두 반납 

중간에 추가로 필요한 자원이 없게 하는 방법. wait 할 일이 없다 

하지만 프로세스가 매 시점마다 필요로 하는 자원이 다른데 이걸 처음부터 다 들고 있으면 비효율적이다 

방법 2) 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다

즉 이미 hold 한 자원도 뱉어내고 기다린다

No Preemption

- 프로세스는 자원을 스스로 내어놓을 뿐 뺏기지 않는다는 조건 

-> 자원을 뺏을 수 있게 하면 데드락이 안생김

-> 모든 필요한 자원을 얻을 수 있을때 프로세스가 다시 시작된다 

중간에 뺏으면 곤란한 자원도 있다. 

CPU나 memory는 아무때나 뺏어도 된다. 자원의 현재 사용 상태를 save, restore 할 수 있기 때문 

Circular Wait 

- 꼬리에 꼬리를 물며 cycle이 형성되어 데드락이 형성되는 경우 

-> 자원에 할당 순서를 매겨서 정해진 순서대로만 자원을 할당하는 것

예)  1번을 갖고 3번을 기다리는 프로세스랑 3번을 갖고 1번을 기다리는 프로세스가 있어야 cycle로 인해 데드락이 생긴다 

그런데 3번을 갖고있는 애가 1번을 얻으려면 일단 3번을 release 해야 순서를 지키면서 얻을 수 있다 

즉 cycle이 생기지 않는다 

 

DeadLock Prevation은 데드락을 예방할 수 있지만 자원에 대한 이용률이 낮아지고 시스템의 성능이 나빠지고 기아 문제가 발생할 수 있다 

생기지도 않을 데드락을 생각해서 제약조건을 많이 달아서 비효율적이다 

DeadLock Avoidance 

- 프로세스가 시작되어서 끝날 때까지 그때그때 쓰려는 자원의 종류나 수가 다르다

- 프로세스가 시작될 때 프로세스가 평생 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피해가는 것임

- 이 자원을 할당해주면 데드락이 생길 가능성이 있겠다고 판단이 되면 자원이 여유가 있어도 할당을 안해줌 

 

avoidance는 두가지 방법으로 가능하다

1. 자원 당 인스턴스 1개 : 자원 할당 그래프 : Resource Allocation Graph Algorithm

2. 자원 당 인스턴스 여러개 : Banker's Algorithm 

 

Resource Allocation Graph Algorithm

자원의 인스턴스가 하나밖에 없는 상황에서 사용 

기존 자원 할당 그래프에 점선이 추가되었다

점선은 프로세스 -> 자원 방향만 있다. 프로세스가 자원을 적어도 한번 사용할 일이 있다는 뜻이다

실제로 요청을 하면 점선이 실선으로 바뀐다 

맨 오른쪽 그림은 데드락이 아니다. P1 -> R2가 점선이기 떄문이다. (당장 요청한 것은 아님)

만약 진짜 요청한다면 점선이 실선으로 바뀔 것이다. 그럼 cycle이 생기고 데드락 발생한다. 

점선을 포함해서 cycle이 만들어진 것은 데드락은 아니지만 데드락의 가능성이 있다. 

 

1번째 그림 상태에서 P2가 R2를 요청하고(2번쨰 그림, 점선이 실선으로) 받아들이면 (3번쨰 그림, R2가 P2에게 할당) 데드락의 가능성이 있는 상태가 된다.

따라서 데드락의 가능성이 있는 요청을 애초에 받아들이지 않는 것이 Deadlock Avoidance이다 

 

P1이 R2를 요청하는건 줘도 된다. 왜냐하면 cycle이 생길 일이 없기 떄문이다. 

 

available한 자원이 있다고 해서 다 내어주먼 안되고 데드락의 위험성이 있으면 애초부터 자원을 주지 않는 방식으로 데드락을 막는 것이다. 

 

Banker's Algorithm

자원 당 인스턴스가 여러개 있는 경우다.

Allocation : 지금 할당받은 자원 

Max : 프로세스가 살면서 최대로 이 자원을 할당받을 때 개수

Availabe : 각 자원 개수에서 지금 할당된 자원들을 빼서 현재 가용 인스턴스 개수 

 

이제 프로세스가 자원을 요청하면 주는데 마찬가지로 가용이라고 무조건 주는게 아니라 문제가 생길 수 있으면 안준다.

 

Need : 추가 요청 가능량 Max - Allocation 

최대 요청 가능량에서 현재 할당된 걸 뺀것이다. 

 

P1 reqeust(1,0,2) 즉, P1이 A 1개, C 2개를 요청했다고 하자. 

Available, 가용 가능한 A가 3개 C가 2개이므로 줄 수는 있다.

그런데 P1의 Need, 즉 추가로 요청하는 것이 가용자원으로 모두 충족이 되는 지 확인 후 준다 

P1의 Need는 (1,2,2)로 Available (3,3,2)로 충족할 수 있다. 이런 상황에서는 주고, 데드락으로부터 안전하다.

 

P0 request(0,2,0)을 예시로 들어보자.

Available (3,3,2)이므로 B 2개 여분은 있다.

하지만 P0의 Need는 (7,4,3)으로 Available로 충족이 안된다.

이럴 떄는 줄 수 있어도 안 준다. 왜나하면 P0이 최대로 요청을 해버리면 가용자원으로 처리가 안되고 데드락이 걸리기 때문이다.  

이럴 때는 다른 프로세스들이 처리가 끝나고 자원을 release 해서 가용자원이 되면 그 때 자원을 할당해준다. 

 

즉 무조건 최악의 경우를 가정하고 자원을 줄지 말지 결정하는 알고리즘이다. 

보수적으로 절대 데드락이 생기지 않도록 한다. 프로세스가 최대 요청을 한다고 생각하고 자원을 줄지 말지 결정한다.

 

프로세스들이 할일을 마치고 자원을 반납하면 가용 자원이 늘어날 것이고 그에 따라 더 많은 프로세스의 요청을 받아줄 수 있다. 

<P1,P3,P4,P2,P0> 이런 순서대로 받아들일 수 있는데 이런 것을 safe state라고 한다. 절대 데드락이 생기지 않는 상태다. 

bankers algorithm은 모든 프로세스가 한번에 최대 요청을 해도 데드락이 생기지 않는 그런 상황에 대해서만 요청을 수락한다. 

 

데드락은 안생기지만 비효율적이다. 자원이 남아 돌아도 혹시 모를 상황을 대비해서 안 주기 때문이다. 

 

즉 Deadlock avoidance는 자원 할당이 데드락으로부터 safe 한지를 동적으로 조사해서 safe 한 경우에만 자원 할당한다.

safe state : 시스템 내의 프로세스에 대한 safe sequence가 존재하는 상태 

safe sequence 

- sequence <P1,P2,...Pn>이 safe 하려면 Pi의 자원 요청이 "가용 자원+모든 Pj(j<i)의 보유 자원" 에 의해 충족되어야 함 

가용자원 + Pj(j<i) 인 이유는 이전 프로세스들이 끝나면서 자원을 뱉어내기 때문이다.

- 자원 요청을 즉시 충족할 수 없으면 이전 프로세스가 끝날 때까지 기다렸다가 만족시켜서 수행한다

 

시스템이 safe state에 있으면 데드락이 발생하지 않는다

unsafe state에 있으면 데드락의 가능성이 있다. 

 

 

DeadLock Detection & Recovery

데드락 detection 

자원 당 인스턴스 1개 : 자원 할당 그래프 사용

자원 당 인스턴스 여러개 : 테이블을 그려서 확인 

 

그래프의 cycle을 통해서 데드락 여부를 파악할 수 있다. 

자원할당 그래프를 중간에 자원을 빼버리고 더 간단하게 그릴 수 있다. (오른쪽 wait for graph)

P4->P1 : P4는 P1이 가진 자원을 기다리고 있다. 

 

프로세스 n개일 때 wait for graph에서 cycle 여부를 조사하는 알고리즘은 O(n^2)의 시간복잡도를 갖는다. 

점이 n개면 화살표가 최대 n(n-1)개 생기기 때문이다.

DFS나 BFS로 cycle 여부를 알 수 있다. (조금 수정하면)

 

자원 당 인스턴스가 여러개인 경우는 테이블을 사용한다. 

데드락 detection은 프로세스가 요청하면 자원을 다 준다. 

어떤 프로세스가 자원을 최대로 요청할지인 max값은 여기서 알 필요는 없다.

Request는 현재 요청이다. 

이번에는 보수적이지 않고 낙관적으로 접근해야 한다. 

그냥 프로세스가 추가로 요청한 건 없다고 치고 할당된 자원을 반납한다고 가정한다. 

그러면 sequence <P0,P2,P3,P1,P4>가 가능하다. 

 

P2의 요청이 000이 아니라 001이라면?

데드락이 발생한다 

 

데드락이 발견되면 ? 

Recovery를 해야한다.두가지 방법이 있다

1. Process termination

- 데드락에 연루된 모든 프로세스를 한번에 죽인다 

- 데드락에 연루된 프로세스를 하나씩 죽여본다. 

2. Resource Preemption 

- 데드락에 연루된 프로세스로부터 자원을 뺏는다. 

- 누구한테 뺏을지 victim을 선정한다

- Starvation이 발생할 수 있다 

동일한 프로세스가 계속해 victim으로 선정되는 경우

자원을 뺏는 패턴을  조금씩 다르게 해서 예방할 수 있다. (똑같은 패턴이 계속 발생하는 것도 예방 가능)

 

 

Deadlock Ignorance 

아무일도 안한다

데드락을 예방하는것은 오버헤드가 크다

감지하는 것도 조금만 늦어져도 오버헤드가 크다 

그냥 놔두고 데드락으로 인해 시스템에 문제가 생기면 사용자가 알아서 프로세스를 종료시키는 것이다. 

데드락은 드물게 발생해서 데드락에 대한 조치 자체가 오버헤드가 더 크다