[운영체제] DeadLock ( 교착상태 )

 DeadLock(교착상태)란?

 

두 개 이상의 작업이 서로 상대방의 작업이 끝나기를 기다리며, 어떤 작업도 완료되지 않는 상태를 의미합니다.

 

[프로세스 1]는 프로세스2에게 할당된 자원 2를 요구하고, [프로세스2]는 프로세스2에게 할당된 자원1을 할당하면서 어떤 프로세스도 자원을 얻지 못하고 무한히 대기 하게 됩니다.

 

  

 

교착상태를 사진으로 본다면, 다음과 같은 상태 일거에요..💩

 

  

 

 

DeadLock(교착상태) 발생 조건

 

1. 상호배제(Mutual exclusion) : 한 자원에 여러 프로세스가 동시접근 불가 X
2. 점유대기(Hold and wait) : 자원을 가진 상태에서는 다른 프로세스가 사용하는 자원 반납을 대기한다.
3. 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. 순환대기(Circular wait) :  p0은 p1이 점유한 자원을 대기하고 p1은 p2가 점유한 자원을 대기하고 pn은 p0이 점유한 자원을 요구해야한다.

 

위의 4가진 조건이 모두 충족될 때만!! 교착상태가 발생한다.

 

 

 

🙅🏻‍♂️ 교착 상태 예방 ( Dead Lock Prevention ) 

 

데드락 예방은 4가지 조건 중 하나가 일어나지 않도록 하게끔 하는 방법을 의미한다.

하지만, 각각을 부정 하게 됬을 때 일어나는 부작용이 큰 편이라 이를 채택하는 경우는 드물다.

 

상호 배제(Mutual Exclusion) 부정

• 읽기 전용(= readonly)  파일과 같은 공유 자원을 사용합니다.

점유 및 대기(Hold and Wait) 부정

• 프로세스 대기를 없애기 위해서,  실행되기 전에 필요한 모든 자원을 할당합니다. ( 자원 낭비 발생 )
• 자원을 점유하지 않고 있을 때에만, 다른 자원을 요청할 수 있도록 합니다. ( 기아상태 )

비선점(No Preemption) 부정

• 모든 자원에 대한 "선점"을 허용합니다.
• 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 합니다. ( 자원 낭비 발생 )

순환 대기(Circular Wait) 부정

• 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 합니다. ( 자원 낭비 발생 )

 

 

 

 

🙌 교착 상태 회피 ( Deadlock Avoidance )

 

교착 상태가 발생하기 전에 교착 상태를 예상하여 안전한 상태(safe state)에서만 자원 요청을 허용하는 방법입니다.

키워드로는 [ Safe State, Safe Consequence ] 가 존재합니다.

 

💁🏻‍♂️ 여기서 안전 상태란, 모든 자원을 할당 했을 때 데드락이 발생 하지않는 상태를 의미합니다.

 

 

- Safe State

 

안전 상태란, Safe Sequence가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상황을 의미합니다.

 

반면에 UnSafe State는 비정상적인 종료의 가능성이 조금이라도 존재하는 경우를 의미합니다.

  

 

  

- Banker's Algorithm 

 

자원은 12개, 프로세스는 총 3개가 있는 예시를 통해서 설명 해보겠습니다.

  

   

위와 같이 자원을 할당한다고 가정 했을 때, 현재 남은 총 자원의 수는 3개 ( 12 - (5 + 5 + 2) ) 개 입니다.

현재 상황에서는 [ P2 -> P1 -> P3] 의 Safe Sequence가 나오게 됨으로 Safe State라고 할 수 있습니다.

 

순서를 결정하는 방식은, 현재 자원으로 해결 할 수 있는 순서대로 이동을 하게 되어서, 

 

1) P2이 요구하는 2개의 자원을 제공하고, 반납되는 4개의 자원이 반납된다=> 총 자원 5

2) P1이 요구하는 5개의 자원을 제공하고, 총 10개의 자원이 반납된다 => 총 자원 10

3) P3이 요구하는 7개의 자원을 제공하고, 9개의 자원이 반납된다 => 12개 리턴