7. Deadlocks

The Deadlock Problem

기본적으로 프로세스가 일을 할 때는 프로세스가 일을 하기 위해서 필요한 자원이 있어야 한다. 대표적으로 CPU, 메모리, 버스 등의 하드웨어 자원도 있고, 세마 포어 또는 lock 같은 소프트웨어 자원도 있다.
=> 락을 확보해야 일을 할 수 있으니까.
=> 메모리에 값을 저장할 때는 메모리 버스를 확보해야 한다.
=> CPU 스케줄링도 마찬가지, CPU를 확보를 해야 프로세스가 동작될 수 있다.

프로그래머가 명시적으로 자원을 요청하지 않아도, 시스템 내에는 자연스럽게 자원을 확보하고 반납하는 과정이 발생하고 있다.

근데 어떤 일을 하기 위해 필요한 리소스가 하나가 아니다. 여러 개의 리소스를 확보해야 진도를 나갈 수 있는데, 운이 나쁘게 일부 리소스만 확보하고 나머지 리소스는 확보를 못 해서 그 리소스를 가지고 있는 다른 프로세스가 그 리소스를 놓을 때까지 기다려야 하는 상황이 발생할 수 있다.

A는 B라는 프로세스가 가진 리소스를 대기하고, B는 C라는 프로세스가 갖고 있는 리소스를 대기하는 것 처럼 연쇄적으로 대기가 발생할 수 있다.
이렇게 연쇄적인 대기로 인해 전체 프로세스가 진도를 못나가고 대기를 하고 있는 상황을 데드락 (교착상태)이 발생했다고 한다.

 

Deadlock Characterization

• Mutual exclusion: 자원의 공유가 불가능해야 한다. => 공유 가능한 자원은 데드락과 상관 X

 

• No preemption: 어떤 프로세스가 자원을 잡고 있으면 그 자원은 그 프로세스가 자발적으로 놓을 때까지는 다른 프로세스는 그 자원을 쓸 수 없다는 뜻.
  자원을 놓게 되는 행위는 자원을 잡고 있는 프로세스가 일을 끝마치게 돼서 자발적으로 놓는 경우만 있다.
  => OS는 프로세스의 자원을 강제로 뺏지 않는다.

 

• Hold and wait: 어떤 프로세스가 일을 하기 위해 필요한 자원은 여러 개가 있다고 했다.
  근데 반쯤 잡고 나머지 반을 기다리고 있을 때, 나머지 반을 잡을 수 없는 상황이네 라고 확인했을 때, 음,, 나는 일을 어짜피 못 하니까 나머지 반은 놓아버리자 이런 식으로 동작하는 게 아니라, 자원을 잡은 채로 대기를 하게 된다는 조건

 

• Circular wait: P0는 P1이 갖고 있는 자원을 기다리고 있고, P1은 P2가 갖고 있는 자원을 기다리고 쭉쭉 가서 Pn이 다시 P0가 갖고 있는 자원을 기다리는 "원형 대기"가 발생해야 한다.

 

Resource-Allocation Graph

데드락을 formal하게 정의하기 위해서 모델링하기 위해서 그래프를 사용하는데 대표적인 모델링 툴이 Resource- Allocation graph이다.

Vertex는 2가지가 있다.
프로세스들이 하나의 Vertex가 되고, 자원들이 하나의 Vertex가 된다.

그리고 프로세스는 여러 개가 있고 자원의 종류도 여러 개가 있을 수 있다.

프로세스 -> 자원 방향의 화살표는 Request를 의미하고, 자원 -> 프로세스 방향의 화살표는 Allocation을 의미한다.

위의 예시에서는 P1은 R1을 요청하고 있다. R1의 instance는 하나인데 그 하나는 P2에게 할당되어 있기 때문에 P1은 리소스를 할당받을 수 없어 대기하고 있다.

 

Basic Facts

