교착 상태

식사하는 철학자 문제라는 고전적이고 재밌는 문제 상황이 있다.

동그란 원탁에 다섯 명의 철학자가 앉아 있는데 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이 있다고 가정해보자.

 

철학자들은 아래와 같은 순서로 식사를 할 수 있다.

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

순서를 보면 아무 문제 없지만 모든 철학자가 동시에 포크를 집는다면 누구도 식사할 수 없다. 이렇게 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라고 한다.

 

교착 상태 발생 조건 : 상호배제, 점유와 대기, 비선점, 원형대기가 모두 만족 될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호배제 : 근본적인 원인은 해당 장원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 상호배제 상황에서 교착 상태가 발생할 수 있다.
• 점유와 대기 : 철학자 문제에서 '왼쪽 포크를 들고' 다른 철학자의 포크를 기다렸기 때문이다. 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기라고 한다.
• 비선점 : 만약 다른 철학자의 포크를 강제로 빼앗을 수 있었다면 교착 상태는 발생하지 않았을 것이다. 프로세스가 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생할 수 있다.
• 원형 대기 : 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문이다. 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다. 

교착 상태 회피 : 교착 상태가 발생하지 않을 정도로만 조심히 자원을 할당하는 방식. 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다. 

• 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안정 상태 : 교착 상태가 발생할 수도 있는 상황
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • 예) 웹 브라우저, 메모장, 게임 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 웹 브라우저 - 메모리 - 게임 프로세스 순서대로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정하면 이 순서가 안전 순서열이 된다.

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

1. 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식. 즉, 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식.
2. 프로세스 강제 종료를 통한 회복 : 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고, 없어질 때까지 한 프로세스씩 강제 종료할수도 있다. 전자는 한 방에 해결할 수 있지만 작업 내역을 잃게 될 가능성이 있다. 후자는 작업 내역을 잃는 프로세스는 최대한 줄일 수 있다.