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

이제 이 모든 것을 종합하여, <code>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>


<syntaxhighlight lang="c">

</syntaxhighlight>


==각주==