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

此部分主要包括原书第六章（进程同步）和第七章（死锁）的部分习题（有些不属于考试范围），以及一些简单信号量编程习题（低于考试难度）的分析。这部分习题的解答均根据我个人理解编写或翻译， 不保证提供的答案绝对正确或最优 。稍微复杂一些的信号量编程在 《信号量编程（下）》。

原书选题

课后习题的解答主要是我对原书答案的翻译和解释。此外：

• “进程同步”中，第 6 题之后（含第 6 题）超出考试范围
• “死锁”中，第 5 题超出考试范围

进程同步

1. 证明 进程互斥 中介绍的 Peterson 算法 满足临界区的三个要求。
   • 参考 进程互斥 - Peterson 算法 。
2. 什么是 忙等待（busy waiting） ？操作系统中还有哪些等待方式？忙等待可以被完全避免吗？
   • 忙等待意味着进程在等待一个条件被满足，并且进程在等待的过程中仍然不放弃对 CPU 的控制（如通过 while 循环不断判断条件是否被满足）。
   • 操作系统可以在一个进程等待某条件时将 CPU 控制权限交给其他进程，而等待的进程可以在将来某个合适的、条件满足的情况下被唤醒。
   • 忙等待可以被避免，但需要在进程的调度上花费更多的资源。等待进程需要被挂起，等到进程等待的条件满足时再唤醒。
3. 试解释为什么 自旋锁（旋转锁，spinlock） 不适合单处理器系统，但在多处理器系统中很常用。
   • 对于单处理器系统：一个进程使用自旋锁等待条件时仍然占据着唯一的 CPU，其他进程得不到执行，而占据 CPU 的进程等待的条件需要其它进程的执行才能得到满足。
   • 对于多处理器系统：进程使用自旋锁时占据着一个 CPU 资源，而其他进程可以在剩余的 CPU 上运转，并且改变某些数据从而使停滞在旋转锁的进程的等待条件得到满足。
4. 试解释为什么在单处理器系统的用户进程中通过屏蔽中断来实现同步是不合理的。
   • 如果用户进程具有屏蔽中断的权限，那么它可以同样屏蔽计时器中断，没有时钟中断则分派程序无法运行，进程会无限执行。
5. 试解释为什么在多处理器系统系统中无法通过屏蔽中断来实现同步。
   • 屏蔽中断仅仅阻止其他进程在被屏蔽了中断的处理器上运行，其他进程可能在其它处理器上运行。

6. 试在多处理器环境下通过 TestAndSet() 指令实现 wait() 和 signal() 信号量操作。

   • 初始定义 int semaphore_value = 0 表示当前信号量剩余资源，定义 bool guard = TRUE 保证对 semaphore_value 的互斥修改。

     void wait(){
         while (TestAndSet(&guard) == TRUE);
         if (semaphore_value == 0){
             // 暂时没有资源可用，将进程挂起到信号量队列中
         } else {
             semaphore_value --;
         }
         guard = FALSE;
     }
     
     void signal(){
         while (TestAndSet(&guard) == TRUE);
         if (semaphore_value == 0 &&
             there's a process waiting in the queue){
             // 信号量资源数为 0 并且有进程挂起在信号量中
             // 唤醒该进程
         } else {
             semaphore_value ++;
         }
         guard = FALSE;
     }

7. 证明 管程（monitor） 和信号量可以互相实现。

   • 操作系统（六）：管程 - 使用信号量实现管程
   • 使用管程实现信号量：

     monitor semaphore {
         int value = 0;
         condition c;
         
         signal() {
             value ++;
             c.signal();
         }
         
         wait() {
             while (value == 0)
                 c.wait();    // 注意体会此处 while 而非 if 的意义
             value --;
         }
     }

8. 使用管程实现有限缓冲的生产者 - 消费者模型。

   monitor bounded_buffer {
       int items[MAX_ITEMS];    // 生产的资源缓冲区
       int numItems = 0;        // 缓冲区内当前资源数目
       condition full, empty;
       
       void produce(int v) {
           while (numItems == MAX_ITEMS)
               full.wait();     // 缓冲区满时将生产者挂起到条件变量 full
           items[numItems++] = v;
           empty.signal();
       }
       
       int consume() {
           int retVal;          // 临时变量保存返回值
           while (numItems == 0)
               empty.wait();    // 缓冲区为空将消费者挂起到条件变量 empty
           retVal = items[--numItems];
           full.signal();
           return retVal;
       }
   }

