교착상태

• 식사하는 철학자 문제

 

다섯 명의 철학자가 하나의 원탁에 앉아 식사를 한다. 각각의 철학자들 사이에는 포크가 하나씩 있고, 앞에는 접시가 있다. 접시 안에 든 요리는 포크를 두개 사용하여 먹어야만 하는 스파게티 이다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없으며, 번갈아가며 각자 식사하거나 생각하는 것만 가능하다. 따라서 식사를 하기 위해서는 왼쪽과 오른쪽의 인접한 철학자가 모두 식사를 하지 않고 생각하고 있어야만 한다. 또한 식사를 마치고 나면, 왼손과 오른손에 든 포크를 다른 철학자가 쓸 수 있도록 내려놓아야 한다. 이 때, 어떤 철학자도 굶지 않고 식사할 수 있도록 하는 방법은 무엇인가?

 

모든 철학자가 동시에 왼쪽 포크부터 집어들면 어떤 철학자도 식사를 하지 못하고 대기하는 상황이 계속 지속된다

이렇게 진행이 멈춰 버리는 현상을 데드락이라고 한다

 

뮤텍스에서도 교착 상태는 발생할 수 있다

 

• 교착 상태 발생 조건

 

상호 배제

점유와 대기

비선점

환형 대기

 

이 4가지 조건을 모두 만족될때 교착 상태가 발생한다

 

교착 상태를 해결하기 위해서 예방 / 회피 / 검출 후 회복의 3가지 방법을 사용할 수 있다

 

• 교착 상태 예방 방법

 

- 상호 배제를 없애는 방법 : 모든 자원의 상호 배제를 없애는 건 동시성 문제 발생

 

- 점유와 대기를 없애는 방법 : 자원을 모두 할당하거나, 아예 할당받지 못하게 하는 방법 <- 교착 상태를 해결할 수 있지만 자원의 활용률이 낮아지게 된다, 많은 자원을 사용하는 프로세스는 동시에 자원을 할당받기가 더 어려워져서 기아 현상이  발생할 수 있음

 

- 비선점 조건을 없애는 방법

이용중인 프로세스에서 자원을 빼았을 수 있지만 이 방법도 범용성이 떨어짐(프린터기에서 여러 사진을 동시 출력..)

 

- 원형 대기를 없애는 방법

자원에 번호를 붙이고 순서대로 할당, 가능한 방법이지만 모든 자원에 번호를 붙이는 방법은 비효율적이다

 

• 교착 상태 회피

 

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

 

안전 상태 - 모든 프로세스가 자원 할당받아서 사용하고 종료가능한 상태

불완전 상태 - 교착 상태 발생 가능성이 있는 상태

안전 순서열 - 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서(프로그램들의 실행 순서)

 

안전 순서열 대로 프로세스에 자원을 할당해 안전 상태가 유지되게 하는 방법

 

• 교착 상태 검출 후 회복

교착이 발생하면 그때 동작하는 방식

 

선점을 통한 회복 - 교착 상태가 해결될때 까지 한 프로세스씩 자원을 몰아주는 방식

프로세스 강제 종료를 통한 회복 - 교착 상태 발생시 교착 상태 프로세스를 모두 종료하거나, 교착 상태 해결될때까지 하나씩 종료시키는 방법

 

- 교착 상태를 아예 무시하는 타조 알고리즘도 있다