동기화 (2) 세마포어

동시성 프로그래밍의 개척자인 다익스트라는 서로 다른 실행 쓰레드를 동기화하는 문제에 대한 고전적인 해답을 세마포어라고 부르는 특별한 타입의 변수에 기초하여 제안하였다. 

세마포어 s는 음수가 아닌 정수 값을 갖는 전역 변수로 두 개의 특별한 연산인 P와 V를 통해서만 조작이 가능하다.

• P(s): s가 0이 아닌 경우, P는 s를 감소시키고 즉시 리턴한다. 만일 s가 0이라면 쓰레드는 s가 0이 아닌 양의 정수가 될 때까지 기다렸다가, 이후 V 연산에 의해 s가 갱신된 이후에서야 다시 재시작한다. 재시작 이후에 P는 s를 감소시키고 제어권을 다시 호출자에게 돌려준다.
• V(s): V 연산은 s를 1 증가시킨다. 직전의 설명한 P의 반대라고 생각할 수 있다.

P에서 테스트와 감소 연산은 일단 세마포어 s가 0이 아니면 s의 감소가 중단 없이 일어난다는 의미에서 개별적으로 일어난다. 마찬가지로 V 또한 연산이 세마포어를 중단 없이 로드하고 증가하고 저장하기 때문에 개별적이라고 할 수 있다.

V의 정의가 기다리고 있는 쓰레드들이 재시작되는 순서를 정의하지 않는다는 것을 주목해야 한다. 앞서 세마포어의 유일한 요구사항은 V가 정확히 한 개의 대기하는 쓰레드를 재시작시켜준다는 것이였다. 

그래서 여러 개의 쓰레드가 하나의 세마포어를 기다리고 있을 때, 어떤 쓰레드가 V의 결과로 재시작되는지는 예측이 불가능하다.

P와 V의 정의는 돌고 있는 프로그램에서 적절히 초기화된 세마포어가 음수 값을 갖는 상태로 절대 들어갈 수 없도록 보장해준다. 이 특성은 세마포어 불변성이라고 하며, 동시성 프로그램의 궤적을 제어하기 위한 강력한 도구를 제공한다.

P, V 이름의 기원
에드거 다익스트라는 네덜란드 사람으로, P()와 V()는 Proberen(테스트하기)와 Verhogen(증가시키기)라는 네덜란드어에서 유래되었다.

상호 배제를 위해 세마포어 이용하기

세마포어는 공유 변수들을 상호 배타적으로 접근하기 위한 편리한 방법을 제공한다. 기본 아이디어는 세마포어 s를 초기 값 1로 시작해서 각각의 공유 변수에 연계하고 그 후에 대응하는 크리티컬 섹션을 P(s)와 V(s)로 구성된 연산으로 둘러싸는 것이다.

이런 방법으로 공유 변수들을 보호하기 위해서 사용하는 세마포어를 바이너리 세마포어라고 한다. 그 이유는 이들의 값이 항상 0 또는 1이기 때문이다. 그 중에서 상호 배타성을 제공하는 목적으로 사용하는 바이너리 세마포어는 뮤텍스라는 이름으로 부른다. 뮤텍스에서 P 연산을 수행하는 것을 Locking이라고 부르며, 비슷하게 뮤텍스에서 V 연산을 수행하는 것을 unlocking이라고 부른다. 뮤텍스로 lock을 수행했지만 아직 unlock 하지 않은 쓰레드에 대해서는 뮤텍스를 holding 하고 있다고 표현한다. 

그림 1. 상호 배제를 위해 세마포어 이용하기

위의 그림은 바이너리 세마포어를 이용해서 직전 글의 카운터 프로그램을 적절하게 동기화하는 지를 보여준다. 각각의 상태는 해당 상태에서 세마포어 값 s로 표현된다. 핵심 아이디어는 이와 같은 P와 V의 조합이 금지 구역이라고 불리는 상태들의 집합을 생성한다는 것이며, 금지 구역 내에서 s의 값은 음수가 된다.

앞서 설명하였듯 세마포어는 그 특성상 음수 값을 가질 수 없으며 해당 특성을 세마포어의 불변성이라고 소개하였다.  이때 금지 구역이 완전히 위험 구역을 감싸고 있다는 것에 주목해보자. 때문에 모든 가능한 궤적들은 위험 구역의 모든 부분을 지날 수 없다. 모든 가능한 궤적은 안전하고 런타임에 인스트럭션의 순서와 무관하게 정확히 카운터를 증가시킬 것이다.

이를 코드로 표현하면 다음과 같다. 먼저 뮤텍스라고 불리는 세마포어를 선언한다.

volatile int cnt = 0; /* Counter */
sem_t mutex;          /* Semaphore that protects counter */

그리고 그 후에 main 루틴에서 1로 초기화한다.

Sem_init(&mutex, 0, 1);

마지막으로 쓰레드 루틴에서 P와 V 연산으로 공유 변수 cnt를 둘러싸서 이 변수의 갱신을 보호하며 동기화를 구현한다.

void *thread(void *vargp)
{
    int i, niters = *((int *)vargp);

    for (i = 0; i < niters; i++) {
        P(&mutex);   
        cnt++;
        V(&mutex);
    }
    return NULL;
}

 

다만 명심해야 할 점은 세마포어의 P와 V를 아무 곳에서나 남발해서는 안된다는 것이다. P와 V를 자주 사용한다면, 그만큼 동기화 측면에서 안정성을 보장받을 수는 있겠으나 앞서 설명했던 바와 같이 세마포어 연산들은 기존 흐름들을 중단시키는 작업을 포함할 수 밖에 없다. 시스템에 부하가 생겨 발생하는 오버헤드는 아니지만, 프로그램의 속도에 심각한 영향을 끼칠 수 있기에 반드시 필요한 적재적소의 라인에 작성해주는 것이 핵심이다.