计算机操作系统（第三版 西电） 复习提纲及重点习题
a. 在整型信号量机制中，未遵循\让权等待\的准则，存在“忙等”现象。
b. 记录型信号量机制完全遵循了同步机构的四条准则。
21 如何利用信号量机制来实现多个进程对临界资源的互斥访问？并举例说明之。 答：P50的伪代码 Repeat
Entry section
Critical section //对共享资源（临界资源）的访问 Exit section
Remainder section //不访问共享资源的其他代码 Until false
说明了多个进程对临界资源的互斥访问的解决思路，具体的，可设一记录型信号量S，初值为1，用P(S)替代Entry section，V（S）替代Exit section
在教材生产者消费者和读者写者的例子中都能看到上述用法。
22 试写出相应的程序来描述图2-17所示的前驱图（图略） 答：参考P54-55“2利用信号量实现前驱关系”（考研的同学应把这部分内容看一下）。这也是信号量对进程同步的一种用法，信号量初值为0。
23. 在生产者－消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响? 答：缓冲区满后，生产者进程被阻塞（进入关于信号量empty的等待队列），由于消费者取走产品后不执行signal(empty), 被阻塞的生产者进程继续被阻塞，即便缓冲区有空位也不能生产。
缓冲区空后，消费者进程被阻塞（进入关于信号量full的等待队列），由于生产者生产后不执行signal(full), 被阻塞的消费者进程继续被阻塞，即便缓冲区有产品也不能消费。
计算机操作系统（第三版 西电） 复习提纲及重点习题
24. 在生产者－消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置；或者是将signal(mutex)与signal(full)互换位置结果会如何?
答：首先，教材P58是生产者消费者问题的最佳解，它支持多个生产者进程和多个消费者进程并发，而不仅仅是一个生产者进程和一个消费者进程并发。
（1）如果将（消费者的）两个wait操作即wait(full)和wait(mutex)互换位置，后果是：
a.影响了多个消费者的并发性，当一个消费者进行了wait(mutex)，其它消费者因得不到mutex被阻塞，即便缓冲区有多个产品也不允许取。形象的说，教材的解法允许多个消费者同时逛商店，但拿产品时一个一个消费者拿；而颠倒wait(full)和wait(mutex)顺序后，商店一次只能允许一个顾客进入，等顾客拿完产品出门后，另一位顾客才能进去。 b. 可能造成死锁。假如某消费者执行wait(mutex)后没被阻塞，但接着执行wait(full)后被阻塞了, 要等待生产者的signal (full)才能解除阻塞，而生产者可能因消费者提前使mutex=0而被阻塞，无法执行signal (full)，这样就造成死锁。 c 可能还有其它后果。
（2）将（生产者的）signal(mutex)与signal(full)互换位置，似乎不会影响并发性，也不会造死锁，个人认为这也是一种正确的写法。
这道题我给出的答案仅供参考。
25. 我们为某临界区设置一把锁W，当W=1时，表示关锁；W=0时，表示锁已打开.试写出开锁原语和关锁原语，并利用它们去实现互斥.
答: 先看教材P50的伪代码 Repeat
Entry section
Critical section Exit section
Remainder section Until false
计算机操作系统（第三版 西电） 复习提纲及重点习题
说明了多个进程对临界资源的互斥访问的解决思路，在前面的第21题中，讨论了可设一记录型信号量S，初值为1，用P(S)替代Entry section，V（S）替代Exit section。 还有一种办法是教材P75介绍的“互斥锁”，其思路很简单：将Critical section想象成只允许一个进程进入的小黑屋，小黑外有一把锁，当进程发现锁是开着的，可以进入小黑屋，然后关上锁不让其它进程进入，出来时把锁打开给其它进程进入的机会。
锁可以看作是（小黑屋外的）共享变量W，对W有两个操作：unlock(W) ，lock(W)，这两个操作必须也是原子操作，其理由与信号量必须是原子操作一样。
开锁原语: unlock(W){W=0;}
关锁原语: lock(W) { if(W==1) do no_op; W=1;}
利用开关锁原语实现互斥，用lock(W);替代Entry section，unlock(W)替代Exit section即可。 var W:=0; process : repeat lock(W);
critical section unlock(W); remainder section until false;
锁比信号量简单，但只能用于进程互斥，不能用于同步。
26试修改下面生产者—消费者问题解法中的错误 答：按P58的正确解法修改即可。
27 试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法. 答：先看P62哲学家进餐问题的解及可能出现死锁的原因（出现了循环等待）。
根据P105死锁的四个必要条件，只要破除其中一个必要
计算机操作系统（第三版 西电） 复习提纲及重点习题
条件即可。
下面的解的思路是：偶数哲学家现拿左面的筷子，后拿右面的，奇数哲学家正相反，这样就破除了循环等待，使死锁不可能发生。
设初始值为1的信号量c[I]表示I号筷子被拿(I=1,2,3,4,...,2n),其中n为自然数. Begin
if I mod 2==1 then { //如为奇数哲学家 P(c[I]);
P(c[I-1 mod 5]); Eat;
V(c[I-1 mod 5]); V(c[I]); }
else{ //如为偶数哲学家 P(c[I-1 mod 5]); P(c[I]); Eat; V(c[I]);
V(c[I-1 mod 5]); } End
28 在测量控制系统中的数据采集任务，把所采集的数据送一单缓冲区；计算任务从该单缓冲中取出数据进行计算.试写出利用信号量机制实现两者共享单缓冲的同步算法.
答：解法与生产者消费者问题一样。这个题目的用意在于给出生产者消费者问题的一个实际应用---多进程的单缓冲通信。生产者消费者是非常重要、有广泛实际价值的问题。
29画图说明管程由哪几部分组成?为什么要引入条件变量? 答：见P56图2-13
管程由三部分组成:局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的
计算机操作系统（第三版 西电） 复习提纲及重点习题
语句.
因为调用wait原语后，使进程等待的原因有多种，为了区别它们，引入了条件变量.
30 如何利用管程解决生产者消费者问题？
答：见P60。考研的同学无需看这道题，只需会使用记录型信号量解进程同步问题即可，管程、信号量集、AND信号量只需从概念上了解一下即可，无需做大题。
31 什么是AND型信号量？。。。。 32 什么是信号量集？。。。。
答：考研的同学只需从概念上了解一下即可，无需做大题
33试比较进程间的低级通信工具与高级通信工具.
答：P65。信号量是低级的进程通信工具，优点是速度快（教材认为效率低是片面的），缺点是难以使用，通信对用户不透明（所有的操作都必须由程序员来实现）,而且必须借助共享内存才能通信。而高级通信工具则可弥补这些缺陷，用户可直接利用操作系统所提供的一组高级通信命令，高效地传送大量的数据。
34当前有那几种高级通信机制？ 答：P65-66
a. 共享存储器系统通信方式（低级）; b. 消息传递系统通信方式（高级）; c. 管道通信方式（高级）.
d. RPC(远程过程调用)，教材没有介绍。RPC允许一台机器远程呼叫另一台机器上的过程（或函数），这是网络时代最常见的高级通信机制，JAVA的RMI, RMI-IIOP 微软的COM+RPC .net remoting，以及CORBA, web Service等分布式通信（和组件）技术都是从RPC发展起来的。
35 消息队列通信机制有哪几方面功能？
答：P69-71。主要有消息缓冲区、发送原语、接受原语。
计算机操作系统（第三版）汤小丹第2章
