← 返回首页
读书笔记

《Operating System：Three Easy Pieces》第三十一章 信号量

📅 2023-01-18📝 GJJ⏱️ 约 5 分钟🏷️ 文字 · 整理

作为与同步有关的所有工作的唯一原语。

信号量的定义

信号量是有一个整数值的对象，可以用两个函数来操作它。在 POSIX 标准中，是sem_wait()和 sem_post()。因为信号量的初始值能够决定其行为，所以首先要初始化信号量，才能调用其他函数与之交互。

c
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

其中申明了一个信号量 s，通过第三个参数，将它的值初始化为 1。sem_init()的第二个参数，在我们看到的所有例子中都设置为 0，表示信号量是在同一进程的多个线程共享的。 读者可以参考手册，了解信号量的其他用法（即如何用于跨不同进程的同步访问），这要求第二个参数用不同的值。 信号量初始化之后，我们可以调用 sem_wait()或 sem_post()与之交互。

c
int sem_wait(sem_t*s) {
    decrement the value of semaphore s by one
    waitif value of semaphore s is negative
}

int sem_post(sem_t*s) {
    increment the value of semaphore s by one
    if there are one or more threads waiting, wake one
}

二值信号量（锁）

用信号量作为锁

c
sem_t m;
// 初值要为1
sem_init(&m, 0, 1);

sem_wait(&m);
// critical section heresem_post(&m);

信号量用作条件变量

信号量也可以用在一个线程暂停执行，等待某一条件成立的场景。

例如，一个线程要等待一个链表非空，然后才能删除一个元素。在这种场景下，通常一个线程等待条件成立，另外一个线程修改条件并发信号给等待线程，从而唤醒等待线程。因为等待线程在等待某些条件（condition）发生变化，所以我们将信号量作为条件变量（condition variable）。

一个线程创建另外一线程，并且等待它结束:

c
sem_t s;

void * child(void *arg)
{
    printf("child\n");
    sem_post(&s); // signal here: child is done
    return NULL;
}

int main(int argc, char *argv[])
{
    sem_init(&s, 0, X); // what should X be? X初始值应是0
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

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

c
sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg)
{
    int i;
    for (i = 0; i < loops; i++)
    {
        // empty/full是一个条件变量，用于唤醒和等待
        // 不过可以自动形成等待队列，比条件变量方便
        sem_wait(&empty); // line p1
        // mutex是一个锁，用于商品队列的操作的保护
        // 锁的作用域很重要，尽可能缩小临界区来避免死锁和提高性能
        sem_wait(&mutex); // line p1.5 (MOVED MUTEX HERE...)
        put(i);           // line p2
        sem_post(&mutex); // line p2.5 (... AND HERE)
        sem_post(&full);  // line p3
    }
}

void *consumer(void *arg)
{
    int i;
    for (i = 0; i < loops; i++)
    {
        sem_wait(&full);  // line c1
        sem_wait(&mutex); // line c1.5 (MOVED MUTEX HERE...)
        int tmp = get();  // line c2
        sem_post(&mutex); // line c2.5 (... AND HERE)
        sem_post(&empty); // line c3
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[])
{
    // ...
    sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...
    sem_init(&full, 0, 0);    // ... and 0 are full
    sem_init(&mutex, 0, 1);   // mutex=1 because it is a lock
    // ...
}

读者—写者锁

另一个经典问题源于对更加灵活的锁定原语的渴望，它承认不同的数据结构访问可能需要不同类型的锁。

例如，一个并发链表有很多插入和查找操作。插入操作会修改链表的状态（因此传统的临界区有用），而查找操作只是读取该结构，只要没有进行插入操作，我们可以并发的执行多个查找操作。

读者之间不互斥，写者之间互斥，读者和写者互斥:

c
typedef struct _rwlock_t
{
    sem_t lock;      // binary semaphore (basic lock)
    sem_t writelock; // used to allow ONE writer or MANY readers
    int readers;     // count of readers reading in critical section
} 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)
{
    // lock锁保护readers计数器
    sem_wait(&rw->lock);
    rw->readers++;
    // 第一个读者需要获取写锁，来与写者互斥
    // 不停有新读者进来会导致写者饿死
    if (rw->readers == 1)
        sem_wait(&rw->writelock); // first reader acquires 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); // last reader releases 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);
}

这一方案可行（符合预期），但有一些缺陷，尤其是公平性。读者很容易饿死写者。存在复杂一些的解决方案，有写者等待时，如何能够避免更多的读者进入并持有锁。 最后，应该指出，读者-写者锁还有一些注意点。它们通常加入了更多开锁（尤其是更复杂的实现），因此和其他一些简单快速的锁相比，读者写者锁在性能方面没有优势。

哲学家就餐问题

题的基本情况是（见图 31.10）：假定有 5 位“哲学家”围着一个圆桌。每两位哲学家之间有一把餐叉（一共 5 把）。哲学家有时要思考一会，不需要餐叉；有时又要就餐。而一位哲学家只有同时拿到了左手边和右手边的两把餐叉，才能吃到东西。关于餐叉的竞争以及随之而来的同步问题，就是我们在并发编程中研究它的原因。

每个哲学家的基本循环：

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

关键的挑战就是如何实现 getforks()和 putforks()函数，保证没有死锁，没有哲学家饿死，并且并发度更高（尽可能让更多哲学家同时吃东西）。

查找餐叉的数量：

c
int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

如果哲学家 p 希望用左手边的叉子，他们就调用 left(p)。类似地，右手边的叉子就用right(p)。模运算解决了最后一个哲学家（p = 4）右手边叉子的编号问题，就是餐叉 0。我们需要一些信号量来解决这个问题。假设需要 5 个，每个餐叉一个：sem_t forks[5]

有问题的解决方案

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

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

使用这个方案会形成死锁，每个人都拿着左手边的叉子就无法继续了（循环等待）

一种方案：破除依赖

选第 4 个人改为先获取右手的叉子，打破循环等待

c
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)]);
    }
}
还有其他一些类似的“著名”问题，比如吸烟者问题（cigarette smoker’s problem），理发师问题（sleeping barber problem）

如何实现信号量

c
typedef struct _Zem_t
{
    int value;
    pthread_cond_t cond;
    // 对value的修改锁
    pthread_mutex_t lock;
} Zem_t;

// only one thread can call this
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);
    // 在这里递减value，value值就不会小于0了。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);
}

小结

信号量是编写并发程序的强大而灵活的原语。有程序员会因为简单实用，只用信号量，不用锁和条件变量

信号量基于锁和条件变量，可以实现两者的功能

作为锁时，可以自动管理等待队列

作为条件变量时，免去了 while 判断是否需要等待的操作，因为内部包含了一个 value 值用于判断

参考

#文字#整理

本文由 GJJ 创作，内容来源于 Notion 数据库，随时可在 Notion 中编辑更新。 本站由 DeepSeek-v4-flash 辅助构建，项目参考 NotionNext。

← 返回首页
61
文章
6
标签
3
分类
962
运行天数