Resource allocation graph가 edge들로 이루어진 cycle을 갖고 있지 않으면 데드락이 발생하지 않은 것이다.
cycle이 있다면 즉, 원형 대기가 발생했다면 무조건 데드락이냐? 그건 아니다.
resource type마다 instance가 하나면 데드락이지만 instance가 여러 개인 상황에서 cycle이 발생했다면 데드락일 수도 있고 아닐 수도 있다.

 

위의 예시에서는 2개의 사이클이 존재한다.

하지만 R2의 instance가 2개이기 때문에 위 예시는 데드락일 수도 있고, 아닐 수도 있다.

그런데 모두가 일을 하지 못하고 대기만 하고 있으므로 데드락이 맞다.

P1이 일을 하기 위해서는 R1을 확보해야 하는데 R1은 P2가 진도를 나가서 다 쓰고 놓아야 한다.
P2가 진도를 나가려면 R3를 확보해야 하는데 R3는 P3가 갖고 있기 때문에 P3가 진도가 나가서 끝나야 한다.
P3가 진도를 나가려면 R2를 확보해야 하는데 P1과 P2가 갖고 있기 때문에 P1, P2 중 하나가 진도를 나가서 끝내고 자원을 반납해야 한다.
=> 서로가 서로를 기다리는 상황이 발생했기 때문에 데드락이다.

 

이 예시에서 역시 사이클이 발생했지만, 위의 경우엔 데드락이 아니다.

P2가 일을 마치고 R1을 반납하게 되면, P1은 자원을 확보하여 일을 할 수가 있다.

P3 역시 P4가 일을 마치고 R2를 반납하거나, 자원을 확보한 P1이 일을 마치고 R2를 반납하게 되면 일을 할 수가 있다.

=> 언젠가 모두가 일을 마칠 수 있으므로 데드락이 아니다.

 

Methods for Handling Deadlocks

OS는 데드락에 대해서 어떻게 대처할까.

1. 절대로 데드락 자체가 발생하지 못하도록 하는 방법.

=> Prevent와 Avoidance 2가지 방법이 있다.

2. 데드락이 발생하는 것을 허용하되, 데드락이 발생했을 때는 조치를 취해준다.

=> 평소에 감시를 하다가 발생하면 조치

3. 데드락을 무시하는 전략

=> 데드락이 발생하면 사용자가 컴퓨터를 껐다 켜야 한다.

말도 안 되는 전략처럼 보이지만, 의외로 요즘 대부분의 OS가 사용하고 있는 방식이다.

그 만큼 데드락이 발생할 확률이 매우 드물다는 것이다.

=> 요즘 시스템들은 자원이 풍부하기 때문에 데드락이 잘 발생하지 않는다.

그렇다고 절대 발생 안 하는 것은 아니다.
락이나 세마포어의 경우 이를 확보하기 위한 경쟁이 엄청 치열하게 일어난다.
특히 멀티 코어나 멀티 스레드의 경우 더욱 치열하게 발생한다.
=> 데이터 베이스, 애플리케이션(소프트웨어) 입장에서는 엄청 자주 발생한다.

그런데 운영체제 입장에서 볼 때 운영체제가 관리하는 자원들 사이에는 경쟁이 그렇게 치열하게 발생하지 않기 때문에, 데드락이 잘 발생하지 않더라.
그래서 굳이 데드락까지 신경쓰면서까지 운영체제가 일을 해줄 필요가 없더라는 것.

=> 그럼 왜 배우냐?
운영체제에서는 중요하지 않더라도 데드락 개념 자체가 중요하기 때문에.
아까 말했다시피 데이터 베이스 시스템에서는 이 문제가 매우 심각한 문제가 될 수 있다.
자원이 넉넉하지 않던 시절엔 OS에서도 발생을 했었으니까 OS에서 다루고 있다.

 

Deadlock Prevention

데드락이 발생할 수 있는 조건 차제를 막아버린다.
앞에서 데드락이 발생하려면 4가지 조건을 만족해야 한다고 했다.
그 중에 하나를 만족하지 못하도록 원천적으로 막아버리면 되겠다.
=> 그럼 그냥 데드락을 신경쓰지 않아도 발생을 하지 않게 된다.

 

