[CS스터디] Deadlock

by VICENTE97P4

May 3, 2022, 2:22 p.m.

Deadlock

Process는 일을 할 때 자원이 필요합니다.

CPU, memory, bus 같은 HW 자원과 semaphore, lock 같은 SW 자원 모두 필요하죠.

그런데 이 자원들 중 일부는 확보하고 일부는 확보 못할 수 있습니다.

그때 resource를 가진 다른 process가 resource를 반환해주길 기다릴 수 있는데 이게 순환적으로 이어질 수 있습니다.

그럼 이 관계에 있는 process들이 일을 못하고 진도를 못나간 채 멈춰서는 경우를 deadlock이라고 합니다.

발생조건

deadlock 발생 조건은 4가지입니다.

1. Mutual exclusion(상호배제)

자원의 공유가 불가능한 경우입니다.

- 한 process가 어떤 자원을 사용하고 있으면 다른 process는 그 자원을 사용할 수 없는 경우를 말합니다.

이런 자원에 대해서만 deadlock이 발생합니다.

2. No preemption

어떤 process가 자원을 잡고 있으면 그 자원은 소유하고 있는 process가 놓기 전에 다른 process가 뺏어서 사용할 수 없는 경우입니다.

- 즉, 자원에 대한 release는 그 자원을 잡고 있는 process가 일을 끝마치고 나서 자발적으로 자원을 놓게될 때만 release할 수 있습니다.

강제로 뺏을 수 없다는 말이죠.

3. Hold and wait

어떤 process가 일을 하기 위해 필요한 자원은 통상 여러개입니다.

이때 필요한 자원 중 일부는 잡고, 일부는 잡지 못했을 때, 이미 잡은 자원들을 '에라 모르겠다!' 하면서 놓지 않는다는 말입니다.

- 즉, 모든 process는 자기가 확보한 자원은 손에 쥐고 기다린다는 뜻입니다.

4. Circular wait

일부 자원을 잡고 다른 process의 자원을 기다리고 있을 때 원형 대기가 이루어지는 경우입니다.

p0은 p1을, p1은 p2를 p2는 다시 p0의 자원을 기다리는 경우입니다.

위 4가지 경우를 모두 만족한 경우에만 deadlock이 발생합니다.

OS의 Deadlock 대처법

1. deadlock이 아예 발생하지 못하도록 만듭니다.

- deadlock prevention

- deadlock avoidance

2. deadlock을 허용하되 발생 시 조치합니다.(recover)

- deadlock detection

3. deadlock 무시

- 의외로 대부분의 OS가 선택하는 방법입니다.

요즘 computer system은 자원이 풍부해서 웬만하면 deadlock이 잘 발생하지 않습니다.

게다가 OS가 관리하는 자원들은 경쟁이 심한 편도 아닙니다.

그래서 deadlock 발생 여부 계산에 드는 오버헤드가 deadlock 발생 확률보다 훨씬 높기 때문에 무시한다고 합니다.

그럼 왜 배울까요?

DB에서는 deadlock이 발생할 수 있다고 합니다.

DB의 경우 많은 user들이 동시에 접근 하는데 그 요청을 thread를 만들어서 처리합니다.

이때 그 많은 thread가 공유된 DB에 접근하기 때문에 경쟁이 심해져서 deadlock이 발생할 수 있다고 합니다.

또한 요즘처럼 core와 thread가 많은 시스템에서는 lock이나 semaphore 같은 동기화 부분에서도 경쟁이 치열해서 deadlock의 위험성이 더욱 커집니다.

Deadlock Prevention

아예 deadlock이 발생할 수 있는 조건을 없애는 방법입니다.

위에서 말했던 deadlock 발생 4가지 조건 중 하나를 원천적으로 막는 방법입니다.

그럼 경우를 하나씩 따져봅시다.

1. Mutual exclusion(상호배제) 없애기

자원의 공유 여부는 자원의 특성에 따라 이미 결정되기 때문에 OS가 물리적으로 변경시킬 수 없습니다.

따라서 mutual exclusion을 없애는 것은 불가능합니다.

