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

식사하는 철학자 문제

 

교착 상태를 설명하기 위한 고전적인 문제 상황. 교착 상태가 어떤 상황에서 왜 발생하고 어떻게 해결 가능한지 볼 수 있는 시나리오

 

둥근 원탁에 철학자 5명이 앉아 있고 앞에 식사가 있음. 식사는 포크 2개로 먹을 수 있는 음식일 때 철학자들은 아래 순서로 식사를 함

 

1. 계속 생각하다가 왼쪽 포크를 쓸 수 있으면 집어듬
2. 계속 생각하다가 오른쪽 포크를 쓸 수 있으면 집어듬
3. 왼쪽, 오른쪽 포크를 모두 들면 정해진 시간 동안 식사
4. 식사가 끝나면 오른쪽 포크를 내려놓음
5. 오른쪽 포크를 내려놓고 왼쪽 포크 내려놓음
6. 다시 1부터 반복

 

모든 철학자가 동시에 포크를 집으면 어떤 철학자도 식사할 수 없고 영원히 생각만 해야 할 수 있다

이렇게 일어나지 않을 사건을 기다리며 진행이 멈추는 현상을 교착 상태라고 함

 

자원 할당 그래프

 

어떤 프로세스가 어떤 자원을 쓰고 있고, 어떤 프로세스가 어떤 자원을 기다리는지 표현하는 그래프

교착 상태는 자원 할당 그래프로 단순하게 표현 가능함. 자원 할당 그래프는 아래 규칙으로 그려짐

 

1. 프로세스는 원, 자원의 종류는 사각형으로 표현
2. 쓸 수 있는 자원 개수는 자원 사각형 안에 점으로 표현 (3개 쓸 수 있으면 점 3개)
3. 프로세스가 어떤 자원을 할당받아 쓰고 있다면 자원에서 프로세스를 향해 화살표 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표 표시

 

교착 상태 발생 조건

 

교착 상태 발생 조건 : 상호 배제, 점유와 대기, 비선점, 원형 대기

 

• 상호 배제 : 한 프로세스가 쓰는 자원을 다른 프로세스가 쓸 수 없는 상황
• 점유와 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점 : 자원을 쓰는 프로세스의 작업이 끝나야만 쓸 수 있음
• 원형 대기 : 자원 할당 그래프가 원형으로 그려지면 교착 상태가 발생할 수 있음. 프로세스들이 원형으로 자원을 대기하는 걸 원형 대기라고 함

 

교착 상태 해결 방법

 

교착 상태 예방

 

프로세스에 자원을 할당할 때 4가지 조건 중 하나라도 만족시키지 않게 할당하면 교착 상태는 발생하지 않음

 

교착 상태 회피

 

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

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

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

 

교착 상태 검출 후 회복

 

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

 

• 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복