[데이터베이스] 데드락 DeadLock(교착 상태) 이란?

데드락(DeadLock) 또는 교착상태는 멀티 프로세스와 멀티 스레드 둘 다 발생할 수 있습니다.

이번 글에서는 편의상 멀티 프로세스로 일괄해서 설명하겠습니다.

 

데드락(DeadLock)은 교착상태로도 언급되며,

이번 설명에서는 주로 데드락(DeadLock)이라는 용어를 사용하겠습니다.

 

데드락 DeadLock(교착상태) 이란?

무한 대기 상태

데드락(DeadLock) 또는 교착상태는 두 개 이상의 프로세스가 서로의 작업이 끝나기를 기다리는 '무한 대기 상태'입니다.

각 프로세스는 다른 프로세스가 보유하고 있는 자원을 기다리는 동시에 그 자원을 다른 프로세스에게 제공하기를 기다리는 상황에 발생합니다.

 

데드락 4가지 필요 조건

데드락은 다양한 형태의 자원에 대한 경쟁에서 발생할 수 있습니다.

자원은 주로 CPU 시간, 메모리, 파일, 장치 등을 포함합니다.

데드락은 다음 네가지 필요 조건이 동시에 성립할 때 발생합니다.

 

상호배제 (Mutual Exclusion)

자원은 한 번에 하나의 프로세스나 스레드만이 사용할 수 있어야 합니다.

다른 프로세스나 스레드가 사용 중인 자원에 대한 접근은 허용되지 않습니다.

점유대기 (Hold and Wait)

프로세스가 이미 어떤 자원을 보유한 상태에서 다른 자원을 요청하고, 해당 자원을 얻기 위해 대기하고 있는 상태입니다.

비선점 (No Preemption)

이미 보유한 자원을 강제로 빼앗을 수 없어야 합니다.

다른 프로세스나 스레드가 이미 사용 중인 자원을 강제로 해제할 수 없습니다.

순환대기 (Circular Wait)

프로세스 집합 {P0, P1, ..., Pn}에서 P0는 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하며, Pn은 P0이 점유한 자원을 대기해야 합니다.

이때, n은 1보다 크거나 같습니다.

 

데드락이 발생하면 각각의 프로세스는 원하는 자원을 얻지 못해 무한히 대기하며, 전체 시스템이 정체되게 됩니다.

데드락을 해결하거나 방지하기 위해서는 필요조건 중 하나 이상을 제거하거나, 데드락이 발생하면 이를 탐지하고 복구할 수 있는 방법을 사용해야 합니다.

대표적인 방법으로는 데드락의 조건 중 하나 이상을 깨트리는 방법, 탐지 및 회피 알고리즘 등이 있습니다.

 

데드락 해결방법

데드락을 해결하기 위해서는 다양한 방법이 사용됩니다.

주요 데드락 해결 방법은 다음과 같습니다.

 

예방 (Prevention)

데드락이 발생하지 않도록 필요 조건을 제거하는 방법입니다.

필요 조건 중 하나 이상을 방지함으로써 데드락이 발생하지 않는 것이 목표입니다.

상호 배제, 점유대기, 비선점, 순환대기 중 하나라도 만족되지 않으면 데드락을 예방할 수 있습니다.

회피 (Avoidance)

데드락이 발생할 가능성이 있는 경우, 시스템이 특정 자원을 할당할지 말지를 결정하는 동적인 방법입니다.

리소스 할당 그래프 등을 사용하여 데드락 발생 여부를 미리 예측하고, 데드락이 발생하지 않도록 할당을 조절합니다.

이는 보다 적극적인 관리를 통해 데드락을 회피하는 방법입니다.

검출 및 회복 (Detection and Recovery)

데드락이 발생하면 이를 검출하여 회복하는 방법입니다.

주기적으로 시스템 상태를 모니터링하고, 데드락이 발생했는지 여부를 감지합니다.

데드락이 감지되면, 회복을 위한 조치를 취하여 데드락을 해결합니다.

회복 방법으로는 데드락을 발생시킨 프로세스를 중지시키거나, 자원을 선점하여 회복하는 방법 등이 있습니다.

선점을 통한 회복

교착 상태가 해결될 때까지 다른 프로세스부터 자원을 강제로 빼앗아 한 프로세스씩 자원을 몰아주어 (선점) 해결하는 방법이 있습니다.

프로세스 강제 종료를 통한 회복

가장 단순하면서 확실한 방법으로는 교착 상태가 없어질 때까지 교착 상태에 놓인 모든 프로세스 전체 또는 하나씩 강제로 종료하는 방법입니다.

단, 전체를 종료할 경우엔 많은 작업 내역을 잃는다는 단점이 있습니다.

하나씩 종료할 경우엔 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드를 야기한다는 단점이 있습니다.

타조 알고리즘

교착 상태를 완전히 무시하는 방법으로 타조 알고리즘(orstrich algorithm)이 있습니다.

문제의 발생 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 이 방법이 적합할 때도 많습니다.