세마포어란 무엇인가

문제의 복잡성이 발생하는 근본 원인은, 2.2절에서 설명된 것처럼 복잡한 해결책으로 이어지는 이유는 공유 변수에 대한 접근이 항상 "단방향 정보 흐름"이라는 사실 때문입니다. 즉, 개별 프로세스는 새로운 값을 할당하거나 현재 값을 검사할 수는 있지만, 이러한 검사는 다른 프로세스에 대해 아무런 흔적을 남기지 않습니다. 그 결과, 한 프로세스가 공유 변수의 현재 값에 반응하려 할 때, 해당 값은 검사와 그에 따른 반응 실행 사이에 다른 프로세스에 의해 변경될 수 있습니다. 다시 말해, 기존의 통신 방식은 해당 문제를 해결하기에 부적합하며, 더 적합한 대안을 찾아야 합니다.

그러한 대안은 다음과 같이 도입함으로써 제공됩니다: a) 공유 변수 중 특수 목적의 정수를 도입하는데, 이를 우리는 "세마포어(semaphores)"라고 부릅니다. b) 각 프로세스가 구성되는 동작들의 집합에 두 가지 새로운 기본 연산을 추가하며, 이를 우리는 각각 "P-연산"과 "V-연산"이라고 부릅니다. 이러한 연산들은 항상 세마포를 대상으로 작동하며, 동시 실행되는 프로세스들이 세마포어에 접근할 수 있는 유일한 방법을 나타냅니다.

세마포어는 본질적으로 음수가 아닌 정수입니다. 상호 배제(Mutual Exclusion) 문제를 해결하는 데만 사용될 경우, 그 값의 범위는 "0"과 "1"로 제한될 수도 있습니다. 더 큰 값도 가질 수 있는 세마포의 광범위한 적용 가능성을 입증한 것은 네덜란드의 물리학자이자 컴퓨터 설계자인 C.S. Scholten 박사의 공로입니다. 필요에 따라 구분할 때, 우리는 이를 각각 "이진 세마포어(binary semaphores)"와 "일반 세마포어(general semaphores)"라고 부를 것입니다. 이제부터 제가 제시할 P-연산과 V-연산의 정의는 이러한 구분에 영향을 받지 않습니다.

-다익스트라의 노트 EWD123

들어가며

사실 세마포어는 어려운 개념이다. 동기화 문제의 근본이며 뮤텍스와 더불어 가장 먼저 배우는 개념이지만, 처음 접근할때 이해가 어렵다.

보통 세마포어를 요약할때 다음과 같이 요약한다.

'세마포어는 공유 자원에 대한 동시 접근 시 동기화가 보장되지 않아 발생하는 문제들을, P와 V라는 특수한 원자적 연산을 통해 자원의 가용성을 나타내는 카운터를 조작함으로써 해결하는 기법'

이라고 할 수 있다.

하지만 대체 공유 자원은 무엇이고, 원자적 연산은 무엇이며, 자원의 가용성과 P와 V는 무엇인가?

그것을 설명하기 위해 써본다.

이 글의 목표는 동시성 프로그래밍의 기초와 세마포어를 이해하는 걸 목표로 한다.

공유 자원이란 무엇인가?

프로그램이 병렬로 실행될 때, 여러 개의 스레드나 프로세스가 동시에 접근하는 데이터를 ‘공유 자원(shared resource)’이라 부른다

- 예시: 메모리 상의 변수, 파일 핸들, 네트워크 포트, 큐 등

공유 자원은 상태(state)를 가진다.

이 상태에 동시에 접근하고 수정하려 할 경우, 예기치 못한 오류를 발생시킨다.

공유자원을 프린터 비유로 생각해보자

하나의 프린터가 있다고 가정해보자. 두 사람이 동시에 프린터를 사용하려고 할 때를 생각해보자.

- A가 인쇄 중인데 B가 중간에 인쇄를 시작하면?

- 출력이 중단되거나, 중첩되거나, 백지 출력이 일어날 수 있다.

-> 이처럼 공유 자원에 대한 동시 접근은 충돌을 유발한다!

원자적 연산이 필요한 이유

그렇다면 이런 문제를 어떻게 해결할 수 있을까?

핵심은 여러 스레드가 동시에 접근하더라도 상태의 일관성을 보장하는 것, 즉 ‘원자성(Atomicity)’을 확보하는 데 있다.

예를 들어 변수 x에 1을 더하는 연산 'x = x + 1'은 실제로는 다음과 같이 세 단계로 분해된다.

1. x의 현재 값을 읽는다

2. 1을 더한다

3. 결과를 다시 x에 저장한다

이 단순한 연산조차 중간에 다른 프로세스가 끼어들면 결과가 손상된다. 예컨대 두 개의 스레드가 동시에 x = x + 1을 수행하면, 최종 결과가 1만 증가하는 것이 아니라, 0만큼 혹은 1만큼 덜 증가할 수도 있다.

두 개의 스레드가 동시에 x = x + 1을 수행하는 상황을 인터리빙으로 보자.

(인터리빙 플레이그라운드)

이처럼 서로 경쟁하면서 값을 바꾸려 할 때, 예상치 못한 상태가 발생하는 것을 Race Condition(경쟁 상태)이라고 부른다.

“한 줄의 연산처럼 보이는 것”도 실제로는 여러 단계로 나뉘기 때문에, 중간 개입을 차단할 수단이 필요하다.

이를 해결하는 방법이 바로 원자적 연산이다. 원자적 연산은 불가분의 단위 작업으로, 실행 도중에는 어떠한 외부 개입도 허용하지 않는다.

다시 프린터 비유로 생각해보자

- A가 프린터에 인쇄 요청을 보내면, 인쇄가 완전히 끝나거나 실패하거나 중단될 때까지 B의 요청은 대기해야 한다.

- 인쇄 도중 B가 끼어들어 출력을 시작하면, 출력물이 섞이거나 일부 누락되는 오류가 발생할 수 있다.

- 따라서 "A의 인쇄 상태"가 명확히 종료되었을 때만 다음 요청(B)을 처리해야, 출력 상태의 일관성이 보장된다.

이것이 바로 원자성의 요구 조건이다.  

출력 중에는 프린터의 상태(State)가 “사용 중”으로 잠금(lock) 상태에 있어야 하며,  

오직 완전한 종료가 일어난 후에만 다음 작업으로 넘어가야 한다.

프로그램 내의 상태 기반 자원을 동시에 다루기 위해서는, 중간에 끼어들 수 없는 원자적 제어 장치가 필요하다.

자, 그럼 이제 원자성은 어떻게 보장될까? 그것이 오늘의 주제이다.

다익스트라의 제안: 세마포어란 무엇인가

특별한 목적을 가진 정수 (special-purpose integers)

앞서 본 프린터의 예시처럼, 우리는 “사용 중”이라는 상태를 외부에서 명확히 제어하고 감시할 수 있어야 한다. 하지만 일반적인 변수만으로는 그 상태를 안전하게 관리할 수 없다.

그 이유는 다음과 같다:

- 변수는 누구나 읽고 쓸 수 있으며,  

- 어떤 프로세스가 읽어들인 값은, 그 직후에 다른 프로세스에 의해 바뀔 수 있다.  

- 다시 말해, 값을 읽고 그에 반응하기까지의 시간 사이에, 상태는 변할 수 있고, 그 변화는 반영되지 않는다.

이처럼 기존 방식은 “검사-결정-실행”이라는 일련의 흐름이 중간에 깨지기 쉬운 구조이다.  

이 구조적 한계를 극복하기 위해, Edsger W. Dijkstra는 새로운 해결책을 제안한다.

공유 변수 중 특수 목적의 정수를 도입하는데, 이를 우리는 "세마포어(semaphores)"라고 부릅니다

-Dijkstra, EWD 123

세마포어란 무엇인가?

세마포어(semaphore)는 단순한 정수가 아니다.  

외부 접근이 통제되는, 특별한 목적을 가진 상태값이다.

 핵심은 "직접 접근을 금지하고, 두 가지 연산(P/V)을 통해서만 간접 제어한다"는 점이다.

