Deadlock

Deadlock

Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 무한정 대기하는 상태

프로세스 A가 a라는 자원을 가지고 있고 b라는 자원이 필요한 상황이라 가정해보자. 이 때 프로세스 B가 b라는 자원을 현재 가지고 있고 B도 a자원으로 요청하게 된다면 두 프로세스 중 누군가가 자원을 반환하지 않는 이상 두 프로세스는 모두 무한정 대기하게 된다.

일반적으로 프로세스가 자원을 사용하기 위해서는 요청, 획득, 사용, 반납 절차를 거치게 되는데 Deadlock은 모든 프로세스가 요청 상태에서 멈춰버리는 상황을 의미한다.

Deadlock의 조건

데드락이 발생하기 위해서는 4가지 조건을 만족해야만 한다.

• 1. Mutual Exclusion : 매순간 하나의 프로세스만이 독점적으로 자원을 사용할 수 있어야 한다.
• 2. No Preemption : 프로세스가 가진 자원을 빼앗기지 않으면서 추가 자원을 요청해야 한다.
• 3. Hold and Wait - 가진 자원을 프로세스가 반납하지 않으면서 추가 자원을 요청해야 한다.
• 4. Circular Wait - 자원을 기다리는 프로세스 간의 Cycle이 형성되어야 한다.

Resource-Allocation Graph

프로세스와 자원간의 상태를 그래프로 도식화해볼 수 있는데 이를 Resource-Allocation Graph(자원 할당 그래프)라고 한다.

각 부분은 다음과 같다.

• 동그라미 : 프로세스
• 사각형 : 자원
• 자원에서 프로세스로 가는 화살표 : 자원이 해당 프로세스에 할당됨을 의미
• 프로세스에서 자원으로 가는 화살표 : 프로세스가 해당 자원을 요청함을 의미
• 사각형 내부 점 : 자원의 개수 (인스턴스 수)

일반적으로 자원 할당 그래프에서 Cycle이 있다면 데드락을 의심해 볼 수 있다. 이 경우 자원당 인스턴스가 하나밖에 없다면 데드락에 해당하고 자원에 인스턴스가 여러개 있는 경우에는 데드락일 수도 있고 아닐수도 있다.

Deadlock 처리 방법

Deadlock을 처리하는 방법은 대표적으로 4가지가 존재한다.

• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection and Recovery
• Deadlock Ignorance

지금부터 각 방법에 대해 알아보자

Deadlock Prevention

데드락이 발생하는 4가지 조건 중에 하나를 원천적으로 차단해서 데드락 상태가 발생하지 못하도록 하는 방식이다.

1. Mutual Exclusion
   Mutual Exclusion은 critical section 문제 해결을 위해 반드시 필요한 조건으로 이 조건은 항상 만족되는 막을 수 없는 조건이다.

2. Hold and Wait
   프로세스가 시작할 때 필요한 모든 자원을 할당받아 시작되게 하는 방법이다. 일반적으로 프로세스는 작업을 진행하다 필요한 시점에 자원을 요청하게 되는데 처음부터 데이터를 모두 가지고 있다보니 비효율적인 방식이다. 이를 개선하기 위해 자원이 필요한 경우 보유 자원을 모두 뱉어내고 다시 요청하는 방식을 사용하기도 한다.

3. No Preemption
   프로세스가 가지고 있는 자원을 preemption할 수 있게 해주는 방법이다. 모든 필요한 자원을 얻을 수 있을 때 해당 프로세스를 다시 시작되게 한다.

4. Circula Wait
   자원마다 순서를 정해서 정해진 순서에 따라 자원을 할당할수 있게 한다.

이 방식은 Deadlock을 방지할 수는 있지만 생기지도 않을 데드락을 고려하기 때문에 자원에 대한 이용률과 시스템의 성능이 감소될 수 있다.

Deadlock Avoidance

Deadlock prevention 처럼 사전에 미리 Deadlock 발생을 방지하는 방식이다. Deadlock Avoidance는 자원 요청에 대한 부가적인 정보를 이용해서 데드락이 발생할 가능성이 있는지 확인하고 가능성이 아예 없는 경우에만 자원을 할당하는 방식이다.

