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


Deadlock을 막는 방법으로 Deadlock Prevention이 있다. 

이는 아주 간단한 원리이다. 이전의 포스팅에서 이야기 했듯이 Deadlock이 발생하려면 네 가지 조건이 필요하다. 다르게 말하면, 네 가지 중 한 가지라도 이루어지지 않으면 Deadlock이 발생하지 않는다는 뜻이다. 왜냐하면 모든 Deadlock은 네 가지 조건을 만족시키니까.


그렇다면 그 네 가지 조건. Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait 중 한 가지라도 일어나지 않게 하면 Deadlock을 막을 수 있다. 그런데 이는 현실적으로 불가능하다고 한다. 예를 들어, Mutual exclusion 같은 경우, sharable 해야 Deadlock을 막을 수 있는데, 프린터같은 자원은 무조건 nonsharable하다. 

(프린터 공유할수 있잖아?! 라고 말하면... -_- 이런 거다.. 여기서 공유할 수 있다? 없다?는 동시에 사용할 수 있는지 여부를 말한다. 프린터가 아주 아주 동시에 내 작업 요청과 너의 작업요청을 동시에 아주 동시에 수행할 수 있다고 생각하는가? 아니다!! 정확히 말하면 누구든지 프린터에게 작업을 요청하면 내가 동시에는 못 해주지만 순서대로는 해줄께!! 이런 개념이지 프린터 공유할 수 있다고.. 왜 프린터가 nonsharable하냐고 따지면 안 된다.)


아무튼 Deadlock Prevention은 현실적으로 불가능하다. 그렇다면 Deadlock Avoidance이다.  Deadlock Avoidance는 두 가지 방법으로 구현가능하다.

1. Safe State

2. Resource-Allocation-Graph Algorithm


1. Safe State

항상 시스템의 상태를 Safe State 상태로 놓자는 방법이다. Safe State는 다음과 같은 상태를 의미한다. 여러 개의 프로세스가 있는데, 그 프로세스가 어떤 특정 순서대로 자원을 요청할 때 아무런 문제없이 자원을 할당받을 수 있는 경우이다. 예를 들어서 설명하는 것이 이해가 빠를 것 같다. 


12개의 tape가 있다고 치자. (각각이 자원이다.) 이 tape를 사용하려고 하는 프로세스는 P0, P1, P2 세 개이다. 각각의 프로세스가 요청할 수 있는 최대의 테이프 자원의 개수와 실제 T0이라는 시간에 요청한 자원의 개수는 다음과 같다.


프로세스

사용 가능한 최대 자원 개수

t0 에 사용 중인 자원 개수

P0

10

5

P1

4

2

P2

9

2


그러면 다음과 같은 자원 사용 현황이 나오겠다.



 P0

 free

P1 

free

P2

                       


t0에 12개의 자원이 위와 같이 쓰여서 3개의 테이프가 남아있다.

이 상태에서 만일 < P1, P0, P2 > 순서로 프로세스를 실행시키면 어떻게 될까? P1이 실행되는 동안 어떤 일이 벌어질지는 모르지만, 아무튼 P1이 요청할 수 있는 프로세스의 개수는 4개이다. 그런데 아직 테이프는 3개나 남았기 때문에 P1은 마음 놓고 실행하고 종료할 수 있다. P1이 종료되면 다음과 같은 상태가 된다.


 P0

 free

P2

            


그 다음에 P0가 요청을 해볼까? 남아있는 칸은 다섯 칸이고 P0는 다섯 칸 사용하고 있고, 최대 사용할 수 있는 칸 수는 10칸이기 때문에 P0 역시 마음 놓고 실행하고 종료할 수 있다. 마지막으로 P2역시 마찬가지이다.


따라서 < P1, P0, P2 > 순서대로 실행을 시키면 Deadlock이 발생하지 않는 안전한 상태이다.  그런데 만일 P2가 현재 2칸을 사용하고 있는 것이 아니고 3칸을 사용하고 있다고 가정해보자. 


 P0

 free

