Semaphore 문서 원본 보기

상위 문서: [[Synchronization]]

==개요==
Edsger Dijkstra는 세마포어(semaphore)라는 특수한 유형의 변수를 기반으로, 서로 다른 스레드를 동기화하는 해결책을 제안했다. 세마포어 s는 전역 변수이며, 0 이상의 정수 값을 가지는 변수이고, 두 연산 P와 V만이 이 값을 조작할 수 있다:
* <code>P(s)</code>:
** 만약 s가 0이 아니라면, P 연산은 s를 감소시키고 즉시 리턴한다.
** 만약 s가 0이라면, 스레드를 일시 중단(suspend)시키고, s가 0이 아니게 될 때까지 기다린다. 스레드가 재시작되면, P 연산은 s를 감소시키고 리턴한다.
* <code>V(s)</code>: 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 표준은 세마포어를 제어하기 위한 다양한 함수를 정의한다. 
<syntaxhighlight lang="c">
#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) */
</syntaxhighlight>
<code>sem_init()</code> 함수는 세마포어 sem을 지정된 value로 초기화한다. 또한 프로그램은 각각 <code>sem_wait()</code>과 <code>sem_post()</code> 함수를 호출하여 P 연산과 V 연산을 수행한다. 더 간결한 표현을 위해, 다음과 가튼 P, V의 래퍼(wrapper) 함수를 대신 사용하는 것이 권장된다.
<syntaxhighlight lang="c">
#include "csapp.h"
//반환값: 없음
void P(sem_t *s);   /* sem_wait의 래퍼 함수 */
void V(sem_t *s);   /* sem_post의 래퍼 함수 */
</syntaxhighlight>

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

이제 이 모든 것을 종합하여, <code>[[Synchronization#Synchronizing Threads|badcnt.c]]</code> 예제 프로그램을 세마포어를 사용해 적절히 동기화하려면, 먼저 mutex라는 세마포어를 선언한다:
<syntaxhighlight lang="c">
volatile long cnt = 0;  /* 카운터 */
sem_t mutex;            /* 카운터를 보호하는 세마포어 */
</syntaxhighlight>
그리고 main 루틴에서 이를 1로 초기화 한다.
<syntaxhighlight lang="c">
Sem_init(&mutex, 0, 1);  /* mutex = 1 */
</syntaxhighlight>
마지막으로, 스레드 루틴 내에서 공유 변수 cnt를 갱신하는 부분을 P와 V 연산으로 감싸서 보호한다:
<syntaxhighlight lang="c">
for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++;
    V(&mutex);
}
</syntaxhighlight>
이제 적절히 동기화된 프로그램을 실행하면, 아래와 같이 항상 올바른 결과를 출력한다.
<syntaxhighlight lang="c">
linux> ./goodcnt 1000000
OK cnt=2000000

linux> ./goodcnt 1000000
OK cnt=2000000
</syntaxhighlight>

==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)를 공유한다. 생산자 스레드는 새 항목을 반복적으로 생성하고, 버퍼에 삽입한다. 소비자 스레드는 항목을 반복적으로 제거하고, 그 항목을 소비(사용) 한다.<ref> 다수의 생산자와 소비자가 있는 변형도 가능하다.</ref> 

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

실제 시스템에서는 이러한 상황이 자주 발생한다. 예를 들어, 멀티미디어 시스템에서는 생산자 스레드가 비디오 프레임을 인코딩하고, 소비자 스레드가 이를 디코딩하고 화면에 렌더링할 수 있다. 이때 버퍼의 목적은, 각 프레임의 인코딩/디코딩 시간 차이로 인한 지터(jitter)<ref>디지털 전송에서 신호가 예정보다 빠르게 혹은 느리게 나타나서 발생하는 오류를 의미한다.</ref>를 줄이는 것이다. 버퍼는 생산자 스레드에게는 슬롯의 저장소(reservoir), 소비자 스레드에게는 인코딩된 프레임의 저장소 역할을 한다. 또 다른 예시로는 래픽 사용자 인터페이스(GUI) 설계이다. 이 상황에서 생산자 스레드는는 마우스 및 키보드 이벤트를 감지하고 버퍼에 삽입하며, 소비자 스레드는 버퍼에서 이벤트를 우선순위 기반 방식으로 처리하고 이를 화면에 표시한다.

