데드락(DeadLock)

데드락이란?

운영체제 또는 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로스세 또는 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황으로, 멀티스레딩, 병렬 프로그래밍, 분산 컴퓨팅에서 흔히 발생하는 문제이다. 쉽게 말해 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태이다. 다른말로는 교착 상태라고도 한다.

• 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되는 것을 말한다. 다른말로는 교착 상태라고도 한다.

데드락의 조건

상호배제

• 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

점유상태로 대기

• 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

비선점 조건의 제거

• 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

순환대기

• 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

 

데드락의 해결방

현재의 대부분의 운영 체제들은 교착 상태를 막는 것은 불가능하다. 교착 상태가 발생하면 여러 운영 체제들은 제각기 다른 비표준 방식들로 이러한 교착 상태에 대응한다. 대부분의 접근들은 4가지 코프먼 조건(코프먼 교수가 제시한 조건)들 가운데 하나(특히 4번째 것)를 막음으로써 동작한다. 주요 접근 방식은 다음과 같다.

 

1. 교착 상태의 예방

• 상호배제 조건의 제거

교착 상태는 두 개 이상의 프로세스가 공유가능한 자원을 사용할 때 발생하는 것이므로 공유 불가능한, 즉 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있다.

• 점유와 대기 조건의 제거

한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다. 즉 간단하게 여러 자원을 동시에(atomically) 땡겨받게 만들거나 기다려야 하는 자원을 할당받으려면 다른 자원을 반환하도록 만들어서 문제를 해결하는 방법이다. 하지만 자원 과다 사용으로 인한 효율성, 프로세스가 요구하는 자원을 파악하는 데에 대한 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용, 기아 상, 무한대기 등의 문제점이 있다.

• 비선점 조건의 제거

비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.

• 환형 대기 조건의 제거(순환성 대기)
•  

자원 유형에 따라 순서를 매긴다. 이해를 돕기 위해 포크 철학자 문제를 예로 들겠다.

 

포크철학자문제

 

5명의 철학자와 5명의 스파게티가 존재한다.

 

포크는 한개씩있고, 스파게티를 먹으려면 두개의 포크가 있어야한다. 모두 오른쪽의 포크를 동시에 집어든다면?

 

1. 포크를 공유하지 못함. 상호배제

2. 왼쪽 철학자가 포크를 놓기를 기다림(점유상태로 대기)

3. 왼쪽 철학자의 포크를 뺏을 방법이 없음(선점불가)

4. 각 철학자들은 자신의 왼쪽 철학자의 포크를 대기한다( 순환대기)

점유대기 해결방법 : 왼쪽포크를 못집으면 오른쪽 포크를 내려놓는다.

순환대기 해소방법 : 포크의 우선순위를 메긴다. 

 

이 교착 상태의 해결 방법들은 자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

 

2. 회피

예방과 비슷하지만, 각 요청을 운영체제가 직접 분석함으로써 데드락이 발생할 가능성이 확인하는 방식이다. 회피 기법은 크게 3가지로 나눌 수 있다.

• 은행원 알고리즘
  • 데드락에 빠질 가능성을 운영체제가 판단한 후, 데드락에 빠질 가능성이 없다고 판단되면 자원을 할당해 주는 방식이다.
  • 예를들어 프로세스 A, B, C가 각각 15, 30, 40의 자원을 요청하며 운영체제는 현재 40의 자원을 보유하고 있다고 가정 시, 운영체제는 우선 A에게 15의 자원을 빌려준 후, 이후 A의 작업이 끝나 자원을 반환하면, B에게 30의 자원을 빌려주고, 이후 B가 자원을 반납하면 C에게 40의 자원을 빌려주는 형식이다.
  • 장점은 시스템이 항상 안전상태를 유지할 수 있다는 것이지만, 단점은 최대 자원의 요구량을 미리 알아야하며(하지만 프로그램은 정확하게 15의 자원을 요구하지 않는다.), 자원 이용도가 낮거나 유한한 시간내로 자원을 사용 후 반납하여야 하는 문제점으로 인해 현재 운영체제에 사용되지는 않는다. 단적으로 위의 예시만 봐도 A에게 15를 빌려주면 A가 자원을 사용하는 동안에는 25의 자원이 그냥 놀고 있는 것과 다름없게 된다.
  • 한가지 알고있어야 할 사항은 불완전 상태라고해서 반드시 교착상태가 발생하는 것은 아니라는 것이다. 불완전 상태가 지속되어도 교착이 발생하지 않을 가능성은 얼마든지 있다.
• Wait-Die 기법
  • 프로세스 A가 보유한 자원을 프로세스 B가 요청할 때 프로세스B가 프로세스A보다 적은 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기가 허용된다. 만약 그렇지 않다면 B는 롤백된다.
  • 즉 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 적은 타임스탬프를 보유하고 있어야 한다는 것을 의미한다.
• Wound-Wait 기법
  • 프로세스 A가 보유한 자원을 프로세스 B가 요청할 때 프로세스B가 프로세스A보다 큰 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기가 허용된다. 만약 그렇지 않다면 B는 롤백된다.
  • 즉 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 큰 타임스탬프를 보유하고 있어야 한다는 것을 의미한다.
  • 여기서 타임스탬프(Timestamp)는 쉽게 이해해서 '프로세스가 시작되고 종료 될 시간' 정도로 생각하면 된다. 둘 다 불필요한 롤백이 발생한다는 단점이 발생하기는 한다.

 

3. 탐지

데드락을 막는 것이 아닌 데드락이 필연적으로 발생할 것을 가정하고, 현재 시스템상에서 어느 부분에 데드락이 발생했는지를 탐색하는 방식이다. 그래프를 그림으로써 교착상태가 발생할 수 있는 가능성을 탐지하는 '자원할당 그래프 알고리즘'(Resource-Allocation Graph Algorithm)과 자원할당 그래프 알고리즘을 살짝 변형시킨 'Wait for Graph'가 있다. 쉽게 말해 교착 상태를 미리 탐지할 수 있는 수단이다.

 

4. 복구

데드락을 예방하는 방법도 감지하는 방법도 결국 실제로 데드락 자체를 해결할 수 있는 것은 아니다.

데드락 복구 방법은 크게 두 가지로 나눌 수 있다.

1. 프로세스 종료
   가장 단순무식하고 속편한 방법인 '교착 상태인 프로세스'를 골라 종료 시키는 방법이다. 물론 이 과정도 그나마 피해를 덜 입을 수 있는 희생자(Selection of a victim)를 최소한으로 골라 종료를 시켜야 한다는 점이 까다롭다. 만약 종료가 안된다면 교착 상태가 발생하기 전으로 Roll back 시키거나 기아 상태(Starvation)의 방지를 고려해 볼 수 있다.
2. 자원 회수
   프로세스에 할당된 각 자원들을 데드락 현상이 사라질 때까지 강제로 회수하는 방법이다. 주로 운영체제 수준에서만 가능하다.