第二章 习题
8、如图2-58所示，设有一个可以存放m个数据的有界缓冲区，现有一组进程不断将数据放入该缓冲区，另有一组进程bu断从缓冲区取出数据使用。请定义信号量并利用P、V操作画出逻辑框图，实现进程对该有界缓冲区共享使用的方案。若取出速度远远大于放入速度，则应该如何修改框图，为什么？ 有界缓冲区
图2-58
解：（1）设置信号量：互斥使用有界缓冲区的信号量s,初值为1；
同步信号量：有界缓冲区的大小，即可以存放产品的最大数m,初值为m； 有界缓冲区中已经存放的产品个数n，初值为0；
逻辑框图如下：
放入数据 取出数据
P(m) P(n) P(s) P(s) 放入数据到缓冲区 从缓冲区取出数据 V（s） V(s) V(n)
V(m)
（2）若取出数据远远大于放入速度，只需去掉P（m）、V(m),因为取出速度>放入速度，不需要限定缓冲区的大小，即可以存放产品的最大数m。
9、如图2-59所示，进程A、B、C公用两个有界缓冲区1、2，其长度分别可以存放m与n个数据。进程A不断把数据放入有界缓冲区1中，进程B从有界缓冲区1中取出数据，加工后，送入有界缓冲区2中，进程C从有界缓冲区2取出数据打印。请用P、V操作实现三 个进程同步，并画出逻辑图。
有界缓冲区1 有界缓冲区2 B A C 图2-59 习题9用图
解：设置信号量：
有界缓冲区1：互斥使用有界缓冲区的信号量s1，初值为1；
有界缓冲区的大小，即可以存放产品的最大数m1，初值为m； 有界缓冲区中已经存放的产品个数为n1，初值为0；
有界缓冲区2：互斥使用有界缓冲区的信号量s2，初值为1；
有界缓冲区的大小，即可以存放产品的最大数m2，初值为n； 有界缓冲区中已经存放的产品个数为n2，初值为0；
逻辑框图如下：
A P（m1） B P（n1） C P（n2）
P(s1) P(s1) P(s2) 放入数据 取出数据 取出数据 V(s1) V(s1) V(s2) V(n1) P(m2) V(m2) P(s2) 加工后放入数据 V（s2） V(n2)
11、一条东西方向的河上有一座桥，桥宽仅能允许一辆汽车通过。桥上同一方向的汽车可以鱼贯而行，但若桥两边的汽车同时上桥向对面行驶就会发生阻塞。试用信号量机制设计一个避免死锁的算法，并画出流程图。
若甲车想往南过桥时，乙车正在向北过桥，则甲车只能等待；如果此时不断有车向北过桥，则甲车将处于“饿死”状态请设计一个避免“饿死”的算法，并画出流程图。
避免死锁的流程图如下：
向北方向 P（N） C1= = 0? Y N P(S) C1++ V(N) 过桥 P(N) C1-- C1= =0? Y N V(S) V(N)
向南方向 P（S） C2= = 0? Y N P(N) C2++ V(S) 过桥 P(S) C2-- C2= =0? Y N V(N) V(S)
18、一位银行家向若干客户承诺一定的贷款额度。现有四个客户，需要贷款的最大额度之和为22个单位的资金。银行家知道不可能所有客户同时都需要最大贷款额，所以只保留10个单位的资金为客户服务。在某一时刻，资金分配如下： 客户 Zhang Wang Li Zhao 最大需求 6 5 4 7 已分配 1 1 2 4 请问： （1） 当Zhao在申请一个单位资金时，银行家能否给他，为什么？
（2） 若申请一个单位资金的要求分别来自Zhang、Wang、Li时,情况如何，为什么？ 解：（1）按题意，这一时刻银行家所剩资金还有2个单位，若分给Zhao一个单位资金，客户需求与分配情况如下： 客户 Zhang Wang Li Zhao 最大需求 6 5 4 7 已分配 1 1 2 5 当前可用资金 1 此时还剩下1个单位的可用资金，此时，无论将1个单位的资金分给Zhang、Wang、Li还是Zhao自己都不能满足各自的需求，所以4个客户都无法满足，即找不到安全序列。在某一时刻，银行家是可以满足的客户的需求的，但是由于Zhao申请一个单位资金的请求，使得银行家无法满足4个客户的需求，因此Zhao在申请一个单位资金时，银行家是不能给他的。
（2）若Li申请1个单位的资金时，银行家所剩资金还有2个单位，客户需求与分配情况如下：
客户 Zhang Wang Li Zhao 最大需求 6 5 4 7 已分配 1 1 3 4 当前可用资金 1 当前所剩可用资金只能满足Li的需求 ①若给Li分1个单位资金，客户需求与分配情况如下： 客户 Zhang Wang Li Zhao 最大需求 6 5 4 7 已分配 1 1 4 4 当前可用资金 0 此时，Li可以满足，可以归还4个单位的资金，当前可用资金为4个单位，可以满足Zhao或Wang的要求。
②若给Zhao分3个单位的资金，客户需求与分配情况如下：
客户 Zhang Wang Zhao 最大需求 6 5 7 已分配 1 1 7 当前可用资金 1 此时Zhao可以满足，可以归还7个单位的资金，当前可用资金为8个单位，能够满足Wang或zhang的贷款要求。
③若给Wang分4个单位的资金，客户需求与分配情况如下： 客户 Zhang Wang 最大需求 6 5 已分配 1 5 当前可用资金 4 此时Wang可以满足，可以归还5个单位的资金，当前可用资金为9个单位，能够满足Zhang的贷款要求。
④若给Zhang 分5个单位的资金，客户需求与分配情况如下： 客户 Zhang 最大需求 6 已分配 6 当前可用资金 4 则Zhang可以满足，归还10个单位的资金，此时，银行家将10个单位的资金全部收回。 假如按照Li、Zhao、Wang、Zhang序列分配资金，所有的贷款都可以完成，不会发生死锁。所以Li申请一个单位的请求可以满足。
而Wang、Zhang的请求如Zhao的情况一样，不能满足，银行家是不可以给他。