9. 试提出一种解决读者-写者问题中饥饿现象的方法。

   • 第 3 类读者-写者问题的一种解答：操作系统（五）：进程同步 - 第三读者-写者问题
   • 另一种方案：每个读者/写者都保留开始等待时刻的时间戳，当一个写者完成写任务后，会唤醒等待时间最长的进程。当有读者正在临界区内而有新读者到来时，新读者必须在没有写者在等待的情况下才能也进入临界区。
10. 信号量的 signal() 和管程中条件变量 signal 操作的区别。
    • 如 操作系统（六）：管程 所讲，管程模式下的 x.signal() 和信号量的 signal() 区别在于： 信号量操作 signal() 会影响信号量的状态 ，而管程下的 x.signal() 在 x 不存在挂起进程的情况下没有任何影响。
11. 一个系统包含 n 个进程 P1~n，每个进程都有唯一的优先级编号，共有 3 台打印机供这 n 个进程使用。试通过管程实现按优先级调度的资源分配。

    monitor printers {
        int num_avail = 3;    // 可用资源数量
        int num_waiting;      // 等待进程数量
        int waiting_processes[MAX_PROCS];    // 等待进程列表
        condition c;
        
        void request_printer(int proc_number) {
            if (num_avail > 0) {        // 有资源可分配则进程直接获得
                num_avail --;
                return;
            }
            waiting_processes[num_waiting] = proc_number;
            num_waiting++;
            sort(waiting_processes);
            while (num_avail == 0 && 
                waiting_processes[0] != proc_number)
                // 当可用资源数量为 0 并且当前进程不处于等待队列的第一位
                c.wait();
            waiting_processes[0] = waiting_processes[--num_waiting];
            sort(waiting_processes);
            num_avail--;    // 使用一个资源
        }
    
        void release_printer() {
            num_avail ++;
            c.signal();
        }
    }

死锁

1. 考虑教材 7.1 描述的交通死锁问题（如下图所示），试说明死锁发生的四个必要条件在这个问题中均得到满足，并简述在这个问题中避免死锁的方案。（原书 7.1）
   
   • 死锁发生的四个必要条件分别是：互斥、占有并等待、非抢占和循环等待。因为只有一条道路的每个位置上只能由一辆车占据，故满足资源互斥；当一辆车占据道路上某个位置时，它必须等待前面的车移动（获取新位置）才可以移动，，即占有并等待；一辆车不能被移开，故此系统为非抢占；每个车都在等待前面的车移动，每个十字路口的车辆则循环等待下一个十字路口的车辆移动，故循环等待。
   • 一个简单的方案是：当十字路口已存在车辆时，新到来的车辆不能进入十字路口。
2. 在真实计算机系统中，无论是可用资源还是进程对资源的需求都会随着时间的推移而改变。假设现在系统处于安全状态（通过银行家算法计算出），那么对于下面的几种改变，哪些改变执行之后一定能维持系统的安全状态？（原书 7.5）
   • 增加可用资源：维持安全状态
   • 减少可用资源：可能导致死锁，因为银行家算法计算出的安全状态是基于改变前的资源数量
   • 增加某个进程所需要的最大资源数量：可能导致死锁，理由同上
   • 减少某个进程所需要的最大资源数量：维持安全状态
   • 增加进程数量：可能导致死锁，理由同上
   • 减少进程数量：维持安全状态，进程退出竞争必然使可用资源增加或保持不变
3. 一个系统有四个相同类型的资源，它们被三个进程同时共享，每个进程最多需要两个资源。试证明这个系统不会发生死锁。（原书 7.6）
   • 假设系统发生死锁，则必然满足占有并等待和循环等待的条件。故每个进程都持有一个资源（若持有两个则已经满足要求，可以运行结束并释放），并且每个进程都在等待下一个资源。根据狄利克雷抽屉原理，四个资源分配给三个进程，必然有一个进程获得两个资源，这个进程必然可以执行完毕，然后释放持有的全部资源以使其它进程得以执行。