1. Mutual Exclusion

자원을 공유하는 것을 막아버린다?

이건 OS가 정할 수가 없는 것이다. => 이 조건을 없애는 것은 애초에 불가능하다.

 

2. Hold and Wait

그럼 Hold and wait 조건을 없애 보자
=> 잡고 기다리지 못 한다는 것은 무조건 빈 손에서 시작해야 한다는 뜻이다.
빈 손인 상태에서 한 번의 요청으로 한 번에 모든 자원을 확보하지 못 하면 다 내려놓는다.
=> 모든 자원을 확보할 수 없다면 이미 확보한 자원도 내려 놓게 (all or nothing)

=> 이 방법을 현실화 시키려면?
1, 2, 3번 자원을 확보해야 하는 상황이라면 1, 2, 3번 중에 하나라도 확보하지 못하면 모두 내려 놓도록.
모두 확보할 수 있을 때만 확보하도록 한다.

그런데 이렇게 하면 resource utilization이 떨어지게 되고, Starvation이 발생할 수 있다.

예를 들어 1, 2번 자원은 확보를 했는데, 3번을 확보하지 못하면 이미 확보한 1, 2 번도 내려 놓는 방식인데 나중에 3번을 확보할 수 있게 되었을 때 1, 2번이 남아있을 것이라는 보장이 없다.
그러면 또 다시 내려놓고 모든 자원을 확보할 수 있을 때까지 기다린다.
나중엔 또 1번은 확보할 수 있지만, 나머지를 확보하지 못 해서 또 기다려야 하는 상황이 발생할 수 있다.

 

3. No Preemption

No preemption 조건을 없애보자.
=> 이 말은 이 프로세스가 자원을 확보할 수 없어서 기다리고 있으면 이 프로세스가 갖고 있는 자원을 OS가 뺏어버리겠다는 뜻.

Hold and wait와 차이가 뭐냐, Hold and wait는 빈 손에서 시작해서 1, 2, 3 번을 동시에 확보하지 못하면 그냥 놓아버린다.
No preemption은 1번 잡았네? Ok, 2번도 잡았네? Ok, 근데 3번을 요청했는데 못 잡으면 1, 2번도 다 뺏어가버림.

=> Hold and wait를 막아버린 것과 결과적으로는 사실 같다.
=> 결과적으로는 Hold and wait를 막은 것과 같기 때문에 Hold and wait를 없앴을 때와 똑같은 문제를 가진다.

=> resource utilization이 떨어지고 starvation을 유발할 수 있다.

 

4. Circular Wait

원형 대기가 발생하지 않도록 하는 방법은 뭘까?
자원의 종류마다 번호를 매긴다. CPU는 1번, 메모리는 2번, ... 이렇게 자원마다 번호를 매겨서 어떤 프로세스가 자기가 필요로하는 자원이 있으면 자원의 번호를 보고 낮은 번호부터 확보를 해라 이렇게 순서를 정해준다.

3, 5, 7번 자원이 필요하다면 3, 5, 7 순서대로 확보하도록 해야 함.
7, 3, 5 뭐 이런 순으로 확보하는 건 불가능.

3번을 확보하지 못 하면, 5번을 확보할 수 있어도 일단 3번을 먼저 기다린다.

이러면 왜 원형대기가 발생하지 않을까?
P0가 P1이 가진 자원을 기다린다고 했을 때, 낮은 번호부터 요청을 하기 때문에 P1이 갖고 있는 자원은 P0가 갖고 있는 자원보다 번호가 높은 자원이다.
또 P1이 P2가 가진 자원을 기다린다고 했을 때 P2가 가진 자원은 P1이 가진 자원보다 높은 번호의 자원이다.
이렇게 되면 마지막 프로세스인 Pn이 P0가 가진 자원을 기다리는 상황이 발생할 수가 없다.
Pn이 가진 자원이 제일 높은 번호의 자원일 테니까.
=> 원형 대기(사이클)가 발생하지 않음

