데드락 방지(Deadlock Prevention)

이 글은 원 저자 Jakob Jenkov의 허가로 포스팅된 번역물이다.

원문 URL : http://tutorials.jenkov.com/java-concurrency/deadlock-prevention.html

상황에 따라 데드락을 방지하는 것이 가능하다. 여기서는 세 가지 기술을 소개한다.

1. 락 정렬
2. 락 타임아웃
3. 데드락 감지

락 정렬

데드락은 다수의 쓰레드들이 같은 락들을 필요로 하면서 서로 다른 순서로 서로의 락을 획득하려 할 때 발생한다.

만약 모든 락이 항상 같은 순서로 획득된다는 보장이 있다면, 데드락은 발생할 수 없다. 다음 예제를 보자:

Thread 1:

  lock A 
  lock B


Thread 2:

   wait for A
   lock C (when A locked)


Thread 3:

   wait for A
   wait for B
   wait for C

한 쓰레드가 여기 Thread 3 처럼 다수의 락을 필요로 한다면, 이 쓰레드는 반드시 정해진 순서로 락을 획득하여야 한다. 이 쓰레드의 락 획득은 정해진 순서 안에서 이전 락을 획득할 때까지 다음 락을 획득할 수는 없다.

예를 들어서, Thread 2 나 Thread 3 은 먼저 A 의 락을 획득해야 C 의 락을 획득할 수 있다. Thread 1 이 A 의 락을 잡고 있기 때문에, Thread 2 와 Thread 3 은 일단 A 의 락이 풀릴 때까지 기다려야 하고, B 나 C 의 락을 시도하기 전에 반드시 A 의 락을 계속 시도하게 된다.

락 정렬은 아직까지 효과적인 데드락 방지 기술이다. 하지만, 이 방법은 획득하려는 락의 순서를 알고 있는 상태에서만 사용될 수 있다. 언제나 사용할 수 있는 방법은 아니다.

락 타임아웃

다른 데드락 방지 기술로는 락 시도에 타임아웃을 거는 방법이 있다. 이 타임아웃이란 쓰레드가 락을 획득하기 위해 기다리는 시간을 정해놓는다는 것을 의미한다. 락 타임아웃을 건 쓰레드가 주어진 시간을 소진하기까지 락을 획득하지 못하면 쓰레드는 이 락을 포기한다. 만약 쓰레드가 반드시 획득해야 하는 락에서 타임아웃이 걸리면, 이 쓰레드가 잡고 있는 모든 락을 해제하고 '얼마간의' 시간을 기다린 뒤 다시 락을 시도한다. 이 얼마간의 시간이란, 같은 락(타임아웃이 걸린)을 획득하려는 다른 쓰레드에게 모든 락을 획득할 기회를 주는 것이다. 때문에 이런 경우에는 어플리케이션이 어디에도 락을 걸지 못하고 계속 돌아가는 경우가 생길 수도 있다.

다음 예제는 두 쓰레드가 다른 순서로 같은 두 락을 획득하려 하다가 재시도를 하게 되는 경우이다:

Thread 1 locks A
Thread 2 locks B

Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked

Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.

Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.

위 예제에서 Thread 2 는 Thread 1 보다 약 200 밀리초 먼저 락 획득을 시도하게 될 것이다. 그리고 Thread 1 는  락 A 획득을 위해 기다리다가 Thread 2 의 작업이 끝나면 락을 획득할 수 있게 된다(그 사이 Thread 2 나 다른 쓰레드가 끼어들어 락을 가져가지 않는다면).

여기서 기억할만한 점은, 락 타임아웃은 꼭 데드락에 대해서만 발생하지 않는다는 것이다. 락 타임아웃은 데드락 뿐만 아니라, 단순히 작업을 처리하기 위해 락을 오래 잡고 있게 되면 얼마든지 발생할 수 있다.

