操作系统（专题）：信号量编程（下）

2017-01-08

此部分包括一些和《信号量编程（上）》相比稍难的信号量编程习题，可能有一小部分超出了考试范畴。这部分习题的解答均根据我个人理解编写， 不保证提供的答案绝对正确或最优 。

注 1：习题主要来自 2000 年左右的各高校入学考试题，部分来自网络以及经典的信号量问题。
注 2：以下问题顺序随机，难度之间并无递增/递减关系，可能有部分问题超出考试范畴。但其中第 1 ~ 4 题和之前信号量编程（上）中的习题 7.16 类似，之间存在类比、递进的关系。
注 3：我提供了一份比较简陋的代码，可以帮助你 测试设计的信号量算法是否正确 。详细可查看本文末尾的 “信号量编程测试”。

单向行驶问题

（北京大学 1992 年）有一座桥连接了南北两侧，两侧均有车辆试图到另一侧，桥上不允许两车交会，但允许相同方向多辆车依次通行（桥上可以有多个同方向的车）。用信号量实现交通管理。
本题和信号量编程（上）中的习题 7.16 （过桥问题）类似，但过桥问题要求桥上同时只能通过一人且保证不出现饥饿现象（习题 7.15 不要求处理饥饿，7.16 要求保证不会发生饥饿），所以此处我将其称之为单向行驶问题。我对本题的进一步修改和分析记录在互斥读者-读者问题中。
分析：因为同方向允许多辆车连续通行，很容易联想到读者-写者问题的读者。在操作系统（五）：进程互斥里介绍的读者-写者问题中，允许多个到来的读者一起读数据库。将车辆视作读者，同方向到来的多个车辆可以依次通过而不必等待。既然允许多个读者，就必须记录当前的　“读者”，也就是这里的汽车数量。
定义信号量和变量如下：
- count1 = count2 = 0 ：分别记录当前已经位于桥上的南北两个方向来车数量，显然两个变量要么均为 0，要么一个非 0 而另一个就必须为 0。
- mutex1 = mutex2 = 1 ：用于控制对 count1 和 count2 的互斥操作。
- bridge = 1 ：过桥的权限。
代码如下

int count1 = count2 = 0;
semaphore mutex1 = mutex2 = 1;
semaphore bridge = 1;
// 北方来车
void car_from_north() {
    wait(mutex1);
    count1 ++;
    if (count1 == 1)
        wait(bridge);
    signal(mutex1);
    // 过桥
    wait(mutex1);
    count1 --;
    if (count1 == 0)
        signal(bridge);
    signal(mutex1);
}

// 南方来车与北方对称

士兵过桥问题

独木桥的左右两端各停留一队士兵，左侧有 m 个，右侧有 n 个。两侧士兵均可上桥，但一旦有一侧士兵上桥，另一侧士兵必须等待已上桥一侧的士兵全部通过后才可上桥。试使用信号量描述此过程。
分析：与单向行驶问题类似，只需要保证一方先全部通过即可。因此需要记录两侧的人数。
定义变量和信号量：
- int left = 0, right = 0 ：记录左右两侧已经通过的士兵数目
- semaphore left_mutex = right_mutex = 1 ：操作变量 left 和 right 的互斥锁
- semaphore bridge = 1 ：桥的资源
代码如下

// 左侧士兵
do {
    wait(left_mutex);
    left ++;
    int number = left;  // 临时变量记录自己是第几个通过的士兵
    if (left == 1)
        wait(bridge);
    signal(left_mutex);
    // 过桥
    if (number == m)
        signal(bridge);
} while (TRUE);  

// 右侧士兵与左侧同理

有限双向行驶问题