그러나 이 방법 역시 자원의 활용도가 떨어진다. 7번을 확보할 수 있음에도 3번을 확보하지 못해서 확보하지 않는다.
=> 만약 7번을 확보했다면 7번을 가지고 할 수 있는 일이 있을 수 있다.
=> 그것마저 못 하게 되는 것이다.

=> 데드락 Prevention은 공통적으로 자원 활용의 효율이 떨어지기 때문에 근본적으로 좋은 방법이 아니다.

 

Deadlock Avoidance

Prevention은 데드락의 싹을 잘라버리는 것이고, avoidance는 4가지 조건을 허용하긴 하지만 데드락이 발생하지 않도록 제어를 하겠다는 방식이다.

프로세스가 OS에게 자원을 요청했을 때, 할당해 줄 자원이 남아 있더라도 이 남아 있는 자원을 요청한 프로세스에게 줬을 때 나중에 데드락을 발생시킬 가능성이 있으면 요청을 받아들이지 않고 기다린다.
이걸 주더라도 데드락이 발생할 가능성이 없다는 것이 보장되면 할당해주게 된다.
=> 매우 보수적이다.
=> 다른 프로세스가 자원을 Release 해서 안전한 상태가 되면 할당해 준다.

=> 회피하기 위해서는 미래에 데드락이 발생할 가능성을 판단해야 한다.
=> 즉, 미래를 예측해야 한다. 그러려면 미리 정보를 수집해야 한다.
어떤 정보?
각 프로세스마다 자기는 일을 할 동안에 이 자원은 최대 몇 개를 사용하고 저 자원은 최대 몇 개를 사용할지 이렇게 각 자원의 타입마다 자원의 최대 사용량을 선언하도록 한다.

이 정보를 가지고 현재 자원의 사용 상황을 고려해서 알고리즘을 돌려서 절대로 원형 대기가 발생하지 않는 길로만 가겠다.  

=> 안전하다고 판단되면 요청을 받아들임

 

Safe State

안전한 상태란 그 상태에서 모든 프로세스가 무사히 종료될 수 있는 프로세스의 종료 Sequence가 존재하면 안전한 상태라고 한다.

각 프로세스에 대해 현재 자기가 이미 확보한 자원과 시스템에 남아있는 자원과 나보다 먼저 끝 마칠 프로세스가 반납할 자원까지 더해서 일을 끝낼 수 있는지를 본다.
=> 이때 프로세스가 Claim한 최대 자원량을 사용했을 때도 일을 마칠 수 있는지 확인한다.

=> 이렇게 해서 모든 프로세스가 종료될 수 있는 Sequence가 존재한다면 안전한 상태라고 판단한다.

 

Safe state => no deadlocks

Unsafe sate => possiblity of deadlock

만약 safe하지 않은 상태이면 데드락이 발생할 "가능성"이 있는 상태라고 판단한다.
아니 모든 프로세스가 종료될 수 있는 Sequence가 없으면 데드락이 발생하는 것 아니냐 왜 발생할 가능성이 있다고 하느냐.

우리가 safe하냐 safe하지 않냐를 판단할 때 어떤 프로세스가 끝이 난다는 기준을 뭘로 잡냐면, 프로세스가 최초에 선언한 "최대" 자원 요구량을 바탕으로 끝이 날 수 있다는 것을 판단한다.

그런데 프로세스는 최대 자원 요구량을 동시에 요구하지 않는다.
1번 3개, 2번 5개, 3번 2개를 최대 자원 요구량으로 선정했을 때, 1번 3개, 2번 5개, 3번 2개를 동시에 요청하는 것이 아닌 1번 3개를 요청해서 일을 하고 반납한 다음 2번 5개를 요청해서 일을 하고 이렇게 할 수도 있다.

