데드락(Deadlock)

데드락(Deadlock) == 교착상태

• 리소스에 대한 요청이 뒤엉킨 상태
• 서로 다른 프로세스가, 서로 점유하고 있는 자원을 기다릴 때 무한 대기에 빠지는 상황

 

데드락 발생 조건

아래 4가지 조건이 동시에 성립해야 발생함

 

상호 배제

• 한 번에 프로세스 하나만 해당 자원을 사용할 수 있음

점유 대기

• 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림

비선점

• 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림

순환 대기

• 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건

 

데드락 해결 방법

예방(Prevention)

• 위 발생 조건 4가지 중 하나를 방지하여 데드락 발생을 예방하는 방법
• 상호 배제 방지
• 점유 대기 방지
• 비선점 방지
• 순환 대기 방지

 

위 예방 방법은 시스템 처리량이나 자원 사용의 효율성 측면에서 안 좋음

 

회피(Avoidance)

Safe State

• 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생 시키지 않으면서도 차례대로 모두에게 할당해줄 수 있는 상태

Safe Sequence

• 특정 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 안전한 순서(Safe Sequence)라고 부름

Unsafe state

• 데드락이 발생할 가능성이 있는 상황

 

위 개념을 기반으로, 안전한 상태에서만 자원 요청을 허용하는 방법

대표적으로 은행원 알고리즘, 자원 할당 그래프 알고리즘이 있음

 

데드락 탐지(Detection) 및 회복(Recovery)

탐지(Detection)

• 시스템에 데드락이 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것
• 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드가 발생

 

회복(Recovery)

• 프로세스 종료 방법
• 자원 선점 방법

 

데드락 무시

• 발생 조건 네 가지가 다 충족이 되더라도 반드시 교착이 일어나는 것은 아님.
• 환경에 따라서 오버헤드를 감수하는 것이 비효율적일 수 있음
• 그냥 내비두는 방법도 있음.

 

식사하는 철학자 문제

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

 

이 상황에서 철학자(프로세스)들이 동시에 오른쪽 포크(자원)를 집어든다면? 

• 철학자들은 포크를 공유할 수 없음(상호 배제)
• 자신의 왼쪽에 앉은 철학자가 포크를 놓을 때까지 기다림 (점유 상태로 대기)
• 철학자들은 왼쪽 철학자의 포크를 빼앗을 방법도 없음 (선점 불가)
• 각 철학자들은 자신의 왼쪽 철학자의 포크를 대기 (순환대기)

 

해결 방법

• 상호 배제와 선점 불가의 경우, 문제의 조건 때문에 해소가 불가능
• 점유 대기를 해제하려면 왼쪽 포크를 집을 수 없을 때, 오른쪽 포크를 식탁 위에 내려놓는 방법
• 순환 대기를 해소하려면 포크에 우선 순위를 매기는 방법