P1 

free

P2

            


2칸 더 사용가능한 상태에서 P1이 최대 차지할 수 있는 칸 역시 네 칸이니까 아직은 괜찮다. P1이 수행을 마치면 아래와 같은 상태가 될 것이다. 


 P0

 free

P2

            


여기에서 P0이 다음에 수행을 하려고 한다면 문제가 발생한다. P0는 10칸 사용가능한데 현재 P0는 5칸 사용 중이고 남은 공간은 4칸 뿐이다. 만일 P0이 실행 중에 10칸을 요구할 상황이 오게 된다면 문제가 발생한다. 그런데 이는 P2에게도 문제이다. P2는 최대 9칸 사용 가능한데 현재 사용 중인 칸수 3칸에 4칸의 여유공간을 합하면 7칸 밖에 안된다. 즉, P2이든 P1이든 둘 다 서로 간의 자원이 free되기를 기다릴 수 밖에 없다.


앗!! 여기서 깜짝 질문!! 어짜피 P0이든 P2이든 무조건 한번에는 하나의 프로세스만 실행될 수 있는 것 아니야? 그런데 어떻게 P0과 P1이 동시에 서로의 자원이 free되기를 기다려서 Deadlock에 걸릴 수 있냐는 말이다. P0가 10개의 자원을 모두 사용할 수도 있기 때문에 P2가 사용하고 있는 자원 중 하나가 free되기를 기다리는 것은 말이 된다. 그런데 두 개의 프로세스가 동시에 기다릴 수가 있다고? 아!! 그럴 수 있겠다!! P0가 P2에게 자원을 요청하고 기다리고 있는 상태는 프로세스 상태 변이 중에서 wait state에 해당하니까, P0의 PCB가 Device Queue에 쌓여서 기다리지 않을까? 즉, P0와 P2 둘다 Wait State에 빠지게 되어 해당 자원을 계속 못 쓰고 Wait State에서 빠져나올 수 없는 그런 상태에 빠지게 되는 것인가? 무셔라...


2. Resource-Allocation-Graph Algorithm

알고리즘 이름대로 그래프를 그려서 Deadlock 여부를 판단하는 것이다. 여기에서 새로운 Type의 Edge를 소개하겠다. Claim Edge이다. 이는 보통 점선으로 그려지는데, P → R이 점선으로 그려지면 이는 프로세스 P가 자원 R을 미래의 언젠간 요청할 수도 있다는 뜻이다.



기본적으로 위의 상태를 의미하는 그래프를 OS는 가지고 있을 것이다. 그 상태에서 만일 P1이 실제로 R2를 요청을 하면, R2가 실제 요청을 허락한다는 가정하에 P1 → R2의 점선(Claim Edge)을 R2 → P1 방향의 실선(Assignment Edge)으로 바꾼다. 아래와 같이 말이다.

그리고 해당 그래프가 사이클이 있는지 검사한다. 검사할 때는 실선까지 포함해서 검사를 한다. 사이클이 있다. 이는 반드시 Deadlock에 걸린다는 뜻은 아니지만 Deadlock이 존재할 수도 있는 상태인 Unsafe State에 들어가게 됨을 의미한다. 이런 상태를 피해야한다. 이것이 Deadlock Avoidance이다.


지금까지 설명한 두 가지 방법은 자원에 Instance가 여러 개 있을 경우는 고려되지 않았다. 그것을 고려해서 만든 알고리즘이 있는데, 바로 다음 포스팅에서 설명할 Banker's Algorithm이다.

'Operating Systems' 카테고리의 다른 글

[OS] Deadlock Detection  (2) 2013.02.03
[OS] Deadlock Avoidance (Banker's Algorithm)  (5) 2013.02.03
[OS] Deadlock  (0) 2013.02.03
[OS] Remote Procedure Call  (1) 2013.01.22
[OS] Scheduling Algorithm  (2) 2013.01.13
Posted by 빛나유
,