그러나 동시에 요청한다고 생각하고 safe한 지를 판단하기 때문에 그러한 Sequence가 없다고 해도 데드락이 발생하지 않을 수도 있다.

=> 그러나 최악의 경우를 생각하고 데드락이 발생할 가능성이 조금이라도 있다면 그 길은 가지 않겠다는 것이 avoidance
=> 매우 매우 보수적

 

Avoidance 알고리즘은 리소스 타입마다 하나의 instance만 가질 때와 하나의 리소스 타입이 여러 instance를 가질 때를 나눠서 생각한다.

리소스 타입이 Single instance를 가질 때는 resource-allocation graph를 사용한다.

리소스 타입이 Multiple instance를 가질 때는 banker's algorithm을 사용한다.

 

Resource Allocation Graph Algorithm (리소스 타입마다 instsance가 하나)

instance가 하나밖에 없는 경우엔 최대 자원 요구량이 무조건 1이기 때문에 사실은 Resource를 사용하냐 안 하냐를 나타낸다.
내가 나중에 사용할 것이라는 것을 Edge를 사용해서 표현할 수 있다.
=> 이것을 claim edge(점선으로 표현)라고 한다.
=> 미래에 언젠가는 이 자원을 사용할 거야 라는 것을 나타낸다.

그리고 실제로 자원을 요청을 할 때는 claim edge가 request edge(실선으로 표현)로 바뀌게 된다.

 

요청이 받아들여져서 자원을 할당 받으면 assignment edge가 그려지게 된다.

request edge에 대해서 request를 받아들여서 assign을 했을 때 safe하면 request edge를 assignment edge로 바꾼다.

single instance에서는 safe한지 판단하는 것이 쉽다. assign을 했다고 치고 assignment edge를 그렸을 때 사이클이 발생하면 safe하지 않은 것이다.

=> 모든 자원의 instance가 하나일 때는 사이클이 발생하면 무조건 데드락이 발생한 것.

 

자원을 할당 받았다가 자원을 반납하게 되면 edge는 없어지는 게 아니라 다시 claim edge로 돌아가게 된다.
=> 사용한다고만 했지 몇 번 사용한다고는 선언하지 않았기 때문에

Claim edge를 Request edge로 바꾸고, 실제 할당을 해준셈 치고 Allocation edge로 바꾸었을 때 사이클이 발생하게 된다.

사이클이 발생했기 때문에 safe하지 않다고 판단한다.
P1이 언젠가 실제로 R2를 요청하게 되면 데드락이 발생하기 때문에 P2에게는 R2를 할당해주지 않는다.

물론 사이클이 발생하긴 하지만 P1이 일을 어떤 순서로 하냐에 따라 데드락이 발생하지 않을 수도 있다.
=> 만약 P2에게 할당해줘도 P2가 다시 반납한 후에 P1이 R2를 요청하면 데드락이 발생하지 않는다.
=> 그래도 일단 발생할 가능성이 있으니까 할당을 하지 않겠다.

 

Banker's Algorithm

Multiple instance를 가지는 resource가 있는 경우에는 데드락을 avoid하기 위해 어떻게 해야 할까?

Banker's Algorith에 대해 살펴보기 전에, Banker's algorithm을 위해 필요한 자료 구조는 어떤 것들이 있는지 보자.

• Available: 이용 가능한 자원의 수

Available[j] = k 라면 Rj 라는 자원을 k개 사용할 수 있다는 뜻이다.

• Max: 최대 자원 요구량

Max[i, j] = k 라면 Pi는 Rj라는 자원을 최대 k개 필요로 한다는 뜻이다.

=> 미리 선언하는 값이다.

• Allocation: 할당된 자원의 양

Allocation[i, j] = k 라면 Pi는 Rj라는 자원을 k개 할당받았다는 뜻이다.

• Need: 할당 받은 자원 외에 추가로 필요로 하는 자원의 양

Need[i, j] = k 라면 Pi는 Rj라는 자원을 k개 추가로 필요로 한다는 뜻.

