교착상태(Deadlock)

목차

교착상태란?

• 교착상태(Deadlock)란 일어나지 않을 사건을 기다리며 진행을 멈춰버리는 현상입니다.
  • 간단하게 두 프로세스예시를 들어본다면 프로세스 A는 프로세스 B가 사용 중인 자원을 기다리고, 프로세스 B는 프로세스 A가 사용 중인 자원을 기다리고 있는 상태입니다. 이럴 경우 서로 계속 기다리게만 될 것입니다. (교착상태)
• 비유를 통한 교착 상태 예시
  • 도로에서의 교착상태
    • 
    • 
      • 앞으로 지나가야하는데 차들이 가로막고 있어 지나갈 수가 없는 상태입니다.

교착상태(Deadlock)를 만드는 네 가지 조건

• 아래 4가지 조건을 모두 만족하는 경우라면 데드락이 발생합니다.
  
  • Mutual exclusion(상호 배제) : 리소스를 공유해서 사용할 수 없는 경우(임계구역, CPU, 프린터 등)
  • Hold and wait : 프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다리는 경우(wait)
  • No preemption(비선점형) : 리소스 반환(release)은 오직 그 리소스를 취득한 프로세스만 할 수 있는 경우
  • Circular wait : 프로세스들이 순환(circular) 형태로 서로의 리소스를 기다리는 경우
• 도로에서의 교착상태 (자원 : 도로 1,2,3,4 각각이 자원이 됨)
  • 
  • Mutual exclusion : 도로의 한 구역에 여러 차가 있는 것은 말이 안 되는 경우입니다.(예를 들어 도로 1에 차 2대가 있는 경우는 말이 안 됨)
  • Hold and wait : 각 차가 도로 1,2,3,4를 차지했는데, 다음 도로를 가기 위해서 대기하고 있는 상태입니다. (예를 들어 왼쪽에서 온 차는 4번 도로를 차지하고 있는 상태인데, 아래쪽에서 온 차가 점유하고 있는 1번 도로를 기다리고 있는 상태입니다.)
  • No preemption : 각 차가 다른 차가 서있는 도로를 강제로 밀고 갈 수 없습니다. (예를 들어 왼쪽에서 온 차는 4번 도로를 차지하고 있는 상태인데, 아래쪽에서 온 차가 점유하고 있는 1번 도로를 강제로 밀어버리고 갈 수는 없습니다.)
  • Circular wait : 4번에 있는 차는 1번에 있는 차의 도로를, 1번에 있는 차는 2번에 있는 차의 도로를, 2번에 있는 차는 3번에 있는 차의 도로를, 3번에 있는 차는 4번에 있는 차의 도로를 원하는 상태입니다. 즉, 순환 형태로 서로의 리소스를 기다리고 있는 상태입니다.

운영체제에서 교착상태(Deadlock)를 해결하는 방법

데드락 방지

• 데드락 방지
  • 네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인
  • ( Mutual exclusion ) (불가)
    • 리소스를 공유 가능하게 하는 것은 현실적으로 불가능합니다. 리소스를 공유할 때 생기는 문제를 방지하기 위해서 동기화 작업을 진행했었습니다. 그만큼 리소스를 공유 가능하게 한다는 것은 위험부담이 큽니다.
      • 예를 들어 두 차가 한 공간에 있게 하는 것은 불가능합니다.
  • ( Hold and wait ) (가능)
    • 사용할 리소스들을 모두 획득한 뒤에 시작합니다.
      • 예를 들어 왼쪽에서 오는 차의 경우, 4번과 1번 도로를 먼저 칸막이를 설치해서 자신만 갈 수 있도록 확보한 뒤에 시작하는 것입니다.
      • 이러한 경우의 단점은 리소스 사용 효율이 떨어집니다. 4번의 작업이 만약 오래 걸린다고 하면 1번 리소스는 아무도 사용할 수 없기 때문에 그동안 방치한 채 있게 됩니다. (자원 낭비)
    • 혹은 리소스를 전혀 가지지 않은 상태에서만 리소스를 요청하는 것입니다.
      • 예를 들어 왼쪽에서 오는 차의 경우, 4번에 진입한 뒤에 1번을 요청해야 하는데 1번을 요청하기 전에 4번을 반납하고 나서 리소스를 전혀 가지지 않은 상태에서 리소스를 요청하는 것입니다.
  • ( no preemption) (가능)
    • 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 합니다.
      
      • 즉, 자신의 가지고 있는 리소스를 반환하고 기다리는 것입니다. 다른 누군가가 자신의 리소스를 선점할 수 있도록 허용해 주는 것입니다. (Hold and wait에서 제시한 방법 중 하나랑 동일합니다.)
        • 예를 들어 왼쪽에서 오는 차의 경우, 4번에 진입한 뒤에 1번을 요청해야 하는데 1번을 요청하기 전에 4번을 반납하고 나서 리소스를 전혀 가지지 않은 상태에서 리소스를 요청하는 것입니다.
  • ( Circular wait ) (가능)
    • 이 방법이 4가지 데드락 방지 기법 중 가장 많이 사용되는 방식입니다. 
    • 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청하는 것입니다.
      • 예를 들어 왼쪽에 있는 차가 진입할 때, 4번과 1번 공간이 필요한데, 우선적으로 1번부터(오름차순으로) 할당받도록 하는 것입니다. 나머지는 모두 오름차순으로 진행하기 때문에 다른 문제는 없습니다.
      • 
      • 
      • 
      • 
      • 

