데드락

게임에 대한 내용은 Deadlock(게임) 문서 참고하십시오.

동음이의어에 대한 내용은 데드락(동음이의어) 문서 참고하십시오.

1. 개요2. 발생 조건

2.1. 상호 배제2.2. 점유 상태로 대기2.3. 선점 불가2.4. 순환성 대기

3. 해설

3.1. 비전공자를 위한 설명3.2. 예시를 동반한 설명

4. 상세5. 해결 방법

5.1. 예방5.2. 회피

5.2.1. 은행원 알고리즘5.2.2. Wait-Die 기법5.2.3. Wound-Wait 기법

5.3. 탐지5.4. 복구

6. 현실에서의 예시7. 관련 문서

1. 개요

Deadlock

운영체제 또는 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로세스 [1] 또는 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황으로, 멀티스레딩, 병렬 프로그래밍, 분산 컴퓨팅에서 흔히 발생하는 문제이다. 한국어로는 교착 상태라고 한다.

주로 한정된 자원을 여러 프로세스에서 동시에 사용하는 환경에서 서로 상대방이 사용 중인 자원을 쓰기 위해 대기하는 상황, 그러니까 A가 B를 기다리고 B가 A를 기다릴 때 발생한다. 위에 언급된 시에서는, 아기와 아빠는 서로 잠들지 못하는 교착(deadlock) 상태에 빠져 있다고 볼 수 있다.

흔히 병목 현상과도 혼동하지만 둘은 근본 원인 자체가 다르다. 병목 현상은 여러 구성 요소가 동시에 실행될 때, 가장 느린 쪽의 속도에 맞추기 위해 전체 시스템이 느려지는 상황이며, 반대로 교착 상태는 한정된 자원을 둘 이상의 주체가 서로 동시에 사용하려고 기다리기 때문에 발생한다.

2. 발생 조건

흔히 1971년 코프만 교수가 저서에서 공개한 코프만 조건(Coffman conditions)을 기준으로 하며, 아래의 4가지 조건이 모두 만족하는 상태를 교착 상태로 정의한다.[2]

상호 배제 (Mutual exclusion)
점유 상태로 대기 (Hold and wait)
선점 불가 (No preemption)
순환성 대기 (Circular wait)

2.1. 상호 배제

Mutual exclusion

프로그램이 자원을 점유하는 데 있어서 배타적이다. 즉 자원 자체를 동시에 쓸 수 없으며, 반드시 한 번에 하나의 프로세스만이 해당 자원을 사용할 수 있는 경우를 일컫는다. 일반적으로 가변성(mutable) 자원이 이 경우에 속한다.

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

이 상호 배제(mutual exclusion)의 줄임말이 바로 뮤텍스이다.

2.2. 점유 상태로 대기

Hold and wait[3]

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

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

2.3. 선점 불가

No preemption

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

우선순위 선점이 가능해진다면 위의 Skype의 예시에서 녹음기가 마이크를 뺏어와서 먼저 자기 할 일을 하거나 Skype가 카메라 앱을 죽이고(...) 통신을 시작할 수 있다. 다만 일반적으로 운영체제가 아닌 일반 Userland의 프로세스들은 서로 우선순위 선점이 불가능한 경우가 많기 때문에 이런 해결방법은 운영체제 수준이 아니라면 불가능하다.

2.4. 순환성 대기

Circular wait

모든 프로세스가 다른 프로세스가 사용중인 있는 자원을 기다리는 상황에서, 마지막 프로세스가 첫 프로세스가 사용 중인 자원을 쓰기 위해 대기중인 상황. 쉽게 말해서 대기가 꼬리를 물고 사이클이 된 것. 그러니까 대기 체인을 어떻게 어거지로 해결하려고 해도 결국 자기 자신으로 돌아오는데 자기 자신이 막상 기다리고 있으니 해결이 안 되는 상황. 가장 유명한 예시로 식사하는 철학자 문제가 있다.

엄밀히는, 대기중인 프로세스의 집합 [math(P=\{P_1,\,P_2,\,\dots,\,P_N\})]가 존재할 때, [math(P_1)]이 [math(P_2)]가 사용중인 자원을 대기중이고, [math(P_2)]는 [math(P_3)]가 사용중인 자원을 대기중이고, 이런 식으로 쭉 이어지다가 [math(P_N)]이 [math(P_1)]이 사용중인 자원을 대기할 때 이 집합 [math(P)]가 순환성 대기를 가진다고 정의한다. 데드락을 해결하는 방법은 주로 이런 대칭성을 깨트려 열린 그래프로 만드는 방식이 많다.

