信号量

1. 信号量概述

信号量（Semaphore）是一种同步原语，由 Edsger Dijkstra 引入，用于解决并发问题。它可以作为锁和条件变量的替代，用于线程同步。信号量是一个带有整数值的对象，通过 sem_wait() 和 sem_post() 两个主要函数操作。

• 初始化：通过 sem_init(&s, 0, value) 初始化信号量，第三个参数指定初始值。
• sem_wait()：将信号量值减 1，如果值变为负数，调用线程阻塞。
• sem_post()：将信号量值加 1，如果有等待线程，唤醒其中一个。
• 特性：信号量值为负时，绝对值表示等待线程数（尽管用户通常看不到此值）。

2. 二值信号量（用作锁）

信号量初始值为 1 时，可用作锁（二值信号量），保护临界区。

sem_t m;
sem_init(&m, 0, 1); // 初始值为 1
sem_wait(&m);       // 进入临界区，值减为 0
// 临界区代码
sem_post(&m);       // 离开临界区，值恢复为 1

• 工作原理：
  • 第一个线程调用 sem_wait()，信号量值从 1 减到 0，进入临界区。
  • 其他线程调用 sem_wait()，值变为负数，线程阻塞。
  • 释放锁时，sem_post() 增加值并唤醒一个等待线程。
• 场景分析：
  • 单线程：顺利进入和退出临界区。
  • 多线程：第二个线程尝试获取锁时阻塞，直到第一个线程释放锁。

3. 信号量用作条件变量

信号量初始值为 0 时，可用于线程等待某个条件成立，例如父线程等待子线程完成。

sem_t s;
sem_init(&s, 0, 0); // 初始值为 0

void *child(void *arg) {
    printf("child\n");
    sem_post(&s);   // 子线程完成，信号量加 1
    return NULL;
}

int main() {
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s);   // 父线程等待子线程
    printf("parent: end\n");
    return 0;
}

• 工作原理：
  • 场景 1：父线程先运行，sem_wait() 使信号量值减为 -1，阻塞；子线程运行后，sem_post() 使值增为 0，唤醒父线程。
  • 场景 2：子线程先运行，sem_post() 使信号量值增为 1；父线程运行时，sem_wait() 发现值大于 0，直接继续。
• 关键点：初始值 0 确保父线程等待子线程完成。

4. 生产者/消费者问题（有界缓冲区）

生产者/消费者问题是经典的并发问题，使用信号量可实现有界缓冲区同步。

4.1 第一次尝试（无互斥）

使用两个信号量 empty 和 full 分别表示空槽和满槽数量。

sem_t empty, full;
sem_init(&empty, 0, MAX); // 初始 MAX 个空槽
sem_init(&full, 0, 0);    // 初始 0 个满槽

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&empty); // 等待空槽
        put(i);           // 放入数据
        sem_post(&full);  // 增加满槽
    }
}

void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&full);  // 等待满槽
        int tmp = get();  // 取出数据
        sem_post(&empty); // 增加空槽
        printf("%d\n", tmp);
    }
}

• 问题：当 MAX > 1 时，put() 和 get() 操作可能引发竞态条件。例如，两个生产者同时操作缓冲区可能覆盖数据。

4.2 错误修正（加入互斥但有死锁）

引入二值信号量 mutex 保护 put() 和 get()，但直接包裹整个操作会导致死锁。

sem_t mutex;
sem_init(&mutex, 0, 1);

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&mutex); // 获取锁
        sem_wait(&empty);
        put(i);
        sem_post(&full);
        sem_post(&mutex); // 释放锁
    }
}

• 死锁场景：消费者持有 mutex 并等待 full，生产者等待 mutex，形成循环等待。

4.3 正确方案

调整锁范围，仅保护 put() 和 get() 操作，避免死锁。

void *producer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&empty);
        sem_wait(&mutex); // 保护 put
        put(i);
        sem_post(&mutex);
        sem_post(&full);
    }
}

void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        sem_wait(&full);
        sem_wait(&mutex); // 保护 get
        int tmp = get();
        sem_post(&mutex);
        sem_post(&empty);
        printf("%d\n", tmp);
    }
}

• 关键点：将 sem_wait(&empty) 和 sem_wait(&full) 移到锁外，减少锁持有时间，避免死锁。

5. 读者-写者锁

读者-写者锁允许多个读者并发访问，但写者独占访问。

typedef struct _rwlock_t {
    sem_t lock;      // 保护 readers 计数
    sem_t writelock; // 控制写者或读者访问
    int readers;     // 读者计数
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock); // 第一个读者获取写锁
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock); // 最后一个读者释放写锁
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

• 工作原理：
  • 读者：第一个读者获取 writelock，阻止写者；多个读者可并发访问。
  • 写者：等待 writelock，确保独占访问。
  • 最后一个读者释放 writelock，允许写者进入。
• 缺陷：可能导致写者饥饿，需更复杂方案优化公平性。
• 注意：读者-写者锁复杂性可能降低性能，简单锁（如自旋锁）有时更优（Hill 定律）。

6. 哲学家就餐问题

哲学家就餐问题是 Dijkstra 提出的经典并发问题，涉及 5 位哲学家共享 5 把餐叉。

• 问题描述：哲学家在思考和就餐间切换，就餐需同时持有左右两把餐叉。需避免死锁、饥饿，并提高并发性。

• 基本循环：

  c while (1) { think(); getforks(); eat(); putforks(); }

6.1 有问题的方案

每个哲学家按顺序获取左右餐叉，可能导致死锁。

sem_t forks[5];
sem_init(&forks[i], 0, 1); // 每个餐叉初始值为 1

void getforks() {
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
}

void putforks() {
    sem_post(forks[left(p)]);
    sem_post(forks[right(p)]);
}

• 死锁场景：所有哲学家同时获取左餐叉，等待右餐叉，形成循环等待。

6.2 解决方案

通过调整最后一个哲学家的取叉顺序打破循环依赖。

void getforks() {
    if (p == 4) {
        sem_wait(forks[right(p)]); // 先取右叉
        sem_wait(forks[left(p)]);
    } else {
        sem_wait(forks[left(p)]);  // 先取左叉
        sem_wait(forks[right(p)]);
    }
}

• 原理：最后一个哲学家（p=4）先取右叉，避免所有哲学家同时持有左叉的死锁情况。

7. 信号量实现（Zemaphore）

使用锁和条件变量实现信号量（Zemaphore）。

typedef struct _Zem_t {
    int value;             // 信号量值
    pthread_cond_t cond;   // 条件变量
    pthread_mutex_t lock;  // 互斥锁
} Zem_t;

void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

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

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

• 特点：

  • 使用锁保护 value 和条件变量操作。
  • Zem_wait() 等待值大于 0，减 1 后继续。
  • Zem_post() 增加值并唤醒等待线程。
  • 区别于 Dijkstra 定义：值永不小于 0，不反映等待线程数，简化实现。
  • 注意：用信号量实现条件变量较复杂，可能引入缺陷，需谨慎。

8. 总结与扩展

• 信号量优势：灵活且强大，可替代锁和条件变量，解决多种并发问题。
• 经典问题：生产者/消费者、读者-写者锁、哲学家就餐问题展示了信号量的多用途。
• 注意事项：
  • 信号量需正确初始化值，错误值可能导致死锁或逻辑错误。
  • 避免过度泛化（Lampson 建议），简单锁可能更高效。
• 扩展思考：
  • 如何优化读者-写者锁的公平性？
  • 哲学家就餐问题是否可以用其他同步原语（如锁）更高效解决？
  • 信号量在分布式系统中的适用性如何？