> [!abstract] Introduction > [[Lock|락]]은 한 시점에 하나의 스레드만 임계 구역에 진입하도록 보장하지만, "최대 $N$개의 스레드가 동시에 자원에 접근할 수 있게 하라"거나 "A 스레드가 끝난 뒤에 B 스레드가 시작하도록 순서를 보장하라"와 같은 요구에는 락만으로 대응하기 어렵습니다. 이러한 요구를 하나의 프리미티브로 해결하기 위해 Edsger Dijkstra가 1965년에 제안한 것이 바로 세마포어*Semaphore*입니다. 이 글에서는 세마포어의 정의와 두 가지 원자적 연산, 이진·카운팅 세마포어의 구분, 대표적인 사용 패턴, 그리고 실제 구현 원리까지를 다룹니다. ## 세마포어의 정의 세마포어*Semaphore*는 음이 아닌 정수 변수 $S$와, 이 변수에 대해 수행할 수 있는 두 개의 원자적 연산 $P$와 $V$로 구성되는 동기화 프리미티브다(Dijkstra, 1965).[^pv-naming] 세마포어의 핵심 불변식*invariant*은 다음과 같다. $S \geq 0$ 세마포어의 값은 어떤 상황에서도 음수가 되지 않는다. $P$ 연산이 값을 감소시키려 할 때, 값이 이미 0이면 호출 스레드는 값이 양수가 될 때까지 대기한다. 이 단순한 불변식 하나가 상호 배제, 실행 순서 제어, 자원 수량 관리라는 세 가지 동기화 패턴을 모두 가능하게 한다. ## P 연산과 V 연산 세마포어를 구성하는 두 연산은 반드시 **원자적*atomic***으로 실행되어야 한다. 즉, 하나의 연산이 실행되는 도중에 다른 스레드가 끼어들 수 없다. ### P 연산 (wait, down) $P(S)$ 연산은 세마포어의 값을 감소시킨다. 값이 0이면 양수가 될 때까지 호출 스레드를 대기시킨다. $ P(S): \text{while } S = 0 \text{ do wait};\quad S \leftarrow S - 1 $ 직관적으로, $P$는 "자원을 하나 가져간다" 또는 "허가를 하나 소비한다"로 이해할 수 있다. ### V 연산 (signal, up) $V(S)$ 연산은 세마포어의 값을 증가시킨다. 대기 중인 스레드가 있으면 그중 하나를 깨운다. $ V(S): S \leftarrow S + 1 $ 직관적으로, $V$는 "자원을 하나 반환한다" 또는 "허가를 하나 발급한다"로 이해할 수 있다. $V$ 연산에서 주목할 점은, 대기 중인 스레드가 없어도 세마포어의 값이 증가한다는 것이다. 이 성질 덕분에 $V$가 $P$보다 먼저 호출되어도 신호가 소실되지 않는다. 이것이 [[Monitor#조건 변수|조건 변수]]의 `signal`과 세마포어 $V$의 결정적인 차이다 — 조건 변수의 `signal`은 대기자가 없으면 효과가 사라진다.[^signal-vs-v] ## 이진 세마포어와 카운팅 세마포어 세마포어는 초기값에 따라 두 가지로 나뉜다. ### 이진 세마포어 (Binary Semaphore) 초기값이 1인 세마포어로, 0 또는 1의 값만 가질 수 있다. [[Lock|락]]과 동일한 상호 배제*mutual exclusion* 기능을 수행한다. ```c semaphore mutex = 1; /* 초기값 1 */ /* 스레드 A */ P(&mutex); /* 0이 됨 — 진입 */ // 임계 구역 V(&mutex); /* 1로 복원 */ /* 스레드 B */ P(&mutex); /* A가 V를 호출할 때까지 대기 */ // 임계 구역 V(&mutex); ``` 이진 세마포어와 뮤텍스*mutex*는 기능적으로 유사하지만 중요한 차이가 있다. 뮤텍스는 **소유권*ownership*** 개념이 있어 락을 획득한 스레드만 해제할 수 있지만, 이진 세마포어는 소유권이 없어 어떤 스레드든 $V$를 호출할 수 있다.[^mutex-vs-binary-semaphore] 이 차이는 뒤에서 다루는 시그널링 패턴을 가능하게 하는 핵심이다. ### 카운팅 세마포어 (Counting Semaphore) 초기값이 $N$($N > 1$)인 세마포어로, 동시에 최대 $N$개의 스레드가 자원에 접근하도록 허용한다. 세마포어의 값은 "현재 사용 가능한 자원의 수"를 나타낸다. ```c semaphore pool = 5; /* 초기값 5 — 자원 5개 */ /* 스레드가 자원을 사용할 때 */ P(&pool); /* 사용 가능 자원 수 감소 */ // 자원 사용 V(&pool); /* 사용 가능 자원 수 증가 */ ``` 데이터베이스 커넥션 풀, 스레드 풀, 동시 접속 수 제한 등이 카운팅 세마포어의 전형적인 활용 사례다. ## 세마포어의 사용 패턴 세마포어는 세 가지 기본 동기화 패턴을 구현할 수 있다. ### 패턴 1: 상호 배제 (Mutual Exclusion) 초기값 1의 이진 세마포어로 임계 구역을 보호하는 가장 기본적인 패턴이다. ```c semaphore mutex = 1; void critical_section_work() { P(&mutex); // 임계 구역 — 한 스레드만 진입 가능 V(&mutex); } ``` $P$와 $V$가 임계 구역을 감싸는 형태로, [[Lock|락]]의 `acquire`/`release`와 동일한 역할을 한다. ### 패턴 2: 시그널링 (Signaling) 한 스레드의 특정 지점이 실행된 뒤에 다른 스레드의 특정 지점이 실행되도록 **실행 순서를 강제**하는 패턴이다. 초기값 0의 세마포어를 사용한다. ```c semaphore done = 0; /* 초기값 0 */ /* 스레드 A — 먼저 실행해야 하는 작업 */ void thread_A() { do_work_A(); V(&done); /* "A의 작업이 끝났다" 신호 */ } /* 스레드 B — A 이후에 실행해야 하는 작업 */ void thread_B() { P(&done); /* A가 V를 호출할 때까지 대기 */ do_work_B(); } ``` 이 패턴이 작동하는 이유는 세마포어의 초기값이 0이기 때문이다. 스레드 B가 먼저 `P`에 도달하면 값이 0이므로 대기한다. 스레드 A가 작업을 마치고 `V`를 호출하면 값이 1이 되어 B가 깨어난다. 반대로 A가 먼저 `V`를 호출하면 값이 1이 되고, 나중에 B가 `P`를 호출할 때 즉시 통과한다. 어떤 순서로 실행되든 "A 다음 B"라는 순서가 보장되는 것이다. 이 패턴은 뮤텍스로는 구현할 수 없다. 뮤텍스는 소유권이 있어 `unlock`은 `lock`을 호출한 스레드만 수행할 수 있기 때문이다. 세마포어의 $V$에는 이러한 제약이 없으므로, A가 $V$를 호출하여 B를 깨우는 교차 스레드 시그널링이 가능하다. ### 패턴 3: 자원 관리 (Resource Management) $N$개의 동일한 자원을 관리하는 패턴이다. 카운팅 세마포어의 값이 남은 자원 수를 추적한다. ```c #define MAX_CONNECTIONS 10 semaphore db_pool = MAX_CONNECTIONS; void handle_request() { P(&db_pool); /* 커넥션 하나 획득 (없으면 대기) */ connection_t *conn = get_connection(); // 데이터베이스 작업 수행 release_connection(conn); V(&db_pool); /* 커넥션 반환 */ } ``` 모든 커넥션이 사용 중이면(`db_pool == 0`), 새 요청은 어떤 스레드가 `V`를 호출할 때까지 대기한다. ## 구현: Busy Waiting vs. 대기큐 앞서 $P$ 연산의 정의에서 `while S = 0 do wait`이라 적었는데, 이 "대기"를 어떻게 구현하느냐에 따라 세마포어의 성능 특성이 크게 달라진다. ### Busy Waiting (Spinlock 방식) 가장 단순한 구현은 $P$ 연산에서 조건이 만족될 때까지 루프를 돌며 반복 확인하는 것이다. ```c void P(semaphore *s) { while (atomic_load(&s->value) == 0) ; /* 바쁜 대기 — CPU 사이클 소모 */ atomic_dec(&s->value); } ``` 이 방식은 **스핀락*spinlock***과 동일한 문제를 가진다. 대기 중인 스레드가 CPU 사이클을 계속 소모하므로, 대기 시간이 길면 심각한 자원 낭비가 발생한다. 단일 프로세서 시스템에서는 특히 치명적인데, 대기 중인 스레드가 CPU를 독점하면 $V$를 호출할 스레드가 실행 기회를 얻지 못하여 사실상 교착 상태에 빠질 수 있다.[^spinlock-single-cpu] ### 대기큐 방식 (Sleep Queue) 실제 운영체제는 $P$ 연산에서 조건이 만족되지 않으면 호출 스레드를 **대기큐*wait queue***에 넣고 잠재운다*sleep*. $V$ 연산은 대기큐에서 스레드를 하나 꺼내 깨운다*wake*. ```c struct semaphore { int value; struct list_head wait_list; /* 대기큐 */ spinlock_t lock; /* 내부 상태 보호용 */ }; void P(struct semaphore *s) { spin_lock(&s->lock); if (s->value > 0) { s->value--; spin_unlock(&s->lock); } else { /* 현재 스레드를 대기큐에 삽입하고 잠재움 */ add_to_wait_list(&s->wait_list, current); spin_unlock(&s->lock); schedule(); /* 다른 스레드에게 CPU 양보 */ } } void V(struct semaphore *s) { spin_lock(&s->lock); if (list_empty(&s->wait_list)) { s->value++; } else { /* 대기큐에서 스레드를 하나 꺼내 깨움 */ struct task *t = remove_from_wait_list(&s->wait_list); wake_up(t); } spin_unlock(&s->lock); } ``` 이 구현에서 주목해야 할 점이 두 가지 있다. 첫째, 세마포어 내부 상태(`value`, `wait_list`)를 보호하기 위해 별도의 스핀락이 사용된다. 이 스핀락은 매우 짧은 구간(몇 줄의 코드)만 보호하므로 busy waiting의 비용이 무시할 만하다. 둘째, $V$ 연산에서 대기자가 있으면 `value`를 증가시키는 대신 대기자를 직접 깨운다. 이는 깨어난 스레드가 다시 $P$에서 값을 확인하는 불필요한 단계를 없애는 최적화다.[^v-wake-optimization] ### 리눅스 커널의 구현 리눅스 커널의 세마포어(`kernel/locking/semaphore.c`)는 대기큐 방식을 사용한다. 사용자 공간에서는 POSIX 세마포어(`sem_wait`, `sem_post`)가 [[Inter-Process Communication#Futex: 사용자 공간 동기화의 기반|Futex]][^futex-def]를 기반으로 구현되어, 경합이 없는 빠른 경로*fast path*에서는 커널에 진입하지 않고 원자적 연산만으로 처리하며, 실제 대기가 필요한 경우에만 `FUTEX_WAIT` 시스템 호출을 통해 커널의 대기큐에 진입한다(Love, 2010). ```mermaid flowchart TD WAIT["sem_wait()"] --> CAS{"원자적 감소<br/>value > 0?"} CAS -->|"성공"| DONE["자원 획득<br/>(커널 진입 없음)"] CAS -->|"실패 — value == 0"| FUTEX["futex(FUTEX_WAIT)<br/>커널 대기큐에서 잠듦"] POST["sem_post()"] --> INC["원자적 증가<br/>value++"] INC --> CHECK{"대기자 존재?"} CHECK -->|"없음"| RET["완료<br/>(커널 진입 없음)"] CHECK -->|"있음"| WAKE["futex(FUTEX_WAKE)<br/>대기자 깨우기"] ``` ## POSIX 세마포어 API POSIX는 두 종류의 세마포어를 제공한다. **이름 없는 세마포어*unnamed semaphore***는 스레드 간(또는 공유 메모리를 통한 프로세스 간) 동기화에 사용하고, **이름 있는 세마포어*named semaphore***는 비관련 프로세스 간 동기화에 사용한다. ### 이름 없는 세마포어 ```c #include <semaphore.h> sem_t sem; /* 초기화: pshared=0이면 스레드 간, 1이면 프로세스 간 */ sem_init(&sem, 0, initial_value); sem_wait(&sem); /* P 연산 — 블로킹 */ sem_trywait(&sem); /* P 연산 — 비블로킹 (실패 시 EAGAIN) */ sem_post(&sem); /* V 연산 */ int val; sem_getvalue(&sem, &val); /* 현재 값 조회 */ sem_destroy(&sem); /* 파괴 */ ``` `sem_wait`이 블로킹되는 동안 시그널에 의해 중단될 수 있으며, 이 경우 `errno`가 `EINTR`로 설정된다. 시그널 안전한 코드를 작성하려면 `EINTR` 처리를 반드시 포함해야 한다.[^sem-wait-eintr] ### 이름 있는 세마포어 ```c /* 생성 또는 열기 */ sem_t *sem = sem_open("/my_semaphore", O_CREAT, 0666, initial_value); sem_wait(sem); sem_post(sem); /* 닫기 — 현재 프로세스의 참조만 해제 */ sem_close(sem); /* 삭제 — 파일 시스템에서 이름 제거 */ sem_unlink("/my_semaphore"); ``` 이름 있는 세마포어는 `/dev/shm` 디렉토리(tmpfs)에 파일로 생성된다.[^named-sem-devshm] 이름이 `/`로 시작해야 하고 그 뒤에 추가 `/`가 없어야 한다는 POSIX 명세의 이식성 규칙을 따르는 것이 좋다. ### 예제: 생산자-소비자 세마포어를 사용한 유한 버퍼*bounded buffer* 생산자-소비자 구현이다. 세 개의 세마포어가 각각 다른 역할을 수행한다. ```c #include <stdio.h> #include <pthread.h> #include <semaphore.h> #define N 10 int buffer[N]; int in = 0, out = 0; sem_t empty; /* 빈 슬롯 수 (초기값 N) — 카운팅 */ sem_t full; /* 찬 슬롯 수 (초기값 0) — 카운팅 + 시그널링 */ sem_t mutex; /* 버퍼 접근 상호 배제 (초기값 1) — 이진 */ void *producer(void *arg) { for (int i = 0; i < 100; i++) { int item = produce_item(); sem_wait(&empty); /* 빈 슬롯이 생길 때까지 대기 */ sem_wait(&mutex); /* 버퍼 접근 잠금 */ buffer[in] = item; in = (in + 1) % N; sem_post(&mutex); /* 버퍼 접근 해제 */ sem_post(&full); /* 찬 슬롯 수 증가 — 소비자에게 신호 */ } return NULL; } void *consumer(void *arg) { for (int i = 0; i < 100; i++) { sem_wait(&full); /* 찬 슬롯이 생길 때까지 대기 */ sem_wait(&mutex); /* 버퍼 접근 잠금 */ int item = buffer[out]; out = (out + 1) % N; sem_post(&mutex); /* 버퍼 접근 해제 */ sem_post(&empty); /* 빈 슬롯 수 증가 — 생산자에게 신호 */ consume_item(item); } return NULL; } int main() { sem_init(&empty, 0, N); /* N개의 빈 슬롯 */ sem_init(&full, 0, 0); /* 0개의 찬 슬롯 */ sem_init(&mutex, 0, 1); /* 상호 배제 */ pthread_t prod, cons; pthread_create(&prod, NULL, producer, NULL); pthread_create(&cons, NULL, consumer, NULL); pthread_join(prod, NULL); pthread_join(cons, NULL); sem_destroy(&empty); sem_destroy(&full); sem_destroy(&mutex); return 0; } ``` 이 코드에서 `empty`와 `full`은 각각 빈 슬롯과 찬 슬롯의 수를 추적하는 카운팅 세마포어이면서, 동시에 생산자와 소비자 사이의 시그널링 역할도 수행한다. `mutex`는 버퍼 배열에 대한 상호 배제를 보장하는 이진 세마포어다. 이처럼 하나의 문제에도 세마포어를 세 개나 사용해야 하고, `sem_wait`의 호출 순서가 미묘하게 중요하다.[^sem-ordering-deadlock] ## 세마포어의 한계 세마포어는 상호 배제, 시그널링, 자원 관리를 모두 구현할 수 있는 강력한 프리미티브지만, 그 범용성은 곧 위험성이기도 하다. $P$와 $V$의 호출 순서를 한 번이라도 잘못 배치하면 상호 배제 위반, 교착 상태, 영구 블로킹 등이 발생할 수 있다. 생산자-소비자 예제만 보아도 세마포어 세 개의 `sem_wait` 순서를 바꾸면 교착 상태가 발생하며, 이 실수를 컴파일러가 잡아주지 않는다. 또한 동기화 로직($P$/$V$ 호출)이 비즈니스 로직 전체에 흩어져 있어 정확성을 검증하기 어렵다. 이러한 구조적 한계를 해결하기 위해 등장한 것이 [[Monitor#모니터의 정의|모니터]]다. 모니터는 보호 대상 데이터, 락, [[Monitor#조건 변수|조건 변수]]를 하나의 추상 자료형으로 캡슐화하여 **상호 배제를 구조적으로 강제**하고, 프로그래머는 "어떤 조건을 기다릴 것인가"만 선언하면 된다. 세마포어와 모니터는 표현력 면에서 동등하지만(Silberschatz, Galvin and Gagne, 2018), 모니터가 제공하는 구조적 안전성 덕분에 현대 프로그래밍 언어 대부분이 모니터 스타일의 동기화를 기본으로 채택하고 있다. ```mermaid flowchart BT HW["하드웨어 원자적 명령어<br/>(CAS, Test-and-Set)"] LOCK["[[Lock|락]]<br/>(spinlock, mutex)"] SEM["세마포어<br/>(정수 + P/V)"] MON["[[Monitor|모니터]]<br/>(lock + condition variable)"] LANG["언어 수준 지원<br/>(Java synchronized, Python with)"] HW --> LOCK LOCK --> SEM LOCK --> MON SEM -.->|"동등한 표현력"| MON MON --> LANG ``` --- ## 출처 - Dijkstra, E.W. (1965) 'Cooperating Sequential Processes', Technical Report EWD-123, Technological University Eindhoven. Reprinted in: Hansen, P.B. (ed.) (2002) *The Origin of Concurrent Programming*, New York: Springer, pp. 65–138. - Silberschatz, A., Galvin, P.B. and Gagne, G. (2018) *Operating System Concepts*. 10th edn. Hoboken: Wiley. - Love, R. (2010) *Linux Kernel Development*. 3rd edn. Upper Saddle River: Addison-Wesley. - Kerrisk, M. (2010) *The Linux Programming Interface*. San Francisco: No Starch Press. - Downey, A.B. (2016) *The Little Book of Semaphores*. 2nd edn. Green Tea Press. [^pv-naming]: $P$와 $V$라는 이름은 네덜란드어에서 유래한다. $P$는 *proberen*(시도하다)의 약자이고 $V$는 *verhogen*(증가시키다)의 약자다. 영어권에서는 `wait`/`signal` 또는 `down`/`up`이라는 이름으로도 불린다. — Dijkstra (1965). [^signal-vs-v]: 세마포어 $V$와 조건 변수 `signal`의 차이: 세마포어는 내부에 정수 상태를 가지므로, 대기자가 없어도 $V$가 값을 증가시켜 다음 $P$ 호출이 즉시 통과한다. 조건 변수는 상태가 없으므로, 대기자가 없을 때의 `signal`은 아무 효과도 남기지 않는다. 이 차이를 "메모리가 있다/없다"로 표현하기도 한다. — Downey (2016), §3.1. [^mutex-vs-binary-semaphore]: 뮤텍스와 이진 세마포어의 차이는 소유권의 유무에 있다. 뮤텍스는 `lock`을 호출한 스레드만 `unlock`할 수 있으므로, 실수로 다른 스레드가 임계 구역을 열어버리는 상황을 방지한다. 이진 세마포어는 이런 보호가 없지만, 대신 한 스레드가 $P$하고 다른 스레드가 $V$하는 시그널링 패턴이 가능하다. — Silberschatz, Galvin and Gagne (2018), §6.6. [^spinlock-single-cpu]: 단일 프로세서에서 비선점형 스케줄링을 사용하는 경우, 스핀락 방식의 세마포어는 교착 상태를 유발한다. $P$에서 대기 중인 스레드가 CPU를 독점하므로 $V$를 호출할 스레드가 실행될 수 없기 때문이다. 선점형 스케줄링에서는 타이머 인터럽트가 CPU를 빼앗지만, 여전히 CPU 사이클을 낭비하는 문제는 남는다. — Silberschatz, Galvin and Gagne (2018), §6.6. [^v-wake-optimization]: 대기자가 있을 때 `value`를 증가시키지 않고 직접 깨우는 최적화는 리눅스 커널의 `up()` 구현(`kernel/locking/semaphore.c`)에서 확인할 수 있다. 이 방식은 깨어난 스레드가 다시 `value`를 확인하고 감소시키는 불필요한 원자적 연산을 제거한다. [^futex-def]: Futex*Fast Userspace Mutex*: 경합이 없는 경로에서 커널 진입 없이 원자적 CAS 연산만으로 동작하는 동기화 프리미티브. `pthread_mutex_lock()`, `pthread_cond_wait()`, `sem_wait()` 등의 기반이 된다. [^sem-wait-eintr]: `sem_wait`이 시그널에 의해 중단되는 경우의 처리: `while (sem_wait(&sem) == -1 && errno == EINTR) continue;` 패턴을 사용하여 시그널 중단 후 재시도하는 것이 관례다. — `sem_wait(3)` 맨 페이지; Kerrisk (2010), §53.3. [^named-sem-devshm]: 이름 있는 POSIX 세마포어의 파일 시스템 위치는 구현에 따라 다를 수 있다. glibc에서는 `/dev/shm/sem.이름` 형태로 생성된다. `ls /dev/shm/`으로 현재 시스템의 이름 있는 세마포어 목록을 확인할 수 있다. — Kerrisk (2010), §53.4. [^sem-ordering-deadlock]: 생산자-소비자 예제에서 `sem_wait(&mutex)`와 `sem_wait(&empty)`(또는 `sem_wait(&full)`)의 순서를 바꾸면 교착 상태가 발생한다. 예를 들어 생산자가 `mutex`를 먼저 획득한 뒤 `empty`를 대기하면, `empty`를 증가시킬 소비자가 `mutex`를 획득하지 못해 영원히 진행할 수 없다. — Downey (2016), §4.1.