[07] 교착 상태 - Dead Lock

식사하는 철학자 문제

• 교착 상태를 설명하기 위한 아주 고전적인 예시 상황

• 철학자들은 아래와 같은 순서로 식사

1. 생각하다가 왼쪽 포크가 사용 가능 하면 집어든다 

2. 생각하다가 오른쪽 포크가 사용 가능하면 집어든다

3. 왼쪽, 오른쪽 포크를 모두 들었다면 정해진 시간동안 식사

4. 식사 시간이 끝나면, 오른쪽 포크를 내려놓고

5. 왼쪽 포크도 내려 놓는다.

6. 1번부터 반복

• 이 때, 모든 철학자가 동시에 왼쪽 포크를 집어 든다면, 5명의 철학자는 절대로 식사를 할 수 없는 상태가 됨
• 이렇게, 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 것을 교착상태라고 함
• 철학자를 프로세스(or 스레드), 포크가 자원, 생각하는 과정이 자원을 기다리는 행위라고 보면 됨

자원 할당 그래프 (Resource - allocation graph)

• 교착 상태를 자원할당 그래프를 통해 단순하게 표현 가능
• 어떤 프로세스가 어떤 자원을 사용하고 있고, 프로세스가 어떤 자원을 기다리는 지 간단하게 표현

• 프로세스는 원으로, 자원의 종류는 사각형으로 표현

• 사용가능한 자원 개수는 자원 사각형 내 점으로 표현

• 자원을 사용하고 있으면 사용하고 있는 자원에서 프로세스로 화살표로 연결

• 프로세스가 자원을 기다리고 있으면 프로세스에서 자원으로 화살표 연결

교착 상태는...

• 자원 할당 그래프가 원의 모양을 하고 있을때 교착상태 라고 함

교착 상태 발생 조건

네 가지가 존재함

1. 상호 배제 (mutual exclusion)
2. 점유와 대기 (hold and wait)
3. 비선점 (nonpreemptive)
4. 원형 대기 (circular wait)

상호 배제 - Mutual exclusion

• Dead Lock의 근본적인 원인은 해당 자원을 하나의 프로세스만이 사용 가능하기 때문임
  • 포크를 여러명이 동시에 사용 가능했다면 교착은 발생하지 않음
• 이처럼 프로세스도 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 상호 배제라고 함

점유와 대기 - Hold And Wait

• 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다리는 상태

비선점 - Nonpreemptive

• 교착 상태가 발생하게된 또 하나의 근본적인 원인
• 비선점이기 때문에, 강제로 뺏지 못하고 기다리면서, 무기한의 기다림이 된 것

원형 대기 - Circular Wait

• 프로세스와 프로세스가 요청 받은 자원, 할당받은 자원이 원의 형태를 이루었기 때문
• 이처럼 프로세스들이 원의 형태로 대기하는 것을 원형 대기라고 함

<주의!>  원의 형태라고 해서 꼭 교착 상태라는 것은 아님!!!

 

교착 상태 해결 방법

교착 상태 예방

• 교착 상태, Dead Lock을 예방하기 위해서는 앞서 말했던 4가지 조건 중 하나를 충족하지 못하게 하는 방법과 같음

1. Mutual Exclusion 없애기

• 모든 자원을 공유 가능하게 만든다는 뜻
• 그러나 이론적으로 교착상태를 없앨 수 있으나, 현실에서 사용하기에는 어려움이 존재

2. Hold And Wait 없애기

• 점유와 대기를 없앤다면, 운영체제가 특정 프로세스에 자원을 모두 할당 하던지, 할당하지 않던지 해야 함
• 이론적으로는 완벽하게 해결이 가능하나, 자원의 활용률이 낮아질 위험이 있음

3. NonPreemptive 없애기

• 비선점 조건을 없애면 사용할 자원을 뺏을 수 있음
• 선점하여 사용할 수 있는 일부 자원에서는 효율적이지만, 프린터와 같은 하나의 프로세스만 이용가능한 경우는 범용성이 떨어짐

4. Circular Wait 없애기

• 모든 자원에 번호를 붙이고 오름차순으로 자원 할당
• 앞서 세 방식에 비하면 현실적이고 실용적
• 그러나, 시스템 내에 전부 번호를 붙이고 하는 일이.. 어렵고
• 자원의 활용률이 떨어질 위험이 있음

교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식
• 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도로만 자원을 배분

안전 상태 - Safe State

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

불안전 상태 - Unsafe State

• 교착 상태가 일어날 수도 있는 상황

안전 순서열 - Safe Sequence

• 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미
• 안전 상태의 경우는 안전 순서열 순서가 있는 상태
• 불안전 상태의 경우는 안전 순서열 순서가 없는 상태

예시

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2
P3	9	2

• 해당 표는 다음과 같이 설명할 수 있음
  • 할당 가능 자원 : 12
  • 할당한 자원 : 9
  • 남은 자원 : 3
• 해당 상태는 P2 - P1 - P3이라는 안전 순서열이 존재

1. P2에게 자원 2를 할당

프로세스	요구량	현재 사용량
P1	10	5
P2	4	2 + 2
P3	9	2

• 해당 표는 다음과 같이 설명할 수 있음
  • 할당 가능 자원 : 12
  • 할당한 자원 : 11
  • 남은 자원 : 1
• 이 때, 요구량을 충족하였으므로 P2에서 사용한 자원을 반납하면, 4개가 남은 자원에 추가
  • 할당 가능 자원 : 12
  • 할당한 자원 : 7
  • 남은 자원 : 5

프로세스	요구량	현재 사용량
P1	10	5 + 5
P2	4	2 + 2
P3	9	2

• 다음엔 이제 P1도 요구량을 충족할 수 있으므로... 사용 후 반납
• 이후에 P3에 남은 자원을 모두 갖다주면, 안정적인 상태로 작업이 종료됨

교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식
• 방식은 두가지가 존재한다

선점을 통한 회복

• 교착 상태가 해결될 때 까지 한 프로세스씩 자원을 몰아주는 방식
• 교착상태가 해결될 때 까지 다른 프로세스의 자원을 강제로 빼앗아 진행시킴

프로세스 강제 종료를 통한 회복

• 단순하면서 확실한 방식
• 교착 상태가 없어질 때 까지 한 프로세스씩 종료하거나, 전체를 종료하거나...
• 전체를 없애면...
  • 작업 내용이 사라질 위험이 있음
• 하나씩 없애면
  • 교착 상태 확인 여부를 판단하면서 오버헤드가 발생할 수 있음

<참고> 교착 상태를 아예 무시하는 방법도 있는데, 잠재적 문제를 무시로 대처하는
타조 알고리즘 (Ostrich Algorithm)이라고 한다.