[09] 운영체제 - Deadlock-1

안녕하세요. 저번 포스팅까지가 1차 중간고사의 범위였고 시험을 치렀습니다!
하지만 성적은... 물론 교수님이 어렵게 내셔서 70점을 넘는 학생이 한 명 밖에 없기는 하지만...
그래도 아쉬움이 많이 남는 시험이었습니다. 다음 시험은 더 잘 보기 위해 다시 포스팅을 시작해보도록 하겠습니다.
오늘은 앞에서 언급했던 Deaklock 상태에 대해 더욱 자세히 다뤄보도록 하겠습니다.
그럼 바로 시작하도록 하겠습니다.

Deaklock  
Deaklock 이란 프로세스 P1이 자원 A를 갖고 있으면서 B를 필요로 하고 프로세스 P2는 자원 B를 갖고 있으면서 자원 A를
필요로 하는 상황에서 두 프로세스 모두 더 이상 진행이 되지 않는 상황을 말합니다. 

Deadlock에 관해 설명하고 해결법을 설명하기 위해 System model과 Deadlock의 조건들을 설명해가면서 글을 써보도록 하겠습니다.

System model
1. 시스템의 자원은 타입을 가지며 해당 타입은 자원(R)의 실체인 인스턴스(W)를 갖게 됩니다.
(타입은 자바의 class, 인스턴스는 class를 new 하여 생성해 준 것이라고 생각하시면 이해가 되실 것입니다.)
타입 : CPU cycles, Memory space, I/O devices etc

2. 각 프로세스는 자원을 요청 사용 반납합니다.

Deadlock Condition
다음은 Deadlock이 일어나기 위한 조건입니다. 다음의 조건 네 가지가 동시에 일어나야만 Deadlock이 발생하게 됩니다.
(Deadlock이 안 일어나게 하려면 하나의 조건만 충족시키지 않아도 되겠죠?)

1. Mutual Exclusion
오로지 하나의 프로세스만이 하나의 자원을 사용할 수 있습니다.
2. Hold and Wait
자원을 최소한 한 개를 갖고 있으면서 다른 자원을 기다리고 있는 상태.
3. No Preemption
프로세스는 작업을 완료한 후에만 소유하고 있던 자원을 반납할 수 있습니다.
(운영체제가 강제로 회수 불가능)
4. Circular Wait
프로세스가 다른 프로세스의 자원을 요구하는 형태가 원형을 이루고 있는 상태.
ex) P1 -> P2 -> P3 -> P4 -> P1
(P1원은 P2가 소유하고 있는 자원을 요청, P2는 P3 , P3는 P4, P4는 P1의 자원을 필요로 함.)

Deadlock은 프로세스들 간의 자원 요구와 소유를 간단하게 표현한 그래프를 통해 보다 쉽게 검사할 수 있습니다.
밑의 그림에서 P -> R 은 해당 자원을 필요로 하는 것을, R -> P는 프로세스가 해당 자원을 소유하고 있는 것을 의미합니다.

위의 그림으로 판단했을 때 Deaklock이 일어날까요?
네! Deadlock이 발생을 합니다. 그 이유를 천천히 설명해드리겠습니다.
P1은 R2를 소유하면서 R1을 요청합니다.
P2는 R1을 소유하면서 R3 를 요청합니다.
P3라는 R3를 소유하면서 R2를 요청합니다.

즉 P1은 R1을 할당받고 작업을 완료해야 R2와 R1을 반납합니다.
P2는 R3를 할당받고 작업을 완료해야 R3와 R1을 반납합니다.
P3는 R2를 할당받고 작업을 완료해야 R2와 R3를 반납합니다.

여기서 반드시 인지하셔야 할 조건은 No preemption 조건입니다.
그렇기 때문에 현 상황에서는 어떠한 프로세스도 작업을 완료할 수 없고 어떠한 자원도 반납할 수 없기 때문에
Deadlock이 발생하게 됩니다. 

그리고 보다 빠르고 쉽게 판단하려면 자원 요청이 사이클이 존재하시는지 확인을 하시면 됩니다.
위의 그림은 자원 요청의 화살표가 사이클을 이루고 있는데요. 이러한 사이클이 있다면 Deadlock을 의심해봐야 합니다.
말 그대로 '의심'입니다. 즉 사이클이 있다 하더라도 Deadlock이 발생하지 않을 수도 있다는 뜻이죠!
다음 그래프를 보겠습니다.

이 그래프는 보시다시피 사이클이 존재합니다. 하지만 Deadlock은 발생하지 않습니다.
그 이유는 P2는 현재 어떠한 자원도 요청하지 않습니다. 그리고 R1이라는 자원을 소유하고 있죠.
그 말인즉슨 P2는 언제든지 끝날 준비가 되어 있다는 뜻입니다. P2가 작업이 끝나고 R1을 반납하면
P1은 R1을 할당받고 그렇다면 자원 요청의 사이클은 깨지게 됩니다.

정리하자면 자원 할당 그래프의 사이클이 존재하지 않는다면 Deadlock은 발생하지 않습니다.
그리고 사이클이 존재하는데 자원의 인스턴스(위의 그래프들에서 점)가 자원 당 하나라면 Deadlock이 발생하고
인스턴스가 여러 개라면 Deadlock이 발생할 수도 있고 발생하지 않을 수도 있습니다.

다음으로 다룰 주제는 Deadlock을 다루는 방법 즉 방지하는 방법들입니다.
하지만 주제가 주제인 만큼 글이 길어질 것 같아서 여기까지 작성하고 다음 포스팅에서 자세히 다뤄보도록 하겠습니다.
감사합니다.