임계 영역의 문제 해결 (1)

임계 영역의 통제, 즉 임계 영역에 대한 문제를 해결하기 위해서는 아래의 세 요구사항들을 충족시켜야 한다.

 

1. 상호 배제 (Mutual exclusion)

한 프로세스가 임계 영역에서 실행되고 있다면 다른 프로세스들은 임계 영역에 진입할 수 없다는 뜻이다.

다르게 말하면, 두 개 이상의 프로세스가 동시에 임계 영역에 존재해서는 안 된다는 뜻으로 이는 경쟁 상태(Race condition)를 방지하기 위해, 프로세스의 동기화를 위해 반드시 필요한 기본 조건이다.

 

---

2. 진행 (Progress)

임계 영역이 비어 있을 때, 임계 영역에 진입하고자 하는 프로세스가 존재한다면 그 진입은 반드시 이루어져야 한다는 뜻이다.

만약 진입이 영원히 이루어지지 않는다면 다른 프로세스에도 영향을 끼쳐 교착 상태(Deadlock)를 일으킬 수 있기 때문에 이 또한 충족되어야 할 조건이다.

 

---

3. 한정 대기 (Bounded waiting)

말그대로 프로세스가 임계 영역에 진입하기 위한 대기 시간은 한정되어야 한다는 뜻이다.

구체적으로는, 한 프로세스가 임계 영역에 진입하기를 요청한 순간부터 그 프로세스를 제외한 나머지 프로세스들은 임계 영역에 진입할 수 있는 횟수가 한정되는 것이다.

 

진행과 헷갈리지 말아야 할 것은, 진행은 둘 이상의 프로세스가 아예 실행될 수 없는 상태를 방지하기 위함이며 한정 대기는 프로세스가 실행될 수 있는 상태임에도 자신의 차례가 오지 않는 상태인 기아 상태(Starvation)를 방지하기 위함이다.

 

---

 

위의 세 조건을 모두 충족시키는 것은 쉽지 않은 일이다.

