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

13-1 교착 상태란

두 개 이상의 프로세스가 각자 필요한 자원을 무작정 기다리며 그 어떤 프로세스도 더 이상 진행할 수 없는 상태 

 

식사하는 철학자 문제

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

만약 모든 철학자가 동시에 식사를 하기 위해 왼쪽 포크를 집어든다면, 모든 철학자가 오른쪽 포크가 사용 가능할 때까지 기다리게 되며, 진행이 멈춰버리는 교착 상태에 빠지게 된다.

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

철학자는 프로세스(스레드), 포크는 자원, 생각하는 행위는 자원을 기다리는 것에 비유하여 볼 수 있다.

 

자원 할당 그래프

• 교착 상태를 그래프를 통해 단순하게 표현하는 방법.
• 첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현.
• 둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현.

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

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

• 식사하는 철학자 문제를 자원 할당 그래프로 표현.
• 교착상태는 다음과 같이 원의 형태를 띄고 있다.

 

교착 상태 발생 조건

교착 상태가 발생하는 조건은 아래의 4가지이며, 하나라도 만족하지 않는다면 교착상태가 발생하지 않으나, 모든 조건이 충족된다면 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
• 점유와 대기
  • 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태일 때.
• 비선점
  • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 비선점 상태일 때.
• 원형 대기
  • 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이룰 때.(자원 할당 그래프)

 

 

13-2 교착 상태 해결 방법

교착 상태 예방

• 교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법.
• 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 따른다.
• 상호 배제 제거
  • 모든 자원을 공유 가능하게 만든다.
  • 이론적으로는 가능하나, 현실적으로 모든 자원의 상호 배제를 없애기는 다소 무리가 있다.
• 점유와 대기 제거
  • 운영체제가 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분.
  • 마찬가지로 이론적으로는 가능하나, 자원의 활용률이 낮아질 우려가 있다.
  • 자원을 많이 사용하는 프로세스일수록 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.
• 비선점 제거
  • 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있기 때문에 일부 자원에 대해서는 효과적이다.
  • 선점하여 사용할 수 있는 일부 자원(ex: CPU)에 대해서는 효과적이다.
  • 하지만 선점하기 어려운 자원(ex: 프린터)도 있으므로 다소 범용성이 떨어지는 방법이다.
• 원형 대기 제거
  • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당.
  • 앞의 3개의 방식에 비하면 비교적 현실적인 방법.
  • 하지만 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것이 간단한 작업이 아니며, 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다는 단점이 있다. 

 

교착 상태 회피

• 안전 상태를 유지할 수 있는 경우에만 자원을 할당하는 방법.
• 안전 순서열: 교착 상태가 발생하지 않도록 모든 프로세스들에 자원을 할당할 수 있는 순서.
  • 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태를 안전 상태라고 한다.
  • 불안전 상태는 안전 순서열이 없는 상태이며, 교착 상태가 발생할 수 있는 위험이 있다.

 

교착 상태 검출 후 회복

• 교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 그때그때 회복하는 방법.
• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스씩 자원을 몰아주는 방식.
• 프로세스 강제 종료를 통한 회복
  
  • 방식1. 교착 상태에 놓인 프로세스를 모두 강제 종료
    • 교착 상태를 해결 할 수 있는 가장 확실한 방식이지만 그만큼 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있다.
  • 방식2. 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
    • 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기.