Semaphore

상위 문서: Synchronization

개요

Edsger Dijkstra는 세마포어(semaphore)라는 특수한 유형의 변수를 기반으로, 서로 다른 스레드를 동기화하는 해결책을 제안했다. 세마포어 s는 전역 변수이며, 0 이상의 정수 값을 가지는 변수이고, 두 연산 P와 V만이 이 값을 조작할 수 있다:

• P(s):
  • 만약 s가 0이 아니라면, P 연산은 s를 감소시키고 즉시 리턴한다.
  • 만약 s가 0이라면, 스레드를 일시 중단(suspend)시키고, s가 0이 아니게 될 때까지 기다린다. 스레드가 재시작되면, P 연산은 s를 감소시키고 리턴한다.
• V(s): V 연산은 s를 1 증가시킨다. 만약 s가 0이어서 P 연산에서 대기 중(blocked)인 스레드들이 있다면, V 연산은 이러한 스레드 중 정확히 하나를 재시작시킨다. 재시작된 스레드는 s를 감소시키며 P 연산을 마친다.

P 연산에서의 검사(test)와 감소(decrement) 동작은 불가분적으로 발생한다. 이는 세마포어 s가 0이 아닌 상태가 된 이후에는 해당 감소가 중단되지 않고 실행된다는 의미이다. 마찬가지로, V 연산에서의 증가 연산(increment) 도 불가분적으로 수행되며, 이는 세마포어의 값을 읽고(load), 증가시키고(increment), 저장(store)하는 전 과정이 중단 없이 일어난다는 의미다. 이때, V 연산을 구현할 때 중요한 것은 대기 중인 스레드들을 어떤 순서로 재시작할 것인지에 대한 정의가 아니라, 대기 중인 스레드들 중 정확히 하나를 재시작해야 한다는 것이다. 따라서 세마포어에 여러 스레드가 대기하고 있을 경우, V 연산으로 인해 어떤 스레드가 재시작될지 예측할 수 없다.

P와 V의 정의는, 적절히 초기화된 세마포어가 음수값을 가지는 상태에 프로그램이 절대 진입하지 않는 것을 보장한다. 이 속성은 세마포어 불변식(semaphore invariant) 으로 알려져 있으며, 동시성 프로그램의 실행 경로(trajectory)를 제어하는 강력한 도구를 제공한다. Posix 표준은 세마포어를 제어하기 위한 다양한 함수를 정의한다.

#include <semaphore.h>
//반환값: 성공 시 0, 실패 시 -1
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s);   /* P(s) */
int sem_post(sem_t *s);   /* V(s) */

sem_init() 함수는 세마포어 sem을 지정된 value로 초기화한다. 또한 프로그램은 각각 sem_wait()과 sem_post() 함수를 호출하여 P 연산과 V 연산을 수행한다. 더 간결한 표현을 위해, 다음과 가튼 P, V의 래퍼(wrapper) 함수를 대신 사용하는 것이 권장된다.

#include "csapp.h"
//반환값: 없음
void P(sem_t *s);   /* sem_wait의 래퍼 함수 */
void V(sem_t *s);   /* sem_post의 래퍼 함수 */

Using Semaphores for Mutual Exclusion

세마포어는 공유 변수에 대해 상호 배제적인 접근(mutually exclusive access)을 보장하는 편리한 방법을 제공한다. 기본적인 아이디어는 초기값이 1인 세마포어 s를 각 공유 변수(또는 관련된 공유 변수 집합)에 연관시키고, 해당하는 임계 구역(critical section) 을 P(s)와 V(s) 연산으로 감싸는 것이다. 이 방식에 더욱 자세히 설명하기 위해, 아래의 여러 단어와 표현들의 뜻에 대해 먼저 설명한다:

