3eb8c077abc236a14e81d2b628f1756fc5807b77



문제의 복잡성이 발생하는 근본 원인은, 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는 무엇인가?
그것을 설명하기 위해 써본다.

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


3eb8c075abd828a14e81d2b628f1726931c8cd



공유 자원이란 무엇인가?

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

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

공유 자원은 상태(state)를 가진다. 이 상태에 동시에 접근하고 수정하려 할 경우, 예기치 못한 오류가 발생시킨다.


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

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

- A가 인쇄 중인데 B가 중간에 인쇄를 시작하면?
- 출력이 중단되거나, 중첩되거나, 백지 출력이 일어날 수 있다.

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

원자적 연산이 필요한 이유

그렇다면 이런 문제를 어떻게 해결할 수 있을까?
핵심은 여러 스레드가 동시에 접근하더라도 상태의 일관성을 보장하는 것, 즉 ‘원자성(Atomicity)’을 확보하는 데 있다.

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

1. `x`의 현재 값을 읽는다
2. 1을 더한다
3. 결과를 다시 `x`에 저장한다

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

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

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

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

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

- A가 프린터에 인쇄 요청을 보내면, 인쇄가 완전히 끝나거나 실패하거나 중단될 때까지 B의 요청은 대기해야 한다.
- 인쇄 도중 B가 끼어들어 출력을 시작하면, 출력물이 섞이거나 일부 누락되는 오류가 발생할 수 있다.
- 따라서 "A의 인쇄 상태"가 명확히 종료되었을 때만 다음 요청(B)을 처리해야, 출력 상태의 일관성이 보장된다.

이것이 바로 원자성의 요구 조건이다.  
출력 중에는 프린터의 상태(State)가 “사용 중”으로 잠금(lock) 상태에 있어야 하며,  
오직 완전한 종료가 일어난 후에만 다음 작업으로 넘어가야 한다.

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

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


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

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


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

그 이유는 다음과 같다:

- 변수는 누구나 읽고 쓸 수 있으며,  
- 어떤 프로세스가 읽어들인 값은, 그 직후에 다른 프로세스에 의해 바뀔 수 있다.  
- 다시 말해, 값을 읽고 그에 반응하기까지의 시간 사이에, 상태는 변할 수 있고, 그 변화는 반영되지 않는다.

이처럼 기존 방식은 “검사-결정-실행”이라는 일련의 흐름이 중간에 깨지기 쉬운 구조이다.  
이 구조적 한계를 극복하기 위해, Edsger W. Dijkstra는 새로운 해결책을 제안한다.

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


3eb8c074abc236a14e81d2b628f1756a305d6e


세마포어란 무엇인가?

세마포어(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(s)wait / acquire세마포어 값이 양수면 1 감소하고 통과, 0이면 대기
V(s)signal / release세마포어 값을 1 증가시킴


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

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

그것이 세마포어이다.


P / V 연산의 정의

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


3eb8c072abc236a14e81d2b628f1756db71b15


현대 OS에서는 이 과정을 futex, spinlock, sleep queue 등으로 구현하는데

주의할 점은

P, V 연산 의사코드에서 `s = s - 1` 이나 `s = s + 1` 그리고 `while (s <= 0) wait;` 조건 검사 부분은 하나의 분리될 수 없는 원자적 단위로 실행되어야 한다.


여기서 `P(s)`의 `while (s <= 0) wait;` 부분이

만약 CPU를 계속 사용하면서 조건이 만족될 때까지 반복 확인하는 바쁜 대기(busy-waiting 또는 spin-waiting)라면, CPU 자원을 매우 비효율적으로 사용하게 된다. 다른 유용한 작업을 할 수 있는 CPU 시간을 낭비하는 것이다.


따라서 현대 운영체제는 이 "wait" 과정을 훨씬 효율적으로 처리하기 위해 다음과 같은 메커니즘들을 사용하는데, 이것이 현대 비동기 처리방법이라고 봐도 무방하다.


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


이 방식들 전반의 이론적 원점은 저 간단한 연산이다. 


요약해서 현대의 OS에서 세마포어 연산을 이야기하면 다음과 같다.


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

- 2. 내부 원자성 확보: P, V 연산 자체의 아주 짧은 코드 실행 동안 세마포어 변수(`s`)나 슬립 큐를 안전하게 수정하기 위해 (커널 내부에서) 스핀락 등이 사용될 수 있음.

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



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

구분의미사용처
Binary Semaphore값: 0 또는 1뮤텍스(Mutex)와 동일
General Semaphore값: 0 이상제한된 자원 (예: DB 커넥션 풀)ㅇㅇ

- C.S. Scholten의 일반 세마포어 개념 확장
    
- 뮤텍스와의 차이점운 소유권 개념 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)에 대한 동시 접근을 제어하고, 사용 가능한 자원의 개수를 정확하게 관리하는 데 사용된다.

끝맺으며

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

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

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