데드락(Deadlock, 교착 상태)

둘 이상의 프로세스가 서로 남이 가진 자원을 요구하면서 양쪽 모두 작업 수행을 할 수 없이 대기 상태로 놓이는 상태를

교착상태 Deadlock이라고 합니다.

식사하는 철학자 문제

교착상태를 설명하기 위한 문제 상황입니다. 철학자는 앞의 음식을 먹기 위해선 양쪽의 포크를 모두 사용해야 합니다.

순서

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

여기서, 모든 철학자가 동시에 왼쪽 포크를 집어들면 어떤 철학자도 식사를 할 수 없는 상황이 발생하게 됩니다.

모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다려야 합니다.

이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태라고 합니다.

 

자원 할당 그래프

어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프로 교착상태를 단순하게 표현할 수 있습니다.

 

그리는 규칙

출처 : https://wannabe-gosu.tistory.com/26

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현합니다.
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현합니다. 
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시합니다.
   • 프로세스가 자원 이용을 끝내고 운영체제에 자원을 반납하면 화살표는 삭제됩니다.
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.

 

식사하는 철학자 문제를 자원 할당 그래프로 표시

이미지 출처 : https://aerocode.net/388

 

교착 상태  발생 조건

아래 네가지 조건이 모두 만족할 때 교착 상태가 발생할 가능성이 생깁니다. 

• 상호 배제
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
• 점유와 대기
  • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점
  • 프로세스가 다른 프로세스의 자원을 강제로 빼앗지 못함
• 원형 대기
  • 프로세스들이 원의 형태로 자원을 대기
  • 단, 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아님

교착 상태 예방

교착 상태 발생 조건 중 하나의 조건이라도 만족시키지 않게 한다면 교착 상태는 발생하지 않습니다.

• 자원의 상호 배제 제거
  
  • 모든 자원을 공유 가능하게 만든다.
  • ⇒  현실적으로 적용하기엔 무리
• 점유와 대기 제거
  • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
  • ⇒ 자원의 활용률 감소
  • ⇒ 많은 자원을 필요로 하는 프로세스는 동시에 많은 자원을 사용할 타이밍을 확보하기가 어렵기 때문에 기아 현상을 야기할 우려가 있음
• 비선점 조건 제거
  • 선점 가능한 일부 자원에 대해서 효과적 ( ex. CPU)
  • 프린터 같은 한번에 하나의 프로세스만 이용 가능한 자원에서는 해당 방식 사용 어려움
• 원형 대기 조건 제거
  • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당
  • 수많은 자원에 번호를 붙이기가 간단한 작업이 아님, 붙은 번호에 따라 특정 자원의 활용률이 떨어질 수 있음 

교착 상태 회피

교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식입니다. 이 방법을 학습하기 전 알아야할 세가지 용어가 있습니다.

• 안전 상태 : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태                                      안전 순서열이 있는 상태
• 불안전 상태 : 교착 상태가 발생할 수도 있는 상황                                                                                                                                  안전 순서열이 없는 상태
• 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

---

안전 상태

 

할당 가능한 자원 : 12

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

 

1. 남아 있는 자원 3개 중 2개를 P2에 할당

2. P2의 자원 사용이 끝나면 4개의 자원이 반환 → 남아있는 자원 5개

3. P1에 남아있는 자원 5개를 할당 P1 최대 요구량 충족

4. P1의 사용이 끝난 자원 10개 반환 → 남아있는 자원 10개

5. P3에 7개의 자원 할당

 

불안전 상태

 

할당 가능한 자원 : 12

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

 

1. 남아 있는 자원 2개 모두를 P2에 할당

2. P2의 자원 사용이 끝나면 4개의 자원이 반환 → 남아있는 자원 4개

3. P1, P3의 최대 요구량에 맞는 자원 할당 불가 → 불안전 상태로 교착 상태 발생

 

---

따라서, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이라고 보면 된다.

 

교착 상태 검출 후 회복 

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

 

• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 다른 프로세스로부터 자원을 강제로 뺴앗고 할당
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스를 모두 강제 종료→ 많은 프로세스들의 작업내용을 잃을 수 있음
  • 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료→ 작업내용 소실을 줄일 수 있지만, 교착 상태 제거 여부 확인 과정에서 오버헤드를 야기

교착 상태를 무시

드물게 발생하는 잠재적 문제를 무시로 대처하는 방식으로 타조 알고리즘 방식이 있다.