데드락(Deadlock)

이 글에서는 컴퓨터에서 발생하는 데드락(deadlock)에 대해서 알아본다. 여기저기서 글을 읽고 나름대로 정리한 것이므로 개념이 100% 정확하다고 할 수는 없겠지만 이해에는 도움이 될 것이다...

데드락

데드락은 교착 상태라고 부르기도 한다. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있어, 결과적으로 아무것도 완료되지 못하는 상태를 말한다. 그렇다면 데드락은 왜 생겨나게 되었을까? 특히 멀티스레드 환경에서 자주 발생하는 문제이기 때문에 이를 중심으로 설명하겠다.

(단, 아래 사진에서 볼 수 있듯이 멀티스레드 외에도 조건을 만족하는 비슷한 상황에서 발생할 수 있는 문제이다.)

https://en.wikipedia.org/wiki/Deadlock

배경

먼저 Multi-Programming(프로그램을 여러 개 돌리는 것, 다중 프로그래밍이라고 번역할 순 있지만 의미가 다른 듯...)배경에 대해서 알아보자. 컴퓨터의 연산속도가 빨라지면서 우리는 한 번에 하나의 프로그램만 돌리기엔 너무 컴퓨터의 자원을 낭비하는 것이라고 생각했다. 따라서 기억 장치(메모리)에 작업을 여러 개 적재시켜 그 중 하나를 택해서 실행하는 방법으로 CPU 사용률을 높이게 되었다. 이때 하나를 택하는 방법을 CPU 스케줄링(Scheduling)이라고 하며, 작업이 전환되는 것을 문맥 교환(Context Switching)이라고 한다. 

 

하지만 여러 개의 프로세스를 만들기엔 서로의 메모리가 별도로 관리되므로, 생성 및 제거가 무거운 작업에 속하는데다 프로세스 간 데이터 교환도 어려웠다. 따라서 프로세스 보다 더 작은 실행 단위인 스레드를 만들었다. 스레드는 하나의 프로세스 내에서 여러 개가 만들어져 작동할 수 있으며, 프로세스의 메모리를 공유한다. 따라서 데이터 교환이나 생성, 제거, 문맥 교환등의 부하가 적다. 하지만 여러 실행 흐름에서 데이터를 변경하고 공유하다보니 자원 선점과 동기화 문제가 생기게 되었다.

 

이에 스레드 간 동기화를 위해 공유 자원을 건드리는 임계 구역(Critical Section)에 대해서, 오직 작업중인 한 스레드만 접근이 가능하게 하는 상호 배제(Mutual exclusion)가 필요해졌다. 세마포어(Semaphore)와 뮤텍스(Mutex)가 이를 위한 해법이다.

이때 발생할 수 있는 문제가 앞서 말한 "두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있어, 결과적으로 아무것도 완료되지 못하는 상태", 바로 데드락이다. 

 

발생 조건

1. 상호 배제(Mutual exclusion): 필요로 하는 자원을 점유하는 데에 배타적이다. 즉 하나의 자원을 동시에 여럿이 쓸 수 없다는 것이다.
2. 점유 대기(Hold and Wait): 자원을 점유한 상태에서 다른 자원을 기다린다.
3. 비선점(No preemption): 점유된 자원을 뺏어오지 않는다.(선점하지 않는다.)
4. 순환 대기(Circular wait): 자원 점유 및 대기가 순환적으로 이뤄져 있다.

예를 들자면 스레드 A가 자원 a를 점유하고 있는 상태에서 자원 b를 원하며, 스레드 B가 자원 b를 점유하고 있는 상태에서 자원 a를 원하는 것이다. "식사하는 철학자 문제"도 이를 쉽게 설명해준다.

식사하는 철학자들 문제 - 위키백과, 우리 모두의 백과사전

 

해결

그러면 데드락이 발생했을 때 이를 해결할 수 있는 방법이 있을까? 이렇게 하려면 우선 데드락이 발생했는 지 검사할 수 있어야하고, 데드락일 경우 빠져나올 수 있어야 한다. 그래프 알고리즘을 활용하면 가능하지만 오버헤드가 크기 때문에 우리가 사용하는 운영체제는 데드락이 발생해도 무시하고 사용자가 리부팅해야 하는 식으로 대처하고 있다.

 

그렇다면 이를 어떻게 예방할까?

발생 조건 네 가지를 만족하면 데드락의 위험이 있다고 했으니, 이를 예방하려면 조건 중 하나를 피하면 되는 것 아닌가?

1. 상호 배제 부정: 여러 프로세스가 공유 자원을 사용한다. Read/Write가 가능한 경우 동기화는 어떻게 하지?
2. 점유 대기 부정: 작업 전 필요한 모든 자원을 할당받는다. 하나가 자원을 다 갖고 있으면 나머지는 어떻게 하지? (starvation)
3. 선점 허용: 강제로 자원을 뺏을 수 있게 한다. 필요한 자원을 계속 뺏기면 어떻게 하지? (starvation), 작업하던 것의 진행 상태는 어떻게 하지?
4. 순환 대기 부정: 자원에 우선순위를 두어 우선순위가 높은 자원을 요청하려면, 우선순위가 낮은 자원을 모두 해제해야 한다. 우선순위가 높은 자원을 할당받은 상태에서 낮은 자원을 요청했을 때를 가정해보자. 해제와 요청이 너무 빈번하게 발생하지 않나?

결국 예방하는 것은 처리량이나 효율성을 떨어뜨린다는 단점이 있다. 하지만 멀티스레드 환경에서 설계에 따라 순환 대기를 끊어주는 등의 예방은 가능할 수 있으므로... 잘 생각해서 코딩해보자.