데드락(Deadlock)에 대하여

1. 개요

데드락은 교착상태라는 뜻으로, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는

자원을 사용하기 위해 서로 대기하면서 빠지는 무한 대기 상태를 말한다.

---

2. 발생 조건

아래 4가지 조건을 모두 만족해야 데드락이 발생한다.

1) 상호 배제

서로의 경쟁자를 없앤다는 뜻으로, 자원을 점유하는 프로세스는 한 번에 하나만 존재해야 한다.

즉, 둘 이상의 프로세스가 하나의 자원을 동시에 점유할 수 없어야 한다.

 

사용 중인 자원을 다른 프로세스가 사용하려면 자원이 해제될 때 까지 기다려야 한다.

2) 점유 대기

하나 이상의 자원을 점유하고, 다른 프로세스가 사용 중인 자원을 점유하기 위해

대기하고 있는 프로세스가 존재해야 한다.

3) 비선점

자원을 선점할 수 없어야 한다.

즉, 다른 프로세스에게 할당된 자원을 강제로 뺏을 수 없어야 한다.

4) 순환 대기

P는 프로세스를, R은 자원을 나타낸다.

자원을 대기중인 프로세스들이 서로 순환 형태를 이뤄야 한다.

---

3. 해결방법

1) 예방

데드락 발생 조건 4가지 중 최소 1가지를 제거하여(부정하여) 해결하는 방법이다.

단, 예방 방법은 자원 사용 효율성을 떨어트리는 단점이 있다.

• 상호 배제 부정
  • 한 번에 둘 이상의 프로세스가 자원을 사용할 수 있게 만든다.
  • 단, 동기화 문제(synchronous issue)가 발생할 수 있다.
• 점유 대기 부정
  • 프로세스가 필요로 하는 자원이 모두 확보될 때 까지 점유하지 않게 만든다.
  • 요구하는 모든 자원을 한 번에 할당해서 나중에 자원을 대기하는 상황을 없앤다.
• 비선점 부정
  • 자원을 선점할 수 있게 만든다.
  • 높은 우선순위의 프로세스가 다른 프로세스가 사용중인 자원을 선점할 수 있도록 한다.
• 순환 대기 부정 
  • 자원을 선형으로 배치하고 고유번호를 부여한다.
  • 프로세스가 한 쪽 방향으로만 자원을 요구할 수 있도록 만든다.

2) 회피

데드락을 발생시키지 않으면서, 프로세스가 요구하는 자원을 모두 할당해줄 수 있는 순서를 찾는 방법이다.

또한 그런 순서가 존재하도록 시스템이 자원을 할당하게 만드는 것을 의미한다.

 

즉, 데드락을 회피할 수 있는 안전한 상태(안전 상태)를 만드는 방법이다.

안전 상태(Safe State)와 안전 순서(Safe Sequence)
데드락을 발생시키지 않으면서 프로세스의 자원 요구를 모두 만족시키는 방법이 있다면 안전 상태에 있다고 말한다.
데드락을 발생시키지 않고 프로세스에 자원을 할당하는 순서를 안전 순서라고 한다.

대표적으로 은행원 알고리즘이 있다.

은행원 알고리즘
다익스트라가 제안한 기법으로, 자원 할당을 결정하기 전에 모든 자원의 최대 가능한 할당량을 가지고
시뮬레이션을 하여 안전 상태에 들 수 있는지 여부를 판단하는 알고리즘이다.

단, 은행원 알고리즘은 자원의 최대 할당량, 프로세스의 자원 요구량을 알아야하고
최소 하나의 프로세스에게 할당할 만큼의 일정한 자원 수를 유지하는 등 제약조건이 있어 현실적으로 사용하기 어렵다.

3) 탐지 및 회복

예방 및 회피 방법과는 다르게 데드락의 발생 가능성을 열어두고,

데드락 발생 여부를 탐지하여 회복하는 방법이다.

 

매번 데드락 발생 여부를 탐지해야 하기 때문에 오버헤드가 발생한다.

• 탐지 기법
  • 은행원 알고리즘 처럼 시스템의 자원 할당 상태를 가지고 데드락 발생 여부를 판단한다.
  • 자원 할당 그래프를 사용한 방법 등이 있다.

자원 할당 그래프는 프로세스의 요구 자원 및 점유 자원을 방향성 있는 그래프로 나타낸 것이다.

• 회복 기법
  • 프로세스를 중단하는 방법
    • 데드락에 빠진 모든 프로세스를 중단한다. (진행중이던 연산 결과가 폐기될 수 있음)
    • 데드락이 해결될 때까지 프로세스를 하나씩 중단한다. (매번 탐지 알고리즘을 수행해야 함)
  • 자원을 선점하는 방법
    • 데드락이 해결될 때까지 할당된 자원을 선점하여 다른 프로세스에게 할당한다.

---

참고 문서

데드락이란?

데드락의 정의, 발생조건, 해결방법