2. Hold and wait 없애기

추가적인 자원 확보에 실패하면 이미 확보한 자원을 모두 놓아버립니다.

이 방법을 사용하면 자원을 동시에 확보 가능하면 확보하고, 아니면 아예 기다리게 됩니다.

예를 들어 자원 1,2,3이 있다고 하면 1,2를 확보 가능하고 3번 확보에 실패하면 1,2번도 확보하지 않고 기다립니다.

그런데 나중에 자원 3번이 확보 가능할 때 1,2번도 확보 가능하다는 보장이 없습니다.

남아있는 자원을 확보하지 않으니 전체적인 자원의 utilization이 떨어지고 starvation이 발생할 수 있습니다.

* starvation이 생기는 이유는 다른 process들이 자원 1,2,3번을 번갈아가면서 한 개씩 가져다쓰는 경우가 있을 수 있기 때문입니다.

3. No preemption 없애기

자원확보를 못해서 기다리는 process가 있으면 OS가 그 process의 자원을 강제로 빼앗는 겁니다.

* 2번에서 말한 hold and wait 없애기는 동시에 1,2,3을 다 잡거나 아니면 아예 기다리는 방식입니다. 빼앗는 no preemption 없애기와는 다릅니다.

자원 1,2,3이 있을 때 1번 자원을 잡고, 2번을 잡고, 3번을 못 잡으면 1,2번 자원을 빼앗습니다.

즉, 자원을 순차적으로 잡아가는 방식입니다.

어쨌튼 결과적으로 빼앗기는 것은 같기 때문에 hold and wait 없애기 방식과 같이 utilization이 떨어지고 starvation의 위험이 있습니다.

4. Circular 없애기

원형 대기가 생기는 이유는 back edge가 발생하기 때문입니다. 그럼 back edge가 생기지 않도록 해봅시다.

자원의 종류마다 번호를 매깁니다. 예를 들어 CPU: 1번, memory: 2번 등등..

그리고 낮은 번호부터 순차적으로 확보하도록 순서를 정해줍니다.

예를 들어 3, 5, 7번의 자원이 필요하면 무조건 3 -> 5 -> 7 순으로 자원을 확보하도록 합니다.

그럼 높은 번호에서 낮은 번호로 가는 back edge가 발생하지 않게 되어서 원형이 형성될 수 없습니다.

하지만 circular wait 역시 resource utilization이 떨어집니다.

예를 들어 1, 3, 7번의 자원이 있을 때, 1, 3번의 자원을 잡을 수 없으면 7번 자원이 활용 가능한데도 불구하고 잡지 않고 1, 3번을 기다리기 때문입니다.

따라서 전체적으로 resource utilization이 떨어지게 됩니다.

정리하자면 mutual exclusion은 없앨 수 없고, no preemption과 hold and wait를 없애면 starvation과 utilization의 감소,

circular의 제거 또한 utilization의 감소를 불러옵니다.

따라서 deadlock prevention은 별로 좋은 방법이 아닙니다.

Deadlock avoidance(회피)

회피 방법은 deadlock 발생 4가지 조건을 모두 허용하되 동작 과정에서 deadlock이 발생하지 않도록 제어하는 방법입니다.

OS는 자신의 상태를 제어할 수 있습니다.

어떤 process가 자원을 request했을 때 OS가 이를 받아들이면 deadlock이 발생할 수 있겠다고 판단하면 

자원을 주지 않습니다. deadlock 가능성이 없는 안전한 길로만 가는 것이죠.

즉, 자원을 request한 process에게 자원을 줬을 때 deadlock 발생 가능성이 있으면 할당하지 않습니다.

오직 deadlock 가능성이 없을 때에만 자원을 할당합니다.

Deadlock 예측을 위해 정보를 수집하여 안전성을 평가합니다.

- 각 process마다 일정 시점에서 각 자원의 최대 사용량을 선언하게 만듭니다.

이 정보를 가지고 현재 자원 할당 상황을 고려해서 algorithm을 돌려서 circular wait가 발생하지 않는 길로만 갑니다.

