[OS] Deadlock

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

Deadlock을 공부해보자. Deadlock은 한국으로는 교착상태라고 하는데, 이것 또한 생소한 단어라... 잘 이해가 가지 않는다. 상황으로 설명하는 것이 가장 좋을 듯 하다.

철수가 신데렐라 책을 읽고 있었다. 그런데 갑자기 백설공주가 7난장이와 어떻게 되었는지 궁금한거야. 그래서 백설공주 책을 찾고 있는데 이런.. 영희가 백설공주 책을 읽고 있어. 그런데 영희는 백설공주 책을 놓을 생각을 안 하는거야. 왜냐하면 영희는 신데렐라가 12시 이후에 어떻게 되었는지 너무 궁금해서 신데렐라 책을 찾고 있거든.

Deadlock은 프로세스 A가 자원 a를 가지고 있는 상태에서 자원 b를 요청하고 있는데, 자원 b는 프로세스 B에 의해 사용되고 있고, 프로세스 B는 자원 a를 요청하고 있는 상태를 의미한다. 즉, 어떤 프로세스도 자기의 요청하는 자원을 차지할 수 없는 상태를 의미한다. 이 꼴을 제 3자의 입장에서 보자. 이상하게도 프로세스 A와 프로세스 B는 그냥 죽어있는 것처럼 아무것도 안 하고 있는 것처럼 보이겠지? 그래서 Deadlock이다.

Deadlock이 발생하려면 어떤 조건을 만족시켜야한다.

1. Mutual exclusion

2. Hold and wait

3. No preemption

4. Circular wait

이 네 가지 조건은 Deadlock이기 위해서는 반드시 필요하다. 모든 Deadlock은 위의 조건을 만족시킨다. 그런데 위의 네가지 조건을 모두 만족시키는 상황이 모두 Deadlock은 아니다. 이 내용은 참 중요한 내용이다. 그림으로 따지면 다음과 같다.

그림으로 보는 것이 더욱 쉬울 것이라고 생각한다.

나와 같이 머리가 나쁜 사람들은 이런 것의 관계를 생각하기가 굉장히 어렵다. 프로세스 A는 무슨 자원을 가지고 있는데, 프로세스 A는 b를 요청하고 있고 b는 누가 가지고 있는데 그건 누가 요청하고 있고 이건 이렇고 저건 저렇고....!@#!@%!@#

그래서 나와 같은 사람들을 위해 사람들이 이를 이해하기 쉽게 그래프로 표현하고 있다. 여기서의 그래프는 막대 그래프같은 그래프가 아니고 자료구조에 나오는 그래프를 의미한다.

위의 그래프를 조금 설명해보자.

P = { P1, P2, P3 }

R = { R1, R2, R3, R4 }

E = { R2 → P1, P1 → R1, R1 → P2, R2 → P2, P2 → R3, R3 → P3, P3 → R2 }

P는 프로세스의 집합을 의미한다. 위의 그림에서 프로세스는 3개 즉, P1, P2, P3가 있다.

R은 자원의 집합을 의미하여 R1, R2, R3, R4가 있다.

E는 Edge의 약자로 자원과 프로세스를 잇는 선을 의미한다. 

(※ R에서 P로 가는 선, assignment edge,은 자원이 그 프로세스에 의해 점유되고 있다는 뜻이며, P에서 R로 가는 선, request edge,은 프로세스가 그 자원을 요청하고 있다는 뜻이다.)

한 마디로 위의 그래프는 3개의 프로세스와 4개의 자원 그리고 7개의 Edge로 이루어져 있다.

위의 그래프는 Deadlock인가? Deadlock이기 위해서는 이 글의 가장 서두에 말했던 네 가지 조건을 모두 만족시킨다고 했다. 조건을 만족하는지 살펴보자.

1. Mutual Exclusion : 즉, 모든 자원들이 nonsharable해야한다는 것이다. Deadlock의 기본 정의 자체가 누군가가 자원을 쓰고 있기 때문에 기다려야 하는 상황을 뜻한다. 그런데 만일 그 자원이 공유 가능하다면 한 프로세스가 그 자원을 사용하고 있다하더라도 다른 프로세스는 그 자원을 사용할 수 있을 것 아니냐?! 위의 그림에서의 R1, R2, R3, R4는 nonosharable하다. R3를 보면 R3안에 두 개의 점, instance,이 있는데, 이 instance를 가진 프로세스만 그 자원을 사용할 수 있다. 이 말은 R3는 두 개의 프로세스에 의해서만 공유가능하다는 뜻이다. R3가 이미 P1과 P2에 의해 공유되고 있는 상황에서 P3는 더이상 R2를 공유할 수 없다. 즉, nonsharable하다. 

2. Hold and Wait : Hold and Wait에서 and가 가장 중요한 말인 듯 하다. 동시에 Hold하면서 Wait해야한다. 즉, 한 프로세스가 자원을 동시에 가지고 있으면서 동시에 다른 자원을 기다리고 있는 상태가 되어야 한다. 위의 그래프에서 P1은 R2를 Hold하고 있으면서(and) R1을 Wait하고 있다. 즉 P1은 Hold and Wait하고 있다. 마찬가지 원리로 P2, P3 역시 그러하다. 따라서 Hold and Wait 조건은 만족한다.

3. No Preemption : 한 프로세스가 점유하고 있는 자원이 다른 프로세스에 의해 빼앗기면 안된다는 뜻이다. 위의 그림에서 P3는 R2를 요구하고 있다. R2는 자신의 Instance 두 개를 각각 P1과 P2에게 나누어 주고 있는 상태이다. 만일 이 상태에서 P1의 자원(R2)가 갑자기 P3에 의해 Preempt된다고 하면 P3 입장에서는 Hold and Wait을 만족시키지 못 하게 된다. 왜냐하면 P3는 기다리고 있는 자원이 없다는 뜻이 되잖아?! 위의 그림은 No Preemption을 가정한 상태이다. 즉, 3번은 당연히 만족한다.

4. Circular Wait : Wait이 원형으로 이루어져있다는 것이다. 0부터 9까지가 있는데, 0이 1을 기다리고 1이 2를 기다리고 쭉쭉 가서 9가 0을 기다린다면, 그것은 끝날 수 없는 어떤 상태에 빠지게 된다. 위의 그림은 P1은 R1을 기다리고 있고, R1은 P2에 의해 사용되고 있는데 P2는 R3에 요청을 보내고 있다. 그런데 R3는 P3에 의해 사용되고 있고, 하필이면 P3는 P1이 사용하고 있는 R2에 요청을 보내고 있다. 즉, P1 → R1 → P3 → R2 → P1과 같은 사이클을 찾을 수 있다. 즉 이 조건도 만족한다.

위의 네 가지 조건을 모두 만족시키기 때문에 위의 그래프는 Deadlock이다.

다음의 그래프는 위의 네 가지 조건을 모두 만족시키지만 Deadlock은 아니다.

위의 그래프가 Deadlock이 아닌 이유는 P4때문이다. P4가 언제든지 R2의 Instance를 놓아줄 수 있기 때문이다.

여기서 질문 하나, 도대체 Instance가 무엇일까? 스터디하다가 이 부분에 대해서는 답을 내지 못 했다. 도대체 무엇일까? 위키피디아에서 Instance를 찾아보면 프로그래밍에서 나오는 Instance를 설명하고 있다;;; 흠... Resource에서의 Instance는 어디에서 찾을 수 있을까나...

다음 포스팅에서는 Deadlock을 막는 방법에 대해서 설명해보겠다.