Deadlock

교착상태(Deadlock)란?

동기화 기법을 사용하는 시스템에서 두 개 이상의 프로세스나 스레드가 서로가 가진 리소스를 기다리면서 무한 대기에 빠지는 상태를 의미한다.

 

데드락 발생의 네 가지 조건

데드락이 발생하려면 다음 네 가지 조건이 모두 충족되어야 한다. 이 조건들 중 하나라도 충족되지 않으면 데드락이 발생하지 않는다.

1. Mutual Exclusion (상호 배제): 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
2. Hold and Wait (점유 및 대기): 최소한 하나의 자원을 점유한 상태에서 다른 자원을 추가로 요청하며, 해당 자원이 할당될 때까지 대기하는 프로세스가 있다.
3. No Preemption (비선점): 다른 프로세스에 할당된 자원을 강제로 빼앗을 수 없다. 자원을 사용하는 프로세스는 자발적으로 자원을 해제할 때까지 그 자원을 계속 점유한다.
4. Circular Wait (순환 대기): 여러 프로세스가 서로 자원을 기다리며, 이들 프로세스가 원형으로 연결되어 있는 상태

 

데드락 해결 방법

• 데드락 방지 (Deadlock Prevention)
  • 시스템 설계에서 네 가지 데드락 조건 중 하나라도 충족되지 않도록 하는 방법
  • Mutual Exclusion (상호 배제)
    • 리소스를 공유 가능하게 설계하여 상호 배제를 피할 수 있지만, 현실적으로 이는 어렵다. 대부분의 경우, 상호 배제는 불가피하므로 이를 완전히 해결하기는 어려운 경우가 많다.
  • Hold and Wait (점유 및 대기)
    • 리소스 집합 요청: 프로세스가 작업을 시작하기 전에 필요한 모든 리소스를 한 번에 요청하고 확보한 후 작업을 시작하게 한다. 그러나 이 방법은 리소스를 과도하게 사용하게 할 수 있어 자원의 낭비를 초래할 수 있다.
    • 리소스 요청 규칙: 리소스를 전혀 가지지 않은 상태에서만 새 리소스를 요청하게 하는 방법도 있다.
  • No Preemption (비선점)
    • 선점 가능: 추가 리소스가 필요할 때, 프로세스가 이미 가진 리소스를 다른 프로세스가 사용할 수 있도록 선점할 수 있게 한다. 이 방법은 시스템의 복잡성을 증가시키고, 리소스를 되돌리는 과정에서 오버헤드가 발생할 수 있다.
  • Circular Wait (순환 대기)
    • 순서 지정: 모든 리소스에 순서를 부여하고, 프로세스가 리소스를 요청할 때 오름차순으로 요청하도록 강제하여 순환 대기를 방지한다. 예를 들어, 리소스에 순서 번호를 매기고, 프로세스는 더 높은 번호의 리소스만 요청하도록 규칙을 설정할 수 있다.
• 데드락 회피 (Deadlock Avoidance):
  • 데드락 회피는 실행 중인 시스템에서 데드락을 방지하기 위해 자원의 할당을 동적으로 조정한다. 이를 위해 시스템은 현재의 자원 상태와 프로세스의 자원 요구 사항에 대한 추가적인 정보를 사용하여 자원 요청을 허용할 수 있는지 여부를 결정한다.
  • Banker’s Algorithm은 자원 할당 문제를 해결하기 위한 강력한 도구이지만, 실제 구현에서는 성능 오버헤드와 복잡성 문제로 인해 사용이 제한될 수 있다. 이 외에도 다양한 데드락 회피 기법이 있으며, 특정 상황에 맞는 기법을 선택하여 적용하는 것이 중요하다.
• 데드락 감지와 복구 (Deadlock Detection and Recovery)
  • 데드락이 발생할 가능성을 허용하고, 실제로 발생했을 때 이를 감지하고 복구하는 방법이다. 복구 방법으로는 프로세스를 종료하거나, 리소스를 일시적으로 선점하도록 허용할 수 있다.
• 데드락 무시 (Ignoring Deadlock)
  • 데드락이 발생할 확률이 매우 낮다고 판단하여 특별한 조치를 하지 않는 방법이다.

 

프로그래밍 레벨에서의 데드락

t1은 lock1을 획득한 상태에서 lock2를 기다리고, t2는 lock2를 획득한 상태에서 lock1을 기다리게 되어 교착 상태에 빠질 수 있다.

public class Main {
    public static void main(String[] args) {
        Object lock1 = new Object();
        Object lock2 = new Object();

        Thread t1 = new Thread(() -> {
            synchronized(lock1) {
                System.out.println("[t1] get lock1");
                synchronized(lock2) {
                    System.out.println("[t1] get lock2");
                }
            }
        });

        Thread t2 = new Thread(() -> {
            synchronized(lock2) {
                System.out.println("[t2] get lock2");
                synchronized(lock1) {
                    System.out.println("[t2] get lock1");
                }
            }
        });

        t1.start();
        t2.start();
    }
}

해결 방법

1. Mutual Exclusion이 꼭 필요한지 고려한다. 불필요한 경우 사용을 피한다.
2. Mutual Exclusion이 필요하다면, 리소스 요청에 순서를 부여하여 순환 대기를 방지한다.
3. 리소스를 반환한 후 다른 리소스를 요청하는 방식을 고려한다. 프로세스가 리소스를 반환한 후에 다른 리소스를 요청하게 하여 교착 상태를 방지할 수 있다.
4. 이 외에도, 타임아웃(timeout)을 설정하여 일정 시간이 지나면 리소스 요청을 포기하고 다른 작업을 시도하는 방법이나, 리소스를 최소한으로 사용하여 데드락의 가능성을 줄이는 등의 방법도 고려할 수 있다.