第四章作业参考答案Word格式.doc
《第四章作业参考答案Word格式.doc》由会员分享，可在线阅读，更多相关《第四章作业参考答案Word格式.doc（13页珍藏版）》请在冰点文库上搜索。
数据送到缓冲区B1;
V（S2）;
};
Q:
不能从空的B1读数据，设信号量S2，初值为0；
不能往满的B2送数据，设信号量S3，初值为l（l为缓冲区B2的大小）
P（S2）;
从缓冲区B1读数据;
加工数据;
V（S1）;
P（S3）
加工的数据写入缓冲区B2;
V（S4）
R:
不能从空的B2读数据，设信号量S4，初值为0；
P（S4）;
从缓冲区B2读数据;
V（S3）
打印;
（4）
卡片
打印机
B1
B2
B1未满
B2未满
B1非空
B2非空
进程一：
运行
就绪
等待
j
k
l
m
jB1满
kB1未满
l卡片全部读完
m新的一批卡片作业
进程二：
jB2满
kB2未满
lB1空
mB1非空
进程三：
j无条件
kB2空
lB2非空
13假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上标志（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问：
（1）应编写几个程序完成此项工作，程序的主要动作是些什么？
应设置几个进程？
进程与程序间的对应关系如何？
（2）用P、V操作写出这些进程的同步通信关系。
（1）应该编写四个程序完成工作，分别执行：
管理等待登入队列，登入并分配资源，管理等待离开队列，登出并回收资源。
应设置2个进程，分别负责管理登入和负责管理登出。
（2）设置readercount=100，控制可进入的读者数
设置mutex=1，控制操作登记表
登入进程：
{
P（mutex）
P（readercount）
分配阅览室资源
V（mutex）
}
登出进程：
回收阅览室资源
V（readercount）
17．假设一个系统的磁盘大小为2kB，一个块的平均访问时间是20毫秒，一个有40kB的进程由于资源请求此从运行状态变为阻塞态。
要确保将该进程换出，它必须保持阻塞多长时间？
解：
阻塞时间：
T=40/2*20=400（毫秒）
18.假使A、B两个火车站之间是单轨线，许多列车可以同时到达A站，然后经A站到B站，又列车从A到B的行驶时间是t，列车到B站后的停留时间是t/2。
试问在该问题模型中，什么是临界资源？
什么是临界区？
因为许多列车可以同时到达A站，所以A站不是互斥资源，而A、B之间的单轨线每次只能允许一辆列车发出以后另一辆才能发出。
因为列车行驶时间为t，B的停留时间为t/2，所以只要在前一辆列车走完前1/2路程后再发车，到达B站时前一辆车也已离开B站。
（1）A、B间单轨线的前半段是临界资源。
（2）临界区：
列车在单轨线前半段上行驶
21题（测验的最后一题，类似，更简单）
由于有m个发送者，n个接收者，k大小的缓冲区；
从单个的问题出发，发送者要么等待在第x缓冲区（条件是缓冲区x未被清空，而发送者采用递增环状方式使用缓冲区）要么发送到x，发送完后需要唤醒所有接收进程。
接收进程不停的轮询缓冲区,也采用递增环状方式，如果缓冲区有内容，则收取，并把此缓冲区的未接收数减一，如果减至0，则置缓冲区为空。
综上所述，需要对每个缓冲区单位设置空，满，互斥量，未收取数（empty，full，mutex，count）其中full是一个数组，记录每个接收者的情况，防止重复接收，mutex主要用来做count的互斥访问。
此外，还要设置全局的互斥变量mutex。
TypeBufferType=Record
msg:
MessageType;
count:
integer;
mutex:
semaphore;
{初值为1}
empty:
semaphore;
full:
array[1..n]ofsemaphore；
{初值全为0}
End
Var mutex:
s:
integer;
{初值为0}
buff:
array[0..k-1]ofBufferType;
{k是缓冲区大小；
n是接收进程个数}
{m是发送进程个数，通过s进行“写互斥”}
ProcedureSender_i（i:
integer）;
{i为发送进程的标号}
Var s0,j:
Begin
Repeat
P（mutex）;
s0:
=s;
s:
=（s+1）modk;
V（mutex）;
P（buff[s0].empty）；
在buff[s0].msg中写信息；
P（buff[s0].mutex）；
buff[s0].count:
=n;
V（buff[s0].mutex）;
For（j:
=1tondo）
V（buff[s0].full[j]）;
Untilfalse;
End
ProcedureRecvr（i:
{i为接收进程的标号}
Var j:
j:
=0;
P（buff[j].full[i]）;
从buff[j].msg中读信息；
P（buff[j].mutex）；
buff[j].count:
=buff[j].count-1;
If（buff[j].count=0）
ThenV（buff[j].empty）；
V（buff[j].mutex）;
j:
=（j+1）modk
Untilfalse;
22.<
1>
.信号量说明：
mutex，初值为１，记录可进入临界区的进程数;
互斥算法；
P（mutex）;
进入临界区；
V（mutex）;
结束；
<
2>
mutex，初值为m，记录可进入临界区的进程数;
互斥算法；
结束；
25.一家快餐店招有4种雇员：
（1）开票者，取顾客的订单；
（2）厨师，准备饭菜；
（3）包装员，把食物撞进袋中；
（4）出纳，一手收钱一手交货。
每位雇员可以看作一个在通信的顺序进程。
他们采用的是什么方式的进程间通信？
开票者和厨师之间是管道通信。
开票者源源不断的把订单给厨师，一次可能给一张也可能给多张，厨师一次可能拿走一张订单去做也可能拿走多张去做。
厨师和包装员之间是信箱通信，他们之间有个信箱，可能就是一个小平台，厨师做好就把菜放上去，相当于放进信箱，而包装员可以在任何时候取走那个菜。
包装员和出纳之间是消息缓冲通信，包装员包号了就给出纳发消息，出纳得到消息就取走包好的饭菜然后出售。
29．计算系统CPU利用率。
1）Q等于无穷时，算法退化为FIFO，这时CPU利用率为T/（S+T）
2）Q>
T时，进程在用完时间片之前已被堵塞，因此CPU利用率仍为T/（S+T）
3）S<
Q<
T时，，进程在I/O堵塞之前需使用INT（T/Q）+1个时间片，因此CPU利用率为
T/（（INT（T/Q）+1）*S）+T）
4）Q=S时，当S远小于T时，CPU在调度和运行进程的时间近似相等，CPU利用率为1/2
5）Q趋于零时，几乎所有的时间都花在调度上，因此CPU利用率也趋于零。
34．巴拿马运河建在太平洋和大西洋之间。
由于太平洋和大西洋水面高度不同，有巨大落差，所以运河中修建有T（T>
=2）级船闸，并且只能允许单向通行。
船闸依次编号为1、2、…、T。
由大西洋来的船需经由船闸T、T-1、…、1通过运河到太平洋；
由太平洋来的船需经由船闸1、2、…、T通过运河到大西洋。
试用P、V操作正确解决大西洋和太平洋的船只通航问题
来自不同方向的船只对船闸要互斥使用。
但如过有同方向的船只正在通行，则不用等待。
对一个船闸设以下变量：
PtoAcount整型，记录此船闸正由太平洋往大西洋航行的船只初值0。
AtoPcount整型，记录此船闸正由大西洋往太平洋航行的船只初值0。
Mutex信号量，对PtoAcount互斥初值1
Mutex1信号量，对AtoPcount互斥初值1
Pass信号量初值1
太平洋到大西洋的船：
P（mutex）;
PtoAcount:
=PtoAcount+1;
ifPtoAcount=1
thenP（pass）;
V（mutex）;
过
P（mutex）
=PtoAcount-1;
ifPtoAcount=0;
thenV（pass）;
大西洋到太平洋的船:
P（mutex1）;
AtoPcount:
=AtoPcount+1;
ifAtoPcount=1;
V（mutex1）;
P（mutex1）
=AtoPcount-1;
ifAtoPcount=0;
32题：
有5个带运行的作业，它们的估计运行时间分别是9，6，3，5和x。
采用那种次序的运行各种作业将得到最短的平均响应时间。
采用最短作业优先法运行作业将得到最短平均相应时间。
具体执行顺序是（依赖x）：
1）x<
=3时，xà
3à
5à
6à
9
2）3<
x<
=5时，3à
xà
3）5<
=6时，3à
4）6<
=9时，3à
5）9<
x时，3à
9à
x
35．
设有n个柜台
需要考虑等待人数
如果没有顾客则柜台需要等待设置empty=0
如果顾客太多则顾客需要等待设置Customer=0
intCUSTOMER_NUM=1;
intCOUNTER_NUM=1;
Customer
//取号码
P（MUTEX_CUSTOMER_NUM）;
intX=CUSTOMER_NUM;
CUSTOMER_NUM++;
V（MUTEX_CUSTOMER_NUM）;
//等待叫号
V（COUNTER）;
P（CUSTOMER）;
ACTION_CUSTOMER（X）;
Counter
intX;
REPEAT
//叫号
P（COUNTER）;
V（CUSTOMER）;
P（MUTEX_COUNTER_NUM）;
intX=COUNTER_NUM;
V（MUTEX_COUNTER_NUM）;
ACTION_COUNTER（X）;
UNTILfalse;
37.对PV操作定义做如下修改
P（s）:
s:
=s-1;
Ifs<
0
Then将本进程插入相应队列末尾等待；
V（s）：
s:
=s+1;
=0
Then
从等待队列队尾取一个进程唤醒，
插入就绪队列
问题：
（实现4个进程使用某一个需互斥使用的资源）
1）这样定义P、V操作是否有问题？
不合理：
先进后出；
可能“无限等待”
2）先考虑用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。
思路：
令等待队列中始终只有一个进程。
将“栈”变成“队列”
VarS:
array[1..n-1]ofsemaphore;
{n为进程数目；
S[i]初值为i；
S[n-1]到
S[1]的作用好象是n-1层筛子}
ProcedurePi;
Vari:
Begin
Repeat
Pre_Do_it（）;
Fori:
=n-1Downto1Do
P（S[i]）;
Do_It_In_Critical_Section;
=1Ton-1Do
V（S[i]）;
Post_Do_it（）;
Untilfalse;
3）对于2）的解法，有无效率更高的方法。
如有，试问降低了多少复杂性？
上述解法每次都需要做2（n-1）次P/V操作，
性能低下。
采用二叉树的思想，改进如下：
设有4个进程P1..P4，
VarS1,S2,S3:
ProcedureP1;
{P2isthesame }
Repeat
P（S1）;
P（S3）;
Do_It（）;
V（S3）;
V（S1）;
End;
ProcedureP3;
{P4isthesame}
P（S2）;
V（S2）;
假设共有2N个进程争用临界区；
时间复杂性：
2N-1vs N；
空间复杂性：
2N-1vs2N-1
38用进程通讯的办法解决生产者消费者问题问题（设有N个缓冲区）
生产者：
Voidproducer（void）
intitem;
Messagem;
While（TRUE）{
produce_item（&
item）;
Receive（consumer,&
m）;
Build_message（&
m,item）;
Send（consumer,&
}
消费者：
Voidconsumer（void）;
{
intitem,I;
Messagem;
For（i=0;
i<
N;
i++）send（producer,&
//发N条空消息
While（TRUE）{
Receive（producer,&
m）；
Extract_item（&
m,&
Send（producer,&
Consumer_item（item）;
}
39.用管程实现哲学家就餐问题
解法思想如下：
一个想用餐的哲学家首先拿他（她）的左边叉子，拿到后若他（她）的右边的叉子时空闲的则拿起它开始用餐，否则，他（她）放下左边的叉子并重复这个过程。
该解法是非构造性的，即假设管程已经实现。
FUNCTIONtest_and_pick_up（i:
0..4）:
boolean;
BEGIN
IFfork[i]=usedTHEN
test_and_pick_up=false
ELSE
BEGIN
fork[i]:
=used;
test_and_pick_up:
=true
END
END;
PROCEDUREput_down（i:
0..4）;
{放下}
BEGIN
fork[i]=free;
signal（queue[i]）;
END;
PROCEDUREinitialize;
{初始化}
VARi:
0..4
FORi:
=0TO4DO
BEGIN
fork[i]:
=free;
END
END;
BEGIN
initialize
每个哲学家内部定义一个局部变量：
VARwith_two_gorks:
Boolean;
i号哲学家（i=0,..4,）的活动是这样的：
REPEAT
THINKING；
with_two_fork:
=false;
REPEAT
dining_philosophers.pick_up（i）;
IFdining_philosophers.test_and_pick_up（（i+1）MOD5）THEN
with_two_fork:
=true
ELSE
dining_philosophers.put_down（i）;
UNTILwith_two_forks;
EATING;
dining_philosophers.put_down（i）;
dining_philosophers.put_down（（i=1）MOD5）;
UNTILfalse;
补充题:
写者优先问题：
reader
Repeat
P（s）;
P（mutex）;
RC:
=RC+1;
ifRC=1
thenP（w）;
V（mutex）;
V（s）;
reading;
=RC-1;
ifRC=0thenV（w）;
writer:
Repeat
P（k）;
WC:
=WC+1;
ifWC=1thenP（s）;
V（k）;
P（w）;
writing;
V（w）;
=WC-1;
ifWC=0thenV（s）;
升级会员 