[운영체제] 교착 상태 발생 조건과 자원 할당 그래프

교착 상태

운영체제에서 여러 프로세스는 동시에 실행되며 여러 자원을 사용한다.

그런데 어떤 상황에서는 프로세스들이 서로 필요한 자원을 기다리기만 하고, 아무도 더 이상 진행하지 못하는 상태가 발생할 수 있다.

이런 상태를 `교착 상태(deadlock)`라고 한다.

 

쉽게 말하면, 각 프로세스가 자원을 하나씩 붙잡고 있으면서 서로가 가진 자원을 기다리는 상황이다.

 

프로세스 A는 자원 1을 가지고 자원 2를 기다림
프로세스 B는 자원 2를 가지고 자원 1을 기다림

→ 둘 다 서로의 자원을 기다리기만 함
→ 아무도 진행하지 못함

 

즉, 교착 상태는 프로세스들이 서로 자원을 기다리느라 멈춰버린 상태라고 볼 수 있다.

식사하는 철학자 문제

교착 상태를 설명할 때 자주 나오는 예시가 식사하는 철학자 문제이다.

상황은 다음과 같다.

다섯 명의 철학자가 원탁에 앉아 있다.
각 철학자 앞에는 접시가 있고, 철학자들 사이에는 포크가 하나씩 놓여 있다.

접시에 있는 음식은 스파게티라서 양손에 포크를 하나씩 들어야만 먹을 수 있다고 하자.

철학자는 생각하기, 식사하기 두 가지 행동만 한다.

철학자가 식사하려면 왼쪽 포크와 오른쪽 포크를 모두 집어야 한다.
식사를 마치면 두 포크를 내려놓는다.

 

이를 절차로 표현하면 다음과 같다.

1. 일정 시간 생각한다.
2. 왼쪽 포크가 사용 가능해질 때까지 기다린다.
3. 왼쪽 포크가 사용 가능하면 집어든다.
4. 오른쪽 포크가 사용 가능해질 때까지 기다린다.
5. 오른쪽 포크가 사용 가능하면 집어든다.
6. 양쪽 포크를 모두 잡으면 일정 시간 식사한다.
7. 오른쪽 포크를 내려놓는다.
8. 왼쪽 포크를 내려놓는다.
9. 다시 생각한다.

 

문제는 모든 철학자가 동시에 왼쪽 포크를 집어드는 경우이다.

 

그러면 각 철학자는 왼쪽 포크 하나씩은 가지고 있지만, 오른쪽 포크는 옆 철학자가 이미 들고 있다.

이 경우 누구도 오른쪽 포크를 얻을 수 없다.

 

각자 이미 포크 하나를 들고 있기 때문에, 다른 철학자에게 포크를 넘겨주지도 않는다.
결국 모두가 서로의 포크를 기다리기만 한다.

 

이것이 교착 상태이다.

 

 

교착 상태를 이해하려면

교착 상태를 해결하거나 예방하려면 먼저 두 가지를 파악해야 한다.

1. 교착 상태가 발생한 상황을 정확히 표현할 수 있어야 한다.
2. 교착 상태가 왜 발생하는지 조건을 알아야 한다.

 

교착 상태 상황을 표현할 때 사용할 수 있는 것이 자원 할당 그래프이다.

자원 할당 그래프

자원 할당 그래프(Resource Allocation Graph)는 어떤 프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 기다리는지 표현한 그래프이다.

이 그래프를 사용하면 교착 상태가 발생할 가능성이 있는지 파악할 수 있다.

자원 할당 그래프에서는 프로세스와 자원을 다음처럼 표현한다.

프로세스 → 원
자원 종류 → 사각형
자원의 개수 → 사각형 안의 점

 

프로세스가 어떤 자원을 기다리고 있다면, 프로세스에서 자원으로 화살표를 표시한다.

어떤 자원이 프로세스에 할당되어 사용 중이라면, 자원에서 프로세스로 화살표를 표시한다.

 

