DeadLock

개념

 

데드락이란 두개 이상의 프로세스가 필요한 자원을 얻지 못해 상대방의 작업이 끝나기만을 무한정 기다려 아무 작업을 하지 못하는 상태를 가리킵니다.

위 그림은 다중 쓰레드 프로그래밍 환경에서 흔히 발생하는 데드락 문제입니다.

• Thread2는 A를 점유하고 있으면서 B의 자원을 요청, B의 자원을 습득할 때 까지 대기
• Thread3는 B를 점유하고 있으면서 A의 자원을 요청, A의 자원을 습득할 때 까지 대기
• 서로 상대방이 자원을 내놓기를 바라면서 무기한 연기에 빠지는 상황

시스템 파일이나 다른 프로그램이 공유하는 파일을 건드리기 쉬운 프로그램은 설치 과정에서 "프로그램을 설치할 때는 "가능하면 다른 프로그램은 꺼주세요"라는 문장이 나오면서 모든 프로그램이 꺼지는 경우가 있는데, 이유는 데드락이 발생할 수 있는 가능성이 존재하기 때문입니다.

 

전공용어로서 데드락을 설명하면 프로세스가 세마포어를 차지하려는 경쟁에서 발생합니다.

 

💡 세마포어란?
일정 시간 동안 여러 프로세스에서 사용하지만 한 순간에서는 한 프로세스에서만 사용하는 자원

 

임계 구역

임계구역이란 프로세스 영역중에서 공유자원에 접근하는 코드입니다. 그리고 공유자원을 접근하는데 있어서 문제가 발생하지 않도록 한번에 하나의 프로세스만 공유자원을 이용하게끔 보장해 줘야하는 영역입니다.

 

자바 코드로 임계구역의 문제를 예시로 들겠습니다.

public class Task {
    private long sum = 0;
 
    public void calculate() {
        for (long i = 0; i <10000; i++) {
            ++sum;
        }
    }

    public long getSum() {
        return sum;
    }
}

sum이라는 변수에 +1씩 총 1만번 수행하는 코드입니다.

 

try {
    Task task = new Task();

    Thread threadA = new Thread(() -> {
        task.calculate();
    });

    Thread threadB = new Thread(() -> {
        task.calculate();
    });

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

    threadA.join();
    threadB.join();

    System.out.println(task.getSum());
} catch (InterruptedException e) {
    e.printStackTrace();
}

두개의 스레드를 만든뒤 Task의 인스턴스를 공유하여 각각 calculate() 메서드를 호출합니다.

예상되는 값은 20,000입니다. 하지만 코드를 실행해보면 실행할때마다 다른값이 나옵니다.

 

해당 이슈는 두개 이상의 스레드가 sum이라는 하나의 인스턴스 변수에 접근하여 발생한 임계구역 문제의 전형적인 예 입니다.

 

시스템 모델

데드락을 이해하기 전에 컴퓨터 시스템에서 자원을 획득하는 과정을 먼저 알아야 합니다.

1. 자원을 사용하기 위해 프로세스가 특정 자원을 시스템에게 요청합니다.

2. 시스템은 요청받은 자원이 사용가능한지 그렇지 않은지 판단 후, 사용 가능하면 프로세스에게 할당합니다.

3. 자원이 다른 프로세스에 의해 이미 점유되어 있는 경우, 요청 프로세스는 자원이 사용가능해 질때까지 기다립니다.(Wait State)

4. 자원에 대한 허가가 떨어지면 프로세스는 자원을 사용할 수 있습니다.

5. 프로세스는 자원 사용이 끝나면, 시스템에게 반환 요청(해제)을 합니다.

6. 시스템은 자원을 반환 받아 해당 자원이 필요한 프로세스가 있다면 해당 프로세스에게 자원을 할당해줍니다.

 

OS는 자원에 대한 권한을 획득하고 돌려주기 위해 open과 close라는 시스템 콜을 호출하고

메모리(자원)를 확보하고, 해제하기 위해 allocate와 free 시스템 콜을 호출 합니다.

