13. Semaphores and Condition Variables

Haram Lee
2026-05-25
studies / 26-1 / operating-systems

Synchronization Types

synchronization은 크게 두 종류의 문제를 해결한다.

mutual exclusion
- 한 번에 하나의 thread만 critical section에 들어가게 하는 것
- shared variable이나 shared data structure를 보호할 때 필요하다.
waiting for events
- 어떤 thread가 다른 thread의 action이 끝날 때까지 기다리는 것
- 예를 들어 producer가 data를 만들 때까지 consumer가 기다리는 상황이 있다.

event waiting이 필요한 대표적인 상황은 다음과 같다.
- producer/consumer
  - 여러 producer와 여러 consumer가 buffer를 공유한다.
- pipeline
  - producer와 consumer가 여러 단계로 연결된다.
- background thread
  - 급하지 않은 일을 CPU가 idle할 때 background에서 처리한다.
즉 synchronization은 단순히 “동시에 못 들어가게 막기”만이 아니라, 특정 조건이 만족될 때까지 기다리고 깨우는 것까지 포함한다.

Higher-level Synchronization

spinlock과 interrupt disabling만으로는 충분하지 않다.
spinlock은 아주 짧고 단순한 critical section에는 유용하다.
하지만 lock이 오래 잡혀 있거나, 어떤 조건이 만족될 때까지 기다려야 하는 상황에서는 비효율적이다.
spinlock은 기다리는 동안 CPU를 계속 소비한다.
따라서 다음과 같은 기능이 필요하다.
- lock이 잡혀 있으면 thread를 block시키기
- 어떤 condition이 만족될 때까지 thread를 sleep시키기
이를 위한 higher-level synchronization mechanism이 있다.
- Semaphores
- Mutexes and Condition Variables
semaphore는 단순하지만 강력하다.
하지만 잘못 쓰기 쉬워서 bug가 생기기 쉽다.
mutex와 condition variable은 Pthreads에서 많이 쓰인다.

Semaphores

lock보다 높은 수준의 synchronization primitive
- Dijkstra가 1968년에 THE OS에서 도입한 개념이다.
- semaphore는 busy waiting을 요구하지 않는다.
- semaphore는 내부적으로 integer value를 가진 object다.
이 integer value는 semaphore의 state다. user program은 이 값을 직접 건드리지는 않고, semaphore operation을 통해서만 값을 바꾼다. semaphore의 동작은 이 integer value에 의해 결정된다.

Semaphore Operations

semaphore는 두 가지 atomic operation으로 조작된다.