4. 一个系统有 m 个相同类型的资源，它们被 n 个进程同时共享。在每个时刻，进程只能至多申请或者释放一个资源。假设系统满足以下两个条件：每个进程所需的最大资源数量在 1~m 个之间、所有进程的最大资源需求数量之和小于 m+n 个，试证明这个系统不会发生死锁。（原书 7.7）
   • 解答 1：每个进程尚需的资源向量 Need[i,] = Max[i,] - Allocation[i,]。假设存在死锁，则必有 Σ(i = 1 to n) Allocation[i,] = m ，即所有资源都已经分配，没有资源空闲。
   • 因为进程所需的资源总和不超过 m+n·，故 Σ Need[i,] + Σ Allocation[i,] = Σ Max[i,] < m + n ，和上式结合化简即为 Σ Need[i,] < n 。
   • 因为 n 个进程所需的资源总数小于 n，意味着至少有一个进程 P 还需要 0 个资源，所以进程 P 能够执行到结束。又每个进程所需的最大资源数量不少于 1 个，故 P 执行结束后会释放至少一个资源。因此系统不会产生死锁。
   • 解答 2：假设系统正在发生死锁，则当前状态下的 m 个资源已经全部被 n 个进程所占用，而这 n 个进程还需要更多的资源才能继续运行，也就是说每个进程还需要至少一个资源。因此，系统内 n 个进程正常运行所需要的资源总和大于或等于 m+n，与题意矛盾。故系统不可能发生死锁。
5. 一座桥连接了南北两个村庄，两个村庄的居民可以从桥上通过，但桥上不能同时承载两个人（无论同方向还是相向，这里原题中只要求不能同时相向行走）。使用信号量保证死锁和饥饿都不会发生。（原书 7.16）
   • 注 1：如果将此题的限制改为两个方向的人依次行走，即南向北过桥后，下一次应当是北向南，则此问题等同于缓冲区大小为 1 的生产者-消费者问题。
   • 注 2：此题要求不会产生饥饿现象，则需要考虑两个方面，既要保证不能有一方一直持有过桥的权利，还要保证某一方过桥后，任何一方再次过桥不会依赖已过桥的居民影响（临界区问题的“发展”要求）。
   • 注 3：此题是原书课后习题，课后的 7.15 和 7.16 是递进关系。《信号量编程（下）》中北京大学 1992 年入学考试题（单向行驶问题）也与此题类似。我对该题又做了新的改动，本题的信号量解法以及改动后题目的相关分析均记录在 《互斥读者-读者问题》，如果你有兴趣，欢迎与我讨论改动后题目的解法 。
   • 原书答案给出了管程解法，对其做了一定修改如下：

monitor bridge {
    int num_waiting_north = 0;   // 北方村庄等待过桥人数
    int num_waiting_south = 0;   // 南方村庄等待过桥人数
    int prev = 0;                
        // prev 为 0 表示上一次上桥的人是北方居民，否则为南方居民
    bool on_bridge = FALSE;      // 桥上是否有人
    condition ok_to_cross;       // 条件变量
    
    void enter_bridge_north() {  // 北方村庄居民试图过桥
        num_waiting_north++;
        while (on_bridge ||      // 桥上有人
              (prev == 0 && num_waiting_south > 0))
               // 或者上一次是北方居民过桥，且当前还有南方村庄居民在等待
            ok_to_cross.wait();
        num_waiting_north --;    // 已上桥，北方村庄等待人数减少
        prev = 0;
    }
    
    void enter_bridge_south() {
        num_waiting_south ++;
        while (on_bridge ||
               prev == 1 && num_waiting_north > 0))
            ok_to_cross.wait();
        num_waiting_south --;
        prev = 1;
    }
    
    void exit_bridge() {         // 南北居民离开后都调用此函数
        on_bridge = FALSE;
        ok_to_cross.signal();
    }
}

简单信号量编程

此部分习题选自 2000 年左右各高校的研究生入学考试题，题目均比较简单。

双车间零件装配

• 某工厂有两个生产车间和一个装配车间，两个生产车间分别生产 A，B 两种零件，装配车间的任务是把 A，B 两种零件组装成产品。每个车间生产完一个零件后都要把零件送到装配车间的货架 F1、F2 上，F1 存放零件 A，F2 存放零件 B，两个货架均可分别容纳 10 个零件。装配工人每次从货架上取出一个 A 零件和一个 B 零件然后组装成产品。请用信号量进行正确管理。
• 此问题是生产者-消费者问题的变形，可以认为一个消费者（装配工人）和两个生产者（A，B车间）互斥使用两个缓冲区（F1、F2）。令 mutex1 和 mutex2 这两个互斥信号量控制对缓冲区的互斥操作，另外还需要 empty1、empty2、full1、full2 用来同步。
• 代码如下

// 车间 A
do {
    wait(empty1);
    wait(mutex1);
    // 生产零件 A 并放入 F1
    signal(mutex1);
    signal(full);
} while (TRUE);

// 车间 B 和车间 A 对称

