个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下： A Out in
然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in被加1后，out=in，当缓冲区为空时同理。
b．你可以使用一个可以随意增加和减少的辅助的变量，count。
5.16这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具
5.17通过一下步骤说明消息传递和信号量具有同等的功能：
a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。
b.用消息传递实现信号量。提示：引入一个独立的同步进程。
答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait或signal，来实现WAITHUO SIGNAL.然后生产者执行RECEIVE来接受来自于同步进程的回复。 当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs总是可以完成，但是假如信号值为0时，WAITs将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。假如操作是WAIT并且信号量的值为0时，同步进程进入调
用队列，并且不发送回复。结果是执行WAIT的进程被阻塞。当SIGNAL被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。
第六章 习题
第一部分 复习题
6.1给出可重用资源和可消费资源的例子。
答：可重用资源：处理器，I/O通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。
可消费资源：中断，信号，消息和I/O缓冲区中的信息。 6.2可能发生死锁所必须的三个条件是什么？ 答：互斥，占有且等待，非抢占。 6.3产生死锁的第4个条件是什么？ 答：循环等待。
6.4如何防止占有且等待的条件？ 答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。
6.5给出防止无抢占条件的两种方法。
答：第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。
第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。 6.6如何防止循环等待条件？ 答：可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。 6.7死锁避免，检测和预防之间的区别是什么？ 答：死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。
第二部分 习题
6.1写出图6.1（a）中死锁的四个条件。
解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。
6.2按照6.1节中对图6.2中路径的描述，给出对图6.3中6种路径的简单描述。
解：1.Q 获得 B 和A, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。
2. Q 获得 B和A， P 执行而且阻塞在对 A的请求上. Q释放 B 和A。当 P 重新开始执行的时候，它将会能够获得两个资源。
3. Q 获得 B ，然后 P 获得和释放 A. Q 获得A然后释放 B 和 A. 当 P 重新开始行的时候，它将会能够获得 B。 4. P 获得A然后 Q 获得 B. P 释放 A. Q 获得A然后释放 B. P 获得 B 然后释放 B。
5. P 获得，然后释放 A. P 获得 B. Q 执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当 Q 重新开始执行的时候，, 它将会能够获得两个资源。
6. P 获得A而且释放A然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。
6.3图6.3反映的情况不会发生死锁，请证明。
证明：如果 Q 获得 B 和A（在 P之前请求A）, 那么 Q 能使用这些两类资源然后释放他们, 允许A进行。 如果 P在 Q之前请求A获得A, 然后Q 最多能执行到请求A然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, A能进行。
6.4考虑下面的一个系统，当前不存在未满足的请求。
a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？
d哪个进程（如果存在）是死锁的或可能变成死锁的？
e如果Ｐ3的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？
解： a. 0 0 0 0
0 7 5 0 6 6 2 2 2 0 0 2 0 3 2 0
b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，
运行顺序是p1, p4, p5, p2, p3.
c.系统当前并没有死锁，因为P1进程当前分配与最大需求正好相等，P1进
程可以运行直至结束，接下来运行其他进程
d.P2,P3,P4,P5可能死锁
e.不可以，当进程P1,P4,P5执行完可用资源为（4，6，9，8），P2,P3将死
锁，所以不安全，完全不可以立即同意系统剩下的全部请求。
6.5 请把6.4中的死锁检测算法应用于下面的数据，并给出结果。
Available=(2 1 0 0)
2 0 0 1 0 0 1 0 Request= 1 0 1 0 Allocation= 2 0 0 1 2 1 0 0 0 1 2 0
解： 1. W = (2 1 0 0)
2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) 3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) 4. Mark P1; no deadlock detected 没有死锁
6.6一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o≤max
其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。 输入 输出 P 缓冲区 缓冲区
以下是关于进程的知识：
1、只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 2、只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁盘空间可用）。
I o