among the repertoire of actions, from which the individual processes have to be constructed, two new primitives, which we call the "P-operation" and the "V-operation" respectively. The latter operations always operate upon a semaphore and represent the only way in which the concurrent processes may access the semaphores.

-Dijkstra, EWD 123

이 특별한 정수는 오직 두 개의 연산만으로 조작할 수 있다:

- P 연산 (Proberen, "시험하다")  

- V 연산 (Verhogen, "증가시키다")

이 두 연산은 다음과 같은 규칙을 갖는다:

이 연산들은 항상 원자적으로 수행된다. 즉, 어떠한 중단이나 끼어듦 없이 한 번에 수행된다는 뜻

이것이 바로 우리가 찾던 “중간 개입을 차단하는 메커니즘”

그것이 세마포어이다.

P / V 연산의 정의

간단한 구현은 다음과 같다.

// 세마포어는 s라는 정수값으로 표현
typedef struct {
    int s;
} Semaphore;

// P 연산 (wait): 자원 획득 시도
void P(Semaphore *sem)
{
    while (sem->s <= 0) {
        // 대기 (busy-wait 또는 blocking)
    }
    sem->s = sem->s - 1;
}

// V 연산 (signal): 자원 반환
void V(Semaphore *sem)
{
    sem->s = sem->s + 1;
    // 이 이후, 대기중인 프로세스가 있다면 깨워야 함
}

주의할 점은, P, V 연산 의사코드에서 s = s - 1이나 s = s + 1, 그리고 while (s <= 0) wait; 조건 검사 부분은 하나의 분리될 수 없는 원자적 단위로 실행되어야 한다는 것이다. 만약 원자성이 깨지면 앞서 본 x = x + 1의 race condition과 동일한 파국이 세마포어 자신에서 발생한다.

참고로 위는 개념적 표현이고, 실제로 저 코드를 그대로 C로 옮기면 치명적 결함이 있다. while 검사와 s = s - 1 사이에 다른 프로세스가 끼어들면 둘 다 세마포어를 통과해버리는 race condition이 발생하는데

실무에서는 원자성(atomicity) 보장을 위해 아래처럼 작성한다.
(물론, 아래 코드는 "원자성이 보장되면 P/V는 이렇게 생겼어야 한다"를 보여주기 위해 이미 원자성이 보장된 pthread를 빌려 쓴 것이다. 즉, pthread_mutex가 어떻게 구현됐는지는 이 층에서 다루지 않고, 그 아래 "원자성은 어디서 오는가" 섹션에서 하드웨어까지 파고든다.)

#include <pthread.h>

typedef struct {
    int s;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
} Semaphore;

// P 연산: 원자적으로 실행되어야 함
void P(Semaphore *sem)
{
    pthread_mutex_lock(&sem->mutex);
    while (sem->s <= 0) {
        pthread_cond_wait(&sem->cond, &sem->mutex); // 조건 변수로 대기
    }
    sem->s = sem->s - 1;
    pthread_mutex_unlock(&sem->mutex);
}

// V 연산: 원자적으로 실행되어야 함
void V(Semaphore *sem)
{
    pthread_mutex_lock(&sem->mutex);
    sem->s = sem->s + 1;
    pthread_cond_signal(&sem->cond); // 대기중인 프로세스 깨움
    pthread_mutex_unlock(&sem->mutex);
}

참고로 POSIX 표준에서는 <semaphore.h>의 sem_wait() / sem_post()가 이미 구현되어 있어서 실제로 학습말고는 거의 구현할 일도 드물다.

원자성은 어디서 오는가: 하드웨어 계층

그런데 한 가지 의문이 생긴다. P와 V가 원자적이어야 한다면, 그 원자성은 또 어떻게 보장되는가? 소프트웨어 락으로 세마포어를 보호하면, 그 락은 또 무엇이 보호하는가? 무한히 거슬러 올라가는 이 재귀는 결국 하드웨어에서 끝난다.