위와 같은 과정은 자원에 대한 요청 -> 사용 -> 해제의 과정으로 볼 수 있습니다.

데드락은 3번과정에서 프로세스가 대기 상태에서 빠져 나오지 못하는 상태를 말합니다.

 

데드락 4가지 발생조건

데드락이 발생하기 위해서는 4가지 조건을 동시에 만족 해야합니다.

다만, 4가지 조건을 모두 만족한다 해서 반드시 데드락이 일어나는건 아닙니다. 통상 교착상태가 일어난 상황을 확인 해보면 4가지 조건에 모두 부합하였습니다.

 

 

4가지 조건을 식사하는 철학자 문제에 빗대어 표현할 수 있습니다.

 

상호 배제(Mutual Exclusion)

매 순간 하나의 프로세스만이 자원을 사용할 수 있습니다.  적어도 하나의 자원을 나 혼자만 점유해서 사용합니다.

프린터 등의 일부 입출력 장치 혹은 연산결과를 저장하는 변수와 같이 동시에 건드리면 위험한 자원들이 있어 해당 속성을 없애는 것은 불가능합니다.

식사하는 철학자 문제 : 포크는 공유될 수 없다.

점유와 대기(Hold and Wait)

최소한 하나의 자원을 소유하고 있는 상태에서 다른 프로세스가 소유하고 있는 자원을 추가로 요청하여 대기하는 상태입니다.

식사하는 철학자 문제 : 모든 철학자들이 왼쪽 포크를 쥔상태로 우측의 포크를 상대방이 놓을때까지 기다리고 있다.

비선점(No Preemption)

자원을 점유하고 있는 프로세스들은 도중으로부터 자원이 해제되지 않습니다.

그 어떤 프로세스도 다른 프로세스가 소유하고 있는 자원을 강제로 뺏아 올 수 없습니다.

해당 속성을 없에면, 프린터가 출력하는 도중 자원을 뺏기거나, Skype에서 녹음기가 마이크를 뺏어와서 마이크 기능이 동작하지 않는 등의 문제가 발생하여 없앨 수 없는 조건 입니다.

식사하는 철학자 문제 : 왼쪽 포크를 놓지 않고 다른 철학자들이 가지고 있는 포크를 강제로 빼앗을 수 없다.

순환 대기(Circular wait)

 

프로세스와 자원들이 원형을 이루며, 각 프로세스는 자신에게 할당된 자원을 가지면서, 상대방 프로세스의 자원을 상호 요청하는 경우입니다.

위그림을 보자면

• P1은 P2가 가진 자원을 요청한 후 기다리는 상태
• P2는 P3이 가진 자원을 요청한 후 기다리는 상태
• P3는 P4가 가진 자원을 요청한 후 기다리는 상태
• P4는 P1이 가진 자원을 요청한 후 기다리는 상태

식사하는 철학자 문제 : 각 철학자들이 왼쪽 포크를 가지면서 오른쪽 포크를 요구하는 상황

 

DeadLock 탐지 방법

자원 할당 그래프

자원할당 그래프는 프로세스가 자원을 요청하고 자원이 프로세스에게 할당되는 방향성을 가진 그래프로서, 해당 그래프를 가지고 데드락 발생 여부를 탐지할 수 있습니다.

 

 

위 그림에서 동그라미(P1, P2, P3)은 프로세스, 사각형(R1, R2, R3, R4)은 자원타입, 사각형 안의 점들은 할당 가능한 자원의 인스턴스 개수입니다.

파랑색 선은 프로세스가 자원을 요청만하고 할당받지 못한 상태(대기 상태)이며, 빨강색 선은 자원이 프로세스에게 할당 되었음을 의미합니다.

 

위 그림을 설명하기 전에 해당 자원들은 여러 프로세스들에 의해 공유될 수 없는 자원이라 가정하겠습니다.

1. P1은 R2의 자원을 점유하고 R1의 자원을 대기 중인 상태 - 점유 대기(Hold and wait)

2. P2는 R1과 R2의 자원을 점유하고 R3의 자원을 대기 중인 상태 - 점유 대기(Hold and wait)

