Deadlock

1 컴퓨터 용어

Deadlock. 혹은 교착 상태.

운영체제 혹은 소프트웨어의 잘못된 자원 관리로 인해서 둘 이상의 프로그램(심하면 운영체제 자체도 포함해서)이 같이 다운돼버리는 현상을 말한다. 아래에서 설명하겠지만, 잘 이해하지 못하겠다면 그냥 프로그램 내지는 스레드 둘이서 자원 한 개를 놓고 협상하다가 1의 교착 상태에 빠졌구나 하고 이해하면 쉽다. 식사 하는 철학자 문제를 보는 것도 도움이 된다.

발전된 현대의 운영체제는 당연하게도 프로그램 미숙으로 인해 교착이 일어날 가능성을 어느 정도는 염두에 두고 있다. 해서, OS는 교차점에서 자원을 놓고 교착 상태에 빠지는 것을 가능하면 회피시켜버린다. 하지만 아무리 예측을 잘 하고 회피를 잘 해도 결국 답이 안 보이는 놈은 있는 법. 언젠가는 교착 상태에 빠져버리는 경우가 생길 수 있다. 이런 경우에는 프로그램 자체를 강제로 종료해버리는 수밖에 없는데, 교착에 빠진 프로그램 목록에 저놈들을 관리해야 할 운영체제가 끼어 있다면 그냥 망해버리는거다. 이런 일이 발생하기 쉬운 경우가 시스템 파일이나 다른 프로그램이 공유하는 파일을 건드리기 쉬운 프로그램 설치 과정인데, "프로그램을 설치할 때는 가능하면 다른 프로그램은 모두 꺼 주세요"라는 말이 나오는 이유가 이 놈 때문이다.

2 발생조건

1. 상호 배제 (Mutual exclusion)
2. 점유 상태로 대기 (Hold and wait)
3. 선점 불가 (No preemption)
4. 순환성 대기 (Circular wait)
이 4가지 조건이 모두 만족되면 교착 상태가 일어나게 된다.

2.1 상호 배제

Mutual exclusion. 프로그램이 자원을 점유하는 데 있어서 배타적이다. 즉 자원 자체를 동시에 쓸 수 없는 경우를 일컫는다.

상호 배제가 없다면 (즉, 자원을 여럿이서 동시에 써도 되는 경우라면) 애시당초에 교착 상태는 발생하지 않는다. 하지만 프린터 등의 일부 입출력 장치나 연산 결과를 저장하는 변수와 같이 동시에 건드리면 위험한 자원들이 있어, 상호 배제 그 자체를 없애는 것은 불가능하다.

2.2 점유 상태로 대기

Hold and wait. 자원을 붙잡은 상태에서 다른 자원을 기다리고 있다. 여러 개의 자원을 동시에 써야 하는데 이걸 순차적으로 할당받을 경우 몇 개는 이미 할당이 끝났는데 남은 자원을 다른 프로세스가 붙잡고 놔주지 않아 대기의 무간지옥에 빠질 수 있다. 문제는 이러면서 할당받은 자원은 쓰지도 않으면서 놔주질 않아서 그걸 기다리는 다른 프로세스도 또 무간지옥에 빠진다는 것. 예를 들면 Skype가 마이크와 카메라를 써야 하는데 마이크는 땡겨오는데 성공했지만 카메라 앱이 카메라를 잡고 있어서 그걸 기다리고 있고, 이 때문에 애꿎은 녹음기도 마이크를 못 쓰게 되는 상황을 생각할 수 있다.

점유 상태로 대기하는 일이 없다면 기다리고 있는 프로세스는 다른 자원을 갖고 있지 않으므로 뒤에 설명할 순환성 대기가 발생할 수 없게 된다. 간단하게 여러 자원을 동시에 땡겨받게 만들거나 기다려야 하는 자원을 할당받으려면 다른 자원을 반환하도록 만들어서 문제를 해결할 수 있다.

2.3 선점 불가