Safe state

process가 request한 자원을 주었을 때 모든 process가 다 작업을 끝마칠 수 있는 sequence가 존재하면 안전한 상태입니다.

- 각각의 process가 이미 확보한 자원 + 먼저 종료된 process가 반납한 자원의 양을 합해서 각 process가 충분히 일을 끝마칠 수 있는지를 따집니다.

이 safe state에 있으면 deadlock이 발생하지 않습니다.

unsafe state

safe state로 가는 sequence를 못 찾은 경우를 unsafe state라고 합니다.

물론 unsafe state라고 해서 무조건 deadlock이 발생하는 것은 아닙니다.

process가 모든 자원을 최대치 만큼 동시에 사용하여 일을 처리하는 것이 아니고, 번갈아가면서 자원을 쓰기 때문입니다.

(자원 1,2,3을 동시에 다 쓰는게 아니고, 1번 쓰고 그 다음에 2번 쓰고..)

그래서 unsafe라고 해도 deadlock에 걸릴 확률은 낮으나 그래도 확률이 조금이라도 있으니 unsafe state를 피합니다.

이 unsafe state로 가는 것을 피한다고 해서 avoidance라고 합니다.

Avoidance algorithm

resource type이 instance(자원 수)를 1개만 가지는 경우

- resource allocation graph로 바로 결정을 내릴 수 있습니다.

여러 개의 instance를 갖는 경우

- banker's algorithm을 사용합니다.

instance가 1개인 경우

점선은 claim edge입니다.

- 미래에 이 자원을 사용할 거라는 의미입니다.

자원쪽으로 향하는 실선은 request edge입니다.

- claim edge가 있는 resource에 대해서만 request edge가 그려집니다.

process 쪽으로 향하는 실선은 assignment edge입니다.

- 자원이 할당됨을 의미합니다. request edge가 assignment edge로 바뀝니다.

- 자원 사용이 끝나면 assignment edge가 없어지는 것이 아니고 claim edge로 바뀝니다. 자원을 몇 번 사용할지 모르기 때문입니다.

safe state 여부 판단 방법은 claim, request, assignment edge 모두를 포함해서 cycle이 생기면 unsafe입니다.

위 그림에서 P2에게 R2를 주면 cycle이 형성되기 때문에 unsafe 상태입니다.

물론 P1이 R1으로 일을 마치고 반환된 R1을 P2가 가지고 R1, R2로 일을 할 수도 있습니다.

하지만 cycle이 생길 확률이 미약하게나마 있기 때문에 unsafe 상태이고, unsafe 상태로는 가지 않습니다.

요약하자면, single instance일 때는, request가 왔을 때 request를 받아들였다고 가정하고 assignment edge를 그려봤을 때,

cycle을 형성하게 되면 request를 받아들이지 않습니다. resource가 available 해도 그냥 available 상태로 둡니다.

반대로 cycle이 형성되지 않으면 assign 합니다.

Multiple instance인 경우 -> Banker's algorithm

Banker's algorithm에는 기본적인 가정 3가지가 있습니다.

1. 모든 process는 시작 전 각 resource 별 최대 사용량을 선언합니다.

2. process가 request 해도 safe하지 않으면 기다려야 합니다.

3. process가 필요한 resources를 모두 받았으면 유한 시간 내에 일을 끝내고 resource를 반환해야 합니다.

banker's algorithm에서 쓰이는 자료구조를 적어보겠습니다.

n : process 개수, m : resource 개수
Available : 자원의 개수를 나타내는 vector
- Available[j] = k : j라는 resource type이 k개 남아있다는 뜻입니다.
Max
- Max[i, j] = k : process i가 resource j를 최대 k개 사용한다는 뜻입니다.
Allocation
- Allocation[i, j] = k : process i가 resource j를 k개 할당받은 상태라는 뜻입니다.
Need
- Need[i, j] = k : process i가 resource j를 추가적으로 k개 더 필요로 한다는 뜻입니다.
* Need[i, j] = Max[i, j] - Allocation[i, j] 입니다.

Banker's algorithm