모든 소프트웨어 동기화 원시는 CPU가 제공하는 원자적 기계어 명령 위에 세워진다.

• TAS (Test-And-Set): 메모리 값을 읽고 지정한 값으로 덮어쓰는 두 동작을 한 번에 수행하며, 이전 값을 반환한다.

• CAS (Compare-And-Swap): "예상값과 현재값이 같을 때만 새 값으로 바꿔라"를 원자적으로 수행한다. x86의 CMPXCHG, 현대 lock-free 자료구조의 기반.

• LL/SC (Load-Linked / Store-Conditional): ARM, RISC-V에서 쓰는 한 쌍의 명령어. "내가 읽은 이후 아무도 건드리지 않았다면 써라."

이 명령들은 메모리 버스 수준에서 배타성을 보장받는다. 소프트웨어만으로는 불가능하다. 세마포어·뮤텍스·스핀락·lock-free 큐까지, 모든 동시성의 기본은 CAS 한 줄의 확장이라고 해도 과언이 아니다.

바쁜 대기의 문제

원자성 문제를 하드웨어가 해결해준다 해도, 위 의사코드의 while (s <= 0)는 여전히 심각한 문제를 남긴다. 조건이 만족될 때까지 CPU를 계속 점유하는 바쁜 대기(busy-waiting, spin-waiting) 다.

• CPU 낭비: 다른 유용한 작업을 할 수 있는 시간을 무의미하게 소모한다.

• 에너지 소비: 모바일·임베디드 환경에서 배터리 수명에 직접 타격.

• 단일 CPU 환경의 데드락 위험: 대기 중인 프로세스가 CPU를 놓지 않으면, V를 호출해줄 프로세스가 스케줄링되지 못해 영원히 깨어나지 못한다. 즉, 기다리는 행위 자체가 기다림을 끝낼 수 없게 만든다.

따라서 현대 운영체제는 이 "wait" 과정을 훨씬 효율적으로 처리하기 위해 여러 메커니즘을 계층적으로 조합한다. 이것이 현대 비동기 처리 방식의 원형이라고 봐도 무방하다.

현대 OS의 구현 계층

슬립 큐(Sleep Queue / Wait Queue), 컨텍스트 스위칭, 스핀락(Spinlock), 퓨텍스(Futex)

듣기만 해도 머리가 어지러워지는 이 방식들 전반의 이론적 원점은 저 간단한 P/V 연산이다. 그리고 현대 OS에서는 저 이론적 원점이 어떻게 쓰이는지 간단한 설명을 하겠다.

스핀락: 짧고 빠른 보호

스핀락은 하드웨어 CAS 위에 바로 구축되는 가장 단순한 락이다. 대기 시간이 매우 짧을 것으로 예상될 때 적합하며, 컨텍스트 스위치 오버헤드가 없다는 장점이 있다. 커널 내부에서 세마포어 변수 s나 슬립 큐 자체를 아주 잠깐 보호하는 용도로 쓰인다.

슬립 큐와 컨텍스트 스위칭: 긴 대기의 정석

대기가 길어질 것으로 예상되면 CPU를 붙잡고 있을 이유가 없다.

P(s) 호출 시 s <= 0이면:
  1. 현재 프로세스 상태를 RUNNING -> BLOCKED로 전환
  2. 세마포어의 슬립 큐에 PCB(Process Control Block) 삽입
  3. 스케줄러에게 CPU 양보 (컨텍스트 스위치)

V(s) 호출 시:
  1. s를 1 증가
  2. 슬립 큐에서 프로세스 하나를 꺼내 BLOCKED -> READY로 전환
  3. 스케줄러가 적절한 시점에 해당 프로세스를 재개

CPU는 블록된 프로세스 대신 다른 일을 하므로 바쁜 대기의 낭비가 사라진다. 대신 컨텍스트 스위치 비용(수 μs 단위)이 발생한다.

퓨텍스: Linux의 하이브리드 최적화

Futex(Fast Userspace muTEX)는 "경합이 없는 대다수 경우"를 시스템 콜 없이 해결하는 최적화다.