데드락 회피

• 데드락 회피
  • 실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것 
  • 대표적인 데드락 회피 알고리즘으로 Banker algorithm이 있습니다.
    • 이는 리소스 요청을 허락해 줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때까지 계속 요청을 거절하는 알고리즘입니다.

데드락 감지와 복구

• 데드락 감지와 복구
  • 일단 데드락을 허용하고 데드락이 발생하면 복구하는 전략입니다.
  • 데드락이 감지됐을 때 복구하는 전략 (2가지 존재)
    • 1. 전략 프로세스를 종료시키기
      • 모든 프로세스를 강제로 종료시키기
      • 아니면 한 프로세스씩 종료시키면서 데드락이 해결되는지 보기
      • 지금까지 작업한 내용을 잃을 수 있기 때문에 리스크가 큰 전략
    • 2. 리소스의 일시적인 선점을 허용하기
      • 다른 프로세스가 내가 획득한 리소스를 선점하는 것을 허용하는 것입니다.
      • 이는 방지 부분에서 했던 작업처럼 이미 해당 문제가 발생했을 때 선점하도록 허용해 주는 것입니다.

데드락 무시

• 데드락 무시
  • 개발자가 알아서 하겠지 하고 운영체제가 일을 안 하는 것입니다.

프로그래밍에서 데드락 해결하기

• 운영체제가 데드락을 해결해주지 않는다면 개발자가 직접 데드락을 해결해야 합니다. 
• 아래는 데드락이 발생하는 경우입니다.
  
  • 
    • Thread t1과 Thread t2는 멀티 코어 환경에서 실행되면 병렬적으로 실행될 것입니다. 
    • 따라서 이제 Thread t1은 lock1을 획득하고 해당 임계구역으로 들어갈 것이고, Thread t2는 lock2를 획득하고 임계구역으로 들어가게 될 것입니다.
    • 이제 Thread t1의 경우 해당 임계구역에서 lock2를 획득해야지만 다음 임계구역 코드로 진입할 수 있습니다. 하지만 이제 Thread t2가 lock2를 가지고 있는 상태이기 때문에 다음 임계구역 코드로 진입할 수 없습니다.
    • 마찬가지로 Thread t2의 경우에도 해당 임계구역에서 lock1을 획득해야지만 다음 임계구역 코드로 진입할 수 있습니다. 여기서도 Thread t1이 lock1을 가지고 있는 상태이기때문에 Thread t1과 Thread t2가 서로의 lock만을 기다리는 상태가 됩니다.
    • 따라서 데드락이 발생하게 됩니다.
• 이 경우에도 운영체제가 데드락을 방지하기 위해 했던 방식처럼 데드락 발생 조건 4가지 중 한 가지를 제거하면 됩니다.
  • 우선 코드상 상호배제(mutual exclusion) 조건을 없앨 수 있는 상황인지 먼저 확인해 봅니다. 만약 lock이 없이도 코드를 구현할 수 있다면 이를 제거해 데드락을 해결할 수 있습니다.
  • 다음으로 hold and wait이나 no preemptive 조건을 없앨 수 있게 자신의 가지고 있는 리소스를 반환하고 기다리도록 만들면 됩니다. (즉, 중첩 부분을 제거해 줍니다.
    • 위 코드에서 synchronized (lock1) 부분과 synchronized (lock2) 부분을 중첩으로 작성하는 것이 아닌 따로따로 작성을 해주는 것입니다.
    • 이렇게 작성할 경우 Thread 1의 경우 lock 1을 반환하고 lock2를 대기하게 되고, Thread 2의 경우도 lock2를 반환하고 lock1을 대기하게 됩니다.
    • 프로그램이 정상적으로 작동하게 될 것이고, 데드락 문제를 해결할 수 있습니다.
  • 마지막으로 Circular wait 조건을 없앨 수 있게 순서 체계를 부여해서 오름차순으로 리소스를 요청하는 것입니다. 
    • 현재 코드에서 Thread 1의 경우 lock1 → lock2 순서로 진행하고, Thread 2의 경우 lock2 → lock1 순서로 진행하고 있습니다. 
    • 이를 이제 Circular wait 조건을 없애기 위해 오름차순으로 코드를 변경해 줍니다. 즉, Thread 2를 lock1 → lock2 순서로 진행하도록 변경해줍니다. 
    • 이렇게 코드를 작성할 경우 정상적으로 작동하게 되고, 데드락 문제가 해결될 것입니다.

출처

• https://www.youtube.com/watch?v=ESXCSNGFVto