Work는 임시변수라고 합시다. 현재 남아있는 자원의 양을 나타낸다고 합시다.(위에서 적은 Available과 유사합니다.)

Finish는 일이 끝났는지의 여부입니다. i번째 process의 일이 끝났으면 Finish[i] == True입니다.

디폴트 값은 False입니다.

1. process i를 찾습니다.

a) Finish[i] == False // 일이 안 끝난 process 중

b) Need[i] <= Work // 추가적으로 필요로 하는 자원의 양이 현재 남아있는 자원의 양 이하인 process를 찾습니다.

그럼 찾은 process i에게 자원을 할당하면 process i는 작업을 끝낼 수 있습니다.

2. process i에게 자원을 할당해줍니다. 그럼 i는 일이 끝나고 자원을 반납합니다.

Work = Work + Allocation[i] // process i의 자원 반납

Finish[i] = True // process i 종료

이후 다시 1번으로 돌아가서 끝나지 않은 다른 process를 찾습니다.

그럼 1번과 2번을 반복할 때마다 Work가 증가합니다. 즉, 사용 가능한 자원의 양이 증가합니다.(일이 끝나고 반납 받으니까요.)

그러다가 모든 process가 일이 끝나면

3. process의 종료 sequence가 생겼다는 말입니다. 이는 safe state라는 것을 의미합니다.

그런데 false인 process가 1개라도 있고, available한 자원의 양으로 Max를 충족시키지 못하는 경우에는 unsafe state임을 의미합니다.

safe 상태이면 실제로 process i에 자원을 할당합니다.

unsafe 상태이면 process i는 기다리고, 값들을 원래대로 복원합니다.

- process i는 기다리다가 나중에 다른 process가 종료되고 자원을 반납해서 safe 상태가 확인되면 자원을 받습니다.

자원 소유 상태가 위와 같다고 해봅시다.

이때 P1이 자원을 1, 0, 2 만큼 요구했다고 해봅시다. 

그럼 1, 0, 2를 process 1한테 주었을 때 이런 상태가 됩니다.

위 경우에는 1,3,4,0,2 순서의 sequence가 잇으니 safe state라고 판명났습니다.

그래서 process 1에게 1, 0, 2를 주면 됩니다.

- process 4가 3, 3, 0 을 요청했으면 줘도 될까요?

- process 0가 0, 2, 0을 요청했으면 줘도 될까요?

위는 안되고 아래는 됩니다. 왜인지는 직접 해봅시다 ^^

Deadlock detection

Deadlock 발생 전까지는 아무것도 하지 않습니다.

그냥 request가 오고 available resource가 충분하면 그냥 자원을 줘버립니다.

- 물론 자원이 모자라서 주지 못하면 기다려야 합니다.

- detection은 현재 deadlock 발생 여부를 따집니다.

Detect 역시 resource type 당 instance가 1개인 경우와 여러개인 경우로 나뉩니다.

resource type 당 instance가 1개인 경우

resource allocation graph는 request한 process는 다른 process가 해당 resource를 놓아주길 기다립니다.

그에 반해 여기서 사용할 wait-for graph는 resource 부분을 없애고 process 간에 관계만 표시해주면 됩니다.

이미 자원을 할당한 상태여서 process vertex밖에 없으니까요.

P1 -> P2 : process 1이 process가 가진 resource를 기다리고 있다는 뜻입니다.

위 그림은 a에서 자원을 없애고 wait-for graph로 바꾼게 b입니다.

P1 -> P2 -> P4에서 cycle이 형성되기 때문에 deadlock입니다.

resource type마다 instance가 여러 개인 경우

Deadlock detection algorithm을 사용합니다.

아까 banker's 알고리즘에서 사용했떤 자료구조를 비슷하게 사용합니다.

Available : 현재 사용 가능한 자원 수
Allocation : 각 process 당 어떤 자원이 얼마나 할당되었는지를 나타내는 배열
그리고 미래가 아닌 현재를 보기 때문에 Need, Max 이런건 필요 없습니다!!
Request : request[i, j] = k // process i가 resource j를 k개 요청했다는 뜻입니다.