이걸 어떻게 구할 수 있냐?
처음에 claim한 최대 사용량에서 현재 자신에게 할당된 만큼을 빼면 추가적으로 요청할 수 있는 수를 나타낸다.

Need[i, j] = Max[i, j] - Allocation[i, j]

 

필요한 자료 구조를 모두 알아보았으니, 이제 safe한지 판단하는 algorithm을 살펴보자

Step 1. Work는 현재 시스템에 남아있는 자원의 양을 의미하고, Finish는 각 프로세스가 일을 마쳤는지를 표시하는 Boolean data이다.

Step 2. 현재 끝나지 않은 프로세스 중에, 프로세스가 추가로 필요로 하는 양이 시스템에 남아있는 자원의 양보다 작거나 같은 애들을 찾아라.
=> 추가로 필요로 하는 양은 이미 할당받은 양에서 추가적으로 필요로 하는 양이므로 Max를 한 번에 요청하는 것과 같다.

=> Need < Work라는 것은 현재 시스템의 자원을 몰빵해주면 이 프로세스는 끝이 날 수 있다는 뜻이다.
=> 찾았으면 3번으로 내려간다.

Step 3. 해당 프로세스는 끝이 났다고 표시하고, 해당 프로세스가 할당 받은 자원을 Work에 더해준다(반납).

2, 3번 과정을 계속해서 반복한 후, 모든 프로세스의 Finish 값이 True가 될 수 있다면 safe한 상태라고 판단한다.

 

Process i가 Resource j를 k개 요청했을 때, 받아들일지 말지 결정을 해야 한다.

Step 1. Request <= Need라면 정상적인 요청이므로 다음 단계로 넘어간다.

만약 그렇지 않다면, 자신이 처음에 요구한 요구량을 넘어선 요구이므로 잘못된 요청이다.

Step 2. Request <= Available이면 Request가 현재 시스템 내에 가용한 자원의 양보다 적다는 뜻이다. 그렇다면 다음 단계 로 넘어간다.

step 3. 일단 줬다고 치고, 준 이후의 Available, Allocation, Need 값을 계산한다.

이 값을 기준으로 safety algorithm을 돌려서 safe하면 실제로 프로세스에게 자원을 할당해준다.

만약 unsafe로 판단되면 자원을 주지 않고 기다리게 만든다.
=> 줬다 치고 계산했던 값들을 다시 원래대로 되돌린다.
=> Pi에게 자원을 줘도 safe state가 되는 시점이 오면 그때 주게 된다.

특정 시점에 Snapshot을 찍었다.

초기 Available은 시스템 내의 전체 자원 - 현재 할당되어 있는 (Allocation) 자원의 합이다.

Need <= Available이면 할당할 수 있다는 의미이므로 해당 프로세스를 종료할 수 있다는 뜻이다.

=> 종료했다 치고, Allocation을 Available에 더해준다.

 

<P1, P3, P4, P2, P0>순으로 자원을 몰아줬을 때 모든 프로세스가 무사히 종료될 수 있으므로, 현재 System은 Safe한 상태에 있다는 뜻이다.

 

P1이 (1,0,2)를 요청했다면, 할당해줄 수 있을까?

P1에게 (1,0,2)를 할당해줬다고 치고, 모든 프로세스를 마칠 수 있는 Sequence가 존재한다면 할당해주어도 괜찮다는 뜻이다.

<P1, P3, P4, P0, P2> 순으로 모든 프로세스가 종료될 수 있으므로 P1에게 (1,0,2)를 할당해 주어도 여전히 safe state이므로 할당해줄 수 있다.

 

Deadlock Detection

데드락 Detection 방식은 데드락이 발생하기 전까지는 아무 일도 하지 않는다.
자원이 남아 있으면 그냥 준다.
=> 자원이 없어서 못 주는 것은 어쩔 수 없음

Avoidance는 미래를 예측하고 데드락이 발생할 가능성을 판단했다면, Detection은 현재만 보고 판단한다.
=> 그냥 현재 줄 수 있는 자원이 있으면 준다. (데드락 발생 허용)
=> 대신 Deadlock이 발생하면 Detect하고 Recovery할 수 있어야 한다.

