13. 교착 상태

13-1. 교착 상태란?

식사하는 철학자 문제(dining philosophers problem)

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

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

자원 할당 그래프(resource-allocation graph)

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프

자원 할당 그래프는 아래와 같은 규칙으로 그려집니다.
1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

####[예]

‘현재 사용 가능한 SSD 자원은 세 개, CPU 자원은 두 개, 프린터는 한 개 있는데, 프로세스 A는 SSD를 할당받아 사용 중이고, 프로세스 B와 C는 CPU를 할당받아 사용 중이며, 프로세스 D는 프린터를 사용 중이다. 그리고 프로세스 E는 프린터 자원을, 프로세스 F는 CPU의 할당을 기다리고 있다’

교착 상태 발생 조건

• 상호 배제(mutual exclusion)
• 점유와 대기(hold and wait)
• 비선점(nonpreemptive)
• 원형 대기(circular wait)
  → 위 조건 네 가지가 모두 만족해야 교착상태가 발생하고, 이 중 하나라도 만족하지 않으면 교착상태가 발생하지 않음

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

교착 상태 예방

• 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법

  1. 자원의 상호 배제를 없앤다 = 모든 자원을 공유 가능하게 만든다
     → 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기에 이 방식을 현실에서 사용하기에는 다소 무리
     
     
  2. 점유와 대기를 없앤다 = 한 손에 포크를 들고 다른 포크를 기다리지
     못하게 금지하는 것
     → 자원의 활용률이 낮아질 우려
     → 많은 자원을 사용하는 프로세스가 불리
     → 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상
     을 야기할 우려
     
     
  3. 비선점 조건을 없앤다 = 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗는다.
     → 일부 자원에 대해서는 효과적
     → 다소 범용성이 떨어지는 방안
     
     
  4. 원형 대기를 없앤다 = 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당한다
     → 마치 철학자들이 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황과 유사
     → 위 세 방식보다는 비교적 현실적이고 실용적인 방식
     → 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 그리 간단한 작업이 아님
     → 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있음

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식

교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식
  • 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 프로세스 강제 종료를 통한 회복