Lecture 19.~21. Deadlock

개념

프로세스가 파일을 print 하기 위해서는 두 가지의 자원을 모두 가져야 합니다. 그런데 두 개의 프로세스가 각각 하나씩을 가지고 있으면서 자신이 가진 것을 놓지 않고, 다른 프로세스가 나머지 하나를 놓아주기를 기다리고 있다면 이를 Deadlock이라고 부릅니다.

다르게 표현하면, 데드락은 두 개 이상의 프로세서가 절대 일어나지 않을 , 이 이벤트들은 서로에 의해서만 발생될 수 있기 때문에, 이벤트를 기다리고 있는 경우를 말합니다.

데드락은 OS에서 가장 어려운 문제 중에 하나로, 데드락 문제를 해결하는 과정에서 OS의 퍼포먼스가 상충될 수 있습니다.

//Process A
printer->wait();
disk->wait();

print file

printer->signal();
disk->signal();

//Process B
disk->wait();
printer->wait();

print file

disk->signal();
printer->signal();

Resources

OS는 다양한 자원들을 골고루 분산시켜야 합니다.

1. CPU cycle // preemptable
2. Memoey space // preemptable
3. Files // Non-preemptable
4. I/O devices(printer) // Non-preemptable

특정한 자원 타입에 대한 요청은 그 타입의 어떤 자원으로도 대체될 수 있습니다. 예를 들어서 메모리에서 100btyes를 요구하는 것은 메모리의 어떤 주소를 주어도 요구 조건을 만족시킬 수 있습니다.

일반적인 가정으로서, 프로세스는 자원을 요청-사용-반납 한다고 하겠습니다. 모든 자원들을 재사용이 가능하고 한 번 사용한다고 소멸되는 것이 아니라는 뜻입니다. 만약에 요청한 자원이 접근할 수 없을 때는 접근을 하기 위해서 기다립니다.

데드락이 발생하기 위한 필요 & 충분 조건

아래 조건은 만족하는 것이 좋은 것이 아니라, 아래의 조건을 만족하면 반드시 데드락이 걸린다는 것을 보이기 위한 조건들입니다.

1. Mutual exclusion : 한 프로세스가 하나의 자원을 가지고 있을 때, 이 자원을 요청하는 다른 프로세스는 이를 갖고 있는 프로세스가 이를 release 할 때까지 기다려야 합니다.
2. Hold and Wait : 프로세스는 하나의 자원을 hold하고 다른 프로세스가 가지고 있는 자원을 얻기 위해서 wait할 수 있습니다.
3. No preemption : 자원을 자발적으로 release 됩니다. 다시 말하면 어떤 프로세스나 OS도 프로세스가 자원을 release하게 만들 수 없습ㄴ디ㅏ.
4. Circular wait : 프로세스 1은 2의 자원을 요청하고, 2는 3의 자원을 요청하고, …, N은 1의 자원을 요청하는 등 자원을 요청하기 위해서 기다리는 wait가 circular하게 형성되어야 합니다.

Resource-Allocation Graph ( RAG )

데드락 컨디션은 RAG라는 것으로 모델링 될 수 있습니다.

이 그래프는 두 가지의 노드를 가집니다.

1. 하나는 Box로 표현되는 자원
2. 하나는 Circle로 표현되는 Thread/Process입니다.

그리고 이 그래프는 두 가지의 Directed Edges를 가집니다.

1. Request edge : 프로세스에서 자원으로 이어지는 에지입니다. 박스에서 원으로 이어집니다. 이것은 프로세스가 자원을 요청하고, 이 자원을 얻기 위해서 wait 하고 있음을 나타냅니다.
2. Assignment edge : 자원에서 프로세스로 이어진느 에지입니다. 이는 해당 자원을 프로세스가 hold 하고 있음을 나타냅니다.

요청이 생성되었을 때, 이에 해당하는 request edge가 추가됩니다. 만약 request edge가 실행되었을 때 이는 assignment edge로 변경됩니다. 만약 process가 자원을 release 하면 assignment edge는 지워집니다.

//TODO RAG 그림

그래프에서 싸이클이 없다면 데드락이 발생하지 않습니다.

각 자원의 instance가 하나뿐일 때, 그래프에서 싸이클이 있으면 데드락이 반드시 발생합니다. 역도 성립하므로 싸이클이 존재하는 것은 데드락의 필요-충분조건입니다.

Dealing with Deadlock

The Ostrich Approach

타조가 모래에 머리를 처박고 모른척하는 방법이라고 합니다. 실제에서 사용하는 방법으로 OS에 deadlock이 걸리면 해당 프로세스를 껐다가 킨다고 합니다.