3. P3은 R3의 자원을 가지고 있지만 아무런 추가 자원을 요청하지 않는 상태

 

위 그래프는 P3가 R2의 자원을 요청한 상황입니다.

R2는 이미 할당할 수 있는 자원을 모두 사용했으므로 P3은 대기상태에 빠집니다.

R2는 P2에게 할당되었고, P2는 R3를 기다리고 있습니다. 하지만 R3은 이미 P3에게 할당되어 있습니다.

즉, P2 -> R3 -> P3 - > R2 가 서로 순환대기상태에 빠지게 되어 데드락이 발생했습니다.

 

P1 -> R1 -> P2 -> R2가 순환대기 상태로 보여 데드락인것처럼 보이지만 사실은 아닙니다.

이유는, P3에서 작업이 완료되어 자원을 해제하면 남은 자원을 P1에게 할당할 수 있습니다.

마찬가지로, P4에서 작업이 완료되어 자원을 해제하면 P2에게 할당할 수 있어 순환대기 상태가 아닙니다.

 

DeadLock 처리 방법

예방

예방은 DeadLock의 4가지 조건 중 한가지 이상을 만족하지 못하도록 하는 방법입니다.

상호 배제 방지

자원을 공유하도록 합니다. 예를 들어 Read-Only 전용 자원을 공유하는 방법이 있습니다.

하지만, 프린터와 같은 근본적으로 공유가 불가능한 프로세스가 존재하기 때문에 상호배제를 방지할 수 없습니다.

점유와 대기 방지

프로세스가 어떤 자원도 소유하고 있지 않은 상태에서 자원을 요청하도록 하는 방법입니다.

프로세스를 시작할 때 필요한 모든 자원을 할당받거나, 자원이 필요한 경우 소유하고 있던 자원을 모두 반납하고 다시 일괄요청하는 방식입니다.

점유와 대기 방지는 아래와 같은 단점이 있습니다.

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
• 자원의 활용성이 떨어진다.
• 많은 자원을 사용하는 프로세스는 적은 자원을 사용하는 프로세스보다 자원을 동시에 확보하는 자원 선점에 불리해서 작업이 지연되는 기아 현상이 발생할 수 있다.

💡 기아 현상이란?
특정 프로세스가 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

• 일괄 작업 방식으로 동작한다.
  • 자원을 확보한 프로세스가 자원을 잠깐 사용하든, 오래 사용하든 상관없이 무조껀 필요한 모든 자원을 확보한 후 실행해야 하므로 다른 프로세스는 해당 자원을 기다려야 하는 단점이 있다.

비 선점 방지

자신이 점유하고 있는 자원을 강제로 반납해 다른 프로세스가 선점하게 만듭니다.

만일 어떤 자원을 점유하고 있는 프로세스B가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 프로세스A가 점유하고 있는 모든 자원이 방출되어 필요로 하는 프로세스B에게 선점됩니다.

프로세스A는 자신이 요청하고 있는 새로운 자원은 물론 강제로 방출된 옛 자원들을 다시 획득할 수 있을때에만 작업을 다시 시작할 수 있습니다.

자신이 가지고 있던 상태를 잃어버리고 처음부터 진행해야 하기 때문에 해당 방식을 사용한다면 상태를 쉽게 저장하고 복구할 수 있는 CPU나 Memory에 주로 사용하는 것이 좋습니다.

비선점 방지는 아래와 같은 단점이 있습니다.

• 자원을 빼았을 때 어떤 기준으로 빼았을지, 빼앗은 자원 중 얼마나 사용해야 할지를 결정하는 것이 어렵다.
• 기아현상이 발생할 수 있다.
  • 우선 순위가 높은 프로세스가 자원을 무조껀 선점해버리면 우선순위가 낮은 프로세스는 기아 현상에 빠지게 될 수 있습니다.

순환 대기 방지

점유와 대기를 하는 프로세스들이 순환형태를 이루지 못하도록 막는 방법입니다.

