[컴퓨터공학] 교착 상태(Dead Lock)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

 

 

이번 포스팅에서는 공유 자원을 두고 발생하는 교착 상태에 대해 알아보겠습니다.

교착 상태(Dead Lock)

 지난 포스팅에서 임계 구역에 여러개의 스레드가 접근시 발생할 수 있는 문제와, 이를 막기 위한 뮤텍스 락과 세마포에 대해 알아보았습니다. 이런 수단들을 사용하면 스레드들을 상호 배제시킬수 있지만, 잘못하면 특정 공유자원을 할당받지 못해 계속 대기만 하는 상황이 발생할 수 있습니다. 이렇게 스레드(프로세스)들이 자원 할당을 기다리며 무기한 대기하는 상황을 교착 상태(Dead Lock)라고 합니다.

 

 다음은 C#으로 작성한 교착 상태가 발생하는 예제 코드입니다.

class Alpha
{
    static object alphaObj = new object();

    public static void Test()
    {
        lock(alphaObj) // alphaObj 점유
        {
            Beta.OtherTest(); // Beta 클래스의 함수 호출
        }
    }

    public static void OtherTest()
    {
        lock (alphaObj) 
        {
            Console.WriteLine("Alpha"); 
        }
    }
}

class Beta
{
    static object betaObj = new object();

    public static void Test()
    {
        lock (betaObj) // betaObj 점유
        {
            Alpha.OtherTest(); // Alpha 클래스의 함수 호출
        }
    }

    public static void OtherTest()
    {
        lock (betaObj)
        {
            Console.WriteLine("Beta"); // betaObj 점유해야 실행 가능
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Thread t1 = new Thread(Alpha.Test);
        Thread t2 = new Thread(Beta.Test);

        //스레드 실행
        t1.Start();
        t2.Start();
        //스레드 종료까지 대기
        t1.Join();
        t2.Join();

        Console.WriteLine("스레드 종료");
    }
}

 Alpha 클래스에는 자신의 오브젝트를 잠그고 Beta 클래스의 함수를 호출하는 Test() 함수와 자신의 오브젝트를 잠그고 단순 문자열 출력을 하는 OtherTest() 함수를 선언하였습니다. Beta 클래스도 Alpha 클래스의 함수를 호출하는 점 외에는 동일하게 작성했습니다. Alpha, Beta의 Test() 함수를 스레드 t1, t2로 만들어 실행해보면 교착 상태가 발생하여 프로그램이 종료되지 않음을 확인할 수 있습니다.

 

그림 1. 순환 대기 구조

 

 상기 그림은 위의 예제 코드의 상황을 자원 할당 그래프로 그린 것입니다. Alpha 클래스의 Test()를 실행하는 t1 스레드에서는 alphaObj를 점유하고 Beta 클래스의 OtherTest()를 실행, betaObj를 점유하려고 합니다. 반대로 t2  스레드에서는 betaObj를 점유하고 Alpha 클래스의 OtherTest()를 실행, alphaObj를 점유하려고 합니다. 서로가 자신의 자원을 점유한 상태로 상대방 클래스의 자원을 요청하는 상태인 것입니다. 이렇게 되면 양쪽 모두 원하는 자원을 획득하지 못하고 무한정 대기하는 교착 상태가 발생합니다. 참고로 이렇게 자원 할당 그래프가 원형으로 그려지는 것이 교착 상태가 발생하는 조건 중 하나입니다.

 

 또한 세마포를 잘못 사용해서 교착 상태가 발생할 수도 있습니다.

class Program
{
    static int count = 0;
    //세마포 클래스 초기화(초기값 1, 최대값 1)
    static Semaphore sp = new Semaphore(1, 1);

    static void Main(string[] args)
    {
        Thread t1 = new Thread(Plus);
        Thread t2 = new Thread(Minus);

        //스레드 실행
        t1.Start();
        t2.Start();
        //스레드 종료까지 대기
        t1.Join();
        t2.Join();

        Console.WriteLine(count);
    }

    static void Plus()
    {
        for (int i = 0; i < 10000; i++)
        {
            sp.WaitOne(); // 자원 점유
            count++;
            sp.Release(); // 자원 해제
        }
    }

    static void Minus()
    {
        for (int i = 0; i < 10000; i++)
        {
            sp.WaitOne(); // 자원 점유
            if (i == 1000) // 루프 탈출
                break;
                
            count--;
            sp.Release(); // 자원 해제
        }
    }
}

