[OS] 교착 상태 (자원 할당 그래프, 식사하는 철학자 문제)

 

 

교착 상태

.

 

 

교착상태는 다른 프로세스의 잡업이 끝나기를 기다리며 작업을 진행하지 못하는 상태이다.

 

아사현상은 운영체제가 잘못된 정책을 사용하여 지연되는 문제이고,

교착상태는 여러 프로세스가 작업하다 보니 자연적으로 발생하는 문제이다.

 

즉, 중요한 점은 교착 상태와 아사 현상이 다르다는 것이다.

한 프로세스가 두 자원을 다 점유하거나, 반대로 두 자원을 다 기다리는 상태라면 교착 상태가 아니다.

이는 서로 진행을 방해하는 것이 아니라 선후 관계를 만드는 것이고

서로 진행을 방해해야만 교착 상태가 발생한다 할 수 있다.

 

교착상태는 공유할 수 없는 자원을 사용할 때 발생하고,

자원을 하나씩 가지고 서로가 가진 자원을 기다릴 때 발생한다.

 

 

 

 

예로 P1은 프린터를 할당받은 후 CD 레코더를 기다리고,

P2는 CD 레코더를 할당받은 후 프린터를 기다린다.

 

이는 교착 상태가 발생한 상황이다.

 

 

자원 할당 그래프

.

 

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 기다리는지를 그래프로 표현한 것이다.

이 그래프는 정점 V와 간선 E의 집합으로 구성된다.

 

아래 그림을 보자.

프로세스는 원으로, 자원은 사각형으로 표현한다.

 

방향 간선은 Pi -> Rj로 표현하며

Pi -> Rj를 요청 간선이라 부르고, Rj -> Pi를 할당 간선이라 한다.

 

 

 

자원이 2개 이상의 프로세스를 동시에 허용하는 경우는 '다중 자원'이라 한다.

다중 자원은 사각형 안에 작은 동그라미로 표현한다.

 

유의할 점은 할당 간선은 사각형 안의 하나의 점을 지정해야 하지만,

요청 간선은 사각형만을 가리킨다는 것이다.

 

요청이 가능하면 즉시 할당 간선으로 변환되고,

자원을 더 접근하지 않아도 되면 자원을 방출하고 할당 간선이 삭제된다.

 

 

 

또 다른 예로 '식사하는 철학자 문제'가 있다.

4명의 철학자가 식사를 하기 위해 왼쪽의 포크를 집은 후 오른쪽 포크를 집어야 한다.

 

하지만 오른쪽 포크는 이미 옆의 철학자가 집어 모두 식사를 하지 못한다는 것이다.

 

 

 

여기서 교착 상태 발생하는 조건을 보자.

 

1. 철학자들은 서로 포크를 공유할 수 없다.	자원을 공유하지 못한다.
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다.	자원을 놓을 때까지 기다려야 한다.
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다.	자원 하나를 잡은 상태에서 다른 자원을 기다린다.
4. 자원 할당 그래프가 원형이다.	자원을 요구하는 방향이 원을 이루면 양보를 하지 않는다.

 

 

즉, 교착 상태는 '상호 배제', '비선점', '점유와 대기', '순환 대기'를 모두 충족해야 발생한다.

이 중 하나라도 충족하지 않으면 교착상태는 발생하지 않는다.

 

상호 배제	다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
비선점	사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
점유와 대기	다른 프로세스가 필요로 하는 자원을 점유한 상태에서 또 다른 자원을 기다리는 상태여야 한다.
순환 대기	점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.

 

 

앞에서 교착 상태는 아사 현상과 다르다고 했다.

아사 현상은 양보를 할 때마다 우선순위를 높여주는 기법인 에이징으로 해결할 수 있지만

교착 상태는 자연적으로 발생하여 에이징으로 해결할 수 없고 정책을 바꿔도 막을 수 없다.

 

 

다음은 교착 상태를 해결하는 방법인 예방, 회피, 검출에 대해 알아보겠습니당.

 

 

 

 

 

 

 

 

* 해당 글은 '쉽게 배우는 운영체제'와 '운영체제' 책을 참고하여 작성하였습니다. 출처: 쉽게 배우는 운영체제 (조성호), 운영체제 10판 (Abraham Silberschatz)