07. Deadlock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
자원은 하드웨어와 소프트웨어를 포함하는 개념이다.

 

프로세스가 자원을 사용하는 절차는 네 단계가 있다.
request -> allocate -> use -> release

Deadlock의 발생 조건

아래 조건을 모두 만족해야 Deadlock이 발생한다.

1. Mutual exclusion - 매 순간 하나의 프로세스만 자원을 사용할 수 있다.
2. No preemption - 프로세스는 자원을 빼앗길 수가 없다. 오로지 스스로 내놓아야만 한다.
3. Hold and wait - 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
4. Circular wait - 자원을 기다리는 프로세스 간에 사이클이 형성된다.

Deadlock이 발생했는지 알아보는 방법

Resource-Allocation Graph 자원할당그래프

프로세스 P와 자원 R
R에서 P를 향한 화살표 = 프로세스 P에서 자원 R을 사용 중
P에서 R을 향한 화살표 = 프로세스 P가 자원 R 사용을 요청하는 중

위 그래프에서는 요청만 하고 얻지를 못한 상태이다 (allocate X)
그래프에 cycle이 있으면 deadlock이다.
-> 자원에 인스턴스(위 그림에서 까만 점에 해당)가 하나라면 deadlock이 확실하다.
-> 자원에 인스턴스가 여러 개 있다면 deadlock의 가능성이 있다.
cycle이 없으면 deadlock이 아니다.

Deadlock 처리 방법

1, 2는 Deadlock을 미연에 방지하는 방법이고
3, 4는 Deadlock 발생하도록 그냥 두는 방법들이다.

1. Deadlock Prevention - 자원 할당 시 Deadlock의 발생 조건 중 어느 하나가 만족되지 않도록 하는 방법
2. Deadlock Avoidance - 자원 요청의 부가적인 정보를 활용해 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
3. Deadlock Detection and recovery - Deadlock에 대한 detection 루틴을 둬서 발견 시 recover 작업
4. Deadlock Ignorance - Deadlock을 시스템이 책임지지 않음, 대부분의 OS가 채택한 방식

Deadlock Prevention

각 조건이 만족되지 않도록 하려면

1. Mutual exclusion - 공유해서는 안 되는 자원의 경우 반드시 성립해야 한다.
2. Hold and wait - 프로세스가 자원을 요청할 때 다른 자원을 가지고 있지 않아야 한다.
   방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
   방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
3. No preemption - process가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 선점됨
4. Circular wait - 자원에 할당 순서를 정해서 정해진 순서대로만 할당한다

Deadlock의 발생을 막을 수는 있지만 자원의 이용률과 성능이 낮아지고 starvation의 발생 가능성이 있기에 비효율적이다.

Deadlock Avoidance

프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언한다.
safe state와 unsafe state
safe state = deadlock으로부터 안전한 상태
unsafe state = deadlock으로부터 안전하지 않은 상태

 

Resource Allocation Graph Algorithm - 자원 당 인스턴스가 하나만 있는 경우

claim edge (점선) = 프로세스 P가 자원 R을 미래에 요청할 수 있다
request edge (실선) = 프로세스가 해당 자원을 요청한다

assignment edge = 자원이 할당된 상태
release 후에는 다시 점선으로 바뀐다.

request edge에서 assignment edge로 변경될 때 점선을 포함하여 cycle이 생기지 않는 경우에만 자원을 할당한다. 최악의 상황을 가정하는 방식이다.
위 그림의 마지막 부분에서 점선을 포함해 cycle이 형성되고 있기 때문에 unsafe state에 해당되는데 이 때 P1이 R2를 요청하게 되면 deadlock이 발생하기 때문에 이 요청은 실행되지 않는다. 

n개의 프로세스가 있을 때 cycle 생성 여부를 조사할 경우 O(n^2)의 시간복잡도를 가진다.

 

Banker's Algorithm 은행원 알고리즘 - 자원 당 인스턴스가 여러 개 존재하는 경우

Allocation은 프로세스별 현재 자원 할당 상태
Max는 초기에 파악한 각 자원별 최대 사용량
Available은 가용 자원
Need는 프로세스마다 추가적으로 요청할 수 있는 자원의 양

 

P1이 (1, 0, 2), 즉 A자원 1개와 C자원 2개를 요청했다고 가정
요청한 것이 가용 자원(3, 3, 2)보다 적기 때문에 줄 수 있는 상태이다.
여기서 하나를 더 확인하는데 가용 자원만으로 Need가 다 처리되는지의 여부이다. (Need <= Available)
P1의 경우 Need가 (1, 2, 2)이고 가용 자원이 (3, 3, 2)인데 (1, 2, 2) <= (3, 3, 2)이므로 조건을 만족한다.

 

만약 P0이 (0, 2, 0)을 요청한다면?
-> Need: (7, 4, 3) Available (3, 3, 2)
-> 가용 자원에서 요청한 자원인 B 2개를 줄 수는 있지만 Need가 가용 자원보다 더 크기 떄문에 자원을 주지 않고 기다리도록 한다. 혹시라도 그 프로세스가 자원을 맥시멈으로 요청하면 가용 자원만으로는 처리가 불가능하기 때문이다.

이 알고리즘은 자원이 남아있더라도 항상 최악의 상황을 가정하여 가용 자원으로 처리가 불가능하다면 주지 않기 때문에 낭비가 심한 편이다.

Deadlock Detection and recovery

• 자원 당 인스턴스가 하나인 경우
  • 자원 할당 그래프에서 cycle로 deadlock 여부 판단
• 자원 당 인스턴스가 여러 개인 경우
  • Banker's Algorithm과 유사한 방법 활용 (단, 가용 자원에서 줄 수 있으면 그냥 준다)

wait-for graph 알고리즘 (single instance)

자원 할당 그래프의 변형 방식
프로세스 만으로 노드를 구성한다.
Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
이 알고리즘에서는 그래프에 cycle이 존재하는지를 주기적으로 조사하는데 이 때 시간복잡도는 O(n^2)이다.
n개의 노드에서 나머지 노드들로 화살표가 전부 뻗어나가는 것이 최악의 경우 = n(n - 1)

 

Recovery

1. Process termination - 프로세스를 종료하는 방식
   • Deadlock에 연루된 프로세스를 전부 강제종료한다.
   • Deadlock cycle이 사라질 때까지 프로세스를 하나씩 강제종료한다.
2. Resource Preemption - 프로세스가 돌아가도록 다른 프로세스에서 자원을 선점해오는 방식
   • 비용을 최소화할 희생양 선정
   • safe state로 롤백해서 process를 재시작
   • starvation 발생 가능
     • 같은 프로세스가 계속 victim으로 선정되면 그 프로세스는 자원을 할당받지 못한 상태로 있게 된다.
     • 프로세스별 롤백 횟수를 고려해 한 프로세스가 계속해서 victim으로 선정되지 않도록 해야 한다. 

Deadlock Ignorance

Deadlock이 발생하지 않는다고 생각하고 조치를 취하지 않는 방식
실제로 Deadlock은 아주 드물게 발생하기 때문에 다른 조치를 취하는 것이 오히려 overhead를 키우는 일이 될 수 있다.
만약 시스템에 Deadlock이 발생했다면 사용자가 직접 종료시키도록 한다. (어쩌다 한 번씩 보게 되는 '응답없음'이 그 예시)
현재 대부분의 운영체제에서 채택한 방식이다.