순환성 대기는 데드락 현상의 꽃~~(?)~~이기도 하다. 데드락의 여러 특징이 이러한 순환성에서 기인하고, 위의 세 조건에 비해 예측하기도 탐지하기도 가장 어렵기 때문. 일반적인 순환대기의 경우 자원에 우선순위를 매기는 등의 방식으로 해결이 가능하다.

3. 해설

3.1. 비전공자를 위한 설명

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

만약 운이 좋다면,

사람1이 종이 1, 2를 모두 가져간다.
사람2가 종이가 없는 것을 확인하고 기다린다.
사람1이 계산을 마치고 종이 1, 2를 돌려놓는다.
사람2가 종이 1, 2를 모두 가져간다.
사람2가 계산을 마치고 종이 1, 2를 돌려놓는다.
두 명 모두 작업을 정상적으로 종료한다.

이런 방식으로 일이 진행될 것이다.

하지만 일이 꼬일 수도 있다.

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

이런 경우 서로 기다리느라 명령의 진행이 멈추머, 같은 상태가 계속 지속되게 된다. 이러한 교착 상태를 데드락이라 한다. 교착 문서에 첨부된 사진을 보면 이해가 더욱 쉽다.

제일 쉽게보는 방법은 MTP 프로토콜로 내장 메모리에서 sd 카드로 복사하면 볼수 있다.[4]

3.2. 예시를 동반한 설명

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

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

#!wiki
 1. A의 메모리 주소에 있는 값을 [[레지스터]][* CPU가 직접 연산을 할 수 있는 공간이라 생각하면 편하다.]로 불러온다.
 1. 레지스터에 불러온 값에 1을 더한다.
 1. 1을 더한 값을 다시 메모리에 쓴다.

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

첫 번째 스레드는 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이 되어 버린 것. 순서를 지켜야 되는 연산을 대책없이 멀티코어로 처리할 때 생기는 가장 기본적인 오류이다.

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

#!wiki
 1. 작업을 하기 전, 우선 Lock이라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
 1. 기존의 작업(A읽기, 쓰기)을 그대로 진행한다.
 1. 자원을 다 사용했다는 의미로 Lock을 내린다.

즉, A라는 자원을 사용하기 직전과 직후에 Lock을 올려서 현재 자신이 A를 사용중이라고 알리는 것이다.

다시 방금의 예로 돌아가자.

첫 번째 스레드는 일단 Lock이 올라가 있는지 확인한다. 당연히 처음이니까 내려가 있다. 즉시 Lock을 올린다.
두 번째 스레드는 일단 Lock이 올라가 있는지 확인한다. Lock은 이미 올라가 있으니 락이 풀릴 때까지 그대로 기다린다.
첫 번째 스레드는 두 번째 스레드가 아무것도 못 하는 동안 A의 메모리 주소에 있는 값을 레지스터로 불러온다. (A는 0이었다.)
첫 번째 스레드는 불러온 값에 1을 더한다. (0에다가 1을 더하니 1.)
첫 번째 스레드는 불러온 값을 다시 메모리에 쓴다. (A는 1이 된다.)
첫 번째 스레드가 Lock을 내린다.
두 번째 스레드는 Lock이 내려간 것을 확인. 자신이 사용한다는 의미로 즉시 Lock을 올린다.
두 번째 스레드는 A의 메모리 주소에 있는 값을 레지스터로 불러온다. (A는 1이었다.)
두 번째 스레드는 불러온 값에 1을 더한다. (1에다가 1을 더하니 2.)
두 번째 스레드는 불러온 값을 다시 메모리에 쓴다. (A는 2가 된다.)
두 번째 스레드가 Lock을 내린다.

이것은 첫 번째 스레드와 두 번째 스레드의 순서를 바꿔도 제대로 작동하는 예제가 된다. 그렇다면 이걸로 끝일까? 끝이면 이 항목이 있을 리가. 이번에는 #비전공자를 위한 설명 문단의 예제와 동일하게 스레드 두 개가 두 개의 자원 A, B를 동시에 사용하는 경우를 생각해보자. 자원이 두 개니 뮤텍스 역시 두 개(Lock1, Lock2)임에 주의하자.

첫 번째 스레드는 다음과 같이 동작한다.

#!wiki
 1. Lock1이라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
 1. Lock2라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
 1. A와 B로 작업을 수행한다.
 1. Lock2를 내린다.
 1. Lock1을 내린다.

두 번째 스레드는 다음과 같이 동작한다.