`wait()
- semaphore 값을 감소시킨다.
- 값이 0보다 작아지면 기다린다.
- 다른 이름으로는 다음이 있다.
  - P()
  - down()
  - sem_wait()
signal()이다.
- semaphore 값을 증가시킨다.
- 기다리는 thread가 있으면 하나를 깨운다.
- 다른 이름으로는 다음이 있다.
  - V()
  - up()
  - sem_post()

wait()와 signal() 자체가 atomic해야 한다.
즉 semaphore 내부 값을 바꾸고, block/wakeup queue를 조작하는 과정이 race condition 없이 실행되어야 한다.

Implementing Semaphores

semaphore는 개념적으로 다음과 같이 구현할 수 있다.

c
typedef struct {
    int value;
    struct process *Q;
} semaphore;

value는 현재 semaphore 값이다.
Q는 이 semaphore에서 기다리는 process/thread queue다.
wait()는 다음처럼 동작한다.

c
void wait(semaphore *S)
{
    S->value--;

    if (S->value < 0) {
        add this process to S->Q;
        block();
    }
}

signal()은 다음처럼 동작한다.

c
void signal(semaphore *S)
{
    S->value++;

    if (S->value <= 0) {
        remove a process P from S->Q;
        wakeup(P);
    }
}

wait()와 signal()은 semaphore 내부 state를 수정한다.
따라서 이 두 함수 자체도 critical section이다.
즉 semaphore를 구현하려면 내부적으로 또 lock이나 interrupt disabling 같은 atomicity 보장 수단이 필요하다.
여기서 핵심 질문은 다음이다.
- wait/signal을 어떻게 atomic하게 만들 것인가?

Binary Semaphore

binary semaphore는 값이 0 또는 1처럼 동작하는 semaphore다.
- 초기값을 1로 두면 mutex처럼 사용할 수 있다.
- 하나의 thread만 resource에 접근하게 만들 수 있다.
사용 예시는 다음과 같다.

c
wait(&S);

/* critical section */

signal(&S);

Counting Semaphore

counting semaphore는 값이 여러 개의 resource unit을 나타낸다.
초기값을 N으로 두면 최대 N개의 thread가 동시에 통과할 수 있다.
예를 들어 buffer slot이 N개라면 semaphore 값을 N으로 둘 수 있다.
thread가 resource 하나를 사용하려면 wait()로 값을 하나 줄인다.
resource를 반납하면 signal()로 값을 하나 늘린다.
- 대표적으로 producer/consumer 문제에서 사용된다.

Bounded Buffer Problem

bounded buffer problem은 producer/consumer 문제다.
producer는 buffer에 item을 넣고, consumer는 buffer에서 item을 꺼낸다.
buffer 크기는 정해져 있다.
따라서 다음 조건을 지켜야 한다.
1. buffer가 가득 차면 producer는 기다려야 한다.
2. buffer가 비어 있으면 consumer는 기다려야 한다.
3. buffer, in, out 같은 shared variable은 mutual exclusion으로 보호해야 한다.
producer와 consumer는 서로 다른 속도로 실행될 수 있다.
buffer는 이 둘을 느슨하게 연결해 준다.
producer가 consumer에게 직접 handoff하지 않아도 된다.
pipe도 producer/consumer 구조의 예시로 볼 수 있다.

Bounded Buffer: No Synchronization

synchronization 없이 구현하면 다음과 같은 코드가 된다.

c
int count;

struct item buffer[N];
int in, out;

void produce(data)
{
    while (count == N);

    buffer[in] = data;
    in = (in + 1) % N;
    count++;
}

void consume(data)
{
    while (count == 0);

    data = buffer[out];
    out = (out + 1) % N;
    count--;
}

문제

busy waiting
- buffer가 가득 차거나 비어 있으면 while loop에서 계속 돈다.
- CPU를 낭비한다.
shared variable에 race condition이 생김
- count
- in
- out
- buffer

producer와 consumer가 동시에 count를 수정하면 update가 꼬일 수 있다.
따라서 mutual exclusion과 event waiting이 모두 필요하다.

Bounded Buffer: Critical Section

buffer를 조작하는 부분은 critical section이다.
보호해야 할 shared state는 다음과 같다.
- buffer
- in
- out
- count
단순히 mutex만 쓰면 mutual exclusion은 해결된다. 하지만 buffer가 full이거나 empty인 경우를 처리하기 어렵다.
예를 들어 producer가 mutex를 잡은 상태에서 count == N을 기다리면 consumer가 buffer를 비우기 위해 들어올 수 없다.
즉 mutex만으로는 event waiting을 잘 처리하기 어렵다.
그래서 bounded buffer에는 보통 semaphore 세 개를 사용한다.
- mutex
- empty
- full

Bounded Buffer with Semaphores

semaphore를 사용한 bounded buffer는 다음 세 semaphore를 둔다.

c
Semaphore mutex = 1;
Semaphore empty = N;
Semaphore full = 0;

mutex는 buffer 조작을 위한 mutual exclusion이다.
empty는 비어 있는 slot 개수다.
full은 item이 들어 있는 slot 개수다.
producer는 다음처럼 동작한다.

c
void produce(data)
{
    wait(&empty);
    wait(&mutex);

    buffer[in] = data;
    in = (in + 1) % N;

    signal(&mutex);
    signal(&full);
}

producer는 먼저 empty slot이 있는지 확인한다.
empty slot이 없으면 wait(&empty)에서 잠든다.
empty slot이 있으면 mutex를 잡고 buffer에 data를 넣는다.
data를 넣은 뒤 full을 signal해서 consumer에게 item이 생겼음을 알린다.
consumer는 다음처럼 동작한다.

c
void consume(data)
{
    wait(&full);
    wait(&mutex);

    data = buffer[out];
    out = (out + 1) % N;

    signal(&mutex);
    signal(&empty);
}

consumer는 먼저 full slot, 즉 꺼낼 item이 있는지 확인한다.
item이 없으면 wait(&full)에서 잠든다.
item이 있으면 mutex를 잡고 buffer에서 data를 꺼낸다.
data를 꺼낸 뒤 empty를 signal해서 producer에게 빈 slot이 생겼음을 알린다.
이 구조에서 empty와 full은 event coordination을 담당하고, mutex는 critical section 보호를 담당한다.

Bounded Buffer에서 Semaphore 순서

semaphore 사용 순서가 중요하다.
producer는 empty를 먼저 기다리고, 그다음 mutex를 잡는다.
consumer는 full을 먼저 기다리고, 그다음 mutex를 잡는다.
만약 mutex를 먼저 잡고 empty나 full을 기다리면 deadlock이 생길 수 있다.
예를 들어 producer가 mutex를 잡고 buffer가 full이라서 기다리면, consumer가 buffer를 비우기 위해 mutex를 잡을 수 없다.
따라서 event condition을 기다리는 semaphore를 먼저 처리하고, 실제 buffer 조작 직전에 mutex를 잡는 것이 중요하다.

Readers-Writers Problem

reader는 object를 읽기만 한다.
writer는 object를 수정한다.
- 동시에 여러 reader가 읽는 것은 허용할 수 있다.
- 하지만 writer는 혼자 접근해야 한다.
즉 조건은 다음과 같다.
- 여러 reader는 동시에 가능하다.
- writer는 한 번에 하나만 가능하다.
- writer가 있을 때 reader가 들어오면 안 된다.
- reader가 있을 때 writer가 들어오면 안 된다.
semaphore를 사용한 구현에서는 다음 변수를 둔다.
- readcount: 현재 읽고 있는 reader 수
- mutex: readcount 보호용 semaphore
- rw: 실제 read/write object 접근 제어용 semaphore

Readers-Writers with Semaphores

기본 구조는 다음과 같다.

c
int readcount = 0;

Semaphore mutex = 1;
Semaphore rw = 1;

writer는 단순하다.

c
void Writer()
{
    wait(&rw);

    /* Write */

    signal(&rw);
}

writer는 rw를 얻어야만 쓸 수 있다.
writer가 rw를 잡고 있으면 reader도 writer도 들어올 수 없다.
reader는 조금 더 복잡하다.

c
void Reader()
{
    wait(&mutex);

    readcount++;
    if (readcount == 1)
        wait(&rw);

    signal(&mutex);

    /* Read */

    wait(&mutex);

    readcount--;
    if (readcount == 0)
        signal(&rw);

    signal(&mutex);
}

첫 번째 reader가 들어올 때 rw를 잡는다.
그러면 writer가 들어오지 못한다.
두 번째 이후 reader는 rw를 다시 잡지 않고 들어올 수 있다.
마지막 reader가 나갈 때 rw를 release한다.
그러면 writer가 들어올 수 있다.
이 방식은 multiple readers를 허용하면서 writer와 reader의 동시 접근은 막는다.
writer가 이미 있으면 첫 번째 reader는 rw에서 block된다.
그 뒤 다른 reader들은 mutex에서 block될 수 있다.
writer가 나가면 reader들이 들어갈 수 있다.
마지막 reader가 나가면 writer가 들어갈 수 있다.
하지만 이 구현에는 fairness 문제가 있을 수 있다.
새로운 reader가 계속 들어오면 writer가 오래 기다릴 수 있다.
즉 reader-preference 방식에서는 writer starvation이 생길 수 있다.
반대로 writer를 우선하면 reader starvation이 생길 수 있다.
readers-writers problem은 단순 mutual exclusion보다 정책 문제가 더 중요해지는 예시다.

Dining Philosophers Problem

dining philosophers problem은 Dijkstra가 제시한 고전적인 synchronization 문제다.
철학자 N명이 둥근 테이블에 앉아 있다고 하자.
각 철학자는 다음을 반복한다.
- thinking
- 왼쪽 fork 집기
- 오른쪽 fork 집기
- eating
- fork 내려놓기
각 fork는 인접한 두 철학자가 공유한다.
철학자가 밥을 먹으려면 fork 두 개가 모두 필요하다.
문제는 모든 철학자가 동시에 한쪽 fork만 집으면 deadlock이 생길 수 있다는 점이다.
이 문제는 resource allocation과 deadlock을 설명하기 좋은 예시다.

Dining Philosophers: Simple Solution

각 fork를 semaphore로 표현할 수 있다.
각 fork semaphore는 1로 초기화한다.

c
Semaphore forks[N];

#define L(i) (i)
#define R(i) ((i + 1) % N)

철학자는 다음처럼 동작한다.

c
void philosopher(int i)
{
    while (1) {
        think();
        pickup(i);
        eat();
        putdown(i);
    }
}

단순한 pickup()은 다음과 같다.

c
void pickup(int i)
{
    wait(&forks[L(i)]);
    wait(&forks[R(i)]);
}

putdown()은 다음과 같다.

c
void putdown(int i)
{
    signal(&forks[L(i)]);
    signal(&forks[R(i)]);
}

이 방식은 직관적이지만 deadlock 가능성이 있다.
모든 철학자가 동시에 왼쪽 fork를 집으면, 오른쪽 fork를 기다리면서 모두 멈춘다.
아무도 fork를 내려놓지 않으므로 deadlock이다.

Dining Philosophers: Deadlock-free Solution

deadlock을 피하는 한 가지 방법은 마지막 철학자만 fork를 집는 순서를 바꾸는 것이다.
대부분의 철학자는 왼쪽을 먼저 집고 오른쪽을 집는다.
하지만 마지막 철학자는 오른쪽을 먼저 집고 왼쪽을 집는다.

c
void pickup(int i)
{
    if (i == (N - 1)) {
        wait(&forks[R(i)]);
        wait(&forks[L(i)]);
    } else {
        wait(&forks[L(i)]);
        wait(&forks[R(i)]);
    }
}

이렇게 하면 모든 철학자가 같은 방향으로 resource를 기다리는 cycle이 깨진다.
즉 circular wait 조건을 제거한다.
deadlock의 네 가지 필요조건 중 circular wait을 깨면 deadlock을 막을 수 있다.
이 예시는 semaphore 자체보다 resource acquisition order가 중요하다는 점을 보여준다.

Semaphores: Pros

semaphore의 장점은 하나의 primitive로 여러 문제를 해결할 수 있다는 것이다.
semaphore는 mutual exclusion에도 사용할 수 있다.
- binary semaphore
- mutex처럼 사용
semaphore는 coordination에도 사용할 수 있다.
- counting semaphore
- full/empty slot 관리
- event 발생 기다리기
즉 semaphore는 단순하지만 표현력이 강하다.
bounded buffer, readers-writers, dining philosophers 같은 고전 문제를 모두 semaphore로 해결할 수 있다.

Semaphores: Cons

semaphore는 강력하지만 programming하기 어렵다.
단점은 다음과 같다.

semaphore는 사실상 shared global variable처럼 쓰일 수 있다.
- 어디서든 접근 가능하면 code structure가 나빠질 수 있다.
semaphore와 보호하려는 data 사이의 연결이 명시적이지 않다.
- 어떤 semaphore가 어떤 data를 보호하는지 코드만 보고 헷갈릴 수 있다.
사용법을 강제할 방법이 없다.
- wait()와 signal() 순서를 잘못 쓰면 bug가 생긴다.
- signal을 빼먹거나 wait을 잘못 호출해도 compiler가 잡아주지 않는다.
semaphore는 너무 일반적이라 오히려 이해하기 어렵다.

따라서 semaphore는 powerful하지만 bug-prone하다.

Condition Variables

condition variable, CV는 event waiting을 위한 mechanism이다.
CV는 explicit queue라고 볼 수 있다.
어떤 execution state가 만족되지 않으면 thread가 CV에 자신을 넣고 잠든다.
condition variable은 항상 mutex와 함께 사용한다.
mutex는 critical section에 대한 mutual exclusion을 제공한다.
condition variable은 특정 조건이 만족될 때까지 기다리는 기능을 제공한다.
어떤 condition을 확인하거나 수정하는 작업은 mutex 안에서 해야 한다.
즉 CV의 기본 패턴은 다음이다.
- mutex를 잡는다.
- condition을 확인한다.
- condition이 false이면 CV에서 기다린다.
- condition이 true이면 작업한다.
- mutex를 푼다.

CV Operations

condition variable의 대표 operation은 세 가지다.
- wait()
- signal()
- broadcast()

`wait(cond_t cv, mutex_t mutex)`

wait()은 caller가 mutex를 이미 들고 있다고 가정한다.
wait()은 다음을 atomic하게 수행한다.
- caller를 sleep시킨다.
- mutex를 release한다.
나중에 깨어나면 return하기 전에 mutex를 다시 acquire한다.
이 atomic release-and-sleep이 매우 중요하다.
만약 mutex를 풀고 sleep하기 사이에 signal이 오면 lost wakeup이 생길 수 있다.
따라서 CV wait은 반드시 mutex와 함께 쓰인다.

`signal(cond_t *cv)`

signal()은 CV에서 기다리는 thread 하나를 깨운다.
기다리는 thread가 없으면 아무 일도 하지 않는다.
semaphore와 중요한 차이가 있다.
CV는 history가 없다.
즉 기다리는 thread가 없을 때 발생한 signal은 저장되지 않는다.
나중에 어떤 thread가 wait해도 과거 signal 때문에 깨어나지 않는다.
따라서 CV는 반드시 condition state와 함께 사용해야 한다.
단순히 signal 자체를 event count처럼 생각하면 안 된다.

`broadcast(cond_t *cv)`

broadcast()는 CV에서 기다리는 모든 thread를 깨운다.
기다리는 thread가 없으면 아무 일도 하지 않는다.
어떤 thread를 깨워야 할지 signaler가 모를 때 사용한다.
예를 들어 memory allocator에서 여러 thread가 서로 다른 size의 memory를 기다리는 경우가 있다.
free가 발생했을 때 어떤 thread의 요청이 만족될지 모르므로 모두 깨워서 다시 condition을 확인하게 할 수 있다.

Pthreads Interface

Pthreads에서는 mutex와 condition variable을 함께 제공한다.
기본 선언은 다음과 같다.

c
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void wait_example()
{
    pthread_mutex_lock(&m);
    pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
}

void signal_example()
{
    pthread_mutex_lock(&m);
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

condition을 바꾸는 thread도 mutex를 잡고 signal해야 한다.
condition을 기다리는 thread도 mutex를 잡고 wait해야 한다.

Joining Threads: Initial Attempt

thread join을 condition variable로 구현한다고 생각해보자.
child thread가 끝나면 parent thread가 그것을 기다렸다가 계속 실행해야 한다.
처음 시도는 다음처럼 할 수 있다.

c
mutex_t m = MUTEX_INITIALIZER;
cond_t c = COND_INITIALIZER;

void thread_exit()
{
    mutex_lock(&m);
    cond_signal(&c);
    mutex_unlock(&m);
}

void thread_join()
{
    mutex_lock(&m);
    cond_wait(&c, &m);
    mutex_unlock(&m);
}

이 코드는 문제가 있다.
child가 parent의 cond_wait()보다 먼저 cond_signal()을 호출하면 signal이 사라진다.
CV는 history가 없기 때문이다.
그러면 parent는 이미 끝난 child를 기다리며 영원히 잠들 수 있다.
즉 lost wakeup 문제가 생긴다.

Joining Threads: Keep State

이 문제를 해결하려면 CV와 별도로 state를 둬야 한다.
예를 들어 done 변수를 사용한다.

c
mutex_t m = MUTEX_INITIALIZER;
cond_t c = COND_INITIALIZER;
int done = 0;

child가 끝날 때 done = 1로 만든다.
parent는 wait하기 전에 done을 확인한다.
두 번째 시도는 다음과 같다.

c
void thread_exit()
{
    done = 1;
    cond_signal(&c);
}

void thread_join()
{
    mutex_lock(&m);

    if (done == 0)
        cond_wait(&c, &m);

    mutex_unlock(&m);
}

하지만 이것도 완전하지 않다.
done을 수정할 때 mutex를 잡지 않았기 때문이다.
condition과 관련된 state는 반드시 mutex로 보호해야 한다.

Joining Threads: Correct Pattern

올바른 방식은 condition state를 수정할 때도 mutex를 잡는 것이다.

c
void thread_exit()
{
    mutex_lock(&m);
    done = 1;
    cond_signal(&c);
    mutex_unlock(&m);
}

void thread_join()
{
    mutex_lock(&m);

    if (done == 0)
        cond_wait(&c, &m);

    mutex_unlock(&m);
}

이 구조에서는 done과 CV가 같은 mutex로 보호된다.
child가 먼저 끝났다면 done == 1이므로 parent는 wait하지 않는다.
parent가 먼저 기다리고 있다면 child가 signal해서 parent를 깨운다.
핵심은 CV 자체가 event를 저장하지 않으므로, event 발생 여부를 나타내는 state variable이 필요하다는 것이다.

CV Semantics

Mesa semantics
Hoare semantics

Mesa Semantics

Pthreads는 Mesa semantics를 사용한다.
Mesa semantics에서는 signal()이 waiter를 ready queue에 넣을 뿐이다.
signaler는 critical section 안에서 계속 실행한다.
즉 signal을 받은 thread가 즉시 실행되는 것이 아니다.
따라서 waiter가 실제로 다시 실행될 때 condition이 여전히 true라는 보장이 없다.
다른 thread가 먼저 실행되어 condition을 다시 바꿨을 수도 있다.
그래서 Mesa semantics에서는 wakeup은 단지 “뭔가 바뀌었으니 다시 확인해봐”라는 hint에 가깝다.
따라서 condition check는 반드시 if가 아니라 while로 해야 한다.

Hoare Semantics

Hoare semantics에서는 signal()이 호출되면 즉시 signaler에서 waiting thread로 control이 넘어간다.
이 경우 waiter가 실행될 때 기다리던 condition이 만족된다고 보장할 수 있다.
즉 signal의 의미가 더 강하다.
하지만 구현이 복잡하고 context switch 방식도 다르다.
실제 Pthreads에서는 Mesa semantics를 사용하므로, 우리는 while로 condition을 재확인하는 패턴을 기억해야 한다.

Why while, not if?

condition variable에서는 if보다 while을 써야 한다.
이유는 다음과 같다.
- spurious wakeup이 있을 수 있다.
- signal을 받고 깨어났지만 condition이 다시 false가 되었을 수 있다.
- broadcast로 여러 thread가 깨어났지만 그중 하나만 condition을 만족시킬 수 있다.
시험에서는 다음 Pthreads 안전 패턴을 먼저 떠올리면 된다.

c
pthread_mutex_lock(&m);

while (condition == false)
    pthread_cond_wait(&c, &m);

pthread_mutex_unlock(&m);

pthread_cond_wait()는 기다리는 동안 mutex를 release하고, 깨어날 때 다시 acquire한다.
깨어났다는 사실은 condition이 참이라는 보장이 아니라, 다시 확인해야 한다는 신호다.
bounded buffer를 CV로 구현하면 다음과 같은 패턴을 쓴다.

c
mutex_t m;
cond_t not_full, not_empty;
int in, out, count;

void produce(data)
{
    mutex_lock(&m);

    while (count == N)
        cond_wait(&not_full, &m);

    buffer[in] = data;
    in = (in + 1) % N;
    count++;

    cond_signal(&not_empty);
    mutex_unlock(&m);
}

c
void consume(data)
{
    mutex_lock(&m);

    while (count == 0)
        cond_wait(&not_empty, &m);

    data = buffer[out];
    out = (out + 1) % N;
    count--;

    cond_signal(&not_full);
    mutex_unlock(&m);
}

producer는 buffer가 full이면 not_full에서 기다린다.
consumer는 buffer가 empty이면 not_empty에서 기다린다.
깨어난 뒤에도 반드시 다시 condition을 확인한다.
따라서 while이 맞다.

Using Broadcast

broadcast()는 어떤 thread를 깨워야 할지 signaler가 모를 때 사용한다.
이를 covering condition이라고 볼 수 있다.
예를 들어 memory allocator를 생각해보자.
여러 thread가 서로 다른 size의 memory를 기다릴 수 있다.
free가 발생했을 때 어떤 thread의 요청 size가 만족되는지 signaler는 모를 수 있다.
이런 경우 모두 깨운 뒤 각자 condition을 다시 확인하게 한다.

c
mutex_t m;
cond_t c;
int bytesLeft = MAX_HEAP_SIZE;

void free(void *p, int size)
{
    mutex_lock(&m);

    bytesLeft += size;
    cond_broadcast(&c);

    mutex_unlock(&m);
}

c
void *allocate(int size)
{
    mutex_lock(&m);

    while (bytesLeft < size)
        cond_wait(&c, &m);

    void *ptr = ...;
    bytesLeft -= size;

    mutex_unlock(&m);
    return ptr;
}

free가 memory를 추가하면 모든 waiting allocator를 깨운다.
각 allocator는 자기 size 조건을 다시 검사한다.
조건이 만족된 thread만 진행하고, 나머지는 다시 sleep한다.
broadcast는 안전하지만 많은 thread를 깨우므로 비용이 클 수 있다.
그래서 signal로 충분하면 signal을 쓰고, signaler가 누굴 깨워야 할지 모르면 broadcast를 쓴다.

Semaphores vs. Mutexes + CVs

semaphore와 mutex + condition variable은 같은 expressive power를 가진다.
즉 서로를 이용해서 구현할 수 있다.
semaphore는 내부 count를 가지고 있다.
condition variable은 count를 직접 저장하지 않으므로 별도의 state variable이 필요하다.
semaphore를 mutex와 CV로 구현하면 다음과 같다.

c
typedef struct sema_t {
    int v;
    cond_t c;
    mutex_t m;
} sema_t;

c
void sema_init(sema_t *s, int v)
{
    s->v = v;
    cond_init(&s->c);
    mutex_init(&s->m);
}

c
void sema_wait(sema_t *s)
{
    mutex_lock(&s->m);

    while (s->v <= 0)
        cond_wait(&s->c, &s->m);

    s->v--;

    mutex_unlock(&s->m);
}

c
void sema_signal(sema_t *s)
{
    mutex_lock(&s->m);

    s->v++;
    cond_signal(&s->c);

    mutex_unlock(&s->m);
}

여기서 v가 semaphore의 count 역할을 한다.
c는 count가 양수가 될 때까지 기다리는 queue 역할을 한다.
m은 v와 c 조작을 보호한다.
이 구현에서도 while을 사용한다.
condition variable에서는 깨어났다고 해서 condition이 반드시 true라는 보장이 없기 때문이다.

Semaphore와 CV의 차이

semaphore와 CV의 가장 큰 차이는 history의 유무다.
semaphore는 count를 가진다.
- signal이 먼저 발생하면 count가 증가한다.
- 나중에 wait하는 thread가 그 count를 사용할 수 있다.
CV는 history가 없다.
- signal이 먼저 발생했는데 waiting thread가 없으면 signal은 사라진다.
- 나중에 wait해도 과거 signal은 기억되지 않는다.
따라서 semaphore는 resource count 표현에 좋다.
CV는 condition state와 함께 사용할 때 좋다.
semaphore는 하나의 primitive로 mutual exclusion과 coordination을 모두 표현할 수 있다.
mutex + CV는 역할이 더 분리된다.
- mutex: shared state 보호
- CV: condition이 바뀔 때까지 기다림
그래서 mutex + CV가 code 의미를 더 명확하게 만들 수 있다.

Disabling Interrupts

synchronization mechanism을 정리하면 가장 낮은 수준에는 interrupt disabling이 있다.
interrupt disabling은 single CPU kernel에서만 제한적으로 유용하다.
user program에서는 사용할 수 없다.
multi-core에서는 한 CPU의 interrupt를 꺼도 다른 CPU가 실행될 수 있으므로 충분하지 않다.
따라서 현대 multiprocessor 환경에서는 일반적인 synchronization 도구로 쓰기 어렵다.

Spinlocks

spinlock은 atomic instruction을 이용해서 구현된다.
thread는 lock이 풀릴 때까지 busy waiting한다.
짧은 critical section에는 유용하다.
하지만 오래 기다릴 수 있는 상황에서는 CPU를 낭비한다.
semaphore나 mutex/CV는 이런 spinlock의 한계를 보완한다.
즉 thread를 block시켜 CPU를 다른 작업에 쓸 수 있게 한다.

Summary

이 단원은 lock보다 높은 수준의 synchronization mechanism을 다룬다.
synchronization 문제는 크게 두 가지다.
- mutual exclusion
- waiting for events
spinlock과 interrupt disabling은 짧은 critical section에는 유용하지만, 복잡한 coordination에는 부족하다.
semaphore는 integer value를 가진 synchronization object다.
semaphore의 주요 operation은 다음이다.
- wait()
- signal()
binary semaphore는 mutex처럼 사용할 수 있다.
counting semaphore는 여러 개의 resource unit을 관리할 수 있다.
bounded buffer에서는 보통 다음 semaphore를 사용한다.
- mutex
- empty
- full
readers-writers problem에서는 여러 reader는 동시에 허용하고 writer는 exclusive하게 만든다.
dining philosophers problem은 deadlock과 resource ordering 문제를 보여준다.
semaphore는 강력하지만 너무 일반적이라 사용하기 어렵고 bug-prone하다.
condition variable은 thread가 특정 condition을 기다릴 수 있게 해준다.
CV는 반드시 mutex와 함께 사용한다.
CV의 주요 operation은 다음이다.
- wait()
- signal()
- broadcast()
Pthreads는 Mesa semantics를 사용한다.
따라서 깨어난 thread는 condition을 반드시 다시 확인해야 한다.
그래서 cond_wait()은 보통 if가 아니라 while 안에서 사용한다.
semaphore와 mutex + CV는 같은 expressive power를 가진다.
하지만 semaphore는 count를 가지고 history가 있고, CV는 history가 없으므로 별도의 state variable이 필요하다.
결국 13단원의 핵심은 shared resource 보호뿐 아니라 thread 간 event waiting까지 다루기 위해 semaphore와 condition variable 같은 higher-level synchronization이 필요하다는 것이다.

Discussion

13. Semaphores and Condition Variables

Synchronization Types

Higher-level Synchronization

Semaphores

Semaphore Operations

Implementing Semaphores

Binary Semaphore

Counting Semaphore

Bounded Buffer Problem

Bounded Buffer: No Synchronization

Bounded Buffer: Critical Section

Bounded Buffer with Semaphores

Bounded Buffer에서 Semaphore 순서

Readers-Writers Problem

Readers-Writers with Semaphores

Dining Philosophers Problem

Dining Philosophers: Simple Solution

Dining Philosophers: Deadlock-free Solution

Semaphores: Pros

Semaphores: Cons

Condition Variables

CV Operations

wait(cond_t *cv, mutex_t *mutex)

signal(cond_t *cv)

broadcast(cond_t *cv)

Pthreads Interface

Joining Threads: Initial Attempt

Joining Threads: Keep State

Joining Threads: Correct Pattern

CV Semantics

Mesa Semantics

Hoare Semantics

Why while, not if?

Using Broadcast

Semaphores vs. Mutexes + CVs

Semaphore와 CV의 차이

Disabling Interrupts

Spinlocks

Summary

`wait(cond_t cv, mutex_t mutex)`

`signal(cond_t *cv)`

`broadcast(cond_t *cv)`