모든 리소스 타입이 Single instance인 경우에는 사이클이 발생하는 경우에 데드락이라고 Detection할 수 있다.

그렇다면 Multiple instance인 경우에는 어떻게 데드락을 Detection할 수 있을까?

 

Single Instance of Each Resource Type

Process -> Resource 로 Request를 그리고 Resource -> Process로 Allocation을 그렸었는데, Resource vertex를 지우고 Process -> Process 로 edge를 그려서 프로세스가 다른 프로세스가 갖고 있는 자원을 기다린다는 것을 표현한다.

왜 wait-for graph로 표현하냐?

그래프에서 Deadlock을 detect하기 위해서는 single instance에서는 그래프 내에 사이클이 발생하는지를 통해 판단할 수 있다고 했는데 이 사이클을 감지하는 알고리즘의 시간 복잡도가 vertex의 수에 영향을 받기 때문에 vertex의 수를 줄이는 것이 좋기 때문이다.

 

Deadlock Detection Algorithm

Multiple instance Resource가 존재하는 상황에서 데드락을 감지하는 알고리즘을 보자.

그 전에 먼저 알고리즘을 위해 필요한 자료 구조들을 살펴보자.

avoidance는 미래에 데드락이 발생할 가능성이 있는지 판단하는 것이기 때문에 미래에 얼마나 자원을 요청할지 알아야 하기 때문에 Max 같은 정보들이 있었는데, Detection은 현재 데드락이 발생했는지만 판단하면 되기 때문에 Request만 있으면 된다.

Step 1. 어떤 프로세스에게 Allocation된 자원이 하나라도 있으면 아직 일을 하고 있는 프로세스라 판단하고,

현재 Allocation된 자원이 없으면, 물론 일이 끝나지 않은 프로세스일 수도 있지만 이 프로세스의 자원을 기다리는 프로세스가 없다는 뜻이므로 데드락과는 연관이 없는 프로세스이므로 Detection에서는 없는 것과 마찬가지인 프로세스다.
=> Detection은 현재만 보기 때문에 지금 당장 데드락과 상관 없으니까 빼버리고 Finish로 취급한다.

Step 2. 아직 끝나지 않은 프로세스 중에 Request <= Work인 프로세스를 찾는다.

Step 3.  Request <= Work면 걔는 자원을 몰빵해주면 일을 마칠 수 있는 애니까 끝났다고 표시하고 걔가 갖고 있던 자원을 회수해서 Work에 집어 넣는다.

Step 4. 그렇게 2,3 번 과정을 반복했을 때, Finish가 False인 프로세스가 존재하면 모든 프로세스가 종료될 수 없다는 뜻이므로 데드락이 발생한 것으로 판단한다.

 

특정 시점의 시스템 내의 Snapshot이 위와 같다면,

<P0, P2, P3, P1, P4> 순서대로 자원을 할당해주면, 모든 프로세스가 종료될 수 있으므로 현재 시스템 내에는 데드락이 발생하지 않았다는 뜻이다.

지금 당장의 Request만 처리할 수 있다고 Finish로 처리하고 Allocation된 것을 반납 받아도 되냐, 나중에 또 요청할 수도 있지 않냐. 이렇게 생각할 수 있지만

Detection에서 미래는 중요하지 않다. 지금 당장 데드락이 발생하는지만 확인하면 된다.

지금 당장 한 칸이라도 진도를 나갈 수 있으면 데드락이 발생하지 않는다고 판단한다.

Detection 알고리즘은 시간 복잡도가 O(n^3)인 매우 복잡한 알고리즘이다.

이러한 알고리즘이 너무 자주 돌아가면 성능이 저하될 수 있다.

그래서 현실적으로는 사용할 수 없는 알고리즘임. 매 요청마다 O(n^3) 만큼의 시간복잡도를 잡아먹으면 CPU를 너무 많이 잡아먹는다.
=> 그래서 무시하는 정책을 사용한다.

