[OS Chapter 7] Deadlocks

데드락(= 교착상태)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

출처: https://blog.oureducation.in/deadlocks-2/

 

Resouce(자원)

• 하드웨어 소프트웨어등을 포함하는 개념
• I/O device, CPU cycle, memory space, semaphore

예제 1

두개의 디스크가 필요한데 각 프로세스가 서로다른 하나씩 가지고 기다리는 상태

예제 2

세마포어

출처: 강의

---

Deadlock발생의 4가지 조건

• Mutual exclusion(상호 배제) - 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption(비선점) - 자원을 강제로 빼앗기지 않음
• Hold and wait(보유 대기) - 내가 자원을 가진채로 다른 자원을 요청함
• Circular wait(순환 대기) - 자원을 기다리는 프로세스 간 사이클이 형성

 

Resource-Allocation Graph (자원할당 그래프)

• 프로세스와 자원간의 관계를 그래프로 표현
• cycle이 없으면 deadlock이 아니다.
• cycle이 있으면 자원당 인스턴스가 하나면 데드락이다.
• 만약 인스턴스가 여러개있으면 가능성을 체크해봐야한다.
• 왼쪽 그림은 2개의 인스턴스가 전부 싸이클이 걸리고 오른쪽 그림은 하나의 인스턴스가 남으므로 데드락이 안걸림

 

출처: 강의

---

Deadlock 처리방법 4가지

• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection and recovery
• Deadlock Igonorance

Ignorance방법을 제외한 3가지 방법은 예방하는 것이다.

 

Deadlock Prevention - 데드락의 4가지 조건을 차단

• Mutual exclusion - 배제할 수 없음
• Hold and wait
  • 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법1 프로세스 시작시 모든 필요한 자원을 할당받게 하는 방법
  • 방법2 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No preemption
  • 자원은 preemption 할 수 있게 하면 된다.
  • CPU나 Memory같은 state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용
• Circular wait
  • 자원에 할당 순서를 정하여 정해진 순서대로만 자원 할당

=> 전부 Utilization 저하, throughput 감소, starvation 문제가 발생함.

---

Deadlock Avoidance

자원 요청에 대한 부가정보를 이용해서 deadlock가능성이 확실히 없는 경우(= unsafe)만 할당

자원할당그래프나 뱅커스 그래프를 사용하여 피해갈 수 있음

 

Resource Allocation Graph Algorithm

자원당 인스턴스가 하나인 경우 쓰임

출처: 강의

• 점선 화살표가 추가됨. process가 적어도 한번은 해당 자원을 요청할 수 있다는 뜻이다.
• 현재 상황은 데드락이 아니지만 unsafe한 상태가 된다. 최악의 상황을 고려하기 때문이다.

 

Banker's Algorithm

자원당 인스턴스가 여러개일 경우 쓰임.(하나일 때도 가능)

출처: 강의

• 프로세스가 5개
• 자원이 3개이고 각 자원의 인스턴스 개수 10 / 5 / 7
• Allocation은 현재 할당 정보
• Max는 avoidance 특성상 미리 알고 있는 정보로 최대 요청량에 대한 정보
• Available 은 남아있는 자원의 수다.
• Need 는 Max - Allocation으로 추가 요청 가능양이다.

 

가용자원에서 줄 수 있어도 추가 요청 자원에서 가능한지 판단하고 줘야한다.

Availabvle자원이 Need의 개수보다 같거나 많아야 한다. 충족이 되어야 한다.

현재 가용자원으로 MAX 요청을 처리할 수 있느냐가 관건이다.

최대 요청을 해버리면 처리가 안되기 때문이다.

절대 데드락이 안생길거라는 가정하에 진행한다. 보수적이다.

 

위의 예제에서는 sequence가 존재하므로 시스템은 safe state

P1 -> P3 -> P4 -> P2 -> P0

 

주의! unsafe != deadlock unsafe상태일시 데드락의 가능성이 있다는 것이다. 

---

Deadlock Detection and recovery

Detection

출처: 강의

• 자원당 인스턴스가 1개일 경우는 자원할당 그래프 그대로 사용
• 사이클이 있으면 deadlock
• 오른쪽 그림처럼 자원을 빼버리고 process간의 관계로만 표현 가능

Q. 싸이클을 찾는 시간복잡도는 얼마나 되나??

A. O(n제곱)이다. n개의 정점이 있으면 n-1개의 edge가 나올 수 있기 때문이다.

 

 

자원당 인스턴스가 여러개 일경우

• 5 processes
• 3 resource types 7 / 2 / 6
• bank알고리즘처럼 최대 개수가 필요없음.
• 낙관적으로 바라봐야 한다.
• 아직 요청이 없는 항목들은 반납을 한다.
• 가용자원 처리 가능? -> 반납 가능한 자원들 보고 다시 파악 -> 처리하고 반납 후 과정 반복 

 

P0 -> P2 -> P3 -> P1 -> P4 순으로 작동하면 deadlcok이 없다.

 

Recovery

• Process termination
  • 데드락에 관련된 모든 프로세스를 죽이는 방법
  • 데드락이 없어질 때까지 프로세스를 하나씩 죽이는 방법
• Resource Preemoption
  • 자원을 뺏는 것이다.
  • 비용을 최소화할 victim의 선정
  • safe sate로 롤백하여 실행

---

Deadlock Ignorance

• 데드락을 무시하는 방법이다.
• 대부분의 범용 OS가 채택한다.
• 데드락을 찾고 조치하는 오버헤드가 너무 크기 때문이다.