자원을 순환이 아닌 한 방향으로만 사용하도록 설정함으로써 순환대기를 방지합니다.

모든 자원마다 고유의 번호를 부여하고 필요한 자원을 번호가 작은 것 부터 큰 순서대로 획득을 한다면 추가로 필요한 자원들이 어떠한 프로세스에게도 점유되어 있지 않음을 보장한다.

 

위 그림에서 자원 선점을 왼쪼겡서 오른쪽으로 다가갈 순 있지만, 오른족에서 왼쪽으로는 못가게 함으로써 한 방향으로만 사용하도록 만듭니다.

 

예시를 한번 들어보겠습니다.

 

R1과 R2 자원에 대해 우선순위를 부여 했습니다.

1. P1은 R1을 할당받은 상태에서 자원 R2를 기다립니다.

2. P2는 R2를 할당받은 상태에서 R1을 기다립니다. 하지만 R1의 번호가 소유하고 있는 R2의 번호보다 작으므로 P2의 요청이 거절됩니다.

3. P2는 R1을 할당받을 수 없어 강제 종료되고 P1은 R2를 할당받아 정상적으로 실행합니다.

 

즉, 작은 번호의 자원을 사용할 수 없게 하면 원형이 생기지 않습니다.

순환대기 방지는 아래와 같은 단점이 있습니다.

• 프로세스 작업 진행에 유연성이 떨어진다.
  • 자원을 할당받지 못한 프로세스가 만약 중요한 프로세스 였다면 사용자 입장에서는 갑자기 종료되어 결국 사용성이 떨어진다.
• 자원의 번호를 부여하는 기준
  • 프로세스가 큰 번호의 자원을 사용한 후 작은 번호의 자원을 사용할 수 없기 때문에 자원에 번호를 붙이는 데 매우 신중해야 한다.

 

회피

회피 알고리즘은 프로세스가 작업을 완료하는데 필요한 최대 자원의 개수를 OS에게 요청하면, OS는 자원 할당 상태를 검사하여 데드락이 발생할 것 같은 요청은 거절함으로써 데드락이 발생하는 여지를 회피하는 방법입니다.

 

프로세스는 자원의 총수와 할당된 자원의 수를 기준으로 안전상태와 불안정 상태로 나눌 수 있습니다.

안전상태는 OS가 각 프로세스들에게 DeadLock을 피할 수 있는 안전한 순서열로 자원을 배분할 수 있는 상태입니다.

불안전상태는 안전한 순서열이 존재하지 않는 상태로, 교착상태가 발생할 수 있는 가능성이 있습니다.

위 그림은 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날 수록 불안정 상태가 커지는 것을 나타냅니다.

불안정상태에서 항상 데드락이 발생하는 것은 아닙니다. 데드락은 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아질 뿐입니다.

 

즉, 프로세스들이 자원을 요청하면 OS는 안정 상태를 유지할 수 있을 경우에만 자원을 할당해줍니다.

 

💡 방지 vs 회피
방지는 read-only, OS의 선점, 자원을 몰아서 가져가거나 순서대로 자원을 접근 하는 등 프로세스 입장에서 경쟁해야 합니다.
회피의 경우는 특정 알고리즘을 이용하여 애초에 시스템에서 데드락이 발생하지 않도록 자원을 배분해줍니다.

안정상태인지를 판별하는 알고리즘들을 살펴보겠습니다.

 

자원 할당 그래프 알고리즘

 

자원 타입 당 사용할 수 있는 인스턴스가 하나일 경우에만 사용할 수 있는 알고리즘 기법 입니다.

기존의 자원 할당 그래프에서 클레임 화살표가 추가되었습니다. 클레임 화살표란 프로세스가 미래 언젠가 자원을 요청할 수 있다는 것을 나타냅니다.

 

OS는 위와 같은 그래프를 유지하며, 프로세스로부터 자원에 대한 요청을 받으면 순환 대기 상태가 발생하지 않는 경우에만 자원을 할당합니다.

순환 대기 상태를 탐지하기 위해서 써클 탐지(circle-detection) 알고리즘을 사용합니다.

