信号量 — Lalande.

两个愿望，一次满足！

Dijkstra 提出的信号量 (semaphore) 原语既可以作为互斥锁，又可以作为条件变量。

信号量本质上就是一个被保护的整数变量。

二值信号量

等价于互斥锁。

信号量初始化 sem_init() 为 1，sem_wait() 锁住关键区，sem_post() 释放。

读取/写入问题

读取/写入问题 (readers-writers problem) 也是一个经典的同步场景。读线程仅读取共享资源，而写线程会修改共享资源。

同步要求：

多个读线程可同时访问共享资源
同一时间最多只能有一个写线程访问共享资源
写进程与读进程不可同时访问共享资源

A simple read-write lock

int read_count = 0;

void acquire_readlock() {
    sem_wait(&lock);
    read_count++;
    if (read_count == 1)
        sem_wait(&writelock);   // first reader locks the resource
    sem_post(&lock);
}

void release_readlock() {
    sem_wait(&lock);
    read_count--;
    if (read_count == 0)
        sem_post(&writelock);   // last reader unlocks the resource
    sem_post(&lock);
}

void acquire_writelock() {
    sem_wait(&writelock);   // writer locks the resource
}

void release_writelock() {
    sem_post(&writelock);   // writer unlocks the resource
}

哲学家就餐问题

哲学家就餐问题 (dining philosopher's problem) Dijkstra 提出的一种有趣的同步模型。

5 个哲学家围坐在圆形餐桌旁，每位哲学家之间各有一支餐叉。哲学家会进行两种操作：

思考
进食：需要左右手侧的两支餐叉

直觉做法：每位哲学家进食前 sem_wait(fork[left]) 并 sem_wait(fork[right])，进食后 sem_post(fork[left]) 并 sem_post(fork[right])。但假设每位哲学家开始都拿起了自己左侧的餐叉，将会死锁。

解决方案：改变某位哲学家拿餐叉的顺序：先 sem_wait(fork[right]) 再 sem_wait(fork[left])。

通用信号量

或称计数信号量 (counting semaphores)，常用于控制资源的访问。

sem_init() 初始化信号量为资源数目
线程占用资源时 sem_wait()
进程释出资源时 sem_post()

实现

使用互斥锁与条件变量可以轻松实现信号量。

A simple implementation

typedef struct __Sem_t {
    int value;
    pthread_cond_t  cond;
    pthread_mutex_t lock;
} Sem_t;

// only one thread can call this
void Sem_init(Sem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

void Sem_wait(Sem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
        Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
}

void Sem_post(Sem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

阅读

Chapter 31 – Semaphores, OSTEP, http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf