자바에서 교착상태

서론

---

• 교착상태란 두 개 이상의 프로세스 또는 스레드가 상대방의 작업이 끝나길 하염없이 기다리고만 있는 상태를 말합니다.
• 예를 들면 두 기차가 교차로에 진입했을 때, 두 기차 중 하나의 기차가 지나가는 게 아닌 일단 두 기차 모두 정지하고 상대방이 없어지길 기다린 후 기차가 지나가는 것입니다. 이 예를 보면 기차가 둘 다 정지했는데 어떻게 상대방이 없어지길 기다리고 내가 지나갈 수 있는거지? 라는 생각이 들 것입니다. 이게 바로 교착상태입니다. 앞서 말했듯이 교착상태란 상대방의 작업이 끝나길 하염없이 기다리는데,  상대방 또한 내가 끝나길 하염없이 기다릴 테니 아무런 행동 조차할 수 없는 것이죠

 

교착상태는 어떤 조건하에 발생하는가?

---

교착상태는 상호배제, 점유대기, 비선점, 순환 대기 이러한 4가지 조건이 모두 성립해야 교착 상태가 발생하게 됩니다. 그러면 각각 어떤 의미를 가지고 있는지 살펴보겠습니다.

 

💡 상호배제

 

• 상호배제는 Critical Section(임계구역)에 접근하기 위해서는 Critical Section 내에서 작업 중인 프로세스나 스레드가 있다면 Critical Section에 진입하지 못하고 밖에서 대기하고 있어야 합니다.

💡 점유 대기

 

• 점유 대기는 Critical Section(임계구역)에서 작업 중인 프로세스나 스레드가 있는 상황에서 Critical Section에 진입하고자 하는 프로세스나 스레드가 존재해야 합니다. 
• Critical Section에 진입하고자 하는 프로세스나 스레드가 없다면 교착 상태는 발생하지 않습니다.

💡 비선점

 

• 비선점은 프로세스나 스레드가 자신의 작업이 I/O 작업으로 인해 대기 큐에 적재되던가 또는 작업이 종료되어 Lock을 스스로 방출해야 합니다.

💡 순환 대기

 

• 자원을 기다리고 있는 프로세스나 스레드간 사이클이 형성되어야 합니다.
• 예를들어 스레드 집합 {T0, T1, T2, T3} 이 형성되어 있을 때, T0은 T1이 점유한 자원을 대기하고, T1은 T2가 점유한 자원을 대기하고 있는 사이클이 형성되어야 합니다.

 

교착상태는 어떻게 해결할 수 있을까?

---

• DeadLock이 발생하지 않도록 예방할 수 있습니다.
• DeadLock이 발생할 것을 인지한 상태에서 회피할 수 있습니다.
• DeadLock 발생을 허용하지만 DeadLock을 탐지하여 복구할 수 있습니다.

 

💡 자바에서 DeadLock이 발생하는 경우

 

    DeadLock이 발생하는 코드

 

• 아래의 결과를 보면 ThreadA는 resouceB를 기다리고 있고, ThreadB는 resourceA를 기다리고 있습니다. 이렇게 서로가 서로의 자원을 기다리고 아무것도 못하고 있어 DeadLock이 발생하게 됩니다.

public class Resource {

}

public class ThreadA extends Thread {

    private Resource resourceA;
    private Resource resourceB;

    public ThreadA(Resource resourceA, Resource resourceB) {
        this.resourceA = resourceA;
        this.resourceB = resourceB;
    }

    @Override
    public void run() {
        synchronized (resourceA) {
            System.out.println("ThreadA가 resourceA 자원을 획득하여 사용중입니다.");

            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("ThreadA가 resourceB 자원을 획득하기 위해 기다리고 있습니다.");

            synchronized (resourceB) {
                System.out.println("ThreadA가 resourceA, resourceB 자원을 획득하여 사용중입니다.");
            }
        }
    }
}

public class ThreadB extends Thread {

    private Resource resourceA;
    private Resource resourceB;