Deadlock preventon

데드락이 발생하는 4가지 조건 중 하나를 없애는 방법으로 데드락을 예방합니다.

Mutual exclusion

프린터와 파일 같이 공유가 불가능한 자원의 MUTEX를 피하는 것을 어렵습니다. 그러나 많은 자원들은 공유가 가능하기 때문에 이러한 자원들에 대해서는 데드락을 피할 수 있습니다. 프린터에 대해서는 Spooling이라는 것을 사용해서 MUTEX를 avoid 합니다. 따라서 이 프로세스는 물리적인 프린터의 응답을 기다릴 필요가 없습니다. 출력 목록 queue를 만들어두는 것을 말합니다.

Hold and Wait

이를 피하기 위해서 다른 자원을 요청할 때에는 그 어떤 자원도 hold하고 있지 못하도록 해야합니다. 모든 자원을 프로세스 execution의 시작 부분에서 한 번에 요청하도록 할 수 있습니다.(영원히 반복하는 프로세스에 대해서는 다른 방법이 필요합니다.)

모든 자원을 프로세스의 특정 시점에서 한 번에 요청하기만 하는 방법이 있습니다.(필요한 모든 자원을 한 번에 요청한다는 부분이 특이점입니다.)

새로운 자원을 얻기 위해서 현재 가지고 있는 모든 자원을 release한 뒤, 새로운 자원 + 기존의 자원을 다시 모두 요청하는 방법이 있습니다.

하지만 이 방법은 세 가지 문제점이 있습니다.

1. 어떤 자원을 요청할지 미리 아는 것이 어렵습니다.
2. 같은 자원을 동시에 요청하는 경우 자원의 untilization이 줄어듭니다.
3. Starvation이 가능합니다.

No preemption

이를 피하기 위해서는 preemption을 허락하면 됩니다. 프로세스 A가 현재 접근할 수 없는 자원을 요청합니다. 그리고 어떤 프로세스가 해당 자원을 가지고 있는지 봅니다. 만약 이 자원을 가지고 있는 B가 추가적인 자원을 가지기 위해서 기다리고 있으면 A가 그 자원을 먼저 차지합니다. 이런 경우가 아니라면 A는 멈춰야 합니다. 기다리는 동안 다른 자원은 다른 프로세스가 사용할 것입니다. 멈춘 프로세스는 오직 새로운 자원과 기존의 자원을 모두 얻었을 때만 일어날 수 있습니다.

만약 프로세스가 allocated 될 수 없는 자원을 요청한다면 해당 프로세스가 가지고 있는 모든 자원은 preempted됩니다. 멈춘 프로세스는 오직 새로운 자원과 기존의 자원을 모두 얻었을 때만 일어날 수 있습니다.

Circular wait :

이를 피하기 위해서 모든 자원에 번호를 부여합니다. 그리고 프로세스는 자원을 그 번호에 따라서 요청합니다.

1. 순서 : disk drive, printer, CDROM (이하 각 1,2,3번 자원)
2. 프로세스 A : 1번 자원을 요청하고 3번을 요청합니다.
3. 프로세스 B : 1번 자원을 요청하고 3번을 요청합니다.

즉 프로세스 B가 3번을 먼저 요청하지 않습니다. 이를 통해서 이 포스팅의 맨 처음에 보았던 데드락의 상황을 미리 피합니다.

자원에 부여되는 순서는 자원이 보통 요구되는 논리적인 순서로 할당될 수 있습니다. 이는 모든 자원을 요청하는 프로세스들을 serialize하는 것으로 입니다. 이는 사실 multi-tasking의 개념에 반하기 때문에 Deadlock 핸들링과 퍼포먼스의 상충을 잘 보여주는 예시라고 할 수 있습니다.

Deadlock detection algorithms

데드락이 발생하는 것을 찾는 방법입니다. 그리고 찾은 뒤에는 Deadlock avoidance algorithms을 실행합니다.

만약 모든 자원이 각 하나의 인스턴스만 가지고 있다면 데드락은 RAG에서 싸이클을 찾는 것으로 발견할 수 있습니다.

Silberschatz가 더 간단한 그래프를 정의했고 이를 wait-for그래프라고 합니다. 이는 자원 할당 그래프입니다. p1에서 p2로 가는 에지는 p1이 p2가 가지고 있는 지원을 기다리고 있음을 의미합니다. 이때 어떤 자원이 involved 되었는지는 상관하지 않습니다.

