Chapter 31 Signal Quantity

第 31 章 信号量

Dijkstra 发明了信号量...信号量可以作为锁和条件变量

1. 信号量的定义

1.1. 初始化

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

初始化参数

1. 信号量s

2. 信号量同一进程的多个线程共享0

3. s初始化值1

1.2. 交互

sem_wait() and sem_post()

int sem_wait(sem_t *s)
{
    // decrement the value of semaphore s by one
    // wait if 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
}

2. 二值信号量（锁）

2.1. 使用

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

sem_wait(&s);

// critical section here

sem_post(&s);

2.2. 两个线程使用同一个信号量

sem_wait() 在 s < 0 时进入等待...否则 - 1 然后进入临界区

所以 s 的初始值的设定也至关重要

这时候信号量只有两个值 就像锁只有 持有和没持有

binary semaphore

3. 信号量用作条件变量

可以用在一个线程暂停执行，等待某一条件成立的场景...一个线程要等待一个链表非空，然后才能删除一个元素...

sem_t s;

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

int main(int argc, char *argv[]) {
    Sem_init(&s, 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;
}

父进程等待子进程...

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

4.1. 第一次尝试

empy 和 full 变量版本...

producer 利用 put

comsumer 利用 get...

4.2. 增加互斥

4.3. 避免死锁

4.4. 可行的方案

5. 读者 - 写者锁

对于并发链表

涉及许多的插入和查找操作，插入操作会修改链表的状态...而查找只是读取该结构...

所以我们可并发执行多个查找操作 reader - writer lock

The code is pretty simple. If some thread wants to update the data structure in question, it should call the new pair of synchronization operations: rwlock_acquire_writelock(), to acquire a write lock, and rwlock_release_writelock(), to release it. Internally, these simply use the writelock semaphore to ensure that only a single writer can acquire the lock and thus enter the critical section to update the data structure in question.

简单的笨方法可能更好 Hill's Law

6. 哲学家就餐问题

dining philosopher's problem

著名的并发问题...

6.1. 有问题的方案

五位哲学家，每人都拿起了左边的叉子，陷入死锁

6.2. 破除依赖

指定最大编号的 philosopher 取餐叉的顺序不同

其他并发问题

吸烟者问题 cigarette smoker's problem

理发师问题 sleeping barber problem

• 哲学家就餐问题是多个哲学家互相争夺有限的资源（筷子），而且需要同时拿到两个资源（左右筷子）才能吃饭

• 吸烟者问题是多个吸烟者需要同时拿到两种不同的资源（材料）才能点烟，而且资源是有限的（桌子上只能放两种）

• 理发师问题是多个顾客和一个服务者（理发师）之间的问题，重点是协调服务的顺序和资源（理发椅和等待椅）的使用

7. 如何实现信号量

底层同步原语（锁 + 条件变量）来实现自己的信号量

Zemaphore

typedef struct __Zem_t {
    int value;
    pthread_cond_t  cond;
    pthread_mutex_t lock;
} Zem_t;

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

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

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

泛化都是错的

8. 作业（编码作业）

write some code...

8.1. fork-join

自己实现一次教材上的例子...关于信号量的初始值...我倒在这一步...现在大致理解了

8.2. 一个双子进程的等待

两个信号量来控制，有点绕，但应该是对的

8.3. 8.2 拓展到 多子进程

主要是初始值的选定

• lock 的初始值为1，表示它可以被一个线程获取（互斥锁）。

• barr 的初始值为 0，表示没有线程可以通过这个信号量（所有线程都会阻塞在这里）。

8.4. reader-writer problem

8.5. reader-writer problem nostarve

8.6. mutex nostarve