    public ThreadB(Resource resourceA, Resource resourceB) {
        this.resourceA = resourceA;
        this.resourceB = resourceB;
    }

    @Override
    public void run() {
        synchronized (resourceB) {
            System.out.println("ThreadB가 resourceB 자원을 획득하여 사용중입니다.");

            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("ThreadB가 resourceA 자원을 획득하기 위해 기다리고 있습니다.");

            synchronized (resourceA) {
                System.out.println("ThreadB가 resourceA, resourceB 자원을 획득하여 사용중입니다.");
            }
        }
    }
}

public class DeadLockTest {

    @Test
    void test() {
        Resource resourceA = new Resource();
        Resource resourceB = new Resource();

        ThreadA threadA = new ThreadA(resourceA, resourceB);
        ThreadB threadB = new ThreadB(resourceA, resourceB);

        threadA.start();
        threadB.start();
    }
}

// 결과
ThreadA가 resourceA 자원을 획득하여 사용중입니다.
ThreadB가 resourceB 자원을 획득하여 사용중입니다.
ThreadA가 resourceB 자원을 획득하기 위해 기다리고 있습니다.
ThreadB가 resourceA 자원을 획득하기 위해 기다리고 있습니다.

 

    그림으로 조금 더 자세히

 

• 아래 사진을 보면 ThreadA가 synchronized 키워드를 사용하여 임계구역에 진입하여 resouceA를 획득하게 됩니다. 그리고 ThreadB도 synchronized 키워드를 사용하여 임계구역에 진입하여 resourceB를 획득하게 됩니다. 그리고 시간이 지나 ThreadA가 resourceB를 점유하고자 하는데 이때 ThreadB가 resourceB를 점유하고 있으므로 대기하게 됩니다. 또한 ThreadB도 마찬가지 입니다.

 

    상호배제

 

• synchronized 키워드를 사용하여 resourceA, resourceB를 동시에 스레드가 사용할 수 없도록 하였습니다.

    점유 대기

 

• synchronized 키워드를 사용하여 임계구역에 하나의 스레드만 진입할 수 있고, ThreadA가 resourceA를 가지고 있는 상태에서 resourceB를 점유하고자 한다면 ThreadB가 resourceB를 가지고 있으므로 ThreadA는 대기하게 됩니다.

    비선점

 

• 스레드의 우선순위 기본값은 NORM_PRIORITY입니다.

    순환 대기

 

• ThreadA는 ThreadB의 resourceB를 기다리고 있고 ThreadB는 ThreadA의 resourceA를 기다리고 있으므로 사이클이 형성됩니다.

    예제의 자원 할당 그래프

🤔 어떻게 해결할 수 있을까?

 

• DeadLock이 발생하기 위해서는 상호 배제, 점유 대기, 비선점, 순환 대기 이렇게 4가지가 성립해야 한다고 했는데 여기서는 순환 대기를 깨트리면서 해결하는 방법을 알아보겠습니다.
• 왜 상호 배제, 점유 대기, 비선점으로 해결할 수 없는지 먼저 알아보겠습니다.

 

    상호 배제로 해결할 수 없는 이유

 

• 우리는 한정적인 자원을 사용할 때, 배타적인 접근을 필요로 하게 됩니다. 하지만 한정적인 자원을 상호 배제를 부정하게 된다면 해당 자원은 공유 자원이 될 수 밖에 없습니다. 이렇게 공유 자원이 되면 동기화 문제가 발생하게 됩니다.

    점유 대기로 해결할 수 없는 이유

 

• 점유 대기가 발생하지 않기 위해서는 일단 스레드가 작업을 하기전 자신이 필요로 하는 자원을 모두 가지고 있어야 합니다. 또한 작업 진행 도중 추가적인 자원이 필요하다면 우선 자신에게 할당되어 있는 자원을 모두 방출한 뒤 다시 자원을 얻어야 합니다.
• 이러한 구조에서는 기아 상태가 발생할 수 있고, 추후 자신이 필요로 하는 자원을 모두 얻었지만 장기간 사용되지 않을 수 있으므로 자원의 낭비가 발생하게 됩니다.

    비선점으로 해결할 수 없는 이유

 