간단한 싸이클 찾기 알고리즘은 아래와 같습니다. 각각의 노드에서 시작해서 DFS를 진행합니다. 만약 각 DFS에 대해서 이미 발견한 노드를 다시 방문하는 경우가 있다면 싸이클이 있는 것입니다.

Interpering a RAG With Multiple Resource Instances

//TODO

그래프에서 까만점은 자원의 인스턴스를 의미합니다. 만약 그래프가 싸이클을 포함하지 않으면 데드락은 존재하지 않습니다.

만약 싸이클이 있다면 데드락이 발생합니다.

multiple resource instances의 경우 싸이클은 데드락의 필요조건일뿐 충분 조건이 아닙니다.

싸이클 –충분—> 데드락 : 아니다. 싸이클 <–필요— 데드락 : 맞다.

• knot : 그래프에서 노드의 집합 k가 있을 때, k의 각 원소는 k에 들어있는 모든 노드 원소에만 reachable하고 나머지는 접근할 수 없는 경우

Knot –충분—> 데드락 : 맞다. Knot <–필요— 데드락 : 아니다.

Multiple Resources of Each Type

//TODO

프로세스 N 종류가 있고 자원 M 종류가 있을 때,

1. Existing Resources vector : 존재하는 모든 각 타입의 자원 수를 의미합니다.
2. Available Resources vector : 존재하는 모든 각 타입의 사용가능한 자원의 수를 의미합니다.
3. i-th row of Current Allocatino matrix : 프로세스 i에 할당된 각 type의 자원을 의미합니다.

모든 자원은 할당되었거나 접근 가능한 상태 둘 중 하나입니다. 따라서 할당된 자원의 수와 접근 가능한 자원의 수를 합치면 해당 타입의 인스턴스의 수를 얻ㅇ르 수 있습니다. Request 테이블의 i-th row는 요청되었지만 아직 얻지 못한 자원의 수를 의미합니다.

Algorithm

각 프로세스는 unmakred 된 상태로 초기화 되어 있습니다. 알고리즘이 진행됨에 따라서 프로세스들은 마크될 것이고, 이 마크는 해당 프로세스가 완료될 수 있음을 의미합니다. 즉, 데드락에 걸리지 않는 것을 나타내는 마크들을 추가할 것입니다. 모든 알고리즘이 끝났으 때, mark되지 않은 프로세스들은 모두 데드락에 걸린 것입니다.

1. 마크된 적이 없는 프로세스 i 의 Request가 Available보다 같거나 작은 경우가 있는지 찾습니다.
2. 이런 경우가 있다면 해당 프로세스에게 Request한 자원을 주고, 실행을 시킵니다. 그리고 이 프로세스가 가지고 있던 자원까지 Availalble에 넣습니다.
3. 다시 1번부터 진행합니다. 더이상 이 과정을 진행할 수 없을 때 알고리즘을 종료합니다.
4. 알고리즘이 종료했을 때 mark되지 않은 프로세스는 데드락에 걸리는 경우입니다.

//TODO 그림

데드락을 발견하면 한 프로세스를 죽입니다. 모든 프로세스가 데드락에 걸렸으면 전체를 껐다가 킵니다. 이게 아니라면 데드락이 발생하지 않을 때까지 하나의 프로세스씩 끕니다. 어떤 프로세스를 끌지는 스케줄링에 따라서 달라집니다.

이렇게 꺼진 프로세스는 이전에 설정해준 check-point까지 돌아가서 다시 현재 상태로 돌아옵니다. 완전 처음으로 돌아가는 것이 아닙니다. 언제로 돌아가는지는 학부의 수준을 넘어섭니다.

Deadlock avoidance algorithms

현재 접근 가능한 자원을 파악합니다. 각각의 Thread에 할당된 자원들을 확인합니다. 그리고 가능한 미래의 요청을 파악합니다. 그리고 데드락이 발생하지 않는 요청만을 수행합니다.

//TODO

그래프에서 오른쪽 또는 위쪽으로만 움직일 수 있습니다. //는 특정 자원에 대해서 두 프로세스가 공통으로 사용하고 있는 영역을 의미합니다. $\$도 마찬가지의 상황을 나타냅니다. unsafe 영역은 결국 \또는 //의 영역으로 들어가야 하기 때문에 deadlock의 영역입니다. 따라서 이 부분을 피해야 합니다.

Safe and Unsafe States

//TODO 그림

(a)는 safe합니다. safe하다는 것은 모든 프로세스들이 완료될 수 있는 순서가 존재함을 의미합니다.

(b)는 unsafe합니다. 이는 데드락이 발생할 수 있음을 의미합니다. 특정 상황에서 다른 프로세스가 자원을 release 할 수도 있기 때문입니다.