（南开大学 1997 年题）在南开大学和天津大学之间有一条小路 S -> T，小路中间有一个安全岛 M，安全岛能够同时容纳两辆自行车，可供两个已经从两端进入小路的自行车错车用。整个地图如下图，S 到 K 段的小路和 T 到 L 段的小路同时都只能允许一辆自行车通过。试设计一个算法，使来往的自行车都能顺利通过。
此题和上面的单向行驶问题类似，但同时每个方向只能允许一辆车通过，并且允许两个方向各有来车一辆。此题和教材 7.16 过桥问题也非常相似。应当注意体会本题和单向行驶、习题 7.16 的区别与联系。
分析：需要先确定需要用信号量维护的资源对象种类和数量。首先 S 端和 T 端能且仅能进入一辆自行车，直到进入的自行车从另一端离开，否则在我方通行两辆自行车期间，一旦对方有来车就会出现死锁。正因为 S 和 T 端最多只能进入一辆，所以安全岛 M 最多也只会出现两辆自行车，所以不需要为 M 设置信号量。此外，除了要控制路口 S 和 T 的进入权限，还要控制两段小路 S-K 和 L-T 的通行权限，不能允许从 S 方向进入的自行车和从 T 方向进入的自行车同时进入这两段小路。因此共有 4 个互斥信号量。
声明信号量：
- semaphore S = T = 1 ：两端最多允许进入一辆
- semaphore SK = LT = 1 ：两段小路最多允许进入一辆
代码如下：

// S 口进入的自行车
do {
    wait(S);
    wait(SK);
    // 通过 S-K 段小路
    signal(SK);
    // 进入安全岛 M
    wait(LT);
    // 通过 L-T 段小路
    signal(LT);
    signal(S);
} while (TRUE);

// T 口进入的自行车与 S 口进入的自行车对称

互斥读者-写者问题

具体见互斥读者-读者问题

理发店问题

（原书书后习题 6.11 ，有修改）一个理发店配有一个有 10 个椅子的休息室和一个有理发椅的理发室。如果没有顾客则理发师睡觉；如果顾客来了而休息室、理发椅都没有空则离开；如果理发师在忙而有空的椅子，则顾客选择一个坐下等待；如果理发师在睡觉则顾客摇醒他。
分析：理发师在没有顾客时睡觉，并且顾客在没有空椅时离开，因此应当记录顾客的数量。
定义信号量：
- int count = 11 ：空闲的椅子数量
- semaphore mutex = 1 ：对椅子数量的修改互斥
- semaphore barber_chair = 1 ：理发师互斥，同时只能给一个人理发
- semaphore customers = 0 ：顾客人数
代码如下：

// 顾客
do {
    wait(mutex);
    if (count == 0){
        signal(mutex);
        return;
    }
    if (count == 11){
        signal(customers);
        // 唤醒 barber
    }
    count --;
    signal(mutex);
    wait(barber_chair);
    // 理发
} while (TRUE);

// 理发师
do {
    wait(customers);  // 睡觉等待顾客
    // 被唤醒
    // 剪发
    wait(mutex);
    count ++;
    signal(mutex);
    signal(barber_chair);  // 下一个客人剪发
} while (TRUE);

上面的代码将顾客排队顺序交给了信号量自身的排队机制处理，如果需要确保顾客能够维持一个先来先服务的剪发顺序，则需要维护一个容量为 11 的队列，顾客到来后加到队列尾部，每次从队头取走最先到来的顾客。

上机实习问题

某高校计算机系安排学生上机实习，机房共 30 台机器，有超过 60 名学生选课。规定每两个学生一组，一组占一台机器，协同完成实习。只有凑够两个学生且机房仍有空闲机器的情况下，门卫才允许该组学生进入机房。每组上机实习结束时需要由一名固定的老师检查完毕后，该组学生才可离开。
分析：互斥资源有需要检查的教师，同步资源涉及机房里的 30 台机器。此外，学生必须两两凑成一组才能进入机房，因此需要维护当前准备进入机房的学生人数，一旦超过 1 个人就可以组成一组。此外，应当注意学生组队和获取机器的先后关系，为了保证两个学生只获取一台机器，可以只使偶数号到来的学生获取机器，因为偶数号学生到来时可以保证能够凑成至少一组。本题涉及的进程只有学生。
定义信号量：
- int count = 0 ：开始时在机房外等候的学生人数
- semaphore mutex = 1 ：修改学生人数的互斥信号量
- semaphore teacher = 1 ：验收的老师
- semaphore machine = 30 ：30 台机器
代码如下