그러나 이를 가능케 하는 소프트웨어적인 방법이 있으니, 바로 피터슨의 알고리즘(Peterson's Algorithm)이다.

피터슨의 알고리즘은 turn과 flag라는 두 개의 변수를 사용하는데, 우선은 하나의 변수만으로도 임계 영역 문제를 해결할 수 있는지 확인해보자.

 

아래 예제는 flag만을 사용한 예제로, flag를 통해 각 스레드가 임계 구역에 진입할 의사가 있음을 나타내도록 하였다.

 

 

결론부터 말하자면, 위 예제는 상호 배제를 만족하지만 진행과 한정 대기는 만족하지 않는다.

예를 들어 스레드 A가 flag[A]를 true로 설정하자마자 스레드 B로 문맥 교환이 일어났다고 하자.

그러면 flag[A]와 flag[B]는 모두 true가 되므로 두 스레드 모두 스핀락(Spinlock) 상태에 빠져 임계 영역에 영원히 진입할 수 없게 된다.

따라서 진행과 한정 대기를 만족하지 않는다.

 

마찬가지로 flag가 아닌 turn을 사용해도 세 조건을 모두 충족시킬 수는 없다.

물론 경우의 수는 많지만 그게 가능했다면 피터슨이 아닌 다른 사람의 이름이 공룡책에 기록됐을 것이니 너무 깊게 파고들 필요는 없다.

 

---

 

이제 피터슨의 알고리즘을 살펴보도록 하자.

 

공룡책

 

피터슨의 알고리즘은 두 개의 프로세스에 대해서만 적용할 수 있는 개념이다.

(셋 이상이 가능한 버전도 있지만 여기서는 다루지 않겠다.)

 

요약하자면, 두 프로세스가 flag를 통해 서로의 상태를 확인하고, turn을 통해 누구의 차례인지를 확인하는 방식이다.

그다지 어려운 내용도 아니고, 변수만 하나 추가했을 뿐인데 상호 배제, 진행, 한정 대기를 모두 만족한다고 한다.

 

물론 진짜로 만족하는 지도 쉽게 확인할 수 있다. 그냥 모든 경우의 수를 따져보면 된다. 혹은 증명하거나...

하지만 그런 식으론 피터슨의 알고리즘을 금방 잊어버리고 말 것이다.

그래서 나는 피터슨의 알고리즘을 횡단보도를 건너기 위한 과정에 빗대어 설명하고자 한다.

 

---

 

예를 들어, 사람 과 차 라는 두 프로세스가 있다고 하자.

 

사람은 횡단보도라는 임계 구역을 건너기 위해 flag[사람 ]을 true로 설정하여 횡단보도 앞에 선다.

그리곤 turn을 차 로 설정하여 주위에 차가 있는지 살피는데,

이 때 flag[차 ]가 true라면 차가 쌩쌩 달리고 있다는 뜻이므로 사람은 횡단보도를 건널 수 없을 것이다.

그러나 flag[차 ]가 false라면 주위에 차가 없다는 뜻이므로 사람은 안심하고 횡단보도를 건널 수 있다.

 

반대로 차의 입장에서는 횡단보도를 지나기 전에 flag[차 ]를 true로, turn을 사람 으로 설정하여 사람을 살피는데,

만약 flag[사람 ]이 true라면 사람이 횡단보도를 건너고 있다는 뜻이므로 차는 횡단보도 앞에서 멈춰야 하고,

flag[사람 ]이 false라면 근처에 사람이 없다는 뜻이므로 안심하고 횡단보도를 지나갈 수가 있는 것이다.

 

---

 

이렇듯 우리는 피터슨의 알고리즘을 사용하면 임계 영역 문제를 이론상 완벽하게 해결할 수 있음을 알았다.

하지만 불행하게도 피터슨의 알고리즘을 실전에서 사용할 일은 없는데, 그 이유는 피터슨의 알고리즘이 제대로 동작한다는 보장이 없기 때문이다.

 

public static class Peterson
{
    public static int count = 0;
    public static bool[] flag = new bool[2];
    public static int turn;

    public static void Main()
    {
        Thread t1 = new Thread(Add1);
        Thread t2 = new Thread(Add2);

        t1.Start();
        t2.Start();

        t1.Join();
        t2.Join();

        Console.Write(count);
    }

    public static void Add1()
    {
        for (int i = 0; i < 100000; i++)
        {
            flag[0] = true;
            turn = 1;

            while (flag[1] && turn == 1) ;

            count++; //Critical section

            flag[0] = false;
        }
    }

    public static void Add2()
    {
        for (int i = 0; i < 100000; i++)
        {
            flag[1] = true;
            turn = 0;

            while (flag[0] && turn == 0) ;

            count++; //Critical section

            flag[1] = false;
        }
    }
}

실행 결과

 

위는 C#으로 작성한 피터슨의 알고리즘의 예제이다.

알고리즘을 충실하게 구현했음에도 불구하고 상호 배제가 정상적으로 이루어지지 않은 모습이다.

대체 피터슨의 알고리즘에는 어떤 문제가 있는 것일까?

 

사실 코드만으로는 알아채기가 굉장히 어려운데(디스어셈블리로도 확인할 수 없다), 피터슨의 알고리즘이 오작동하는 이유는 현대식 프로세서가 자행하는 최적화 때문이다.

프로세서는 최적화를 위해 서로 의존성이 없는 연산에 대하여 실행 순서를 임의로 변경할 수가 있다.

그래서 만일 피터슨의 알고리즘에서 flag와 turn을 설정하는 순서가 바뀌게 된다면,

 

공룡책

 

위와 같이 두 프로세스가 동시에 임계 영역에 진입할 수가 있게 되고, 이는 경쟁 상태가 발생하는 원인이 된다.

따라서 피터슨의 알고리즘을 사용하려면 flag와 turn 사이에 메모리 배리어를 삽입하여 실행 순서가 역전되지 않도록 해야 한다.

 

public static void Add1()
{
    for (int i = 0; i < 100000; i++)
    {
        flag[0] = true;
        Thread.MemoryBarrier(); //Add2에도 동일하게 삽입해야 한다
        turn = 1;

        while (flag[1] && turn == 1) ;

        count++; //Critical section

        flag[0] = false;
    }
}

실행 결과

 

메모리 배리어를 삽입하면 20만이 아닌 2000만이 되어도 경쟁 상태가 발생하지 않게 된다.

그러나, 아무리 문제가 없다 한들, 일일이 이 구조로 작성하는 것은 여간 귀찮은 일이 아니므로(추후 더 편리한 방법을 소개할 것이다) 피터슨의 알고리즘을 실전에서 사용할 일이 없는 것이다.

 

참고로, 위 예시는 해당되지 않으나 컴파일러의 최적화 또한 프로세스의 동기화에 영향을 줄 수 있다.

아래의 위키 문서를 참고하자.

 

volatile 변수 - 위키백과, 우리 모두의 백과사전

 

다음 게시글에서는 소프트웨어적인 방법이 아닌 하드웨어적인 방법으로 임계 영역에 대한 문제를 해결해볼 것이다.