• 이진 세마포어(binary semaphore): 공유 변수를 보호하는 데 사용되는 세마포어, 항상 0 또는 1
• mutex: Mutually exclusive access를 구현하기 위해 사용되는 이진 세마포어
• 잠그다(lock): Mutex에 대해 P 연산을 수행하는 것
• 풀다(unlock): Mutex에 대해 V 연산을 수행하는 것
• 보유하다(hold): 어떤 스레드가 뮤텍스를 잠그고, 아직 풀지 않았다.
• 카운팅 세마포어(counting semaphore): 사용 가능한 자원의 집합에 대한 카운터로 사용되는 세마포어

Figure 6. Using semaphores for mutual exclusion

Figure 1는 어떻게 이진 세마포어를 사용하여 위에서 등장한 badcnt.c 프로그램을 동기화할 수 있는지 보여준다. Figure에서 각 상태는 그 상태에서의 세마포어 s의 값으로 라벨링 되어 있으며, 해당 figure에서 이를 통해 알 수 있는 것은 P와 V 연산의 조합이 s < 0인 상태들의 집합, 즉 금지 영역(forbidden region)을 만든다는 것이다. 이때 세마포어 불변식은 s >= 0임을 보장하므로, 어떤 실행 경로도 비안전 영역을 통과할 수 없다. 따라서 모든 가능한 실행 경로는 안전(safe)하며, 어떤 상황에서도 프로그램은 cnt를 의도대로 증가시킨다. 따라서, P와 V 연산이 만들어내는 금지 영역은 하나의 시점에 여러 스레드가 동일한 임계 구역 내의 명령어들을 실행하는 것을 불가능하게 만들며, 이를 통해 임계 구역에 대한 상호 배제적인 접근을 보장한다.

이제 이 모든 것을 종합하여, badcnt.c 예제 프로그램을 세마포어를 사용해 적절히 동기화하려면, 먼저 mutex라는 세마포어를 선언한다:

volatile long cnt = 0;  /* 카운터 */
sem_t mutex;            /* 카운터를 보호하는 세마포어 */

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

Sem_init(&mutex, 0, 1);  /* mutex = 1 */

마지막으로, 스레드 루틴 내에서 공유 변수 cnt를 갱신하는 부분을 P와 V 연산으로 감싸서 보호한다:

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

이제 적절히 동기화된 프로그램을 실행하면, 아래와 같이 항상 올바른 결과를 출력한다.

linux> ./goodcnt 1000000
OK cnt=2000000

linux> ./goodcnt 1000000
OK cnt=2000000

Using Semaphores to Schedule Shared Resources

세마포어의 또 다른 중요한 용도는 공유 자원에 대한 접근을 스케줄링(scheduling) 하는 것을 포함한다. 이를 구현하기 위한 기본적인 아이디어는 한 스레드가 세마포어 연산을 사용하여 프로그램 상태에서 어떠한 조건이 참이되었음을 알리는 것이다. 이에 대한 전통적인 두 예시는 생산자-소비자 문제(producer-consumer problem) 와 읽기/쓰기 문제(readers-writers problem) 이다.

Producer-Consumer Problem

생산자-소비자 문제(Producer-Consumer Problem)는 figure 2에 나와 있다. 해당 figure에서 생산자 스레드와 소비자 스레드는 n개의 슬롯이 있는 유한 버퍼(bounded buffer)를 공유한다. 생산자 스레드는 새 항목을 반복적으로 생성하고, 버퍼에 삽입한다. 소비자 스레드는 항목을 반복적으로 제거하고, 그 항목을 소비(사용) 한다.

이때 항목을 삽입하거나 제거하는 작업은 공유 변수의 갱신을 포함하기 때문에 해당 상황은 버퍼에 대해 상호 배제적인 접근을 보장해야 한다. 하지만 그것 만으로는 충분하지 않으며, 버퍼에 대한 접근을 스케줄링할 필요도 존재한다. 그 이유는 버퍼가 가득 찼다면(빈 슬롯이 없다면), 생산자는 슬롯이 생길 때까지 대기해야 하기 때문이다. 반대로 버퍼가 비어 있다면(사용 가능한 항목이 없다면), 소비자는 항목이 생길 때까지 대기해야 한다.