Deadlock

• 두 개 이상의 작업이 서로 상대방의 작업을 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태.

deadlock의 조건

1. mutual exclusion : 한 자원은 하나의 프로세스만 접근할 수 있다.
2. hold and wait : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 가리킨다.
3. No preemption : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. Circular wait : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

사실, 이 조건 중에 한 가지라도 만족하지 않으면 deadlock이 발생하지 않는다. 그리고 이 4가지 조건은 서로 완전히 독립적인 것은 아니다.

deadlock의 관리

현재의 대부분의 OS는 deadlock을 막는 것은 불가능하다. 그렇기에 deadlock이 발생하면 여러 OS들은 제각기 다른 비 표준 방식으로 deadlock에 대응한다.

1. Deadlock prevention

deadlock의 예방 방법은 deadlock이 되지 않도록 하는 방법이다.

• Mutual exclusion 부정 모든 자원을 공유 가능하도록 하면 된다. 현실적으로 불가능..
  
• Hold and Wait 부정 프로세스 대기를 없애기 위해 프로세스가 실행되기 전에 필요한 모든 자원을 할당함.(자원 낭비 발생) 자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 함(orphan statement 발생)
  
• No Preemption 부정 모든 자원에 대한 Preemption을 허용 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 반납하고 새 자원과 이전 자원을 얻기 위해 대기함.(자원 낭비 발생)
  
• Circular Wait 부정 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 함.(자원 낭비 발생)
  

deadlock을 예방하는 방법은 많은 자원의 낭비와 문제를 발생시키기 때문에 효율적인 방법은 아니라고 할 수 있다.

2. Deadlock Avoidance

Deadlock이 발생하기 전에 deadlock을 예상하여 safe state에서만 자원 요청을 허용하는 방법이다. 자원을 신중하게 할당하면 deadlock을 회피할 수 있다.

이를 위해서는 다음과 같은 가정이 필요하다.

• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

→ 현실성이 부족하다. 또한, 자원 요청이 있을 때마다 알고리즘을 사용한다는 것은 상당한 overhead임.

unsafe state라서 반드시 deadlock이 발생하지는 않는다.

Deadlock Avoidance를 위한 Algorithm

• 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
  1. 자원 할당 그래프에 예약 간선을 추가함
  • 예약 간선(claim edge) : 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선
  2. 프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시
  3. 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고, cycle이 형성되지 않을 때에만 자원을 할당 받는다.
• example

  1번 그래프에서 프로세스 P2가 자원 R2를 요청하여 자원을 할당 받는다면

  다음과 같이 cycle이 발생하므로 자원 요청을 승인 할 수 없다. 

 반대로 프로세스 P1이 자원 R2를 요청하여 자원을 할당 받는다면 

 cycle이 발생하지 않아 자원을 요청하여 할당 받을 수 있음.

• 은행원 알고리즘(banker’s Algorithm) 각 자원 유형마다 다수의 instance를 갖는 경우 은행원 알고리즘으로 deadlock을 피할 수 있다.
  1. 프로세스 시작 시 자신이 필요한 각 자원의 max 개수를 미리 선언한다.
  2. 각 프로세스에서 자원 요청이 있을 때 요청을 승인하면 시스템이 safe state로 유지되는 경우에만 자원을 할당한다.
  3. unsafe state가 예상되면 다른 프로세스가 끝날 때까지 대기한다.

3. Deadlock Detection

탐지 알고리즘을 사용하여 deadlock이 발생했는지 탐지한다. deadlock이 탐지 되었다면 복구 기법을 통해 deadlock을 복구한다.

이 방식은 지속적으로 확인하는 작업이 필요하기 때문에 성능 저하가 발생한다.

• 탐지 알고리즘

1. 대기 그래프(wait-for graph)

   각 자원 유형마다 instance가 하나 있는 경우 자원 할당 그래프를 변형한 대기 그래프를 사용하여 deadlock을 탐지한다.

   

   대기 그래프에서 Pi→Pj는 프로세스 Pi가 Pj프로세스가 보유하고 있는 자원을 기다리고 있음을 나타낸다.

   대기 그래프에 cycle이 있다면 deadlock을 의미한다.

   주기적으로 대기 그래프에 주기가 있는지 탐지 알고리즘을 호출하여 deadlock을 탐지한다.

2. 은행원 알고리즘(Banker’s Algorithm)

   각 자원 유형마다 instance가 여러 개 있는 경우 은행원 알고리즘을 사용하여 deadlock을 탐지한다. deadlock avoidance에서 사용하는 알고리즘과는 차이가 있다.

   • 각 프로세스의 자원 요청 개수를 사용한다.

   • 현재 상태가 safe state인지 확인한다.

   • unsafe state라면 deadlock이라고 판단한다.

첫 번째로 3만원 더 필요한 첫번째 고객에게 3만원을 빌려주고 첫번째 고객이 일을 해결하고 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주는 방법이 있다.

아니면 두 번째 고객에게 남은 4만원을 빌려주고 두번째 고객이 일을 해결하고 갚을 때까지 기다리는 방법이 있다. 하지만 세번째 고객에게는 통하지 않는다. 은행은 4만원이 남아있는데, 세번째 고객은 5만원이 더 필요하기 때문이다. 돈을 빌려줄 수 있고, 다시 돈을 돌려 받을 수 있는 상태를 safe state라고 한다.

1. 고객1 - 고객2 - 고객3
2. 고객2 - 고객1 - 고객3
3. 고객2 - 고객3 - 고객1

이런 순서대로 모든 고객에게 돈을 빌려줄 수 있고 이를 safe state가 존재한다고 한다.

근데, 만약에 60원이 필요한 고객3이 너무 급하다고 25원 말고 45원을 달라고 했다고 하자. 그럼 은행에 남는 돈은 5원 밖에 없다. 이 상황에서는 세 고객 중 아무도 해결해 줄 수 없다. 이 상태를 unsafe state, deadlock이라고 한다.

• 탐지 알고리즘 호출 주기 오버헤드가 있기 때문에 얼마나 자주 deadlock이 발생하는지 얼마나 많은 프로세스가 deadlock에 연루되어 있는지에 따라 호출 빈도를 조절해야 한다.
  • 자원을 요청했는데도 즉시 할당되지 못하는 시점에 호출
  • 주기적으로 일정 시간마다 호출
  • cpu 이용률이 특정 값 이하로 떨어지는 시점에서 호출

4. Deadlock recovery

deadlock에 있는 프로세스를 종료하는 방식이다. 종료에는 2가지 방식이있다.

1. deadlock의 프로세스를 모두 중지
2. deadlock이 제거 될 때까지 한 프로세스씩 중지