운영체제(5) - 교착 상태

 

교착 상태란

 

교착 상태를 쉽고 재밌게 설명하는 예로 식사하는 철학자 문제가 있는데 이를 자세히 다루지는 않겠다. 간단히 얘기하면 포크라는 한정된 자원을 두고 철학자들이 식사를 할 때 포크를 써야 하는데 한정되어 있는 포크를 사용하기 위해 생각을 하며 무한히 대기하는 것을 다룬다.

 

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태라고 한다. 다른 예로 게임 프로세스는 자원 A를 점유한 채 웹 프로세스가 점유하는 자원 B의 사용이 끝나길 기다리고, 웹 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리는 것이다. 이렇게 서로 상대방이 가진 자원을 기다리기만 하다가 결국 실행을 못하는 상황이 생긴다.

 

앞에서 배운 뮤테스 락 또한 교착 상태가 발생할 수 있다. 예를 들어 프로세스 A는 임계 구역 진입 전 lock1을 잠그고 프로세스 B는 임계 구역 진입 전 lock2를 잠갔다고 하자 이때 프로세스 A는 lock 2가 false가 되길 기다리고 프로세스 B는 lock1이 false가 되길 기다린다면 교착 상태가 발생한다.

 

이런 교착 상태를 해결하기 위해서는 교착 상태가 발생했을 때의 상황을 정확히 표현해 보고 일어나는 근본적인 이유에 대해 알아야 한다.

 

자원 할당 그래프

 

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프다.

 

첫째, 프로세스는 원으로 자원의 종류는 사각형으로 표현한다.

둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.

셋째, 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.

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

위 이미지는 교착 상태가 없는 상태이다. 여기서 교착 상태가 발생한다면 원의 형태를 띠며 서로 무한히 대기한다.

 

교착 상태 발생 조건

 

교착 상태가 발생할 조건에는 네 가지가 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기다. 즉 이 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만 모두 만족할 경우 발생할 가능성이 있다.

 

• 상호 배제

교착 상태가 발생하는 근본적인 원인은 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제 상황에서 교착 상태가 발생할 수 있다.

• 점유와 대기

어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다. 이렇게 자원을 할당받은 상태에서 다른 자원을 기다리는 상태를 점유와 대기라 한다.

• 비선점

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

• 원형 대기

프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이룬 채 프로세스가 대기하는 원형 대기 상태다. 그러나 원의 형태를 띤다 해서 반드시 교착 상태가 발생하는 것은 아니다.

 

교착 상태 해결 방법

 

교착 상태 예방

 

교착 상태를 예방하는 방법은 교착 상태 발생 필요조건 네 가지 중 하나를 충족하지 못하게 하는 방법과 같다.

 

• 상호 배제 제거

자원의 상호 배제를 없앤다는 것은 모든 자원을 공유 가능하게 만든다는 말과 같다. 다만 이론적으로는 교착 상태를 없앨 수 있으나, 현실적으로 어렵기에 이 방식을 사용하기에는 무리가 있다.

 

• 점유와 대기 제거

점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. 이론적으로는 해결할 수 있지만 자원의 활용률이 낮아질 우려가 있다. 점유와 대기를 금지하면 한 프로세스에 자원을 몰아주고, 그다음 프로세스에 필요한 자원을 몰아줘야 한다. 이는 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산해 자원의 활용률이 낮아진다. 게다가 많은 자원을 사용하는 프로세스가 불리해진다. 자원을 많이 사용하면 동시에 자원을 사용할 타이밍을 확보하기 어렵기 때문에 무한정 기다리는 기아 현상을 야기할 우려가 있다.

 

• 비선점 제거

비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다. 선점하여 사용할 수 있는 일부 자원에서는 효과적이나 프린터와 같이 한 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야 하는 자원도 있기에 다소 범용성이 떨어진다.

 

• 원형 대기 제거

원형 대기를 없애는 방법은 간단하다. 모든 자원에 붙여 오름차순으로 자원을 할당하는 것이다. 위 세 방식보다 현실적이고 실용적이나 단점은 있다. 바로 수많은 자원에 번호를 붙이는 일은 그리 간단한 일이 아니고 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.

 

이렇듯 발생 조건을 원천적으로 제거하여 교착 상태를 방지하는 예방 방식은 문제를 해결할 수는 있지만 여러 부작용이 따른다.

 

교착 상태 회피

 

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식이다. 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.

 

프로세스들에 할당할 수 있는 자원이 충분한 상황에서 프로세스들이 한두 개의 적은 자원만을 요구한다면 교착 상태는 발생하지 않는다. 반면 프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세스들이 한 번에 많은 자원을 요구하면 교착 상태가 발생할 위험이 증가한다. 그렇기 때문에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 배분하는 방법이 교착 상태 회피다.

 

교착 상태 회피하는 방법을 알기 위해 안정 상태와 불안정 상태, 안전 순서열이라는 단어를 알아야 한다. 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태라 부르고, 교착 상태가 발생할 수도 있는 상황을 불안전 상태라 부른다.

 

안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다. 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태를 안전 상태라 한다. 반면 불안전 상태는 안전 순서열이 없는 상황이어서 교착 상태가 발생할 수 있는 위험이 있다.

 

교착 상태 검출 후 회복

 

교착 상태 검출 후 회복은 교착 상태를 인정하고 사후에 조치하는 방식이다. 검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 교착 상태 발생 여부를 주기적으로 검사한다. 그리고 교착 상태가 검출되면 다음 방법으로 회복한다.

 

• 선점을 통한 회복

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

 

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

가장 단순하며 확실한 방법이다. 운영체제에는 교착 상태에 놓인 프로세스를 모두 강제로 종료할 수 있고 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있다. 전자는 가장 확실하지만 그만큼 많은 프로세서들이 작업 내용을 잃게 될 가능성이 있고, 후자는 작업 내용을 잃는 것을 줄일 수 있으나 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.