데드락
1. 컴퓨터 용어
Deadlock. 교착 상태.먼 길
아기가 잠드는 걸
보고 가려고
아빠는 머리맡에
앉아 계시고.
아빠가 가시는 걸
보고 자려고
아기는 말똥말똥
잠을 안 자고.
- 윤석중
운영체제 혹은 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로세스(심하면 '''운영체제 자체'''도 포함해서)가 함께 멈추어 버리는 현상을 말한다. 위에 언급된 시에서는, 아기와 아빠는 서로 잠들지 못하는 교착(deadlock) 상태에 빠져 있다고 볼 수 있다. 인터럽트와 식사하는 철학자 문제 문서를 보는 것도 도움이 된다.
발전된 현대의 운영체제는 당연하게도 프로그램 미숙으로 인해 교착이 일어날 가능성을 어느 정도는 염두에 두고 있다. 해서, OS는 교차점에서 자원을 놓고 교착 상태에 빠지는 것을 가능하면 회피시켜버린다. 하지만 아무리 예측을 잘 하고 회피를 잘 해도 결국 답이 안 보이는 놈은 있는 법. 언젠가는 교착 상태에 빠져버리는 경우가 생길 수 있다.
이런 경우에는 프로그램 자체를 강제로 종료해버리는 수밖에 없는데, 교착에 빠진 프로그램 목록에 저놈들을 관리해야 할 '''운영체제가 끼어 있다면''' 그냥 망해버리는거다. 이런 일이 발생하기 쉬운 경우가 시스템 파일이나 다른 프로그램이 공유하는 파일을 건드리기 쉬운 프로그램 설치 과정인데, "프로그램을 설치할 때는 가능하면 다른 프로그램은 모두 꺼 주세요"라는 말이 나오는 이유가 이 놈 때문이다.
데드락의 주요 패턴으로 다중 쓰레드 프로그래밍 환경에서의 ABA 문제, AB/BA 문제 등이 있다. 락(뮤텍스 같은 다중 프로세스 동기화 장치)을 저 순서대로 짜면 첫 락에 진입하자마자 쓰레드가 바뀌는 경우(Context-Switching) 다른 쓰레드가 자꾸 얻으려고 시도하는데 이미 락은 걸려 있고, 풀어주진 않고, 그래서 무한 대기하는 현상을 칭한다.
해결법은 코드 순서를 조정해서 ABA는 AAB(= AB)로, AB/BA는 AB/AB로 바꾸어주면 된다. 만약 그게 안 된다면 락을 꼭 두 개를 써야 하는지 의문을 갖고 코드를 갈아엎던가, 처리 시간대를 다르게 바꾸어서 동시에 일어나지 않게 하는 식이다. 락을 하나로 합치는 방법도 있다.
데드락은 평소엔 별 문제가 없다가 가끔 쌩뚱맞게 일어나기 때문에 다중 쓰레드 프로그래밍의 주요 난점 중 하나이며, 이 때문에 락을 그냥 딱 하나만 사용하는 극단적인 경우도 생기게 된다. 물론 이러면 데드락은 없겠지만 CPU 활용도는 좀 떨어진다.
1.1. 발생조건
- 상호 배제 (Mutual exclusion)
- 점유 상태로 대기 (Hold and wait)
- 선점 불가 (No preemption)
- 순환성 대기 (Circular wait)
1.1.1. 상호 배제
'''Mutual exclusion.''' 프로그램이 자원을 점유하는 데 있어서 배타적이다. 즉 자원 자체를 동시에 쓸 수 없는 경우를 일컫는다.
상호 배제가 없다면 (즉, 자원을 여럿이서 동시에 써도 되는 경우라면) 애시당초에 교착 상태는 발생하지 않는다. 하지만 프린터 등의 일부 입출력 장치나 연산 결과를 저장하는 변수와 같이 동시에 건드리면 위험한 자원들이 있어, 상호 배제 그 자체를 없애는 것은 불가능하다.
1.1.2. 점유 상태로 대기
'''Hold and wait.''' 자원을 붙잡은 상태에서 다른 자원을 기다리고 있다. 여러 개의 자원을 동시에 써야 하는데 이걸 순차적으로 할당받을 경우 몇 개는 이미 할당이 끝났는데 남은 자원을 다른 프로세스가 붙잡고 놔주지 않아 대기의 무간지옥에 빠질 수 있다. 문제는 이러면서 할당받은 자원은 쓰지도 않으면서 놔주질 않아서 그걸 기다리는 다른 프로세스도 또 무간지옥에 빠진다는 것. 예를 들면 Skype가 마이크와 카메라를 써야 하는데 마이크는 땡겨오는데 성공했지만 카메라 앱이 카메라를 잡고 있어서 그걸 기다리고 있고, 이 때문에 애꿎은 녹음기도 마이크를 못 쓰게 되는 상황을 생각할 수 있다.
점유 상태로 대기하는 일이 없다면 기다리고 있는 프로세스는 다른 자원을 갖고 있지 않으므로 뒤에 설명할 순환성 대기가 발생할 수 없게 된다. 간단하게 여러 자원을 동시에 땡겨받게 만들거나 기다려야 하는 자원을 할당받으려면 다른 자원을 반환하도록 만들어서 문제를 해결할 수 있다.
1.1.3. 선점 불가
'''No preemption.''' 다른 프로세스가 자원을 뺏어올 방법이 없다. 자원을 한 번 먹으면 뺏어올 방법이 없기 때문에, 위에 서술한 것 같은 대형사고가 났을 때 조치할 방법이 없게 된다. 물론 위에서 언급했던 프린터와 같이 중간에 뺏었다가는 큰일이 나는 자원이 있기 때문에 그렇다고 무턱대고 없앨 수 있는 속성도 아니다.
우선순위 선점이 가능해진다면 위의 Skype의 예시에서 녹음기가 마이크를 뺏어와서 먼저 자기 할 일을 하거나 Skype가 카메라 앱을 죽이고(...) 통신을 시작할 수 있다.
1.1.4. 순환성 대기
'''Circular wait.''' 대기가 꼬리를 물고 사이클이 되었다. 그러니까 대기 체인을 어떻게 어거지로 해결하려고 해도 결국 자기 자신으로 돌아오는데 자기 자신이 막상 기다리고 있으니 해결이 안 되는 상황.
자원에 우선순위를 매기는 등의 방식으로 해결이 가능하다.
1.2. 일반인을 위한 설명
여기 사람1, 사람2 와 종이1, 종이2가 있다. 두 종이에는 숫자가 적혀 있는데, 여기서 사람 두명이 종이1의 숫자에 종이2의 숫자를 더한 것을 계산한다고 생각해 보자. 사람 둘은 접촉할 수 없고, 종이를 교환하지도 못한다. 만약 운이 좋다면,
- 사람1이 종이 1, 2를 모두 가져간다.
- 사람2가 종이가 없는 것을 확인하고 기다린다.
- 사람1이 종이 1, 2를 돌려놓는다.
- 사람2가 종이 1, 2를 모두 가져간다.
- 사람1이 종이1을 가져간다.
- 사람2가 종이2를 가져간다.
- 사람1이 종이2가 없는 것을 확인하고 기다린다.
- 사람2가 종이1이 없는 것을 확인하고 기다린다.
제일 쉽게보는 방법은 MTP 프로토콜로 내장 메모리에서 sd 카드로 복사하면 볼수 있다.[1]
1.3. 예시를 동반한 설명
왜 이런 현상이 일어나는지 알아보려면 일단 멀티스레딩이 기본적으로 어떻게 돌아가는 것인지 알 필요가 있다. 가장 원시적인 멀티스레딩 방식으로 생각할 수 있는 것은, 단순히 함수 두 개 이상의 흐름을 운영체제가 적절하게 연결해 가면서[2] 돌리는 것이다.
하지만 이렇게 멀티태스킹을 처리해버리면 서로 같은 자리의 데이터를 읽거나 써야 할 때 문제가 발생한다. 예를 들어 "(초기 상태에서는 0인) 변수 A에 1을 더한다."라는 작업을 스레드를 두 개로 나눠서 천만 번 수행한다고 가정하자. 이론상 이러면 A는 이천만이 되어야 할 것 같지만 실제로는 그렇지 않다! 얼핏 보면 문제가 없어 보이는 이 코드를 돌려보면 로또가 터지지 않는 한 이천만보다 모자란 값이 나온다. 그 이유라면, 사실 이 작업은 아래와 같이 쪼개져서 이뤄지기 때문이다.
- A의 메모리 주소에 있는 값을 레지스터[3]로 불러온다.
- 레지스터에 불러온 값에 1을 더한다.
- 1을 더한 값을 다시 메모리에 쓴다.
- 첫 번째 스레드는 A의 메모리 주소에 있는 값을 레지스터로 뽑아온다.(A는 0이었다.)
- 두 번째 스레드는 A의 메모리 주소에 있는 값을 레지스터로 뽑아온다.(A는 0이었다.)
- 첫 번째 스레드는 불러온 값에 1을 더한다.(0에다가 1을 더하니 1.)
- 두 번째 스레드는 불러온 값에 1을 더한다.(0에다가 1을 더하니 1.)
- 첫 번째 스레드는 불러온 값을 다시 메모리에 쓴다.(A는 1이 된다.)
- 두 번째 스레드는 불러온 값을 다시 메모리에 쓴다.(A는 1이 된다!)
이런 현상을 막기 위해 막기 위해 세마포어[5]나 뮤텍스[6]가 도입이 된다. 저건 간단히 말해서 어떤 플래그가 서 있는 동안에는 특정한 변수는 건드리지 않는다는 것이다. 쉽게 말해 뮤텍스의 각주에 나온 것과 같이 자물쇠를 채우는 거다. 예를 들어, 다음과 같이 코드를 수정한다고 하자.
- Lock이라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
- (중략...)
- Lock을 내린다.
- 첫 번째 스레드는 일단 Lock이 올라가 있는지 확인한다. 당연히 처음이니까 내려가 있다. 즉시 Lock을 올린다.
- 두 번째 스레드는 일단 Lock이 올라가 있는지 확인한다. Lock은 이미 올라가 있으니 세월아 네월아 기다린다.
- 두 번째 스레드가 아무 것도 못 하고 있으니, 첫 번째 스레드는 문제 없이 A의 메모리 주소에 있는 값을 레지스터로 뽑아오고, 불러온 값에 1을 더하고, 다시 메모리에 쓴다. A는 1이 된다.
- 첫 번째 스레드가 Lock을 내린다.
- 두 번째 스레드는 Lock이 내려간 것을 확인. A를 뽑아오고(1이다), 불러온 값에 1을 더하고(2가 된다), 다시 메모리에 쓴다. A는 2가 된다.
- Lock1이라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
- Lock2라는 뮤텍스가(이하생략)
- A에 1을 더한다.
- Lock2를 내린다.
- Lock1을 내린다.
- Lock2라는 뮤텍스가(이하생략)
- Lock1이라는 뮤텍스가(이하생략)
- A에 1을 더한다.
- Lock2를 내린다.
- Lock1을 내린다.
- 첫 번째 스레드가 Lock1을 확인한다. 내려가 있으니 올린다.
- 두 번째 스레드가 Lock2를 확인한다. 내려가 있으니 올린다.
- 첫 번째 스레드가 Lock2를 확인한다. 안 내려가 있으니 기다린다.
- 두 번째 스레드가 Lock1을 확인한다. 안 내려가 있으니 기다린다.
물론 현실은 항상 이렇지만은 않다. 위 예제는 교착 상태를 의도적으로 일으키기 위해 극단화한 경우이고, 실제로는 예상하지 못한 곳에서 코딩 미스나 운영체제의 설계 미스, 혹은 스펙 한계 등의 이유로 의도하지 않은 교착 상태가 발생할 수 있다는 것. [7] 여러 개의 스레드가 얽히고 여러 종류의 락을 사용할 경우 훨씬 더 복잡하고 골치아픈 경우가 많다. 그래프 알고리즘을 이용하여 교착 상태를 검출해낼 수 있으나 n개의 락을 이용할 경우 O(n3)의 알고리즘이 되어 상당한 성능 저하를 일으킨다.
그러한 연유로 보통의 범용 운영체제는 데드락 방지를 위한 어떠한 처리를 크게 고려하지 않는 편. 가능한 한 교착이 잘 일어나지 않게끔 설계하겠지만 능동적으로 교착 방지 알고리즘을 적용할 경우 일어나는 성능 저하가 가끔 일어나는 교착 상태보다 더 심각한 문제라고 판단하기 때문이다. 그래서 심각한 교착 상태가 일어나는 경우 그냥 사용자가 알아서 리부팅해야 한다. 이와는 반대로 이런 알고리즘을 써서라도 반드시 교착 상황을 방지해야 하는 운영체제도 있는데 바로 '''차량/항공기 전장 운영체제'''이다. 교착이 일어나서 시스템이 뻗는 경우 대형참사로 이어지기 때문에 안정성이 상당히 중요하다.
1.4. 현실에서의 예시
1. OTP의 수명이 끝나서 급한 대로 타행 OTP를 연결하려 하니 공인인증서를 요구한다.
2. 공인인증서까지 만료된 상황이라 공인인증서를 다시 발급받으려 하니 OTP 번호를 요구한다.
OTP 문서의 예시로, 이런 경우 은행에 내방하는 것 외에는 방법이 없다.
비슷한 것으로 일과 경력이 있다. [image]
2. 자동차 용어(Deadlock)
90년대 이전 차 문을 열쇠로 잠그던 시절, 옷걸이나 철사를 창문 틈 사이로 밀어넣어 도어핀이나 내측 도어 열림 손잡이를 조작하여 문을 따는 차도둑들의 수법을 막기 위해 나온 보안 강화 매커니즘을 일컫는다. 다른말로 더블락(Doublelock)이라고도 한다. 열쇠를 90도까지 잠금 방향으로 돌리거나 기타 다른 조작방법으로 데드락을 활성화 하면 도어래치와 내부 손잡이 및 도어핀 간의 기계적 연결상태가 해제되어버려 외부에서 옷걸이 등으로 아무리 도어핀을 끌어올리는 등 조작을 해봤자 절대 문을 못 딴다. 과거 BMW나 재규어 등 고급 차종에 적용되었으나 요즘은 스마트키 및 이모빌라이저의 대중화로 인해 필요없어져서 거의 쓰이지 않는다.
[1] 파일을 읽어야 하는데 파일 쓰는중이고 파일을 써야되는데 읽지를 못하고...[2] 완전히 설명하려면 레지스터의 백업이나 스택, 가상 메모리 같은 컴공과 들어가야 배우는 단어가 나오니까 "적절하게"라는 단어로 여기서는 넘어가도록 한다.[3] CPU가 직접 연산을 할 수 있는 공간이라 생각하면 편하다.[4] 역시 편의상 스레드 사이의 넘겨주기는 생략한다. 사실 스레드 전환에도 작업이 필요하기 때문에 한 줄 단위로 번갈아가면서 실행하는 경우는 거의 없다. 하지만 중간에 스레드를 전환할 수 있는 한 값은 언제든지 어긋날 수 있다.[5] Semaphore, 원래 뜻은 "수기 신호"[6] Mutex, '''Mut'''ual-'''ex'''clusion lock 즉 상호 배제 잠금이라는 뜻[7] 시간적인 타이밍 방식으로 제어하면 자주 생긴다. 두번째 실행을 대기 하기 위하여 1초를 기다리는 경우에 두번째 실행이 여전히 지연같은 예외로 1초를 기다렸으나 여전히 실행중이라면 이런건 작동오류로 이어져 결국 멈추게 된다.