// 学生进程
do {
    wait(mutex);
    count++;
    int temp = count;     // 记录自己的编号
    if (count % 2 == 0)   // 偶数号学生
        wait(machine);
    signal(mutex);
    // 上机
    // 上机完成，等待验收
    wait(teacher);
    // 验收
    signal(teacher);
    if (temp % 2 == 0){
        signal(machine);   // 由偶数号学生释放机器
        // 必须先释放机器再尝试获取 mutex
        // 因为等待的偶数号学生先获取了 mutex，并且正在等待机器
        wait(mutex);
        count -= 2;     // 一组学生离开
        signal(mutex);
    }
} while(TRUE);

吸烟者问题

假设一个系统有 3 个吸烟者进程和一个供应商进程，制造一根香烟需要三种材料各一份。三个吸烟者分别无限量的拥有三种材料中的一种。供应商进程可以无限量的供应这三种材料，一旦一个吸烟者想吸烟，则他向供应商发出请求，供应商会为这个吸烟者提供另外两种材料。供货商同时只能为一个吸烟者提供服务，多个吸烟者同时发出请求时按固定顺序服务。如此循环往复，请用信号量编写程序控制四个进程同步执行。
分析：供货商需要判断有哪些吸烟者当前试图吸烟，因为可能有多个吸烟者发出请求，因此供货商需要分别判断。吸烟者需要三种材料中的两种，因此每种材料需要设置一个信号量表示资源请求。此外多个吸烟者同时发出请求，那么它们可能会同时争抢供货商提供的某个材料，因此需要一个互斥信号量控制提出请求的权限。
代码如下

bool smoker1, smoker2, smoker3;   // 分别表示 1、2、3 吸烟者是否发出请求
semaphore a = b = c = 0;          
// 初始供应的三种材料数量，1、2、3 号吸烟者分别持有 a、b、c类型材料
semaphore smoker_request = 1;     // 吸烟者发出请求权限

// 供应商
do {
    if (smoker1 == TRUE) {   // 吸烟者 1 有请求
        signal(b);
        signal(c);
    } 
    
    if (smoker2 == TRUE) {   // 吸烟者 2 有请求
        signal(a);
        signal(c);
    }
    
    if (smoker3 == TRUE) {   // 吸烟者 3 有请求
        signal(b);
        signal(a);
    }
} while(TRUE);

//吸烟者 1
do {
    wait(smoker_mutex);
    smoker1 = TRUE;
    wait(b);
    wait(c);
    signal(smoker_mutex);
} while (TRUE);

苹果-橘子或老虎与猪

两类问题本质一样，描述不同，在期中考试已经出现过。老虎与猪的描述如下：有一个笼子可以容纳一只老虎或者两只猪，如果笼子中已经有猪，则老虎不能被放入。猎人 A 每次向笼子中放入一只老虎，猎人 B 每次向笼子中放入一只猪。饲养员每次会从笼子中取出一只老虎，厨师每次会从笼子中取出一只猪。对笼子的操作是互斥的。试用信号量描述此过程。
分析：此题的关键在于笼子中允许有两只猪，而当笼子中有猪时就无法放入老虎，因此需要维护猪的数量。猎人 A 需要和饲养员维持同步关系，猎人 B 需要和厨师维持同步关系。本题其实也可以看作生产者-消费者问题和第一类读者-写者问题的结合，但限制了读者的数量。
变量和信号量定义：
- int pig_count = 0 ：笼子中当前猪的数量
- semaphore coop = 1 ：笼子的互斥锁
- semaphore tiger = 0 ：用于在猎人 A 和饲养员之间的同步，同时这个信号量和 coop 也是互补的
- semaphore pig = 0 ：用于在猎人 B 和厨师之间同步
- semaphore pig_space = 2 ：用于限制可以放置猪的剩余空间
- semaphore pig_count_mutex = 1 ：用于限制对 pig_count 的互斥访问
代码如下

