2.5 经典同步问题与管程

用 PV 操作解决生产者-消费者、多生产者-多消费者、读者-写者、哲学家进餐、吸烟者问题的方法与套路；管程的定义、组成与条件变量。

生产者-消费者问题

一组生产者进程和一组消费者进程共享一个初始为空、大小为 $n$ 的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

semaphore mutex = 1;        // 临界区互斥信号量
semaphore empty = n;        // 空闲缓冲区
semaphore full = 0;         // 缓冲区初始化为空（产品数）

producer() {                        consumer() {
    while (1) {                         while (1) {
        produce an item;                    P(full);       // 获取产品
        P(empty);   // 获取空缓冲区         P(mutex);      // 进入临界区
        P(mutex);   // 进入临界区           remove an item from buffer;
        add item to buffer;                 V(mutex);      // 离开临界区
        V(mutex);   // 离开临界区           V(empty);      // 空缓冲区数加 1
        V(full);    // 产品数加 1           consume the item;
    }                                   }
}                                   }

在下面的实验里，你来扮演调度程序，逐步执行各个进程；切换到”P 操作顺序颠倒”预设，体会为什么会死锁：

多生产者-多消费者问题

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

semaphore plate = 1, apple = 0, orange = 0;
dad()      { while (1) { prepare an apple;  P(plate); put the apple;  V(apple);  } }
mom()      { while (1) { prepare an orange; P(plate); put the orange; V(orange); } }
son()      { while (1) { P(orange); take an orange; V(plate); eat; } }
daughter() { while (1) { P(apple);  take an apple;  V(plate); eat; } }

盘子容量为 1，plate 本身就能保证互斥，因此可以不另设 mutex；若容量大于 1，则必须增加互斥信号量。

读者-写者问题

有读者和写者两组并发进程，共享一个文件。要求：① 允许多个读者可以同时对文件执行读操作；② 只允许一个写者往文件中写信息；③ 任意一个写者在完成写操作之前不允许其他读者或写者工作；④ 写者执行写操作前，应让已有的读者和写者全部退出。

int count = 0;              // 记录当前读者数量
semaphore mutex = 1;        // 保护更新 count 变量时的互斥
semaphore rw = 1;           // 保证读者和写者互斥地访问文件
semaphore w = 1;            // 用于实现"写优先"（读者优先版本中去掉 w 即可）

writer() {                          reader() {
    while (1) {                         while (1) {
        P(w);                               P(w);          // 无写进程请求时进入
        P(rw);                              P(mutex);
        writing;                            if (count == 0) P(rw);   // 第一个读者负责加锁
        V(rw);                              count++;
        V(w);                               V(mutex);
    }                                       V(w);
}                                           reading;
                                            P(mutex);
                                            count--;
                                            if (count == 0) V(rw);   // 最后一个读者负责解锁
                                            V(mutex);
                                        }
                                    }

• 读者优先（去掉信号量 w）：只要有读者在读，后来的读者都能直接进入，写者可能长期饥饿；
• 读写公平 / 写优先（加上 w）：当有写者请求时，后来的读者会被 w 挡住，等写者写完。

哲学家进餐问题

一张圆桌边上坐着 5 名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。

semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi() {
    do {
        P(chopstick[i]);            // 取左边筷子
        P(chopstick[(i + 1) % 5]);  // 取右边筷子
        eat;
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        think;
    } while (1);
}

上面的算法存在问题：当 5 名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完 P(chopstick[i])），筷子已被拿光，等到他们再想拿右边的筷子时就全被阻塞，出现死锁。防止死锁的方法：

1. 至多允许 4 名哲学家同时进餐（再设一个初值为 4 的信号量）；
2. 仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子（一次性拿两根，用 mutex 保护”拿筷子”的过程）；
3. 对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。

int num = 0;                                    // 存储随机数，实现轮流
semaphore offer1 = 0, offer2 = 0, offer3 = 0;   // 三种材料组合
semaphore finish = 0;                           // 抽烟是否完成
supplier() { while (1) { num = num % 3;
    if (num == 0) V(offer1); else if (num == 1) V(offer2); else V(offer3);
    num++; 任意两种材料放在桌子上; P(finish); } }
smoker1() { while (1) { P(offer1); 拿走材料、卷烟、抽掉; V(finish); } }   // smoker2、smoker3 同理

semaphore mutex = 1;    // 缓冲区互斥
semaphore empty = N;    // 空单元数
semaphore odd = 0;      // 缓冲区中奇数的个数
semaphore even = 0;     // 缓冲区中偶数的个数

P1() { while (1) {
    x = produce();
    P(empty);
    P(mutex);
    put(x);
    V(mutex);
    if (x % 2 == 0) V(even); else V(odd);
} }
P2() { while (1) {
    P(odd);
    P(mutex);
    getodd();
    V(mutex);
    V(empty);
    countodd();
} }
P3() { while (1) {
    P(even);
    P(mutex);
    geteven();
    V(mutex);
    V(empty);
    counteven();
} }

管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的 PV 操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是便产生了一种新的进程同步工具——管程。

管程的定义：利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。

管程由 4 部分组成：① 管程的名称；② 局部于管程内部的共享数据结构说明；③ 对该数据结构进行操作的一组过程（函数）；④ 对局部于管程内部的共享数据设置初始值的语句。

• 管程把对共享资源的操作封装起来，管程内的共享数据结构只能被管程内的过程所访问；
• 每次仅允许一个进程进入管程，从而实现进程互斥（这一互斥由编译器实现，程序员无须关心）；
• 条件变量：当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量 condition。每个条件变量保存了一个等待队列，对条件变量只能进行两种操作：x.wait（当 x 对应的条件不满足时，正在调用管程的进程调用 x.wait 将自己插入 x 条件的等待队列，并释放管程）、x.signal（x 对应的条件发生了变化，则调用 x.signal，唤醒一个因 x 条件而阻塞的进程）。

即时练习