위 그래프를 기준으로 설명하면 아래와 같습니다.

1. P2가 자원 R2을 요청합니다.(그림에선 반영 X)

2. OS는 R2가 어떠한 프로세스에게 할당되지 않은 상태라고 할지라도 P1의 클레임 화살표가 있기 때문에 바로 자원을 할당해주지 않고 대기합니다.

3. P1은 언제든지 R2의 자원을 요청할 수 있습니다. 만일 P2가 R2를 할당받은 시점에서 P1이 R2의 자원을 요청한다면 순환대기 상태가 발생합니다.

4. 이러한 상황을 막기 위해 OS는 애초에 P2의 요청을 거절해 버림으로써 데드락을 회피할 수 있습니다.

 

해당 알고리즘의 단점으로는 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생합니다.

 

은행원 알고리즘

자원 타입 당 사용할 수 있는 인스턴스가 여러개 일 경우에 사용할 수 있는 알고리즘 기법 입니다.

안전 상태와 불안전 상태의 개념을 이용하여 시스템이 프로세스에게 자원을 할당했을 때 안전 상태가 유지되는 경우에만 자원을 할당하고, 그렇지 않은 경우 프로세스는 자원 요청을 하지 않고 대기하게 됩니다.

 

은행에서 대출 금액이 대출 가능한 범위 내이면(안정 상태) 허용되지만, 그렇지 않으면 거부 되는 것과 유사하기 때문에 은행원 알고리즘 이라 불리게 되었습니다.

 

은행원 알고리즘의 핵심은 가능한 자원 내에서 프로세스가 필요로 하는 자원수를 가장 빠르게 맞출 수 있는 것을 먼저 처리할 수 있는 것이 핵심입니다.

 

은행원 알고리즘은 다음과 같은 자료구조가 존재합니다.

 

안정상태인 경우의 예시를 살펴보겠습니다.

현재 OS에서 사용할 수 있는 총 자원의 수는 2개 입니다.

P2의 기대 자원이 2개 이므로 2개를 할당받아 작업을 완료한 후에 6개의 자원을 반환합니다.

총 자원의 수인 6개로 P1 -> P2 혹은 P2 -> P1 순서로 자원을 할당하여 작업을 모두 마칠 수 있는 안전 순서열이 존재합니다.

만약 처음에 2개의 자원을 P1이나 P3에 할당했다면 기대 자원을 충족할 수 없기 때문에 작업을 마칠 수 없습니다.

 

 

불안전 상태인 경우의 예시를 살펴보겠습니다.

총 사용할 수 있는 자원이 1개입니다. 해당 자원으론 어느 프로세스의 기대 자원도 충족할 수 없습니다.

 

은행원 알고리즘은 아래와 같은 단점이 있습니다.

• 할당할 수 있는 자원의 수가 일정해야 한다.
• 사용자 수가 일정해야 한다.
• 항상 불안정 상태를 방지해야 하기 때문에 자원의 이용도가 낮다.
• 최대 자원 요구량(Max)을 미리 알아야 한다.
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

위와 같은 단점들로 인해 은행원 알고리즘은 굉장히 복잡하며 OS에 많은 오버헤드를 야기합니다. 따라서 현재 사용하는 방식은 아닙니다.

 

탐지

예방은 구현하기 어렵고, 회피는 구현할 수 있지만 리소스 낭비라는 문제가 존재합니다.

가장 현실적인 방안은 탐지방법 입니다.

OS가 프로세스의 작업을 관찰하면서 DeadLock의 발생여부를 계속 주시합니다.

만약 DeadLock을 발견하면 이를 해결하기 위한 회복 절차를 밟습니다.

 

탐지 알고리즘은 2가지가 있습니다.

 

대기 그래프 (Wait-for Graph)

 

자원의 인스턴스가 하나만 있는 경우에 사용하는 알고리즘 기법 입니다.