• Fast path (경합 없음): 사용자 공간에서 CAS로 원자 갱신, 시스템 콜 없음

• Slow path (경합 발생): futex(FUTEX_WAIT)로 커널 슬립 큐 진입, futex(FUTEX_WAKE)로 깨움

실제 생산 환경에서 락 경합은 드물기 때문에 이 최적화는 대부분의 시스템 콜 오버헤드를 제거한다. glibc의 pthread_mutex, C++ std::mutex가 내부적으로 futex를 사용한다.

현대 OS에서 세마포어 연산을 이야기하면 다음과 같이 정리된다.

1. 기본적인 대기/깨움: 슬립 큐를 사용하여 프로세스를 효율적으로 재우고 깨움 (바쁜 대기 방지).

2. 내부 원자성 확보: P, V 연산 자체의 아주 짧은 코드 실행 동안 세마포어 변수(s)나 슬립 큐를 안전하게 수정하기 위해 (커널 내부에서) 스핀락 등이 사용됨. 그리고 그 스핀락은 결국 하드웨어 CAS에 기반함.

3. 성능 최적화 (특히 Linux): 퓨텍스를 활용하여, 경합이 없을 때는 사용자 공간에서 빠르게 처리하고, 경합이 발생할 때만 커널의 슬립 큐 기능을 사용하여 시스템 콜 오버헤드를 줄인다.

이진 세마포어 vs 일반 세마포어

더 큰 값을 가질 수 있는 세마포어의 광범위한 적용 가능성을 입증한 것은 Dijkstra의 동료 C. S. Scholten 박사의 공로이며, 이로써 세마포어는 단일 자원 보호를 넘어 N개의 자원을 다루는 일반적 추상화로 확장되었다.

세마포어 vs 뮤텍스

여기까지 오면 세마포어는 알겠는데, 뮤텍스와 무슨 차이가 있는지 궁금해하는 독자가 있을 것이다.

이진 세마포어와 뮤텍스는 외관상 비슷하지만 의미론적으로 다르다.

핵심 구분: 세마포어는 생산자-소비자 같은 시그널링에 적합하고, 뮤텍스는 "이 데이터 구조를 한 스레드가 독점 사용한다"는 소유권 선언에 적합하다.

이진 세마포어를 뮤텍스 대용으로 쓸 수는 있지만, 우선순위 역전 같은 실시간 문제가 얽히면 부적절하다. 다만 뮤텍스를 설명하기위해선 소유권을 설명해야하는데, 이는 이 글의 논지를 벗어날 위험이 있어 추후에 설명토록하겠다.

다시 프린터로 넘어가서, 프린터의 세마포어 제어

이진 세마포어를 프린터 예시에 적용하면 다음과 같다:

1.프린터 상태를 나타내는 세마포어 s = 1로 시작한다.

2.A 사용자가 P(s)를 호출하여 s = 0으로 만들고 인쇄 시작

3.인쇄 중 B 사용자는 P(s)를 호출하지만, s <= 0이므로 대기

4.A가 인쇄를 마치고 V(s) 호출 → s = 1이 되어 B가 인쇄 가능

이렇게 세마포어는 자원의 “상태”를 숫자로 추상화하고,  

해당 숫자값을 원자적으로 변화시킴으로써 동시성을 제어하는 것이다.

앞서 설명한 이진 세마포어는 사무실에 프린터가 단 한 대만 있어서, 한 사람만 독점적으로 사용해야 하는 상황(상호 배제)에 적합하다. 

s=1은 '프린터 사용 가능', s=0은 '프린터 사용 중'을 의미했다

하지만 만약 사무실에 똑같은 성능의 프린터가 여러 대 (예: 3대) 있다면 어떨까? 

이때는 여러 사람이 동시에 프린터를 사용할 수 있지만, 사용 가능한 프린터의 수를 넘어서지는 않도록 제어해야 한다. 

바로 이럴 때 일반 세마포어(General Semaphore) 또는 계수 세마포어(Counting Semaphore)가 사용된다.

일반 세마포어 s는 사용 가능한 자원의 개수를 나타내는 음이 아닌 정수 값을 가진다.