// 装配工人
do {
    wait(full1);
    wait(full2);
    wait(mutex1);
    wait(mutex2);
    // 取出零件 A 和 B
    signal(mutex1);
    signal(mutex2);
    signal(empty1);
    signal(empty2);
} while (TRUE);

和尚挑水问题

• （北京邮电大学 1998 年）某寺庙有老、小和尚若干，仅有一个水缸和一个水井。小和尚负责将水从井中挑到缸中以供老和尚饮用。水缸可以容纳最多 10 桶水，水井口非常窄，每次只能容纳一个水桶取水。水桶总数有 3 各，每次小和尚挑水、倒入缸内只能使用一个桶，且不可以同时进行。请使用信号量给出从缸中取水和向缸中倒水的算法描述。
• 分析：需要将问题分解为数个过程。从井中取水到向缸中倒水应该是一个连续的动作，算作一个进程；老和尚用桶从缸中取水算作一个进程。题中互斥资源包括水井和水缸，分别需要一个信号量来保证互斥。题中同步问题涉及水桶，抢不到水桶的进程需要等待，水缸满时小和尚需要等待，水缸空时老和尚需要等待，这需要生产者-消费者问题的经典信号量控制满和空。
• 定义信号量如下：
  • mutex1 = mutex2 = 1 ：水井和水缸两个资源各自的互斥访问
  • empty = 10 ：初始水缸为空，可容纳至多 10 桶水
  • full = 0 ：初始水缸为空
  • count = 3 ：水桶数量为 3
• 代码如下

// 小和尚
do {
    wait(empty);
    wait(count);   // 争夺水桶
    wait(mutex1);
    // 从井中打水
    signal(mutex1);
    wait(mutex2);
    // 倒水入水缸
    signal(mutex2);
    signal(count); // 归还水桶
    signal(full);  // 通知老和尚水缸有水
} while (TRUE);

// 老和尚
do {
    wait(full);
    wait(count);
    wait(mutex2);
    // 从水缸中打水
    signal(mutex2);
    signal(count);
    signal(empty);
} while (TRUE);

阅览室登记问题

• （北方交通大学 1999 年）阅览室有 100 个座位，读者进入阅览室需要先在一张登记表上登记，每个座位有一个条目，读者离开阅览室需要注销自己的登记信息。请使用信号量描述同步算法。约定：
  • 语句 I = getflag(0) 可以搜索到一个空座位 i，通过语句 i.flag = 0 或 1 可以标识座位 i 为空闲（0）或者占用（1）；
  • 语句 i = getname(readername) 可以搜索到读者登记的座位号 i，通过 i.name = 0 可以将座位原本的读者姓名清除，通过 i.name = readername 可以将读者名称关联到座位 i 上；
  • 计数信号量用 count，互斥信号量用 mutex。
• 分析：约定部分仅仅为代码编写提供一定现成的符号，问题中仅有读者一个对象，因此只需要考虑读者之间是等价的，只需要考虑一个读者的行为。读者进入阅览室应当先检查是否有空闲座位，若存在则登记否则离开。座位显然需要信号量 count 控制。读者离去时需要注销登记信息并释放座位，无论何时对登记簿的修改都需要互斥，如题中约定使用 mutex 。
• 代码如下，对原题做一定修改，使读者进入阅览室时如果人满则离开，因此需要一个 int 型变量 seats 记录空闲座位数量，而原本的 count 同步信号量可以丢弃。

int seats = 100;
// 读者进程
do {
    // 进入阅览室
    wait(mutex);
    if (seats <= 0) { 
        signal(mutex);
        continue;    // 无空闲座位，离开阅览室
    }
    seats --;
    i = getflag(0);
    i.flag = 1;
    i.name = readername;    // 获取空闲座位、登记
    signal(mutex);
    // 看书
    wait(mutex);
    seats ++;
    i = getname(readername);
    i.flag = i.name = 0;    // 注销登录信息
    signal(mutex);
} while (TRUE);

4 乘 100 米接力

• 用信号量描述 4 × 100 米接力问题。
• 分析：四个选手之间需要保持链式同步关系，因此设置三个信号量分别表示第 i 棒选手和第 i-1 棒选手之间的同步（0 < i < 5）。
• 代码如下

semaphore s1 = 0, s2 = 0, s3 = 0;
// 第一棒起跑并前进 100 米
signal(s1);
// 第二棒
wait(s1);
// 第二棒起跑并前进 100 米
// ...
// ...
// 第四棒
wait(s3);
// 第四棒起跑并前进 100 米到达终点

---

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（十三）：I/O 输入系统
此专栏的下一篇文章：操作系统（专题）：信号量编程（下）

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

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