No preemption. 다른 프로세스가 자원을 뺏어올 방법이 없다. 자원을 한 번 먹으면 뺏어올 방법이 없기 때문에, 위에 서술한 것 같은 대형사고가 났을 때 조치할 방법이 없게 된다. 물론 위에서 언급했던 프린터와 같이 중간에 뺏었다가는 큰일이 나는 자원이 있기 때문에 그렇다고 무턱대고 없앨 수 있는 속성도 아니다.

우선순위 선점이 가능해진다면 위의 Skype의 예시에서 녹음기가 마이크를 뺏어와서 먼저 자기 할 일을 하거나 Skype가 카메라 앱을 죽이고(...) 통신을 시작할 수 있다.

2.4 순환성 대기

Circular wait. 대기가 꼬리를 물고 사이클이 되었다. 그러니까 대기 체인을 어떻게 어거지로 해결하려고 해도 결국 자기 자신으로 돌아오는데 자기 자신이 막상 기다리고 있으니 해결이 안 되는 상황.

자원에 우선순위를 매기는 등의 방식으로 해결이 가능하다.

3 일반인을 위한 설명

여기 사람1, 사람2 와 종이1, 종이2가 있다. 두 종이에는 숫자가 적혀 있는데, 여기서 사람 두명이 종이1의 숫자에 종이2의 숫자를 더한 것을 계산한다고 생각해 보자. 사람 둘은 접촉할 수 없고, 종이를 교환하지도 못한다. 만약 운이 좋다면,

1.사람1이 종이 1, 2를 모두 가져간다.
2.사람2가 종이가 없는 것을 확인하고 기다린다.
3.사람1이 종이 1, 2를 돌려놓는다.
4.사람2가 종이 1, 2를 모두 가져간다.

이런 방식으로 일이 진행될 것이다. 하지만 일이 꼬일 수도 있다.

1.사람1이 종이1을 가져간다.
2.사람2가 종이2를 가져간다.
3.사람1이 종이2가 없는 것을 확인하고 기다린다.
4.사람2가 종이1이 없는 것을 확인하고 기다린다.

이런 경우 명령의 진행이 멈추머, 같은 상태가 계속 지속되게 된다. 이러한 교착 상태를 데드락이라 한다.

4 예시를 동반한 머리 깨지는 설명

왜 이런 현상이 일어나는지 알아보려면 일단 멀티스레딩이 기본적으로 어떻게 돌아가는 것인지 알 필요가 있다. 가장 원시적인 멀티스레딩 방식으로 생각할 수 있는 것은, 단순히 함수 두 개 이상의 흐름을 운영체제가 적절하게 연결해 가면서[1] 돌리는 것이다.

하지만 이렇게 멀티태스킹을 처리해버리면 서로 같은 자리의 데이터를 읽거나 써야 할 때 문제가 발생한다. 예를 들어 "(초기 상태에서는 0인) 변수 A에 1을 더한다."라는 작업을 스레드를 두 개로 나눠서 천만 번 수행한다고 가정하자. 이론상 이러면 A는 이천만이 되어야 할 것 같지만 실제로는 그렇지 않다! 얼핏 보면 문제가 없어 보이는 이 코드를 돌려보면 로또가 터지지 않는 한 이천만보다 모자란 값이 나온다. 그 이유라면, 사실 이 작업은 아래와 같이 쪼개져서 이뤄지기 때문이다.

  • A의 메모리 주소에 있는 값을 레지스터[2]로 불러온다.
  • 레지스터에 불러온 값에 1을 더한다.
  • 1을 더한 값을 다시 메모리에 쓴다.

...그리고 저 작업들이 줄 단위로 쪼개질 수 있다는데서 문제가 생겨버린다. 설명의 편의를 위해 천만 번씩 수행하는 것을 한 번으로 줄여서 다시 해보자. 가끔씩 아래와 같은 상황이 나올 수 있다.[3]

  • 첫 번째 스레드는 A의 메모리 주소에 있는 값을 레지스터로 뽑아온다.(A는 0이었다.)
  • 두 번째 스레드는 A의 메모리 주소에 있는 값을 레지스터로 뽑아온다.(A는 0이었다.)
  • 첫 번째 스레드는 불러온 값에 1을 더한다.(0에다가 1을 더하니 1.)
  • 두 번째 스레드는 불러온 값에 1을 더한다.(0에다가 1을 더하니 1.)
  • 첫 번째 스레드는 불러온 값을 다시 메모리에 쓴다.(A는 1이 된다.)
  • 두 번째 스레드는 불러온 값을 다시 메모리에 쓴다.(A는 1이 된다!)