역시 여기서도 Work = Available입니다.

Finish는 역시 종료여부를 나타낸 것이구요.

allocation된 자원이 0이면 Finish는 True입니다.

?!?!??? 아니 할당된 자원이 0이라도 프로세스의 작업은 안 끝났을 수 있지 않나요?

- 네, 맞습니다. 그런데 여기서는 프로세스가 끝나기를 기다리는 것이 중요합니다. 어차피 프로세스가 가진 자원이 없으면 이 프로세스를 기다리는 프로세스도 없을 것입니다. 그래서 끝나지 않았더라도 allocation된 자원이 0이면 Finish에 True를 넣어줍시다.

1. 

a) Finish[i] = False // 안 끝난 process 중
b) Request[i] <= Work // request가 available 이하인 process를 찾습니다.

avoidance에서는 request가 아닌 Need였는데 detection은 현재가 중요해서 request를 사용합니다.

a와 b를 모두 만족시키면 자원을 줍니다. 그럼 그 process는 최소한 지금은 deadlock chain에 들어있지 않습니다.

그러면 이 process는 deadlock 검사에서 배제해야 합니다. 그리고 일을 끝낸 다음에는 자원을 반납해야 합니다.

2. 그래서 반납했다고 치고

Work = Work + Allocation // 반납으로 인한 available한 자원양 증가
Finish[i] = True // deadlock과 무관한 process가 되었으니 해당 process는 끝났다고 판단합니다.

그리고 1번으로 돌아가서 다시 가능한 process에게 자원을 줍니다.

더이상 가능한 process를 찾지 못할 때까지 반복합니다.

3. 모든 Finish[i] = True면 deadlock이 아니라는 의미입니다.

하나라도 False가 있다면 현재 상태는 deadlock이라고 판단합니다.

위 예시에서는 Process 0, 2, 3, 1, 4 Sequence가 있기 때문에 deadlock이 아닙니다.

그럼 detection 시간 복잡도는 얼마일까요?

O(m * n^2)입니다.(m: 자원의 개수, n: process 개수)

그런데 만일 자원의 개수가 process 개수와 비슷하게 된다면 n^3까지 치솟게 됩니다.

원칙대로라면 자원 할당이나 요청이 바뀔 때마다 이 알고리즘이 돌아가야 합니다. 

그런데 오버헤드가 너무 심하니 요청을 받아들일 수 없을 때만 detection 하기도 합니다.

Recovery from deadlock

1. deadlock에 관여된 process를 죽입니다.

2. deadlock에 관여된 process의 자원을 강제로 뺏기

두 가지 정도가 있습니다.

1. process 죽이기

deadlock이 해소될 때까지 하나씩 abort 시킵니다.

- priority 문제가 생깁니다.

작동시간이 얼마 안 된 process를 죽일지, 사용한 자원의 양이 적은 애를 죽일지(사용된 자원의 양이 많으면 나중에 얘를 다시 실행했을 때 또 그만큼 쓸거기 때문), 앞으로 사용할 자원의 양이 많은 애를 죽일지, background job을 먼저 죽일지(interactive는 user가 불편함을 느끼기 때문) 등등..

2. 자원 빼앗기

victim을 선정해서 자원을 빼앗습니다.

- rollback

한 process의 자원을 뺏어서 그 process를 이전 상태로 돌려놓고 deadlock 해소 후 다시 시작하는 방법입니다.

그런데 자원을 뺏기는 process만 지속적으로 빼앗길 수 있습니다. 그래서 몇 번 rollback 했는지 신경써줘야 합니다.

Avoidance와 detection 차이

Avoidance

미래를 예측해서 안전한 길로만 가는 방법입니다.

모든 process가 동시에 최대 자원을 요구한다고 가정하는 worst case assumption을 했습니다.

사실 자원을 줘도 안전할 확률이 높은데 안 주고 기다리라고 하니까 자원의 낭비가 발생합니다.

Detection

현재 시점에 생긴 request만 생각하는 best case assumption을 합니다.