[ 혼자 공부하는 컴퓨터구조 + 운영체제 ] Chapter13. 교착 상태

13-1. 교착 상태란

(1) 식사하는 철학자 문제

식사하는 철학자 문제는 교착 상태를 설명하기 위한 고전적이고 재미있는 문제 상황으로, 교착 상태가 어떤 상황에서 왜 발생하는지, 나아가 교착 상태를 어떻게 해결할 수 있는지를 엿볼 수 있는 가상의 문제 시나리오이다.

 

모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들 수 없기 때문에, 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다.

 

교착 상태(deadlock): 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

철학자는 프로세스 혹은 스레드, 포크는 자원, 생각하는 행위는 자원을 기다리는 것에 빗대어 볼 수 있다.

 

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

 

(2) 자원 할당 그래프

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

자원 할당 그래프(resource-allocation graph): 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프

 

자원 할당 그래프는 다음과 같은 규칙으로 그려진다.

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

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

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

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

 

교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

 

(3) 교착 상태 발생 조건

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

해당 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

 

- 상호 배제

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

 

- 점유와 대기

어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다.

 

- 비선점

비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다.

어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있다.

 

- 원형 대기

: 프로세스들이 원의 형탤 자원을 대기하는 것

자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다.

※ 자원 할당 그래프가 원의 형태를 띄지 않는다면 교착 상태는 발생하지 않으나, 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다.

 

 

13-2. 교착 상태 해결 방법

(1) 교착 상태 예방

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

 

1. 상호 배제를 없애기

상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 한다는 말과 같은데, 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기에 현실에서 사용하기에는 무리가 있다.

 

2. 점유와 대기 없애기

점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.

이는 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와, 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다.

 

3. 비선점 조건 없애기

CPU와 같이 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이나, 모든 자원이 선점 가능한 것은 아니기 때문에 다소 범용성이 떨어진다.

 

4. 원형 대기 조건 없애기

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.

 

앞선 세 방식에 비하면 비교적 현실적이고 실용적이지만, 수많은 자원에 번호를 붙이는 일은 간단한 작업이 아니며, 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다는 단점이 있다.

 

(2) 교착 상태 회피

교착 상태 회피는 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법

 

안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

안전 상태(safe state): 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태

불안전 상태(unsafe state): 안전 순서열이 없어 교착 상태가 발생할 수도 있는 상황

 

교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이라고 보면 된다.

 

(3) 교착 상태 검출 후 회복

교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식이다.

운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 발생 여부를 주기적으로 검사한다. 그리고 교착 상태가 검출되면 다음과 같은 방식으로 회복한다.

 

- 선점을 통한 회복

: 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스씩 자원을 몰아주는 방식

 

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

교착 상태에 놓인 프로세스 모두를 강제 종료 → 한 번에 해결할 수 있는 확실한 방식이지만 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있다.

교착 상태가 없어질 때까지 한 프로세스씩 강제 종료 → 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.

 

※ 문제 발생의 빈도나 심각성에 따라 교착 상태를 아예 무시하는 타조 알고리즘도 있다.