결과적으로 2가 되어야 할 A는 1이 된다. (간단히 말해서 0 + 1을 한 후 다시 그 결과인 1에 추가적으로 1 + 1을 해야 바른 연산인데, 그냥 0 + 1을 두번 해버렸으니 2대신 1이 되버린 것. 순서를 지켜야 되는 연산을 대책없이 멀티코어로 처리할 때 생기는 가장 기본적인 병크이다.)

이런 현상을 막기 위해 막기 위해 세마포어[4]나 뮤텍스[5]가 도입이 된다. 저건 간단히 말해서 어떤 플래그가 서 있는 동안에는 특정한 변수는 건드리지 않는다는 것이다. 쉽게 말해 뮤텍스의 각주에 나온 것과 같이 자물쇠를 채우는 거다. 예를 들어, 다음과 같이 코드를 수정한다고 하자.

  • 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을 확인한다. 안 내려가 있으니 기다린다.

첫 번째 스레드는 두 번째 스레드가 Lock2를 풀어줘야 동작할 수 있다. 그런데 두 번째 스레드는 첫 번째 스레드가 Lock1을 풀어줘야 동작할 수 있다.

......어?

이런식으로 스레드 두 개의 요구사항이 서로 1번의 교착 상태에 빠져버려서, 프로그램은 기약 없는 기다림 속에 무한 루프에 빠진다.

물론 현실은 항상 이렇지만은 않다. 위 예제는 교착 상태를 의도적으로 일으키기 위해 극단화한 경우이고, 실제로는 예상하지 못한 곳에서 코딩 미스나 운영체제의 설계 미스, 혹은 스펙 한계 등의 이유로 의도하지 않은 교착 상태가 발생할 수 있다는 것. 여러 개의 스레드가 얽히고 여러 종류의 락을 사용할 경우 훨씬 더 복잡하고 골치아픈 경우가 많다. 그래프 알고리즘을 이용하여 교착 상태를 검출해낼 수 있으나 n개의 락을 이용할 경우 O(n3)의 알고리즘이 되어 상당한 성능 저하를 일으킨다.

그러한 연유로 보통의 범용 운영체제는 데드락 방지를 위한 어떠한 처리를 크게 고려하지 않는 편. 가능한 한 교착이 잘 일어나지 않게끔 설계하겠지만 능동적으로 교착 방지 알고리즘을 적용할 경우 일어나는 성능 저하가 가끔 일어나는 교착 상태보다 더 심각한 문제라고 판단하기 때문이다. 그래서 심각한 교착 상태가 일어나는 경우 그냥 사용자가 알아서 리부팅해야 한다. 이와는 반대로 이런 알고리즘을 써서라도 반드시 교착 상황을 방지해야 하는 운영체제도 있는데 바로 차량/항공기 전장 운영체제이다. 교착이 일어나서 시스템이 뻗는 경우 대형참사로 이어지기 때문.
  1. ↑ 완전히 설명하려면 레지스터의 백업이나 스택, 가상 메모리 같은 컴공과 들어가야 배우는 단어가 나오니까 "적절하게"라는 단어로 여기서는 넘어가도록 한다.
  2. ↑ CPU가 직접 연산을 할 수 있는 공간이라 생각하면 편하다.
  3. ↑ 역시 편의상 스레드 사이의 넘겨주기는 생략한다. 사실 스레드 전환에도 작업이 필요하기 때문에 한 줄 단위로 번갈아가면서 실행하는 경우는 거의 없다. 하지만 중간에 스레드를 전환할 수 있는 한 값은 언제든지 어긋날 수 있다.
  4. ↑ Semaphore, 원래 뜻은 "수기 신호"
  5. ↑ Mutex, Mutual-exclusion lock 즉 상호 배제 잠금이라는 뜻