[컴퓨터 구조] Chapter 13 교착 상태

교착 상태란

프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 진행할 수 없는 교착상태가 된다.
 

1) 식사하는 철학자 문제

동그란 원탁에 철학자 5명이 앉아 식사를 한다. 개인의 앞에는 음식과 음식 양 옆에 포크가 있다고 가정해 보자.
아래와 같은 순서로 식사를 한다고 하면,

• 왼쪽 포크가 사용가능하다면 사용한다.
• 오른쪽 포크가 사용가능하다면 사용한다.
• 왼쪽과 오른쪽 포크를 모두 집어 들면 정해진 시간 동안 식사를 한다.
• 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
• 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
• 이 과정을 반복한다.

 
이처럼 모든 철학자가 동시에 포크를 집어 들면 식사를 할 수 없게 된다. 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야 하는데, 이렇게 일어나지 않을 사건을 기다리며 진행이 멈취버리는 현상을 교착상태라고 한다.
 

2) 자원 할당 그래프

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

다음과 같은 특징을 갖는다.

• 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
• 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
• 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
• 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

 

이처럼 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띠는 것을 알 수 있다.
 

3) 교착 상태 발생 조건

교착 상태가 발생할 조건에는 4가지가 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기이다.
 

상호배제

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제 상황에서 교착 상태가 발생할 수 있다.
 

점유와 대기

프로세스는 어떤 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다.
이처럼 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기라고 한다.
 

비선점

비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하기 때문에 교착상태가 발생하는 것이다.
 

원형 대기

프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
 
 

교착 상태 해결 방법

운영체제는 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방할 수 있고, 교착 상태가 발생하지 않을 정도로 조금씩 할당하다가 교착 상태의 위험이 있으면 자원을 할당하지 않는 방식으로 교착 상태를 회피할 수 있다. 또 자원을 제약 없이 할당받다가 교착 상태가 검출되면 교착 상태를 회복하는 방법을 취할 수도 있다.
 

1) 교착 상태 예방

프로세스에게 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 한다면 교착 상태는 발생하지 않는다.
자원의 상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 한다는 말이다. 하지만 현실적으로 불가능!
점유와 대기는, 앞서 나온 철학자 문제에서 한 손에 포크를 들고 다른 포크를 들지 못하도록 하는 것과 같다. 포크 2개를 동시에 들게 하거나 아예 들지 못하게 하는 것이다. 하지만 이런 방법은 자원의 활용률이 낮아진다는 단점이 있다.
비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 뺏을 수 있다. 식사하는 철학자 문제에서 포크를 뺏는다면 교착 상태가 발생하지 않듯, 자원의 비선점 조건을 없애면 교착 상태는 발생하지 않는다.
원형 대기 조건을 없애려면 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 된다. 모든 포크에 번호를 붙이고 낮은 수의 포크에서 높은 수의 포크로 차례로 집어 들게 하면 원형대기는 발생하지 않는다. 하지만 이 방법 또한 현실적으로 어렵다는 단점이 있다.
 

2) 교착 상태 회피

교착 상태 회피는 교착상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방식이다. 프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세스들이 한 번에 많은 자원을 요 규하면 교착 상태가 발생할 위험이 증가한다.
교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수도 있는 상황을 불완정 상태라고 한다.
안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다. 이처럼 교착 상태 없이 안전하게 프로세스들에게 자원을 배분하여 교착 상태가 발생하지 않는 상태를 안전상태라고 한다. 반면 불완전 상태는 안전 순서열이 없는 상황이다.
 

3) 교착 상태 검출 후 회복

교착 상태 예방과 회피는 교착 상태 발생을 막기 위한 노력이라면, 교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방법이다.
 

선점을 통한 회복

선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다. 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 프로세스에 할당하는 방식이다.
 

프로세스 강제 종료를 통한 회복

운영체제는 교착 상태에 놓은 프로세스를 모두 강제종료 할 수 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료를 할 수도 있다.