Deadlock의 발생 조건과 해결법

데드락이 무엇인가?

두개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘다 영원히 끝나지 않는 상황을 가리킨다.

(A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set)

 

예를 들어서

semaphores A and B, initialized to 1

Process1	Deadlock	Process2
wait(A);  wait(B);		wait(B);  wait(A);

 

데드락은 어떨 때 일어나나?

아래 4가지 조건이 모두 만족하면 데드락이 발생할 가능성이 있다. 하나라도 만족하지 않으면 절대 발생하지 않는다.

• Mutual exclusion : 한 리소스는 한번에 한 프로세스만이 사용 할 수 있다.

• Hold and wait : 어떤 프로세스가 하나 이상의 리소스를 점유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다리고 있다.

• No preemption : 프로세스가 테스크를 마친 후 리소스를 자발적으로 반환한다. (강제로 빼앗지 않는다)

• Circular wait : Hold and wait관계의 프로세스들이 circle을 이룬다.

Resource-Allocation Graph

리소스의 할당 상태, 즉 프로세스의 Hold and wait상태를 직관적으로 확인하기 위한 그래프

 

위 그래프는 deadlock이 발생한 그래프이다.

반면에 위 그래프는 cycle이 존재하지만 deadlock이 발생하지 않는 그래프이다. 왜 그런지 생각 해보자.

일단 그래프 상에 싸이클이 없다면 데드락은 절대 발생하지 않는다. 그리고 싸이클이 존재하고 싸이클을 이루는 프로세스들이 리소스 인스턴스를 서도 모두 점유하거나 할당하고 있으면 데드락이 발생 할 가능성이 있다.

 

그렇다면 이런 데드락이 생기지 않도록 하려면 어떻게 해야될까?

데드락이 절대 발생하지 않도록 하거나, 발생한 뒤에 고치는 방법이 있다. 대표적으로 아래 세가지로 나눈다.

1. Prevention : 할당 구조 측면에서, 데드락이 발생할 수 있는 요구조건을 만족시키지 않게 함으로써 데드락을 방지한다.

2. Avoidance : 리소스 할당의 측면에서, Deadlock이 발생할 가능성이 있는 allocation(unsafe allocation)을 하지 않는다.

3. Detection and Recovery : 데드락이 발생 할 수 있도록 놔 두고 데드락이 발생 할 경우 찾아내어 고친다.

 

Prevention은 리소스가 어떻게 할당되건 간에 데드락이 절대 발생 할 수 없는 구조로 만들고, Avoidance는 데드락이 발생 가능한 구조이지만 알고리즘을 사용해서 '이렇게 할당하면 데드락이 생길 수도 있겠구나' 라는걸 확인하고 리소스를 할당 해 준다.

 

Deadlock Prevention

데드락을 발생시키는 조건이 4가지가 있다고 했다. 그 조건 중 하나라도 만족하지 않으면 데드락은 발생하지 않는다고도 했다. 이것이 Prevantion의 핵심이다. 그 조건을 깨는 것이다.

 

• Mutal Exclusion : 꼭 같이 써야 하는 리소스가 아니라면 공유되는 리소스를 hold하지 않는다.

• Hold and Wait : 프로세스가 어떤 리소스를 request 할때 다른 리소스를 hold하고 있지 않은 상태여야 한다. 또는 필요한 모든 request와 allocation이 완료된 다음 실행을 한다. 속도가 느리고 starvation발생 가능성이 있다. (프로그램 실행이 안될 수가 있음)

• No Preemption : 어떤 프로세스가 리소스를 점유하고 있는 상태에서 지금 당장 할당 될 수 없는 다른 리소스를 요청하는 경우 hold하고 있던 리소스를 release시켜 버린다. 필요한 리소스를 리스트에 추가 해두고 프로세스는 wait상태로 간다.
  리스트를 확인해서 필요한 리소스를 모두 얻을 수 있는 상태가 되면 프로세스를 다시 시작한다.

• Circular Wait : 모든 리소스 타입에 번호를 매겨서 순서대로 할당 되도록 한다. 리소스1, 리소스2 이렇게 해 두고, 높은 순서의 리소스를 할당 받았을 경우 더 이전 순서를 요청 할 수 없게 해버리면 Circle이 발생하지 않는다.

 

Deadlock Avoidance

시스템이 unsafe한 상태에 들어가지 않도록 하는 것이 핵심이다. 프로세스가 어떤 리소스를 요청 할때 해당 리소스를 즉시 할당 해 줄 수 있는 상태가 safe한 상태이다. 하지만 unsafe하다고 무조건 데드락이 발생 하는 것은 아니다.

 

리소스가 single instance일 경우엔 Resorce allocation graph를 이용한다. climate를 두어 필요한 resorce를 미리 파악하고 싸이클이 발생할 request를 block시킴으로써 데드락을 방지한다.

리소스가 Multiple instance일 경우엔 프로세스별로 몇개의 resorce를 사용하는지를 미리 declare하여 unsafe하게 될것인지 검사한다. = Banker's algorithm

 

뱅커스 알고리즘은 따로 정리한다. => 클릭

 

Deadlock Detection and Recovery

리소스가 single instance일 경우엔 wait-for 그래프를 주기적으로 확인하다. wait for 그래프는 어떤 프로세스가 어떤 리소스를 wait하고 있는가만 체크한다. 싸이클이 발생했으면 데드락이 발생 한 것이다.

리소스가 Multiple instance일 경우엔 Detection 알고리즘을 사용한다. 뱅커 알고리즘과 흡사하다.

 

이것도 따로 정리한다. => 클릭

 

그렇다면 Recovery는 어떻게 이루어 질까?

Rollback이라는 개념을 쓰는데, 최소한 싸이클이 없어질 만큼의 프로세스는 죽여야 한다.

1. 프로세스간의 상호작용도 있으므로 관련된 모든 프로세스를 죽이기도 한다 - 시스템에 따라 다름

2. 프로세스를 하나씩 죽여 가며 detection 알고리즘을 재호출 해서 검사한다 - 피해 최소화

3. 어떤 프로세스를 먼저 골라서 죽일 것인가?

   • 프로세스의 Priority

   • 얼마나 수행 되었고 얼마나 더 수행될 프로세스인가?

   • 리소스를 얼마나 사용하고 있는가? 얼마나 더 사용할 것인가?

   • 얼마나 많은 프로세스를 더 죽여야 하느냐?

   • 프로세스가 다른 프로세스와 상호작용 중인가?

starvation에 주의 한다. 근본적인 원인이 아닌 프로세스를 죽이고, 데드락이 다시 발생하고, 또 죽이는 악순환이 생긴다. aging기법을 사용 할 수 있다.