식사하는 철학자 교착 상태 그래프는 아래와 같다.

 

 

 

이처럼 교착 상태가 발생한 자원 할당 그래프는 원형 구조를 가지는 경우가 많다.

 

교착 상태 발생 조건

교착 상태는 아무 때나 발생하는 것이 아니다.

교착 상태가 발생하려면 다음 네 가지 조건이 모두 만족되어야 한다.

1. 상호 배제
2. 점유와 대기
3. 비선점
4. 원형 대기

 

이 네 가지 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다.
반대로 네 가지 조건이 모두 만족되면 교착 상태가 발생할 수 있다.

1. 상호 배제

상호 배제(mutual exclusion)는 한 프로세스가 사용 중인 자원을 다른 프로세스가 동시에 사용할 수 없는 상태를 말한다.

 

예를 들어 포크 하나는 동시에 두 철학자가 사용할 수 없다.

즉, 자원이 한 번에 하나의 프로세스에게만 할당될 수 있는 상태이다.

 

상호 배제가 없다면 여러 프로세스가 같은 자원을 동시에 사용할 수 있으므로, 자원을 기다릴 필요가 줄어든다.

 

하지만 현실의 많은 자원은 동시에 사용할 수 없다.
프린터, 파일 쓰기, 특정 장치 등은 한 번에 하나의 프로세스만 사용하는 경우가 많다.

2. 점유와 대기

점유와 대기(hold and wait)는 프로세스가 어떤 자원을 이미 가지고 있으면서, 다른 자원을 추가로 기다리는 상태를 말한다.

식사하는 철학자 문제에서는 각 철학자가 왼쪽 포크를 들고 있으면서 오른쪽 포크를 기다린다.

 

즉, 자원을 하나 잡은 채 다른 자원을 기다리는 것이다.

이 조건이 만족되면 자원이 풀리지 않고 계속 묶여 있게 된다.

3. 비선점

비선점(no preemption)은 어떤 프로세스가 이미 사용 중인 자원을 다른 프로세스가 강제로 빼앗을 수 없는 상태를 말한다.

예를 들어 한 철학자가 포크를 들고 있다면, 다른 철학자가 그 포크를 강제로 빼앗을 수 없다.

 

자원을 가진 프로세스가 스스로 자원을 내놓기 전까지는 다른 프로세스가 사용할 수 없다.

이 조건이 있기 때문에 기다리는 프로세스는 계속 기다릴 수밖에 없다.

4. 원형 대기

원형 대기(circular wait)는 프로세스들이 원형으로 서로의 자원을 기다리는 상태를 말한다.

예를 들어 다음과 같은 상황이다.

P1은 P2가 가진 자원을 기다림
P2는 P3가 가진 자원을 기다림
P3는 P1이 가진 자원을 기다림

 

결국 기다림이 원형으로 이어진다.

이 원형 대기 구조가 생기면 아무도 먼저 빠져나올 수 없기 때문에 교착 상태가 발생한다.

 

 

교착 상태 조건 정리

교착 상태의 네 가지 발생 조건은 다음과 같다.

상호 배제
- 한 프로세스가 사용하는 자원을 다른 프로세스가 동시에 사용할 수 없음

점유와 대기
- 자원을 가진 상태에서 다른 자원을 기다림

비선점
- 다른 프로세스가 가진 자원을 강제로 빼앗을 수 없음

원형 대기
- 프로세스들이 원형으로 서로의 자원을 기다림

 

이 네 가지 조건은 교착 상태의 필요 조건이다.

 

즉, 교착 상태가 발생하려면 이 조건들이 모두 만족되어야 한다.

 

하나라도 깨뜨릴 수 있다면 교착 상태를 막을 수 있다.

 

예를 들어 원형 대기를 없애거나, 점유와 대기 상태를 만들지 않거나, 필요한 경우 자원을 선점할 수 있게 하면 교착 상태를 예방할 수 있다.