[OS] 교착 상태

프로세스의 자원 사용을 위해 자원 요구 → 사용 → 해제의 단계를 거칩니다.
만약 위 과정에서 가용자원이 없다면 자원획득이 가능할 때까지 대기가 필요합니다.
자원을 사용하고 있는 프로세스가 자원을 해제하면 그때 자원을 획득해 사용하게 됩니다.
오늘은 이러한 상황에서 발생할 수 있는 교착상태에 대하여 알아보겠습니다.
 

교착상태와 기아상태

교착상태

영어로는 DeadLock 이라고 칭하는 교착상태는 위와 같은 상황에서 여러 개의 프로세스가 서로 상대방의 작업 종료를 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태를 말합니다.
여기서 키포인트는 영원히 라는 키워드인데요.
언젠간 해소될 수 있다면 교착상태라고 부르지 않습니다.
 

기아상태

기아상태는 언젠가는 해소될 수 있는 가능성이 있는 경우를 칭합니다.
 

교착상태의 특성 

교착상태 발생을 위한 필요조건은 아래와 같습니다.

• 상호배제
• 점유대기
• 비선점
• 환형대기

위의 네 가지 조건이 동시에 만족될 때 교착상태 발생이 가능합니다.
하지만 필요조건일 뿐이지 필요충분조건이 아니기 때문에 네가지 조건을 만족했다고 해서 무조건 발생하는 것은 아닙니다.
 
각 상태에 대해 더 알아보겠습니다.

상호배제조건(mutual exclusion)

지난 포스팅에서 상호배제에 대하여 알아보았기 때문에 간략하게만 설명하겠습니다.
상호배제란 프로세스가 자원에 대한 배타적 통제권을 요구하는 조건입니다.
배타적 통제권이란 해당 자원은 무조건 혼자만 사용해야 한다는 것입니다.
즉 여러 프로세스에 의해 동시 사용 불가능하다는 뜻으로 이러한 상황에서 다른 프로세스가 점유한 자원이 필요하다면 프로세스는 요청한 자원이 해제될 때까지 대기해야 합니다.

점유대기조건(hold and wait )

프로세스가 이미 한 자원을 할당받아 점유한 상태에서 다른 프로세스가 점유 중인 또 다른 자원을 요구하여 해제되기를 기다리는 상황입니다.
 

비선점조건(no preemption)

프로세스가 할당된 자원은 해당 프로세스가 사용을 마치고 스스로 반환하기 전까지는 해제되지 않습니다.
한번 할당된 자원은 타의에 의해서는 해제가 불가능합니다.
 

환형대기조건(circular wait)

프로세스의 자원 점유 및 점유된 자원의 요구관계가 환형을 이르며 대기하는 상황입니다.

 
 

자원 할당 그래프 

자원할당 그래프는 프로세스와 자원 사이에 요구와 할당 관계를 나타내는 그래프입니다.
하나의 자원할당 그래프는 한순간을 표현하고 있으며 변화될 수 있습니다.
그래프를 통해 사이클의 존재 유무를 통해 교착상태의 발생 가능성을 확인할 수 있습니다.
 
자원할당 그래프를 그리는 것은 간단합니다.
수식은 아래와 같습니다.
G = (V, E)
 

V

정점의 집합입니다.
V = P와 R의 합집합으로 나타냅니다.
P는 n개의 프로세스를 R는 m개의 자원을 나타냅니다.

자원 위에는 단위자원의 개수를 표시해 줍니다.
 

E

간선의 집합입니다. 
E = Q와 S의 합집합으로 나타냅니다.
Q는 프로세스가 요구간선, S는 할당간선을 뜻합니다.

글이 너무 단조로운 것 같아 색깔을 넣어봤어요 ㅎㅎ 
 
그럼 예시로 하나 그려볼까요?

어떤 것이 할당간선이고 어떤 것이 요구간선인지 구분이 가능하시다면 성공입니다!
만약 요구 중인 자원에 가용한 단위자원이 존재한다면 요구간선을 할당간선으로 변경하면 됩니다.
주황 선으로 표시한 것처럼요!

 
자원할당 그래프를 이용하면 교착상태의 필요조건을 표현할 수 있는데요.
표현 방법은 아래와 같습니다.

• 상호배제 : 하나의 할당간선 
• 점유대기 : 한 프로세스에 할당간선과 요구간선 연결 
• 비선점 : 요구간선
• 환형대기 : 사이클