만약 이러한 Detection알고리즘을 사용한다고 하면, 얼마나 자주 이 알고리즘이 사용되어야 할까?

1. 원칙적으로는 자원의 상태가 바뀔 때마다 돌아가야 하는데 이러면 오버헤드가 너무 커진다.
2. 요청을 받아들일 수 없을 때만 알고리즘을 돌려서 Detection 하자
3. 데드락 발생 빈도는 매우 적기 때문에 가끔씩 주기적으로 알고리즘을 돌리자

 

Recovery of Deadlocks: Process Termination

• 데드락에 걸린 프로세스는 모두 종료시킨다.
• 데드락에 걸린 프로세스들을 하나 하나 종료시켜보자. 하나 죽이고 Detection, 하나 죽이고 Detection                            => 데드락이 Detection되지 않을 때까지 반복한다.

그렇다면 어떤 프로세스부터 종료시킬 것인가??

1. 우선 순위가 낮은 프로세스를 먼저 종료시키자.

2. 얼마나 오랫동안 동작했냐를 기준으로 시작한지 얼마 안 된 프로세스를 먼저 종료시키자.

3. 프로세스가 사용한 양이 더 중요하지 않냐. 짧게 돌았더라도 엄청난 양의 자원을 사용하면서 동작한 프로세스는 종료시키면 나중에 다시 시작했을 때 또 그만큼 자원을 할당받아서 사용할테니까 종료시키지 말고 먼저 끝내는 게 낫지 않냐

4. 앞으로 이 프로세스가 끝날 때까지 사용할 자원의 양이 얼마나 많냐를 본다.
=> 앞으로 자원을 많이 사용할 애들을 먼저 종료시킨다.

5. 최소한의 프로세스를 종료시켜서 데드락을 해소시킬 수 있는 프로세스의 집합을 찾자.

6. interactive한 프로세스가 아닌 background job을 먼저 종료시키자.

이건 정하기 나름이지만 대부분의 OS는 사실 데드락을 무시하기 때문에 이런 고민을 하지 않는다.

 

Recovery of Deadlocks: Resource Preemption

데드락에 걸린 프로세스의 자원을 뺏는다. abort 시키지는 않고 자원만 뺏는다
=> 그 프로세스의 자원을 기다리고 있던 프로세스가 동작 가능하다.

어떤 프로세스를 victim으로 선정할까

1. Minimize cost: 최소 비용이 발생하도록 victim을 선정하자.

2. Rollback: 이전의 Safe State로 되돌리자.

음 어짜피 이때 다시 실행시키면 또 데드락이 발생하지 않냐?
아니다. 데드락이라는 것은 스케줄링이 절묘하게 되어서 원형 대기가 발생하게 된 것이다.
다시 돌아갔다가 수행하면 OS는 워낙 dynamic하게 동작하기 때문에 또 그런 상황이 발생하지 않을 수도 있다.

 

Resource Preemption을 사용하면 Startvation이 발생할 수 있다.

=> victim을 선정할 때 얼마나 자주 victim으로 선정되었냐를 고려할 필요가 있음.

 

Avoidance vs Detection

Avoidance는 미래를 예측해서 안전한 길로 가기 때문에 데드락이 발생할 수가 없다.

Detection은 현재 데드락이 발생했는지에만 관심이 있고, 데드락을 허용한다.

 

Avoidance

모든 프로세스가 최대 자원 사용량을 요청했을 때를 생각해서 데드락이 발생할 수 가능성이 있는지 판단하기 때문에 Worst case를 assumpton한다.

너무 소극적으로 일을 하기 때문에 자원을 효율적으로 사용하지 못 할 수도 있다.

 

Detection

모든 프로세스가 현재 요청하고 있는 자원의 양 이상으로 요청하지 않을 것이라 생각하고 Detection하기 때문에 Best case를 assumption한다.