  상기 코드에서는 루프를 돌며 count를 1씩 증가시키는 Plus 함수와 1씩 감소시키는 Minus() 함수를 스레드로 실행하였습니다. 단, Minus() 함수는 천번째에 break로 루프를 탈출하도록 했습니다. 스레드의 동기화에는 자원의 초기값과 최대값을 1로 지정한 세마포 클래스를 사용하였습니다. 상기 코드를 실행하면 어떻게 될까요?

 

 Plus()가 만번, Minus()가 천번 실행되어 9000이 나올거 같지만 실제로는 교착 상태가 발생하여 프로그램이 끝나지 않습니다. 이유는 Minus()함수에 있습니다. i == 1000을 만족하는 순간 Release()를 실행하지 않고 루프를 탈출해버리기 때문입니다. 따라서 루프를 탈출하는 시점에서 자원이 반환되지 않아 부족한 상태가 되어버리고, Plus()는 반환될 일 없는 자원을 기다리며 무한정 기다리는 상태가 되어버립니다. 따라서 세마포를 사용할 때에는 다음과 같이 임계 구역을 벗어나는 모든 경로에서 자원을 반환하도록 해야 합니다.

static void Minus()
{
    for (int i = 0; i < 10000; i++)
    {
        sp.WaitOne(); // 자원 점유
        if(i == 1000)
        {
            sp.Release(); // break 전에 자원 해제
            break;
        }

        count--;
        sp.Release(); // 자원 해제
    }
}

그림 1. Minus() 수정 후 실행 결과

 

발생 조건과 예방 방법

 교착 상태는 다음 4가지 조건을 모두 만족할 경우 발생할 수 있습니다(반드시 발생하는 것은 아닙니다).

 

- 상호 배제(mutual exclusion): 자원을 한번에 하나의 스레드(프로세스)만 사용 가능

- 점유와 대기(hold and wait): 한 스레드(프로세스)가 자원을 점유한 채로 다른 자원을 사용하기 위해 대기

- 비선점(nonpreemptive): 스레드(프로세스)가 다른 스레드(프로세스)의 자원을 강제로 뺏을 수 없음

- 원형 대기(circular wait): 스레드(프로세스)들이 자신의 자원을 점유하면서 인접한 스레드(프로세스)의 자원을 요구하여

                                         자원 할당 그래프가 원형으로 그려짐

 

 위에서 Alpha, Beta 예제를 다시 보면 상기 4가지 조건을 모두 충족했음을 알 수 있습니다.

 

1) alphaObj, betaObj는 하나의 스레드에서만 사용 가능

2) t1, t2 스레드는 자신의 자원을 점유한 상태로 반대쪽 클래스의 자원을 사용하기 위해 대기

3) 각각 상대방 스레드의 자원을 강제로 뺏을 수 없음

4) 자원 할당 그래프가 원형으로 그려짐(그림 1 참조)

 

 이렇게 4가지 조건을 모두 만족할 경우 교착 상태가 발생할 수 있으므로, 반대로 4가지 조건중 하나라도 충족하지 않으면 교착 상태가 발생하지 않으므로 교착 상태를 예방할 수 있습니다.

 

 다만 교착 상태를 원천적으로 예방하는 방식은 많은 부작용이 따릅니다. 위의 세마포 예제와 같이 한 공유자원을 변경하는 상황에서 상호 배제나 비선점 조건을 없앨 경우, 문맥 교환에 의해 예기치 못한 결과가 나올 수 있습니다. 점유와 대기는 자원을 하나의 스레드(프로세스)에 모두 할당하는 방식으로 없앨 수 있지만, 이 경우 해당 스레드(프로세스)에 필요없는 자원까지 할당하므로 자원의 활용율이 낮아집니다. 또한 많은 자원을 요구하는 스레드(프로세스)가 실행되기 힘들어지는 기아 현상이 발생할 수 있습니다. 

 

 원형 대기의 상황이 나오지 않도록 하는 것이 비교적 현실적인 예방법이지만, 설계 단계에서 원형 대기가 발생하지 않도록 했더라도 실제 구현하고 기능을 추가하는 과정에서 원형 대기가 발생할 수 있습니다. 더군다나 다른 사람이 작성한 코드를 사용하는 경우 자원의 흐름을 완벽하게 파악하기 어려우므로, 결국 교착 상태를 미리 예방하기란 쉽지 않은 일입니다. 교착 상태가 발생할 우려가 있는 부분에 대해서는 치밀한 테스트 케이스를 거쳐 테스트 단계에서 미리 잡아내도록 하는 것이 중요하겠습니다.