#!wiki
 1. Lock2라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
 1. Lock1이라는 뮤텍스가 올라가 있는지 확인하고, 안 올라가 있으면 올린다. 올라가 있으면 내려올 때까지 기다린다.
 1. A와 B로 작업을 수행한다.
 1. Lock1을 내린다.
 1. Lock2를 내린다.

이렇게 두 개의 스레드를 돌린다면, 재수없으면 이런 경우가 생겨버린다.

첫 번째 스레드가 Lock1을 확인한다. 내려가 있으니 올린다.
두 번째 스레드가 Lock2를 확인한다. 내려가 있으니 올린다.
첫 번째 스레드가 Lock2를 확인한다. 안 내려가 있으니 기다린다.
두 번째 스레드가 Lock1을 확인한다. 안 내려가 있으니 기다린다.

첫 번째 스레드는 두 번째 스레드가 Lock2를 풀어줘야 동작할 수 있다. 그런데 두 번째 스레드는 첫 번째 스레드가 Lock1을 풀어줘야 동작할 수 있다. 이런식으로 스레드 두 개의 요구사항이 서로 1번의 교착 상태에 빠져버려서, 프로그램은 기약 없는 기다림 속에 빠진다.

4. 상세

물론 현실은 항상 위의 예시들과 같이 간단하기만 한 것은 아니다. 위 예시들은 교착 상태를 의도적으로 일으키기 위해 극단화한 경우이고, 실제로는 예상하지 못한 곳에서 코딩 미스나 운영체제의 설계 미스, 혹은 스펙 한계 등의 이유로 의도하지 않은 교착 상태가 발생할 수 있다는 것.[9]

예시를 동반한 설명 문단의 경우 2개의 스레드와 2개의 락을 사용하는 환경이었지만 현실은 여러 개의 스레드가 얽히고 여러 종류의 락을 동시에 사용해 훨씬 더 복잡하고 골치아픈 경우가 많다. 후술할 그래프 알고리즘을 이용하여 교착 상태를 검출해낼 수 있으나 [math(n)]개의 락을 이용할 경우 [math(\mathcal{O}(n^3))]의 알고리즘이 되어 상당한 성능 저하를 일으킨다.

발전된 현대의 운영체제는 당연하게도 프로그램 미숙으로 인해 교착이 일어날 가능성을 어느 정도는 염두에 두고 있다. 예를 들어 OS는 교차점에서 자원을 놓고 교착 상태에 빠지는 것을 가능하면 회피시켜버린다. 하지만 아무리 예측을 잘 하고 회피를 잘 해도 결국 답이 안 보이는 놈은 있는 법. 언젠가는 교착 상태에 빠져버리는 경우가 생길 수 있다.

그러한 연유로 보통의 범용 운영체제는 데드락 방지를 위한 어떠한 처리를 크게 고려하지는 않는 편. 가능한 한 교착이 잘 일어나지 않게끔 설계하겠지만 능동적으로 교착 방지 알고리즘을 적용할 경우 일어나는 성능 저하가 가끔 일어나는 교착 상태보다 더 심각한 문제라고 판단하기 때문이다. 그래서 심각한 교착 상태가 일어나는 경우 그냥 사용자가 알아서 리부팅해야 한다. 이와는 반대로 이런 알고리즘을 써서라도 반드시 교착 상황을 방지해야 하는 운영체제도 있는데 바로 차량/항공기 전장 운영체제이다. 교착이 일어나서 시스템이 뻗는 경우 대형참사로 이어지기 때문에 안정성이 상당히 중요하다.

이런 경우에는 프로그램 자체를 강제로 종료해버리는 수밖에 없는데, 교착에 빠진 프로그램 목록에 저놈(사용자 프로세스)들을 관리해야 할 운영체제가 끼어 있다면 그냥 망해버리는거다. 이런 일이 발생하기 쉬운 경우가 시스템 파일이나 다른 프로그램이 공유하는 파일을 건드리기 쉬운 프로그램 설치 과정인데, "프로그램을 설치할 때는 가능하면 다른 프로그램은 모두 꺼 주세요"라는 말이 나오는 이유가 이 놈 때문이다.

데드락에 대한 유명한 예시로 에츠허르 다익스트라교수가 만든 식사하는 철학자 문제 등이 존재한다. 해설 문단을 보고도 아직 잘 감이 오지 않는다면 참고해보자.