Sbuf는 생산자-소비자 프로그램을 만들기 위한 간단한 패키지이며, 아래와 같이 정의된 sbuf_t 타입의 버퍼를 다룬다:
<syntaxhighlight lang="c">
typedef struct {
    int *buf;       /* Buffer array */
    int n;          /* Maximum number of slots */
    int front;      /* buf[(front+1)%n] is first item */
    int rear;       /* buf[rear%n] is last item */
    sem_t mutex;    /* Protects accesses to buf */
    sem_t slots;    /* Counts available slots */
    sem_t items;    /* Counts available items */
} sbuf_t;
</syntaxhighlight>
각 항목들은 정수형 배열 buf에 저장되며, 이 배열은 동적으로 할당되고, 최대 n개의 항목을 담을 수 있다. 또한  front와 rear 인덱스는 배열 내 첫 번째 항목과 마지막 항목의 위치를 추적한다. 그리고 해당 버퍼 내에서 세 개의 세마포어가 버퍼에 대한 접근을 동기화한다:
* mutex: 상호 배제적인 버퍼 접근을 보장한다.
* slots/items: 카운팅 세마포어이며, 각각 비어 있는 슬롯 수와 사용 가능한 항목 수를 센다. 
아래는 Sbuf 패키지의 구현을 보여주는 코드이다:
<syntaxhighlight lang="c">
#include "csapp.h"
#include "sbuf.h"

/* Create an empty, bounded, shared FIFO buffer with n slots */
void sbuf_init(sbuf_t *sp, int n)
{
    sp->buf = Calloc(n, sizeof(int));
    sp->n = n;                    // 버퍼는 최대 n개의 항목을 저장 가능
    sp->front = sp->rear = 0;     // front == rear라면 비어있는 버퍼
    Sem_init(&sp->mutex, 0, 1);   // 초기 이진 세마포어 값을 1로 초기화
    Sem_init(&sp->slots, 0, n);   // 초기에 버퍼의 비어있는 슬롯은 n개
    Sem_init(&sp->items, 0, 0);   // 초기에 사용가능한 항목은 0개
}

/* Clean up buffer sp */
void sbuf_deinit(sbuf_t *sp) {
    Free(sp->buf);
}

/* Insert item onto the rear of shared buffer sp */
void sbuf_insert(sbuf_t *sp, int item) 
{
    P(&sp->slots);                            // 사용가능한 슬롯에 대해 대기
    P(&sp->mutex);                            // 버퍼를 잠그기
    sp->buf[(++sp->rear)%(sp->n)] = item;     // 항목을 해당 슬롯에 삽입
    V(&sp->mutex);                            // 버퍼를 풀기
    V(&sp->items);                            // 이를 items 세마포어에 반영
}

/* Remove and return the first item from buffer sp */
int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);                            // 사용가능한 아이템에 대해 대기
    P(&sp->mutex);                            // 버퍼 잠그기
    item = sp->buf[(++sp->front)%(sp->n)];    // 해당 함목을 제거
    V(&sp->mutex);                            // 버퍼를 풀기
    V(&sp->slots);                            // 이를 slots 세마포어에 반영
    return item;
}
</syntaxhighlight>
위 코드에서  <code>sbuf_init()</code> 함수는 버퍼를 위한 힙 메모리를 동적 할당하고, front와 rear를 통해서 빈 버퍼임을 명시하고, 세마포어(mutex, slots, items)들에 초기값을 할당한다. <code>sbuf_deinit()</code> 함수는, 애플리케이션의 사용이 끝났을 때 버퍼에 할당된 공간을 해제한다.<br>
<code>sbuf_insert()</code> 함수는 다음과 같은 절차를 따른다.
# slots 세마포어가 1이상이라면, 이를 1 감소시키고 다음 단계로 넘어간다.
#* 만약 slots 세마포어가 0이라면, slots의 값이 증가할 때까지<ref>사용 가능한 슬롯이 나타날 때 까지</ref>기다린다.
# mutex를 잠궈서 다른 스레드가 해당 버퍼에 접근할 수 없도록 한다.
# 항목을 추가한다.
# mutex를 풀어서 다른 스레드가 해당 버퍼에 접근할 수 있도록 한다.
# items 세마포어의 값을 1 추가하고, 만약 다른 스레드가 <code>P(&sp->slots)</code> 함수를 통해 대기중이었다면, 이를 재시작시킨다. 
<code>sbuf_remove()</code> 함수는 이에 대해 대칭적으로 작동한다:
# items 세마포어가 1이상이라면, 이를 1 감소시키고 다음 단계로 넘어간다.
#* 만약 items 세마포어가 0이라면, items의 값이 증가할 때까지<ref>사용 가능한 항목이 나타날 때 까지</ref>기다린다.
# mutex를 잠궈서 다른 스레드가 해당 버퍼에 접근할 수 없도록 한다.
# 버퍼의 앞쪽에서 항목을 제거한다.
# mutex를 풀어서 다른 스레드가 해당 버퍼에 접근할 수 있도록 한다.
# slots 세마포어의 값을 1 추가하고, 만약 다른 스레드가 <code>P(&sp->items)</code> 함수를 통해 대기중이었다면, 이를 재시작시킨다. 

===Readers-Writers Problem===

<syntaxhighlight lang="c">

</syntaxhighlight>

==각주==