[혼공학습단 10기][혼공컴운] 교착 상태

✓ 교착 상태 Deadlock 

두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다려서 그 어떤 프로세스도 더 이상 진행할 수 없는 상태이다. 

일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 의미한다. 

 

✏️ 식사하는 철학자 문제 dining philosophers problem 

By Benjamin D. Esham / Wikimedia Commons, https://commons.wikimedia.org/w/index.php?curid=56559

1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어 든다
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다
4. 식사 시간이 끝나면 오른쪽 포크를 내려 놓는다
5. 오른쪽 포크를 내려 놓은 뒤 왼쪽 포크를 내려 놓는다
6. 다시 1번 부터 반복한다 

 

순서대로 식사를 한다면 문제가 없지만 만약 모든 철학자가 동시에 포크를 집어 식사를 하려고 한다면 그 어떤 철학자도 식사를 할 수가 없고 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야 한다. 

 

 

 

 

 

 

자원 할당 그래프 resource allocation graph

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

- 프로세스는 원으로, 자원의 종류는 사각형으로 표시되며 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현된다.

- 화살표 방향: 프로세스가 자원을 할당받아 사용중이라면 자원→프로세스. 프로세스가 어떤 자원을 기다리고 있다면 프로세스→자원

 

⬇️그래프 모양 확인하기⬇️

Resource Allocation Graph (RAG) in Operating System - GeeksforGeeks

 

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

 

 

 

 

교착상태의 근본적인 이유

1. 상호 배제 mutual exclusion: 해당 자원을 한 번에 하나의 프로세스만 이용 가능
2. 점유와 대기 hold and wait: 자원을 할당받을 상태에서 다른 자원을 할당받기를 기다림 
3. 비선점 nonpreemptive : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못함
4. 원형 대기 circular wait: 자원 할당 그래프가 원의 형태로 그려짐

 

 

 

 

---

✓ 교착 상태 해결 방법

 

1️⃣ 교착 상태 예방

프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당시킨다.

 

- 상호 배제를 없애는 건 현실적으로 불가능

- 점유와 대기를 없애려면 한 프로세스에 필요한 자원들을 몰아주고 그 다음에 다른 프로세스에 또 몰아주고 해야 한다. 그렇게 되면 자원의 활용률이 낮아지고, 특히 많은 자원을 필요로 하는 프로세스의 경우 기아 현상이 야기될 수 있다. 

- 비선점 조건을 없애는 건 모든 자원이 선점 가능한 것이 아니기 때문 범용성이 떨어진다. 

- 원형 대기 조건을 없애려면 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당해야 한다. 비교적 현실적이고 실용적이지만 그리 간단한 작업이 아니며 특정 자원의 활용률이 떨어질 수 있다. 

 

 

 

 

2️⃣ 교착 상태 회피

교착 상태가 발생하지 않을 정도로만 조심조심 자원을 할당하는 방식. 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다. 

 

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

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

 

 

 

 

 

3️⃣ 교착 상태 검출 후 회복

교착 상태 발생을 인정하고 사후에 조치하는 방식. 

 

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

- 프로세스 강제 종료를 통한 회복: 교착 상태인 프로세스를 모두 강제 종료(많은 프로세스들이 작업 내역을 잃게 될 가능성이 있음) or 교착 상태가 없어질 때까지 한 프로세스 씩 강제 종료 (교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드 야기) 

 

 

 

 

+ 교착 상태를 아예 무시하는 방법: 타조 알고리즘 

 

 

 

식사하는 철학자 문제 사진 출처: By Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559