Deadlock - 교착상태

[목차]

1. DeadLock - 교착상태란?
2. 교착 상태가 발생하는 필요 조건
3. 교착 상태를 해결하는 방법
  3-1. 교착 상태 무시
  3-2. 교착 상태 회피
  3-3. 교착 상태 탐지 및 회복
  3-4. 교착 상태 예방
4. 결론

 

 

| DeadLock - 교착 상태란?

In concurrent computing, a deadlock is a state in which each member of a group waits for another member, including itself, to take action, such as sending a message or more commonly releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, where software and hardware locks are used to arbitrate shared resources and implement process synchronization.
In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock.

 

교착상태를 설명할 때 자주 사용되는 사진이죠?!

 

• 교착 상태(DeadLock)란 운영체제에서 시스템 자원에 대한 요구가 뒤엉킨 상태입니다.
  
  
  
• 즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 끝이 없는 대기에 빠지는 상황을 의미합니다.

 

• 프로세스 A와 B 모두 리소스 A,B를 얻어야 한다고 가정할 경우, T 시점에 프로세스 A가 리소스 A를 얻고 , 프로세스 B가 리소스 B를 얻었다면 T 시점 이후에 프로세스 A와 B는 아직 점유하고 있지 않은 리소스를 기다리게 됩니다. 
  
  
• 하지만, 앞서 언급한 것 처럼, 프로세스 A와 B가 각각 하나의 리소스를 가지고 있기 때문에 두 프로세스는 계속 기다릴 수 밖에 없는 것이죠.
  
  
• 동기화 기법을 사용할 때 발생하게 되는 이슈 중 하나가 쓰레드간의 교착 상태현상입니다. 공유 객체인 A와 B가 존재한다고 할 때, 상호 교차 참조하는 연산을 수행하는 동기화된 블록을 수행할 경우 교착 상태가 발생합니다. 이러한 교착 상태를 방지하기 위해 연산 수행 범위를 최소화하거나 혹은 두 객체의 참조 순서가 같게 합니다.(아래 예제의 방식입니다.) 또한 A,B 객체를 참조하는 별도의 객체를 생성하여 사용하는 방식으로 로직의 수정이 필요합니다.

 

[교착 상태가 발생하는 경우]