자원 할당 그래프의 변형으로, 자원 할당 그래프에서 자원 노드를 제거하고 프로세스 간의 간선으로 나타낸 그래프 입니 다.  (a)가 자원할당 그래프이며, (b)는 이를 바탕으로 만든 대기 그래프 입니다.

 

Ti -> Tj의 의미는 Ti는 Tj가 가지고 있는 자원들 중 Ti가 필요한 자원이 반납 되기까지 대기중이라는 의미입니다.

Ti -> Tj는 Ti->R와 R->Tj를 포함하는 경우만 대기 그래프가 존재하며, 대기 클래스에서 사이클이 포함되는 경우에만 교착 상태가 발생합니다.

교착 상태 탐지를 위해 OS는 대기 그래프를 유지해야 하며, 주기적으로 사이클을 탐지하는 알고리즘을 호출해야 합니다.

 

쇼사니 & 포크만 (Shoshani & Coffman) 알고리즘

각 자원의 인스턴스가 여러 개일 경우에 사용하는 알고리즘 기법입니다.

은행원 알고리즘의 예시와 같습니다.

 

탐지 알고리즘 사용

탐지 알고리즘을 사용할 경우 아래와 같은 기준을 잡아서 해당 알고리즘을 사용할지 말지 정해야 합니다.

  1. DeadLock이 얼마나 자주 일어나는가?

  2. DeadLock이 일어나면 대략 몇개의 스레드가 포함되는가?

자원 요청에 대해 대기를 해야할 때 탐지 알고리즘을 돌리는 방법도 있습니다. 하지만 자원을 요청할 때마다 탐지 알고리즘을 호출하는 것이기 때문에 많은 오버헤드가 발생합니다.

 

혹은 지정된 시간 간격으로 돌리거나 CPU 이용률을 기준으로 돌릴 수 있습니다. 하지만 이러한 방법은 DeadLock을 야기한 스레드를 단번에 파악하기가 힘듭니다.

 

회복

탐지기법으로 발견한 DeadLock을 회복시키는 작업을 진행합니다.

교착 상태를 유발한 프로세스를 강제로 종료시켜 자원을 회수합니다.

프로세스를 강제로 종료하는 2가지 방법이 있습니다.

• 교착상태를 일으킨 모든 프로세스를 동시에 종료
  • 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 DeadLock을 일으킬 가능성이 큽니다.
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  • 프로세스를 종료할 때 아래와 같은 기준으로 순서를 지정해야 합니다.
    
    • 우선순위가 낮은 프로세스를 먼저 종료
    • 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
    • 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료
• DeadLock이 발생하기 전 상태로 롤백해 강제 종료한 프로세스를 재시작합니다.
• 롤백은 명령어가 실행될 때마다 체크포인트를 만들어 최근의 검사 시점으로 되돌아 갈 수 있게 만들어 줍니다.
• 그러나, 이 방법은 작업량이 상당하여 시스템에 부하를 주므로 체크포인트를 무분별하게 사용하는 것은 좋지 않습니다.
• 탐지와 같이 사용되어 탐지 & 회복 기법으로 불리기도 합니다.

 

무시

DeadLock이 일어나지 않는다고 생각하여 아무런 조치도 취하지 않는 방법입니다.

DeadLock이 매우 드물게 발생하기 때문에 앞서 설명한 예방,회피,탐지,회복 기법들을 사용하는 것이 오히려 오버헤드가 클 수 있습니다.

만약 DeadLock이 발생하여 시스템이 비정상적으로 작동하는 것을 느낀다면 사용자가 직접 프로세스를 죽이는 방식으로 대체합니다.

해당 방식은 UNIX, Windows 등 대부분의 범용 OS에서 채택하는 방식입니다.

 

 

출처

[운영체제 OS]교착상태(데드락Deadlocks) 정의 및 예시

데드락(나무위키)

[iOS] 차근차근 시작하는 GCD — 14

Deadlock(교착상태)1, Deadlock의 정의와 필수 조건

임계 구역 문제 - 스레드

데드락(Deadlock) 개념 정리

Deadlock(교착상태)2, Deadlock 해결 방법(예방, 회피, 검출, 회복)