데드락의 주요 패턴으로 다중 쓰레드 프로그래밍 환경에서의 ABA 문제, AB/BA 문제 등이 있다. 락( 뮤텍스 같은 다중 프로세스 동기화 장치)을 저 순서대로 짜면 첫 락에 진입하자마자 쓰레드가 바뀌는 경우(Context-Switching) 다른 쓰레드가 자꾸 얻으려고 시도하는데 이미 락은 걸려 있고, 풀어주진 않고, 그래서 무한 대기하는 현상을 칭한다.

해결법은 코드 순서를 조정해서 ABA는 AAB(= AB)로, AB/BA는 AB/AB로 바꾸어주면 된다. 만약 그게 안 된다면 락을 꼭 두 개를 써야 하는지 의문을 갖고 코드를 갈아엎던가, 처리 시간대를 다르게 바꾸어서 동시에 일어나지 않게 하는 식이다. 락을 하나로 합치는 방법도 있다.

데드락은 평소엔 별 문제가 없다가 가끔 쌩뚱맞게 일어나기 때문에 다중 쓰레드 프로그래밍의 주요 난점 중 하나이며, 이 때문에 락을 그냥 딱 하나만 사용하는 극단적인 경우도 생기게 된다. 물론 이러면 데드락은 없겠지만 CPU 활용도는 좀 떨어진다.

5. 해결 방법

기본적으로 교착상태를 벗어나는 방법은 다음 4가지로 나눌 수 있다.

예방 (Prevention)
회피 (Avoidance)
탐지 (Detection)
복구 (Recovery)

5.1. 예방

말 그대로 교착이 일어날 상황 자체를 미연에 방지하는 것이다.

특정 프로세스 A가 자원을 계속해서 점유해야 작업을 처리할 수 있을 것 같은데 그게 언제동안 가지고 있어야할지 마냥 감이 안오는 상황일 때 뒤에서 B가 기다리고 있다면, A는 현재 점유하고 있는 자원을 해제 후 새롭게 자원을 요청하여 기존에 자신이 가지고 있는 자원을 B에게 줘버리는 방식이다.

물론 이는 대표적인 예시 중 하나일 뿐이며, 발생조건의 4가지 조건 중 하나라도 방지하면 데드락을 피할 수 있기 때문에 각 조건별로 '상호 배제의 부정' 또는 '점유 및 대기 부정', '비선점 부정', '순환 대기 부정'등의 여러 방법들이 있다.

5.2. 회피

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

5.2.1. 은행원 알고리즘

데드락에 빠질 가능성을 운영체제가 판단한 후, 데드락에 빠질 가능성이 없다고 판단되면 자원을 할당해 주는 방식이다. Safe sequence[11]라는 일종의 '순서'가 존재하여 교착 상태가 발생할 가능성이 없는 요구(안전상태/Safe State)에는 자원을 할당해주고, 교착 상태가 발생할 가능성이 조금이라도 있는 요구(불안전상태/Unsafe State)에는 추후에 해당 조건을 수행해도 문제가 없을 때 자원을 할당해주는 방식이다.

예를들어 프로세스 A, B, C가 각각 15, 30, 40의 자원을 요청하며 운영체제는 현재 40의 자원을 보유하고 있다고 가정 시, 운영체제는 우선 A에게 15의 자원을 빌려준 후, 이후 A의 작업이 끝나 자원을 반환하면, B에게 30의 자원을 빌려주고, 이후 B가 자원을 반납하면 C에게 40의 자원을 빌려주는 형식이다.

장점은 시스템이 항상 안전상태를 유지할 수 있다는 것이지만, 단점은 최대 자원의 요구량을 미리 알아야하며(하지만 프로그램은 정확하게 15의 자원을 요구하지 않는다.), 자원 이용도가 낮거나 유한한 시간내로 자원을 사용 후 반납하여야 하는 문제점으로 인해 현재 운영체제에 사용되지는 않는다. 단적으로 위의 예시만 봐도 A에게 15를 빌려주면 A가 자원을 사용하는 동안에는 25의 자원이 그냥 놀고 있는 것과 다름없게 된다!

한가지 알고있어야 할 사항은 불안전 상태라고해서 반드시 교착상태가 발생하는 것은 아니라는 것이다. 불안전 상태가 지속되어도 교착이 발생하지 않을 가능성은 얼마든지 있다.

5.2.2. Wait-Die 기법

프로세스 A가 보유한 자원을 프로세스 B가 요청할 때 프로세스B가 프로세스A보다 적은 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기가 허용된다. 만약 그렇지 않다면 B는 롤백된다.

즉 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 적은 타임스탬프를 보유하고 있어야 한다는 것을 의미한다.