이에 더하여, 만약 충분한 수의 쓰레드들이 공유 자원에 대한 작업을 완료한다 해도 이 쓰레드들은 여전히 동시에 자원에 접근한다는 위험부담을 감수해야 하고, 이 사실은 타임아웃과 백업을 적용하더라도 마찬가지다. 타임아웃은 두 쓰레드간의 대기시간이 0 에서 500 밀리초 사이인 경우는 발생하지 않을 수 있지만, 쓰레드의 수가 10이나 20 정도로 많아지면 상황은 달라진다. 두 쓰레드간의 동기 대기에 있어서 발생할 공산이 훨씬 높다.

락 타임아웃 메카니즘의 문제점은 동기화블록에의 진입에 대해서는 타임아웃을 설정할 수 없다는 것이다. 이를 위해서는 커스턴 락 클래스를 만들거나 java.util.concurrency 패키지의 컨커런시 구조를 사용해야 한다. 커스텀 락 클래스 작성은 그리 어렵지는 않지만 이 글의 범위를 벗어나는 일이다. 자바 컨커런시의 다음 글에서 이를 다뤄보기로 한다.

데드락 감지

데드락 감지는 더 무거운 데드락 방지 메카니즘이다. 이것은 락 정렬이나 락 타임아웃으로 커버할 수 없는 상황에 적용될 수 있다.

한 쓰레드가 락을 획들하면 이는 쓰레드와 락의 데이터 스트럭처(맵, 그래프 기타등등) 에 알려진다. 쓰레드가 락을 요청할 때는 언제나 이 데이터 스트럭처에 알려진다.

한 쓰레드가 락을 요청했는데 이 요청이 거부된다면, 이 쓰레드는 데드락을 체크하기 위해 락 그래프를 가로지르며 횡단한다. 예를 들어, Thread A 가 7번 락을 요청했는데 7번 락이 Thread B 에 잡혀 있다면, Thread A 는 Thread B 가 자신(Thread A)이 가진 락들 요청하지 않았는지 체크한다. 만약 thread B 가 욫어을 했엇다면, 데드락이 발생한다.

물론 실제 데드락 시나리오는 두 쓰레드간에 발생하는 방황보단 훨씬 복잡할 수 있다. Thread A 는 Thread B 를 기다리고, Thread B 는 Thread A 를 기다릴 수 있다. Thread A 가 데드락을 감지하기 위해서는 Thread B 에 의해 요청된 락을 수동적으로 확인해야 한다. Thread B 의 락 요청에서부터, Thread A 는 Thread C 로, Thread C 는 Thread D 로, Thread A 가 가진 락을 찾아나가게 된다. 그리고 락을 찾으면 데드락이 발생한다.

아래는 네 개의 쓰레드로부터 요청된 락들의 그래프이다. 이건 데이터 구조가 데드락 감지를 위해 쓰인다.

그래서, 데드락이 감지되면 쓰레드는 무엇을 하는걸까?

한가지 가능한 일은 모든 락을 해제하고, 백업하고, 무작위의 시간을 대기한 뒤 재시도하는 것이다. 이것은 락 타임아웃 메카니즘과 비슷한데, 락 타임아웃에서의 쓰레드는 백업까지만 수행한다. 하지만 백업-대기 를 수행하더라도 만약 많은 수의 쓰레드가 같은 락을 요청한다면 쓰레드들은 결국 반복적으로 데드락에 빠질 수 있다.

여기서 더 나은 선택은, 쓰레드의 우선순위를 정하여 한 번에 한 쓰레드(혹은 적은 수, 몇 개의 쓰레드)만 백업을 하도록 하는 것이다. 남은 쓰레드들은 마치 데드락이 발생하지 않은 것처럼, 필요한 락 획득을 계속해서 시도할 것이다. 만약 쓰레드의 우선순위가 고정적이라면, 동일한 쓰레드들은 언제나 높은 우선순위를 가지게 될 것이다. 이를 방지하기 위해 데드락이 감지될 때마다 우선순위 할당을 랜덤하게 하는 방법이 있다.