어뗜 경우에 데드락과 같이 활동성에 문제가 되는지 살펴보고, 이런 상황을 미연에 방지하는 방법

10.1 데드락

• 식시하는 철학자 문제

  

  • 데드락이 발생하는 경우

    • 모든 철학자가 왼쪽 포크를 든다면 아무도 오른쪽 포크를 들 수 없어 데드락이 발생한다.

      

  • 데드락을 방지하는 경우

    • 기아 상태 (starvation) 에 빠지는 경우
      • 어떤 철학자가 왼쪽 포크를 들었을 떄, 오른쪽 포크를 들 수 있는지 확인한다. 만약 오른쪽 포크를 들 수 없다면, 왼쪽 포크를 내려놓고 기다린 뒤 다시 들어보기를 반복한다.
        • 모든 철학자가 동시에 왼쪽 포크를 든 뒤에 전부 오른쪽 포크를 들 수 없어, 동시에 왼쪽 포크를 내려놓고 기다린 뒤에 다시 왼쪽 포크를 들기를 반복할 수 있다.
    • 세마포어 (semaphore) 를 사용하는 경우

      • 뮤텍스 락을 획득하면 임계 영역으로 진입해 왼쪽과 오른쪽의 포크를 모두 들고 먹은 뒤, 다시 뮤텍스의 락을 획득하면 임계 영역으로 진입해 왼쪽과 오른쪽의 철학자를 깨운다.

        • 전역 뮤텍스로 이진 세마포어 mutex 를 사용하고, 왼쪽과 오른쪽의 포크 쌍에 해당하는 이진 세마포어의 배열 s[N] 을 사용한다.

        

        • 왜 put_forks() 에서 test(LEFT), test(RIGHT) 을 할까?
          • test() 에서 주변의 철학자 중 1명이 EATING 상태여서 if 문을 통과하지 못하면, up(&s[i]) 를 하지 않고 임계 영역을 벗어나 down(&s[i]) 에서 대기한다.
            • 임계영역 안에서 대기하면 다른 스레드가 포크를 놓을 수 없기 떄문에, 임계영역 밖의 down(&s[i]) 에서 기다린다.
          • down(&s[i]) 에서 대기하는 스레드를 깨우기 위해 test(LEFT), test(RIGHT) 한다.

            • 인터페이스의 관점으로 볼 땐 sleep() 이나 join() 상태의 스레드를 interrupt() 을 사용해 깨운 것과 같지 않을까?

            • 자바의 interrupt() 도 마찬가지로 세마포어를 사용해 스레드 간 통신하고 있을까?

              https://github.com/openjdk/jdk/blob/master/src/hotspot/share/runtime/javaThread.cpp#L538

              https://github.com/openjdk/jdk/blob/master/src/hotspot/os/posix/os_posix.cpp#L1628

              

              • POSIX 스레드 API 로 뮤텍스를 제어하는 것으로 보아 비슷하게 처리한다.

• 데이터베이스 시스템의 데드락

  • 데이터베이스의 트랜잭션 처리 시 여러 개의 락이 필요할 수 있고, 한 트랜잭션 안에서 락이 걸리면 트랜잭션이 커밋될 때까지 풀리지 않는다.
    • 1개의 락에 대해 2개 이상의 트랜잭션이 데드락 상태에 빠질 수 있고, 외부에서의 조치가 없다면 트랜잭션은 영원히 끝나지 않고 대기한다.
      • 데이터베이스 서버가 트랜잭션 간에 데드락이 발생했다는 사실을 확인하고 나면, 데드락이 걸린 트랜잭션 가운데 희생양을 하나 선택해 트랜잭션을 강제 종료시킨다.
      • 트랜잭션을 요청했던 애플리케이션에서 중단된 트랜잭션을 재시도 처리할 수 있다.

• JVM 의 데드락

  • JVM 은 데이터베이스 서버와 같이 데드락 상태를 추적할 수 있는 기능이 없어, 자바 프로그램에서 데드락이 발생하면 강제 종료하기 전까지 영원히 멈춘 상태로 유지된다.

    • 데드락이 걸린 스레드가 어떤 스레드인지에 따라

      • 애플리케이션 자체가 완전히 멈춰버릴 수도 있고

      • 일부 모듈만 동작을 멈출 수도 있고
      • 전체적인 성능이 떨어지는 정도의 영향만 줄 수도 있다.

10.1.1 락 순서에 의한 데드락

[예시] 2개의 스레드가 서로 다른 순서로 락을 확보할 때 발생 가능한 데드락

public class LeftRightDeadlock {
    private final Object left = new Object();
    private final Object right = new Object();

    public void leftRight() {
        synchronized (left) {
            synchronized (right) {
                doSomething();
            }
        }
    }

    public void rightLeft() {
        synchronized (right) {
            synchronized (left) {
                doSomethingElse();
            }
        }
    }

    void doSomething() {
    }

    void doSomethingElse() {
    }
}

• 2개의 스레드에서 같은 순서로 락을 확보한다면 데드락이 발생하지 않는다.

10.1.2 동적인 락 순서에 의한 데드락

프로그램을 작성할 때 데드락을 방지할 수 있을 만큼 락을 사용하는 순서를 충분히 조절하지 못할 수도 있다.

[예시] 함수에 넘겨주는 인자의 순서에 따라 락 순서가 달라질 때 발생 가능한 데드락

public static void transferMoney(Account fromAccount,
                                 Account toAccount,
                                 DollarAmount amount)
        throws InsufficientFundsException {
    synchronized (fromAccount) {
        synchronized (toAccount) {
            if (fromAccount.getBalance().compareTo(amount) < 0)
                throw new InsufficientFundsException();
            else {
                fromAccount.debit(amount);
                toAccount.credit(amount);
            }
        }
    }
}

- 스레드 A: transferMoney(myAccount, yourAccount, 10); // myAccount -> yourAccount 
- 스레드 B: transferMoney(yourAccount, myAccount, 20); // yourAccount -> myAccount