일반 세마포어를 이용한 프린터 (3대) 제어 예시

1. 초기 상태:

- 사무실에 프린터가 3대 있으므로, 세마포어 s의 초기값은 3으로 설정 s = 3.

- 이는 "현재 사용 가능한 프린터가 3대 있다"는 의미.

2. 사용자 A가 프린터 사용 요청 (P(s) 연산):

- P(s)를 호출

- s의 현재 값(3)이 0보다 크므로, s를 1 감소시킨다 s = 2가 됨.

    - 사용자 A는 프린터 한 대를 할당받아 인쇄를 시작한다. (이제 사용 가능한 프린터는 2대)

3. 사용자 B가 프린터 사용 요청 (P(s) 연산):

    - P(s)를 호출

    - s의 현재 값(2)이 0보다 크므로, s를 1 감소시킨다 s = 1이 됨.

    - 사용자 B도 프린터 한 대를 할당받아 인쇄를 시작한다. (이제 사용 가능한 프린터는 1대)

4. 사용자 C가 프린터 사용 요청 (P(s) 연산):

    - P(s)를 호출

    - s의 현재 값(1)이 0보다 크므로, s를 1 감소시킨다 s = 0이 됨.

    - 사용자 C도 프린터 한 대를 할당받아 인쇄를 시작한다 (이제 사용 가능한 프린터는 0대)

5. 사용자 D가 프린터 사용 요청 (P(s) 연산):

    - P(s)를 호출

    - s의 현재 값(0)이 0 이하이므로, 사용자 D는 P(s) 연산 내의 while (s <= 0) wait; 조건에 걸려 대기 상태가 된다.(사용 가능한 프린터가 나올 때까지 기다림)

6. 사용자 A가 인쇄 완료 후 프린터 반납 (V(s) 연산):

    - 사용자 A가 인쇄를 마치고 V(s)를 호출한다.

    - s를 1 증가시킨다 s = 1이 됨. (이제 사용 가능한 프린터 1대 발생)

    - V(s) 연산이 완료되면, P 연산에서 대기 중이던 사용자 D가 깨어나 s 값을 다시 확인한다. s가 1이 되었으므로, 사용자 D는 s를 0으로 만들고 프린터를 사용하기 시작한다.

일반 세마포어의 핵심은 단순히 '잠금/해제'의 이진 상태를 넘어, 여러 개로 한정된 자원 풀(pool)에 대한 동시 접근을 제어하고, 사용 가능한 자원의 개수를 정확하게 관리하는 데 사용된다.

(프린터 예시 플레이 그라운드)

끝맺으며: 이론적 원점으로서의 가치

세마포어는 여전히 커널 레벨 동기화의 핵심이며, 상태 기반 접근 모델의 대표적인 예이다.

더 넓게 보면, 현대 동시성 원시 - 뮤텍스, 컨디션 변수, Go의 채널, Rust tokio의 태스크 큐, JavaScript async/await 런타임 등등

모두 "원자적 상태 갱신 + 대기 큐" 라는 동일한 골격을 공유한다. 60년 전 Dijkstra가 제시한 P/V 연산은 이 골격을 가장 앙상하게 드러낸 형태이며, 이후의 모든 구현은 그 위에 성능 최적화(futex, lock-free 자료구조)와 추상화(async runtime, 채널)를 쌓은 것에 불과하다.

따라서 "세마포어 의사코드가 원자적이어야 한다" 는 한 줄의 요구사항이, 하드웨어의 CAS 명령어부터 모던 런타임의 스케줄러까지 관통하는 설계 제약의 원형(archetype)이다.

세마포어는 언뜻 보면 단순한 정수일 뿐이다. 하지만 그것은 시스템에서 자원의 상태를 정확히 나타내고, 안전하게 통제하며, 예측 가능한 방식으로 공유할 수 있게 하는 가장 근본적인 추상화 수단이다.

우리는 이 작은 정수 하나에 수많은 프로세스들의 질서, 충돌 회피, 시스템 안정성이 걸려 있음을 잊지 말아야 한다.