데드락(Deadlock)

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

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

쓰레드 데드락

데드락이란, 둘 이상의 쓰레드가 lock 을 획득하기 위해 기다리는데, 이 lock 을 잡고 있는 쓰레드도 똑같이 다른 lock 을 기다리며 서로 블록 상태에 놓이는 것을 말한다. 데드락은 다수의 쓰레드가 같은 lock 을, 동시에, 다른 명령에 의해, 획득하려 할 때 발생할 수 있다.

예를 들자면, thread1 이 A 의 lock 을 가지고 있는 상태에서 B 의 lock 을 획득하려 한다. 그리고 thread2 는 B 의 lock 을 가진 상태에서 A 의 lock 을 획득하려 한다. 데드락이 생긴다. thread1 은 절대 B 의 lock 을 얻을 수 없고, 마찬가지로 thread2 는 절대 A 의 lock 을 얻을 수 없다. 두 쓰레드 중 어느 쪽도 이 사실을 모를 것이며, 쓰레드들은 각자의 lock - A 와 B 의 - 을 가진 채로 영원히 블록 상태에 빠진다. 이러한 상황이 데드락이다.

아래와 같이 표현된다:

Thread 1  locks A, waits for B
Thread 2  locks B, waits for A

그리고 다음은 서로 다른 인스턴스가 동기화된 메소드를 호출하는, TreeNode 클래스의 예제이다.

public class TreeNode {
 
  TreeNode parent   = null;  
  List     children = new ArrayList();

  public synchronized void addChild(TreeNode child){
    if(!this.children.contains(child)) {
      this.children.add(child);
      child.setParentOnly(this);
    }
  }
  
  public synchronized void addChildOnly(TreeNode child){
    if(!this.children.contains(child){
      this.children.add(child);
    }
  }
  
  public synchronized void setParent(TreeNode parent){
    this.parent = parent;
    parent.addChildOnly(this);
  }

  public synchronized void setParentOnly(TreeNode parent){
    this.parent = parent;
  }
}

Thread1 이 parent.addChild(child) 메소드를, Thread 2 는 child.setParent(parent) 메소드를 각각 동시에, 같은 parent 와 child 인스턴스에 호출한다면,데드락이 발생할 수 있다.

이에 대한 유사코드가 있다:

Thread 1: parent.addChild(child); //locks parent
          --> child.setParentOnly(parent);

Thread 2: child.setParent(parent); //locks child
          --> parent.addChildOnly()

먼저, Thread 1 이 parent.addChild(child) 를 호출한다. addChild() 는 동기화된 메소드이기 때문에 Thread 1 은 parent 객체를 다른 쓰레드로부터의 접근을 막도록 lock 을 건다.

다음으로 Thread 2 은 child.setParent(parent) 를 호출한다. setParent() 역시 동기화된 메소드이고, Thread 2 는 child 객체를 다른 쓰레드로부터의 접근을 막도록 lock 을 건다.

이렇게 child 와 parent 객체들은 두 개의 다른 쓰레드에 의해 lock 이 걸린다. 그리고 Thread 1 은 child.setParentOnly() 메소드 호출을 시도하는데, 이 child 객체는 Thread 2 에 의해 lock 이 걸린 상태이고,Thread 1 은 블록 상태가 된다. Thread 2 는 또한 parent.addChildOnly() 호출을 시도하지만, parent 객체는 Thread 1 에 의해 lock 이 걸린 상태이고 Thread 2 역시 블록 상태가 된다. 이제 두 쓰레드 모두 서로가 잡고 있는 lock 을 기다리며 블록 상태가 된다.

주목할 점: 위 설명에 나와있듯, 이 두 쓰레드의 parent.addChild(child) 와 child.setParent(parent) 호출은 반드시 동시에, 서로의 parent, child 인스턴스에 대해 호출하여야만 데드락이 발생할 수 있다. 위 코드는 갑자기 데드락이 발생하기 전 까지는 정상적으로 작동할 수 있다.

쓰레드들은 정말로 lock 을 '동시에' 획득해야만 한다. 예를 들어, Thread 1 이 Thread 2 보다 약간 앞선다면, 그래서 child 와 parent 양쪽에 모두 lock 을 걸어버린다면, Thread 2 는 child 의 lock 을 획득하려 할 때 이미 블록 상태에 빠질 것이다. 이렇게 되면 데드락은 없다. 쓰레드의 스케쥴링은 예측할 수 없는 경우가 많기 때문에, 데드락이 '언제' 발생할지는 알 수 없다. 그저 '발생할 수 있을' 뿐이다.

더 복잡한 데드락

데드락은 셋 이상의 쓰레드에서도 발생할 수 있다. 이런 현상은 감지되기 더 어렵다.

다음은 네 쓰레드가 데드락에 빠진 예제이다.

Thread 1  locks A, waits for B
Thread 2  locks B, waits for C
Thread 3  locks C, waits for D
Thread 4  locks D, waits for A

Thread 1 은 Thread 2 를 기다리고, Thread 2 는 Thread 3 을, Thread 3 은 Thread 4 를 기다린다. 그리고 Thread 4 는 Thread 1 을 기다린다.

데이터베이스 데드락

데드락이 발생할 수 있는 더 복잡한 상황은, 데이터베이스 트랜젝션이다. 데이터베이스 트랜젝션은 많은 SQL 업데이트 요청으로 구성되곤 한다. 한 트랜잭션에서 어떤 레코드에 대해 업데이트가 수행될 때, 이 레코드는 업데이트 수행을 위해 다른 트랜잭션의 접근을 막도록 lock 이 걸린다. 이 lock 은 업데이트를 수행하는 트랜젝션이 끝날 때까지 지속된다. 같은 트랜잭션 안에서의 각 업데이트는 데이터베이스의 레코드들에 lock 을 걸 수 있다.

다수의 트랜젝션이 동시에 같은 레코드들을 업데이트한다면, 이는 데드락에 빠질 위험성이 있다.

예제:

Transaction 1, request 1, locks record 1 for update
Transaction 2, request 1, locks record 2 for update
Transaction 1, request 2, tries to lock record 2 for update.
Transaction 2, request 2, tries to lock record 1 for update.

여기서 lock 은 서로 다른 요청에 의해 잡혀있고, 어느 쪽도 먼저 알려져 있지 않기 때문에, 데이터베이스 트랜젝션에서의 데드락은 감지하거나 방지하기가 어렵다.