// 猎人 A
do {
    // 抓到一只老虎
    wait(coop);
    // 将老虎放入笼子
    signal(tiger);
} while (TRUE);

// 饲养员
do {
    wait(tiger);
    // 从笼子中取出老虎
    signal(coop);
} while (TRUE);

// 猎人 B
do {
    // 抓到一只猪
    wait(pig_space);
    wait(pig_count_mutex);
    pig_count ++;
    if (pig_count == 1)
        wait(coop);    // 笼子中没有猪的情况下要等待笼子权限
    // 将猪放入笼子
    signal(pig_count_mutex);
    signal(pig);
} while (TRUE);

// 厨师
do {
    wait(pig);
    wait(pig_count_mutex);
    // 从笼子中取出一只猪
    pig_count --;
    if (pig_count == 0)
        signal(coop);
    signal(pig_count_mutex);
    signal(pig_space);
} while (TRUE);

信号量编程测试

我编写了一点简单的测试代码（Windows 下）来辅助测试信号量算法能否工作成功。你可以在这里获取这些代码。
代码包括一个基类 WorkStation（包含在 base.hpp 中）和两个可以用来做参考的测试文件。其中 bridge1.cpp 用来验证信号量编程（上）中习题 7.16， bridge2.cpp 用来验证互斥读者-读者问题中我针对修改后问题给出的自己的解答。你可以仿照这两个文件，继承 WorkStation 类来测试自己的信号量程序。
测试举例：以上面的老虎与猪问题为例，定义一个类 Coop 继承 WorkStation。
将所需变量添加到子类中，并实现虚方法 init()，该方法对你需要用到的信号量/变量做初始化。注意 init() 函数中需要设置 thread_type，这个变量表示有多少不同类型的进程，此问题有 4 种（猎人 A、B，厨师、饲养员），故 thread_type 应当为 4。
定义自己的参数结构体，对于上面老虎与猪问题而言需要将所用到的所有变量/信号量的地址放置到一个结构体中，对于此问题为：

struct Param{
    int *pig_count;
    HANDLE *coop, *tiger, *pig;
    HANDLE *pig_space, *pig_count_mutex;

实现虚函数 void * getParam(int index)，此函数格式比较固定，对于此问题应当为：

void * getParam(int index){
    Param *p = new Param;
    p->pig_count = &pig_count;
    p->coop = &coop;
    p->tiger = &tiger;
    p->pig = &pig;
    p->pig_space = &pig_space;
    p->pig_count_mutex = &pig_count_mutex;
}

实现四个进程对应的函数，只需要将已经写好的代码复制到你的代码中，格式参考 bridge1.cpp 和 bridge2.cpp。例如上面的猎人 A，应当写为：

DWORD WINAPI hunter_A(LPVOID param){
    Param p = *(Param*) param;
    // 抓到一只老虎
    WaitForSingleObject(*(p.coop), INFINITE);
    // 将老虎放入笼子
    ReleaseSemaphore(*(p.coop), 1, NULL);
}

假设你实现的代表四个进程的四个函数分别名为 hunter_A、hunter_B、cook 和 feeder。则向 init() 函数添加下面的代码更新驱动表：

_threads[0] = hunter_A;
_threads[1] = hunter_B;
_threads[2] = cook;
_threads[3] = feeder;

修改 main() 函数以测试。将 main() 函数中 simulate() 方法的第一个参数修改为 1，此参数表示每个进程创建多少个实例，此问题四种进程各一个，因此为 1。后一个参数表示程序运行多久退出，通常默认 60s 足够测试完成。

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（专题）：信号量编程（上）
此专栏的下一篇文章：互斥读者-读者问题

参考资料：《操作系统概念英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/01/08/os-concepts-15/) 、作者信息（Forec）和本声明。