5.2.3. Wound-Wait 기법

프로세스 A가 보유한 자원을 프로세스 B가 요청할 때 프로세스B가 프로세스A보다 큰 타임스탬프를 가지는 경우에만 자원 점유를 위한 대기가 허용된다. 만약 그렇지 않다면 B는 롤백된다.

즉 사용중인 자원을 점유하기 위해 특정 프로세스가 대기해야하는 경우 대기하는 프로세스는 항상 자원을 사용중인 프로세스보다 큰 타임스탬프를 보유하고 있어야 한다는 것을 의미한다.

여기서 타임스탬프(Timestamp)는 쉽게 이해해서 '프로세스가 시작되고 종료 될 시간' 정도로 생각하면 된다. 둘 다 불필요한 롤백이 발생한다는 단점이 발생하기는 한다.

5.3. 탐지

데드락을 막는 것이 아닌 데드락이 필연적으로 발생할 것을 가정하고, 현재 시스템상에서 어느 부분에 데드락이 발생했는지를 탐색하는 방식.

그래프를 그림으로써 교착상태가 발생할 수 있는 가능성을 탐지하는 '자원할당 그래프 알고리즘'(Resource-Allocation Graph Algorithm)과 자원할당 그래프 알고리즘을 살짝 변형시킨 'Wait for Graph'가 있다.

5.4. 복구

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

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

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

6. 현실에서의 예시

OTP의 수명이 끝나서 급한 대로 타행 OTP를 연결하려 하니 공인인증서를 요구한다.
공인인증서까지 만료된 상황이라 공인인증서를 다시 발급받으려 하니 OTP 번호를 요구한다.

OTP 문서의 예시로, 이런 경우 은행에 내방하는 것 외에는 방법이 없다.

비슷한 것으로 일과 경력이 있다.

7. 관련 문서

[1] 심하면 운영체제 자체도 포함한다. [2] Four Necessary and Sufficient Conditions for Deadlock [3] resource holding이라고도 한다. [4] 파일을 읽어야 하는데 파일 쓰는중이고 파일을 써야되는데 읽지를 못하고... [5] 완전히 설명하려면 레지스터의 백업이나 스택, 가상 메모리 같은 컴공과 들어가야 배우는 단어가 나오니까 "적절하게"라는 단어로 여기서는 넘어가도록 한다. [6] 역시 편의상 스레드 사이의 넘겨주기는 생략한다. 사실 스레드 전환에도 작업이 필요하기 때문에 한 줄 단위로 번갈아가면서 실행하는 경우는 거의 없다. 하지만 중간에 스레드를 전환할 수 있는 한 값은 언제든지 어긋날 수 있다. [7] Semaphore, 원래 뜻은 "수기 신호" [8] Mutex, Mutual-exclusion lock 즉 상호 배제 잠금이라는 뜻. 이후로는 간단히 락으로 표기한다. [9] 특히 시간적인 타이밍 방식으로 제어하면 자주 생긴다. 두번째 실행을 대기 하기 위하여 1초를 기다리는 경우에 두번째 실행이 여전히 지연같은 예외로 1초를 기다렸으나 여전히 실행중이라면 이런건 작동오류로 이어져 결국 멈추게 된다. [10] Similar to deadlock prevention, deadlock avoidance approach ensures that deadlock will not occur in a system. The term "deadlock avoidance" appears to be very close to "deadlock prevention" in a linguistic context, but they are very much different in the context of deadlock handling. Deadlock avoidance does not impose any conditions as seen in prevention but, here each resource request is carefully analyzed to see whether it could be safely fulfilled without causing deadlock. - Wikipedia [11] Safe sequence를 찾아낼 수 있다면 무조건적으로 Safe State가 보장된다. [12] 계속해서 작업중이었으나, 저장을 안한 엑셀과 엑셀을 참조하는 애드인이 서로 교착상태가 발생하였다고해서 엑셀을 종료하면 안된다는 것을 이해하면 된다.

데드락

1. 개요

2. 발생 조건

2.1. 상호 배제

2.2. 점유 상태로 대기

2.3. 선점 불가

2.4. 순환성 대기

3. 해설

3.1. 비전공자를 위한 설명

3.2. 예시를 동반한 설명

4. 상세

5. 해결 방법

5.1. 예방

5.2. 회피

5.2.1. 은행원 알고리즘

5.2.2. Wait-Die 기법

5.2.3. Wound-Wait 기법

5.3. 탐지

5.4. 복구

6. 현실에서의 예시

7. 관련 문서

분류