public class DeadLockEx {
    public static void main(String[] args) {
        final String resource1 = "Programmers";
        final String resource2 = "DevCourse";

        Thread t1 = new Thread() {
            public void run() {
                synchronized (resource1) {
                    System.out.println("Thread 1: locked resource1");
                    System.out.println("Thread 1: Waiting for resource2");
                    synchronized (resource2) {
                        System.out.println("Thread 1: locked resource2");
                    }
                }
            }
        };

        Thread t2 = new Thread() {
            public void run() {
                synchronized (resource2) {
                    System.out.println("Thread 2: locked resource2");
                    System.out.println("Thread 2: Waiting for resource1");
                    synchronized (resource1) {
                        System.out.println("Thread 2: locked resource1");
                    }
                }
            }
        };

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

출력 결과

[교착 상태를 해결하는 방법 - 자원 순서 변경]

public class DeadLockEx {
    public static void main(String[] args) {
        final String resource1 = "Programmers";
        final String resource2 = "DevCourse";

        Thread t1 = new Thread() {
            public void run() {
                synchronized (resource1) {
                    System.out.println("Thread 1: locked resource1");
                    System.out.println("Thread 1: Waiting for resource2");
                    synchronized (resource2) {
                        System.out.println("Thread 1: locked resource2");
                    }
                }
            }
        };

        Thread t2 = new Thread() {
            public void run() {
                synchronized (resource1) {
                    System.out.println("Thread 2: locked resource1");
                    System.out.println("Thread 2: Waiting for resource1");
                    synchronized (resource2) {
                        System.out.println("Thread 2: locked resource2");
                    }
                }
            }
        };

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

출력 결과

 

| 교착 상태가 발생하는 조건

• 상호 배제 조건(Mutual exclusion condition)
  - 하나의 리소스는 한 번에 한 프로세스 만이 사용할 수 있습니다. 이미 사용중인 리소스를 점유 및 사용하려면 요청한 자원이 해제될때까지 대기해야 합니다.
  
  
• 점유 대기 조건(Hold-and-wait condition)
  - 하나 이상의 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 추가적으로 점유하기 위해 대기하는 프로세스가 존재해야 합니다.
  
  
• 비선점 조건(No-preemption condition)
  - 다른 프로세스에게 할당 및 점유되고 있는 자원은 사용이 끝날 때까지 다른 프로세스가 강제로 뺏을 수 없습니다.
  
  
• 순환 대기 조건(Circular wait condition)
  - 앞서 확인한 그림처럼, 프로세스 A가 프로세스 B가 가지고 있는 자원을 점유하기위해 대기하고, 프로세스 B가 프로세스 A가 가지고 있는 자원을 점유하기 위해 대기하는 것을 의미합니다.
  
  
  

이 4가지 조건을 모두 만족하게 될 경우, 교착 상태에 빠지게 되는 것입니다.

 

| 교착 상태를 해결하는 방법

 

• 교착 상태 무시
  
  
  • 교착 상태 무시방법에서는, 교착 상태가 거의 발생하지 않거나 혹은 발생하지 않을 것이라고 가정을 하는 것입니다. 이러한 방법은 우리가 흔히 사용하고 있는 윈도우와 유닉스등 운영체제에서 이러한 기법을 사용하고 있습니다. 
    
    
  • 성능이 저하되거나 교착 상태가 발생해 문제가 생긴다면 사용자가 인위적으로 프로세스를 종료하거나 시스템을 재부팅하는 식으로 해결합니다.
    
    
    
• 교착 상태 회피
  
  
  • 회피 기법은 교착 상태가 발생할 가능성을 배제하지 않고 교착 상태가 발생할지 않을지를 예상하여 안전 상태(safe state)일때만 자원 요청을 허용하는 방법입니다.
    
    
    
    • 안전 상태(safe state)
      - 교착 상태를 발생하지 않으면서 차례로 모든 프로세스에게 자원을 할당해 줄 수 있는 상태를 의미합니다.
      
      
    • 안전 순서(safe sequence)
      - 프로세스에게 자원을 할당 등의 작업을 할 때 교착 상태를 발생하지 않은 순서를 찾을 경우 그 순서를 안전 순서라고 부릅니다.
      
      
    • 불안전상태(unsafe sequence)
      - 안전 상태가 아닌 상황을 의미하며 교착 상태가 발생할 수 있는 상황입니다. 불안전 상태일 경우에는 안전상태가 될때까지 기다려야 하죠.
      - 교착 상태는 불안전 상태일 경우 일때 발생할 수 있는 것이므로 아래 그림처럼 표현할 수 있습니다.
      

      

      Safe state vs Unsafe state (And DeadLock)

  • 은행원 알고리즘(Banker's Algorithm)
    
    
    • 교착 상태 회피방법의 대표적인 기법으로 자원의 할당에 관한 여부를 결정하기 이전에 자원들에 대한 할당량을 판단 및 시뮬레이션을 하여 Safe state가 될 수 있을지 없을지를 판단합니다.
      
      
    • 즉, 곧 대기중인 다른 프로세스들도 교착 상태가 발생하는지 안하는지를 확인하는 것입니다.
      
      
    • 알고리즘의 예제를 살펴보기 이전에, 은행원 알고리즘을 적용하려면 자원의 양과 프로세스의 수가 일정해야 합니다. 
      
      
    • 은행원 알고리즘 예제
      
      - 현재 가용 가능한 자원의 양은 4라고 가정하겠습니다.
      
      - Max : 프로세스들이 작업을 완료하기 위해 필요한 최종 자원
      - Allocation : 현재 시점에 프로세스에 할당 되어있는 자원
      - Need : 프로세스가 작업을 완료하기 위해 필요한 추가 자원
      
      

      프로세스	Max	Allocation	Need	Available
      P1	8	2	6
      P2	7	4	4
      P3	4	3	5

      1. P1 프로세스는 현재 할당된 자원은 2, 작업을 완료하기 위해 필요한 자원은 6입니다.
      
      2. 하지만, 가지고 있는 자원은 4이므로 작업을 완료할 수 없습니다.
      
      3. 반면, P2 프로세스는 할당된 자원이 4, 필요한 자원이 4 그리고, 현재 가용 가능한 자원이 4이므로 작업을 완료할 수 있습니다. 그러므로, 현재 가용가능한 자원을 P2 프로세스에 할당합니다.
      
      4. P2 프로세스의 작업이 완료된다면, 이전 가용 가능했던 자원(4) - 필요한 자원(4) + 프로세스의 작업을 최종적으로 완료하는데 필요한 자원(7) 을 계산한 7이 가용가능한 자원으로 생겼을 것입니다.
      
      
    • 이와 같이, 프로세스들을 순회하며 , 프로세스들 간의 필요한 자원과 가용가능한 자원들을 비교하며 자원을 할당하는 것이 은행원 알고리즘입니다.
      
      
    • 아무래도, 프로세스의 수와 자원이 고정되어 있다보니, 동적인 환경에 적합하지 않습니다.

 

• 교착 상태 탐지 및 회복
  
  
  • 탐지 기법은 교착상태가 발생했는지 여부를 탐색하는 것입니다.
    
    
  • 현재 시스템의 자원 할당 상태를 가지고 파악하는 것입니다. 대표적으로 자원 할당 그래프를 통해 탐지할 수 있습니다.
    

    

    https://blog.kakaocdn.net/dn/LLO72/btqENZv5gbB/sddKLOkvTXJdmwJoEDGClK/img.png

    - 프로세스로부터 자원에 대한 간선은 자원에 대한 요청을 의미하며 프로세스가 기다리는 상태입니다.
    
    - 자원에서부터 프로세스에 대한 간선은 자원이 해당 프로세스에 할당된 것을 의미합니다.
    
    - 자원을 요청할 때마다 탐지 알고리즘이 호출될 경우 오버헤드가 발생할 수 있습니다.
    
    
    
  • 여기서 잠깐! 오버헤드란?!
    • 오버헤드는 프로그램의 실행흐름에서 나타나는 현상입니다. 이는 예상하지 못한 추가적인 메모리, 자원, 시간 등이 사용되는 것을 일컫습니다. 
      
      
  • 탐지 기법을 통해 데드락을 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하는 방법을 사용해야 합니다.
    
    
    • 회복 방법으로는 크게 2가지를 이야기 할 수 있습니다.
      
      1. 프로세스 중단시키는 방법
      
          1-1. 교착 상태가 발생한 모든 프로세스를 중단시키는 방법
      
          1-2. 프로세스를 하나씩 중단시키며 매번 탐지 기법을 사용하여 확인하는 방법
          -> 1-1번 방법의 경우에는 작업중이던 다른 프로세스마저 중단시킬 수 있다는 단점이 있습니다.
          -> 1-2번 방법의 경우에는 매번 탐지 알고리즘을 호출해야하므로 그에 따른 부담이 생길 수 있습니다.
      
      2. 자원 선점하는 방법
      
          2-1. 교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하는 것입니            다. 이때, 우선순위, 수행된 정도 등 다양한 사항을 고려하여 자원을 선점합니다.
      
      
      
• 교착 상태 예방
  
  
  • 교착 상태가 발생하는 경우는 4가지 조건이 모두 성립될 때입니다. 그러므로, 교착 상태 예방에서는 4가지 조건에 대한 부정하는 방식으로 교착 상태를 해결하고자 합니다.
    
    
  • 상호 배제 부정
    - 한 번에 여러개의 프로세스가 공유 자원을 접근 및 사용할 수 있게 합니다.
    - 하지만, 추후 동기화와 관련한 문제가 발생할 수 있습니다.
    
    
  • 점유 대기 부정
    - 프로세스가 작업을 하는데 필요한 자원을 모두 한번에 필요하고, 모든 자원을 점유할 때까지 작업을 보류하는 방법입니다. 
    
    
  • 비선점 부정
    - 높은 우선순위를 가지고 있는 프로세스가 작업에 필요한 자원(다른 프로세스가 점유하고 있는 자원)을 점유할 수 있도록 합니다.
    
    
  • 순환 대기 부정
    - 기존의 순환 형태가 아닌 일정한 방향으로만 자원을 요구할 수 있도록 합니다. 

 

 

| Conclusion

• 교착 상태는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 끝이 없는 대기에 빠지는 상황을 의미합니다.
  
  
• 교착 상태가 발생하는 조건은 1. 상호 배제 2. 점유 대기 3. 비선점 4. 순환 대기 이며 이 모두를 만족해야지 교착 상태가 발생합니다.
  
  
• 교착 상태를 해결하는 방법은 1. 교착 상태 무시 2. 교착 상태 탐지 및 회복 3. 교착 상태 예방 4. 교착 상태 회피가 있습니다.
  
  
• 문자열(String, StringBuffer, StringBuilder) 포스팅을 한 이후로, 동기화와 관련하여 이어지는 부분이라고 생각합니다. 물론 Java에서의 Lock Interface나 동기화, 락과 관련한 부분에 대한 추가적인 공부를 더 해야할 것 같습니다. 
  
  
• 개념과 예제를 접하긴 했지만, 조금 더 실제 업무에서 접하는 경우의 예시를 더 알아봐야할 것 같다는 생각이 들었습니다. 

 

(참고)

블로그 1

블로그 2

블로그 3

블로그 4