[운영체제] 교착 상태란?

식사하는 철학자 문제

식사하는 철학자

식사하는 철학자 문제는 교착 상태를 설명하기 위해서 사용되는 문제입니다. 5명의 철학자가 존재하고 왼쪽과 오른쪽에 포크가 존재합니다. 앞에 놓인 음식을 먹기 위해서는 양손에 포크를 가지고 있어야 합니다. 단, 조건이 존재합니다.

1. 왼쪽 포크를 사용할 수 있다면 집어든다.
2. 오른쪽 포크를 사용할 수 있다면 집어든다.
3. 왼쪽과 오른쪽 포크 모두 집었다면 앞에 놓인 음식을 먹을 수 있다.
4. 식사가 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 놓은 후 왼쪽 포크를 놓는다.

단순히 모든 철학자가 양손에 포크를 들어 식사를 하면 될 것 같습니다. 그러나 모든 철학자가 포크를 사용하려고 하면 문제가 발생합니다. 모두가 왼쪽 포크를 집게 된다면 어느 누구도 오른쪽 포크를 집을 수 없게 됩니다. 

 

각자 오른쪽 포크를 잡기 위하여 다른 철학자가 왼쪽 포크를 놓기를 기대하고 있습니다. 그러나 어느 누구도 왼쪽 포크를 놓지 않을 것입니다. 왜냐하면 모두가 오른쪽 포크를 집기 위해서 기다리고 있기 때문입니다.

 

이처럼 발생하지 않을 일(오른쪽 포크를 집는 것)을 기다리며 진행이 멈추는 현상(음식을 먹지 못하는 것)을 교착 상태라고 합니다.

 

뮤텍스 락과 임계 구역

자원 할당 그래프

임계 구역이란 하나의 자원에 동시에 접근하면 문제가 발생하는 자원에 접근하는 영역을 의미합니다. 

프로세스 A

자원 A를 사용하기 전에 임계 구역 A를 잠굽니다. 잠구는 이유는 다른 프로세스가 자원 A를 동시에 사용하지 못하게 하기 위해서입니다.

프로세스 A는 임계구역 B에 접근할 수 있을 때까지 바쁜 대기를 합니다. 바쁜 대기란 임계구역이 잠겨있는지 쉴 새 없이 반복하는 행위를 의미합니다. 

 

프로세스 A가 자원 B를 사용하기 위해 대기하는 시점에서 교착 상태가 발생합니다. 왜냐하면 자원 B는 프로세스 B가 사용하고 있는데, 프로세스 B 또한 자원 A를 사용하기 위해 바쁜 대기를 하고 있기 때문입니다.

lockA = true;
while(lockB == true) {
};
lockA = false;

프로세스 B

프로세스 A와 동일한 작업을 수행합니다.

lockB = true;
while(lockA == true) {
};
lockB = false;

 

교착 상태 발생 조건

교착 상태가 발생하기 위해서는 4가지 조건이 존재합니다. 4가지 조건을 모두 만족하면 교착 상태가 발생할 가능성이 존재하게 됩니다. (교착 상태가 반드시 발생하는 것이 아닙니다) 반대로 조건 하나라도 만족하지 않는다면 교착 상태가 발생하지 않습니다.

 

교착 상태 발생 4가지 조건

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

상호 배제

위에서 프로세스 A와 프로세스 B가 교착 상태가 발생한 이유는 하나의 자원에 대해서 서로가 접근하려고 했기 때문입니다. 프로세스 A는 자원 A를 점유하면서 자원 B를 사용하려고 하고, 프로세스 B는 자원 B를 점유하면서 자원 A를 사용하려고 했기 때문입니다.

 

자원은 한 번에 하나의 프로세스만 사용 가능하기 때문에 이러한 문제가 발생했습니다. 즉, 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 상호 배제가 발생한다고 합니다.

점유와 대기

프로세스 A와 B는 서로가 점유하고 있는 자원을 사용하기 위해서 바쁜 대기를 하였습니다. 이러한 문제가 발생한 이유는 이미 자원을 사용하고 있는 상태에서 다른 프로세스의 자원을 사용하려고 했기 때문입니다. 

 

이처럼 자원을 이미 할당받은 상태에서 다른 자원을 할당받기 위해 대기하는 상태를 점유와 대기라고 합니다.

비선점

각 프로세스는 다른 프로세스가 할당받은 자원을 사용하기 위하여 무작정 대기를 하고 있습니다. 만약 대기를 하는 것이 아닌 뺏을 수만 있었다면 무작정 기다리지 않고 사용할 수 있었을 것입니다.

 

자원을 사용 중인 프로세스의 작업이 끝나야만 대기를 종료하고 해당 자원을 할당받을 수 있게 됩니다. 어떤 프로세스도 다른 프로세스가 사용 중인 자원을 강제로 뺏지 못하는 것을 비선점이라고 합니다.

원형 대기

위 자원 할당 그래프를 보면 원형으로 그려진 것을 확인할 수 있습니다. 자원 할당 그래프가 원의 형태로 그려지면 교착상태가 발생할 수 있습니다. 다만 원의 형태를 띤다고 해서 반드시 교착 상태가 발생하는 것이 아닙니다. 

• 원의 형태 X : 교착 상태가 발생하지 않는다.
• 원의 형태 O : 교착 상태가 발생할 수도 있다.