Deadlock Avoidance가 Deadlock 발생 가능성을 체크하기 위해 사용하는 정보로는 자원 할당 그래프와 banker's 알고리즘이 있다.

자원 할당 알고리즘

기존 자원 할당 알고리즘과 유사하지만 점선이라는 하나의 개념이 추가된다. 점선은 항상 프로세스에서 자원으로 그려지는데 이는 언젠가 해당 프로세스가 그 자원을 요청할 것이라는 것을 의미한다. 이 점선은 후에 프로세스가 자원을 요청할 때 요청에 해당하는 화살표로 변경되고 이는 다시 자원이 프로세스에 할당됨을 나타내는 화살표로 변경 될 수 있다. 이때 데드락이 발생하는 지를 cycle을 통해 확인하며 주로 자원의 인스턴스가 하나일 경우 사용한다.

Banker's 알고리즘

Banker's 알고리즘은 주로 자원의 인스턴스가 여러개일 경우 사용한다.
Banker's 알고리즘은 프로세스 별로 자원의 현재 사용량, 최대 자원 사용량, 남은 추가 요청량과 현재 가용자원을 테이블 형태로 만들고 비교하게 된다.

남은 추가 요청량이 현재 가용자원으로 해결이 되는 프로세스를 찾아 자원을 제공한다. 이후 그 프로세스가 수행되어 자원을 반납하면 그만큼 가용자원이 늘어나고 이를 통해 다시 해결 가능한 프로세스를 찾아 자원을 제공하는 방식을 반복하게 된다.

이런 과정을 반복해서 모든 프로세스를 완료할 수 있는 시퀀스를 safe sequence라고 하며 safe sequence를 가지는 상태를 safe 상태라고 한다.

Deadlock Avoidance는 이런 safe 상태를 항상 유지하게 된다. 단. unsafe이면 데드락이 발생할 수 있는 상황인거지 항상 데드락인 것은 아니라는 점을 주의하자.

Deadlock Detection and Recovery

Deadlock Detection and Recovery는 기존 2방식과 다르게 사전에 Deadlock을 방지하지는 않는다. Deadlock이 발생하면 감지해서 Recovery하는 방식이다.

먼저 Deadlock이 발생했는지를 감지하기 위해 Deadlock Avoidance에서처럼 자원할당 그래프나 알고리즘을 사용하게 된다. 이 과정을 통해 Deadlock이 감지가 되면 Recovery를 하게 된다.

데드락 Recovery는 일반적으로 연루된 모든 프로세스를 죽이거나 연루된 프로세스 중 하나를 죽여 데드락이 해결되는지를 확인하고 해결되지 않았다면 다른 연루된 프로세스를 죽여 해결되는지 체크하는 과정을 반복하게 된다.

추가로 희생자를 하나 정해 자원을 뺏어 데드락을 없애는 방식을 사용할 수도 있는데 자원을 뺏긴 프로세스가 다시 그 자원을 요청해서 동일한 패턴이 발생할 수 있기 때문에 희생자를 정하는 패턴을 변경해가면서 정해야 한다. 이를 통해 같은 희생자에게서만 자원을 뺏어 starvation이 발생하는 것도 방지할 수 있다.

Deadlock Ignorance

Deadlock Ignorance는 데드락 발생에 대한 방지를 따로 하지 않고 처리또한 따로 하지 않는 방식이다. Deadlock에 대한 감지나 처리도 시스템 입장에서 오버헤드가 많이 발생하게 된다. 또한 Deadlock은 빈번하게 발생하지 않는다. 이를 처리하기 위해 추가적인 기법을 도입하는 것이 오히려 비효율적이 될 수 있기 때문에 Deadlock에 대한 어떠한 처리도 진행하지 않고 Deadlock에 대한 처리를 사용자가 알아서 하게끔 하는 방식이다. 이 방식은 대부분의 현대의 운영체제들이 사용하는 방식이다.