• 비선점을 사용하지 않으면 선점 방식을 사용할 수 있지만 CPU 레지스터나 데이터베이스 트랜잭션처럼 그 상태가 쉽게 저장되고, 복원될 수 있는 자원에는 적용할 수 있지만 일반적으로 Mutex나 Semaphore 같은 자원에는 사용할 수 없다고 합니다.

 

    순환 대기를 깨트려 DeadLock을 회피하는 방법

public class ThreadA extends Thread {

    private Resource resourceA;
    private Resource resourceB;

    public ThreadA(Resource resourceA, Resource resourceB) {
        this.resourceA = resourceA;
        this.resourceB = resourceB;
    }

    @Override
    public void run() {
        synchronized (resourceA) {
            System.out.println("ThreadA가 resourceA 자원을 획득하여 사용중입니다.");

            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("ThreadA가 resourceB 자원을 획득하기 위해 기다리고 있습니다.");

            synchronized (resourceB) {
                System.out.println("ThreadA가 resourceA, resourceB 자원을 획득하여 사용중입니다.");
            }
        }
    }
}

public class ThreadB extends Thread {

    private Resource resourceA;
    private Resource resourceB;

    public ThreadB(Resource resourceA, Resource resourceB) {
        this.resourceA = resourceA;
        this.resourceB = resourceB;
    }

    @Override
    public void run() {
        synchronized (resourceA) { // <<<< 달라진 점 (resourceB -> resourceA)
            System.out.println("ThreadB가 resourceA 자원을 획득하여 사용중입니다.");

            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("ThreadB가 resourceB 자원을 획득하기 위해 기다리고 있습니다.");

            synchronized (resourceB) {
                System.out.println("ThreadB가 resourceA, resourceB 자원을 획득하여 사용중입니다.");
            }
        }
    }
}

public class DeadLockTest {

    @Test
    void test() {
        Resource resourceA = new Resource();
        Resource resourceB = new Resource();

        ThreadA threadA = new ThreadA(resourceA, resourceB);
        ThreadB threadB = new ThreadB(resourceA, resourceB);

        threadA.start();
        threadB.start();
    }
}

// 결과
ThreadA가 resourceA 자원을 획득하여 사용중입니다.
ThreadA가 resourceB 자원을 획득하기 위해 기다리고 있습니다.
ThreadA가 resourceA, resourceB 자원을 획득하여 사용중입니다.
ThreadB가 resourceA 자원을 획득하여 사용중입니다.
ThreadB가 resourceB 자원을 획득하기 위해 기다리고 있습니다.
ThreadB가 resourceA, resourceB 자원을 획득하여 사용중입니다.

 

    그림으로 조금 더 자세히

 

• 위의 예제는 순환 대기를 깨트리는 방법을 사용하여 DeadLock을 회피하도록 되어 있습니다.
• DeadLock을 회피하기 위해서 Safe Sequence(안전 순서)를 찾도록하여 DeadLock을 회피할 수 있습니다. DeadLock을 회피하기 위해서는 Safe State라는 것을 찾을 수 있습니다. 이는 T1, T2, T3, Tn ... 와 같은 스레드가 있을 때 임의의 순서를 지정하여 자원이 흘러가도록 하는 것입니다.(임의의 순서를 지정한다? 라는 표현은 스레드의 start 메서드의 순서가 아닐까 생각해봅니다.) 
  이어 표현하자면, T1가 요청한 자원을 시스템에 현재 남아있는 자원과 앞서 수행을 끝낼 스레드 T2가 반납하는 자원들로 T1을 만족시켜줄 수 있음을 말합니다. 만약 T1가 요청한 자원들을 즉시 만족시킬 수 없을것으로 판단이 되면 T1은 앞선 스레드들이 끝날때까지 기다리고 그 스레드들이 반납한 자원을 추가적으로 사용하게 됩니다.

 

    예제의 자원할당 그래프

 

 

 

 

 

 

참고자료

• https://kdg-is.tistory.com/entry/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C