[혼공컴운] chapter 13. 교착 상태

13-1. 교착 상태란

 

- 교착 상태: 두 개 이상의 프로세스가 자원을 기다리며 진행이 멈춰 버리는 현상 

 

식사하는 철학자 문제

 

동그란 원탁에 5명의 철학자, 5개의 음식, 5개의 포크

음식은 2개의 포크로 먹을 수 있음 

 

식사 진행 순서 

1. 왼쪽 포크가 사용 가능하면 집어 든다 

2. 오른쪽 포크가 사용 가능하면 집어 든다 

3. 포크 2개를 집어 들면 정해진 시간 동안 식사를 한다 

4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다 

5. 왼쪽 포크를 내려 놓는다 

6. 1 ~ 5 과정을 반복한다 

 

이러한 과정으로 식사를 한다고 했을 때

모든 철학자가 동시에 포크를 들어 식사를 하면 어떤 철학자도 식사를 할 수 없다 

즉, 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야 한다 

프로세스 / 스레드	자원	대기	임계 구역
철학자	포크	생각	포크

 

자원 할당 그래프

 

교착 상태를 단순하게 표현하는 그래프 

어떤 프로세스가 어떤 자원을 사용하고 있고 대기하는지를 표현

 

1. 원: 프로세스, 사각형: 자원의 종류

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

3. 화살표 (자원 -> 프로세스): 자원을 사용중일 때  

4. 화살표 (프로세스 -> 자원): 자원을 대기 중일 때 

 

식사하는 철학자 문제 자원 할당 그래프

 

=> 교착 상태가 일어난 그래프는 자원 할당 그래프가 원의 형태를 띤다 

 

교착 상태 발생 조건

 

1. 상호 배제

2. 점유와 대기

3. 비선점

4. 원형 대기 

 

1. 상호 배제

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때

 

2. 점유와 대기 

자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태 

 

3. 비선점

다른 프로세스의 자원을 강제로 빼앗을 수 없는 상태 

 

4. 원형 대기

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

---

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

 

예방, 회피, 검출, 회복 

 

교착 상태 예방

 

교착 상태 필요 조건 4가지 중 하나를 충족하지 못하게 하면 된다 

 

1. 상호 배제 제거 

모든 자원을 사용 가능하게 만든다 (현실적으로는 힘듦)

 

2. 점유 대기 제거 

포크를 두 개 동시에 들게 하거나, 아예 들지 못하게 하는 것 

-> 한 프로세스에 필요한 자원을 몰아주는 방식으로 동작 

필요해도 대기해야 하고, 사용하지 않으면서 오래 할당받는 자원을 다수 양산하기에 활용률이 낮음 

자원을 많이 사용하는 프로세스가 불리해짐 (기아 발생 가능)

 

3. 비선점 제거 

이용중인 프로세스에서 자원을 뺏을 수 있음 

교착 상태는 일어나지 않음 

선점하여 사용할 수 있는 자원에 대해서는 효과적 (cpu) 그러나 범용성이 떨어짐 

 

4. 원형 대기 제거 

모든 자원의 번호를 붙이고, 오름차순으로 자원 할당 

5번 포크를 집어 들고 1번 포크를 집어 들 수 없음  

수많은 자원에 번호를 붙이는 건 쉽지 않음, 자원의 활용률이 떨어질 수 있음 

 

=> 교착 상태 발생 조건을 제거하여 방지하는 방식은 여러 부작용이 생긴다 

 

교착 상태 회피

 

교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생한다고 간주하여 문제 해결 (방지)

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

 

- 안전 상태: 교착 상태가 발생하지 않고, 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 

- 불안전 상태: 교착 상태가 발생할 수도 있는 상황 

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

- 안전 상태: 안전 순서열대로 자원을 배분하여 교착 상태가 발생하지 않는 상태 

- 불안전 상태: 안전 순서열이 없는 상태, 교착 상태 발생 가능 

 

교착 상태 검출 후 회복

 

교착 상태 발생을 인정하고 조치하는 방법 

 

1. 선점을 통한 회복 

교착 상태가 해결될 때 까지 한 프로세스씩 자원을 몰아주는 방식

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

가장 확실한 방법

- 모두 강제 종료 (모든 작업 내역 잃을 수 있음)

- 교착 상태가 없어질 때 까지 하나씩 강제 종료 (교착 상태 확인 시 오버헤드 발생) 

3. 타조 알고리즘 

교착 상태 무시 

드물게 발생하는 잠재적 문제를 무시로 대처