[Chapter 4] 개념 이해를 위한 운영체제 [교착상태 - 개요]

다중 프로그래밍을 지원하는 운영체제에서 여러 개의 프로세스들은 제한된 자원들을 공유하여 사용하게 된다. 프로세스가 어떤 자원을 사용하고자 할 경우 프로세스는 그 자원의 할당을 운영체제에게 요청한다. 운영 체제는 요청된 자원이 사용 가능하면 그 자원을 요청한 프로세스에게 즉시 할당해 주지만 그 자원이 다른 프로세스에 의해 점유되어 있으면 요청한 프로세스를 대기 상태에서 기다리도록 한다. 이렇게 대기 상태로 전환된 프로세스가 무한정 기다리게 될 경우가 발생할 수도 있다.

교착상태

 

• 자원 A, B가 프로세스 1, 2에게 각각 할당된 상태에서 프로세스 1, 2가 자원 B, A의 할당을 각각 요청하게 되면 프로세스 1, 2는 무한정 기다리게 된다.
• 이와 같이 다중 프로그래밍 환경에서 프로세스가 결코 발생하지 않을 특정 사건을 무한정 기다리고 있는 상태를 교착상태(DeadLock)이라고 한다.
• 결국 다중 프로그래밍 환경에서 공유 자원을 사용하는 프로세스들이 병행적으로 실행될 경우 즉, 임계 영역이 존재할 경우 항상 교착상태가 발생할 가능성이 있다.
• 따라서 이러한 교착상태가 발생하지 않도록 지원하는 운영체제의 기능이 요구된다.

자원 할당 그래프

프로세스의 교착상태를 보다 정확하게 설명하기 위하여 자원 할당 그래프를 이용한다. 자원 할당 그래프는 G = (V, E)의 쌍으로 구성되며 V(Vertex)는 프로세스와 자원의 집합이고, E(edge)는 프로세스와 자원과의 관계를 나타내는 집합이다.

프로세스는 원으로 , 자원은 네모로, 프로세스와 자원과의 관계는 화살표로 표시한다. 또한 네모 속의 점은 동일 유형의 자원 개수를 의미한다. 화살표의 방향이 자원에서 프로세스일 경우에는 그 자원이 이미 할당(allocation)되어 있음을 의미하며 프로세스에서 자원일 경우에는 그 자원에 대한 요청(request)을 의미한다. 어떤 프로세스(Pi)가 자원 유형(Ri) 중 하나를 요청하면 자원 할당 그래프에 요청 에지( request edge)가 추가된다. 이 요청이 만족되면 요청 에지는 할당 에지(allocation edge)로 바뀌고 프로세스가 자원을 해제하면 할당 에지는 제거된다.

1. Vertex(Process, Resource), Edge의 집합
   1. 프로세스(P) = {P1, P2, P3}
   2. 자원(R) = {R1, R2, R3}
   3. 에지(E) = {(P1, R1), (P2, R3), (R1, P2), (R2, P2), (R2, P1), (R3, P3)}
2. 자원의 유형 및 개수
   1. 자원의 유형 = (R1, R2, R3)
   2. 유형별 개수 = (1, 2, 1)
3. 프로세스(P1, P2, P3)의 상태
   1. 프로세스 P1은 자원 R2의 하나를 점유하고, 자원 R1을 기다리고 있다.
   2. 프로세스 P2는 자원 R1, R2를 하나씩 점유하고 자원 R3를 기다리고 있따.
   3. 프로세스 P3은 자원 R3의 하나를 점유하고 있다.

자원 할당 그래프를 이용하여 프로세스의 교착 상태 여부를 판단할 수 있다. 주어진 자원 할당 그래프에 사이클이 없으면 교착상태의 프로세스는 존재하지 않는다. 그러나 자원 할당 그래프에 사이클이 있다고 해서 교착상태의 프로세스가 반드시 존재하는 것은 아니다.

교착상태가 발생한 자원 할당 그래프

• 위 이미지에서는 두개의 사이클이 존재하며, p1, p2, p3가 교착상태에 있음을 알 수 있다.
• P1은 P2가 점유한 R1을 P2는 P3가 점유한 R2를, P3는 P1이 점유한 R3를 영원히 기다린다.
• 그러나 자원 할당 그래프에 사이클이 존재한다고 해서 반드시 교착상태인 것은 아니다. 

사이클이 있지만 교착 상태가 아닌 자원 할당 그래프

모든 자원 유형의 개수가 하나일 경우에는 자원 할당 그래프에 사이클이 있으면 사이클에 속해 있는 프로세스들은 반드시 교착상태이다. 그러나 자원 유형의 개수가 여러 개 일 경우에는 자원 할당 그래프에 사이클이 있다고 해서 교착상태의 프로세스가 반드시 존재하는 것이 아님을 알 수 있다. 

결론적으로 자원 할당 그래프에 사이클이 없으면 교착 상태의 프로세스가 존재하지 않으며 사이클이 없으면 교착 상태의 프로세스가 존재할 수도 있고 않을 수도 있다. 이러한 자원 할당 그래프의 속성은 교착상태를 설명하는데 매우 중요한 도구로 사용된다.

---

Reference

개념이해를 위한 운영체제 

https://jaehoney.tistory.com/161

OS - 교착 상태(Deadlock) 정리!

https://truemind5.blogspot.com/2017/04/12-1.html

12. 교착상태(Deadlock)1