精选操作系统习题答案Word文档下载推荐.docx
《精选操作系统习题答案Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《精选操作系统习题答案Word文档下载推荐.docx（19页珍藏版）》请在冰点文库上搜索。
C
4
D
2
先来先服务算法
0391315
进程
到达时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
0
3
1
6
9
8
8/6=1.33
C
4
9
13
9/4=2.25
13
15
9/2=4.5
平均周转时间=（3+8+9+9）/4=7.25
平均带权周转时间=（1+1.33+2.25+4.5）/4=2.27
循环（时间片2）
024689111315
周转时间:
由就绪开始时刻到处理完毕时刻的时间
带权周转时间：
周转时间/运行时间
等待时间（waitingtime）：
周转时间与处理时间之差
等待时间
9/3=3
14
8
14/6=2.33
5
2/2=1
平均周转时间=（9+14+9+2）/4=8.5
平均等待时间=（6+8+5+0）/4=4.75
平均带权周转时间=（3+2.33+2.25+1）/4=2.145
短作业优先
1391115
3/3=1
11
15
11/4=2.75
11
5/2=2.5
平均周转时间=（3+8+11+5）/4=6.75
平均带权周转时间=（1+1.33+2.75+2.5）/4=1.895
响应比高者优先
RR=1+WT/BT
在9时刻出现了D和C
C的响应比=1+5/4=2.25
D的响应比=1+3/2=2.5
1391115
7、在一个使用多级反馈队列的系统中，一个只使用CPU的进程的执行时间为40秒，如果第1队列时间片为2，每级时间片增加5个时间单元，那么这个作业运行结束前会被中断多少次，结束时处于哪级队列？
解3：
进程被中断的情况有：
在时刻2（第1队列），在时刻2+7（第2队列），在时刻9+12（第3队列），在时刻21+17（第4队列），当该进程结束时位于第5队列，中断4次。
练习二互斥、同步与通信
1、设有3个进程R、W1和W2，共享缓冲区B，B中每次只能存放一个数，当B中无数据时，可以从输入设备上读数据到B中，若数为奇数时允许W1取出打印，否则允许W2取出打印，W1和W2每次仅能打印一次，它们不能从空的B中取数据。
设信号量sr表示是否可读，初值为1
设信号量sp1表示w1进程是否可打印，初值为0
设信号量sp2表示w2进程是否可打印，初值为0
cobegin
sr,sp1,sp2:
semaphore:
=1,0,0;
x:
integer;
processreaderprocessw1processw2
beginbeginbegin
repeatrepeatreapet
p（sr）;
p（sp1）;
p（s2p）;
读入一个数放入x;
打印x1;
ifxmod2=0thenv（sp2）v（sr）;
v（sr）;
elseuntilfalse;
untilfalse;
v（sp1）;
end;
end;
2、有3个好朋友预定在一个地方集合，然后一起去看电影，请用PV描述他们的同步操作。
定义一个计数器，统计到达的人数：
count，初值为0
定义三个同步信号量s1，s2，s3，表示是否可以去看电影，初值都不可以看，为0
定义一个互斥信号量mutex，用于对count的互斥访问
var
count:
integer:
=0;
s1,s2,s3,mutex:
=0,0,0,1;
P1进程P2进程P3进程
P（mutex）p（mutex）p（mutex）
Count:
=count+1;
=count+1
V（mutex）;
v（mutex）v（mutex）
Ifcount=3thenifcount=3thenifcount=3then
Beginbeginbegin
V（s2）;
v（s1）;
V（s3）;
v（s3）;
v（s2）;
Endendend
Elseelseelse
P（s1）;
p（s2）;
p（s3）;
练习三互斥、同步与通信
1、两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。
进程PA，PB之间的通信满足如下条件：
buf[0]
buf[1]
（1）至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。
（2）当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。
试描述发送过程send（i,m）和接收过程receive（i,m）。
这里i代表缓冲区。
bufempty[0]、bufempty[1]表示缓冲区是否空，初值为n
buffull[0]、buffull[1]表示缓冲区是否满，初值为0
buf[0]、buf[1]表示两个缓冲区
Send（i,m）
Begin
localx
P（bufempty[i]）
按FIFO方式选择一个空缓冲区
buf[i]（x）=m
buf[i]（x）置满标记
V（buffull[i]）
End
Receive（i,m）
Lccalx
P（buffull[i]）
按FIFO方式选择一个装满数据的缓冲区buf[i]（x）
m=buf[i]（x）
buf[i]（x）置空标记
V（bufempty[i]）
Pa调用send（0,m）和receive（1,m）
Pb调用send（1,m）和receive（0,m）
2、设有三组进程PA，PB，PC，PA进程每次从磁盘中读入一条记录到缓冲区1中，缓冲区1可存放N条记录，PB进程每次只能从缓冲区1中取出一条记录到缓冲区2中，缓冲区2可存放N/2条记录，PC进程每次只能从缓冲区2中取出一条记录来打印，请用管程描述它们之间的同步操作。
本题中，PA是一个生产者，PB既是生产者又是消费者，PC是消费者，
条件变量：
notfull1:
表示B1是否满，notfull2：
表示B2是否满
notempty1：
表示B1是否空，notempty2：
表示B2是否空
k1,k2:
分别表示在B1中PA放记录的位置和PB取记录的位置，初值为0。
t1,t2:
分别表示在B2中PB放记录的位置和PC取记录的位置，初值为0。
count1,count2：
分别表示B1存放记录数和B2存放记录数.初值为0。
count1>
=n：
表示B1已满，这时PA进程不能再读入记录到B1中，
将wait（notfull1）
count1<
n：
PA可以放1条记录到B1中，此时看是否有等待B1中记录的，
若有则将singal（notempty1）
count2>
=n/2：
表示B2已满，这时PB进程不能从B1中读记录到B2中，
将wait（notfull2），当count1<
=0时表示B1中无记录，PB不能
从B1中取记录，将wait（notempty1）
count2<
n/2并且count1>
0：
表示PB可以从B1中取1条记录到B2中，此时
检查是否有等待B2的记录，若有则将singal（notempty2）
=0：
表示B2中无记录，PC不能打印，执行wait（notempty2）,否则从B2中取记录打印，同时检查是否有PB在等待B2中放记录，若有则执行singal（notfull2）。
过程：
get（item）：
PC从B2中取记录
put（item）：
PA从磁盘读记录到B1中。
Getput（item）：
PB从B1取记录到B2中。
TypeprocedurePC=monior
Vark1,k2,t1,t2,count1,count2:
integer
B1:
array[0…n-1]ofitem;
B2:
array[0…n/2-1]ofitem;
notfull1,notfull2,notempty1,notempty2:
condition;
procedureentryput（item）
begin
ifcount1>
=nthenwait（notfull1）;
B1[k1]:
=item;
k1:
=（k1+1）modn;
count1:
=count1+1;
signal（notempty1）;
procedureentrygetput（item）
ifcount2>
=n/2thenwait（notfull2）;
ifcount1<
=0thenwait（notempty1）;
B2[t1]:
=B1[k2];
t1:
=（t1+1）modn/2;
k2:
=（k2+1）modn;
signal（notfull1）;
signal（notempty2）;
procedureentryget（item）
ifcount2<
=0thenwait（notempty2）;
打印B2[t2];
t2:
=（t2+1）modn/2;
signal（notfull2）
k1=k2=t1=t1=0;
count1=-count2=0;
processPAprocessPBprocessPC
beginbeginbegin
repeatrepeatrepeat
readanitem;
PC.getput（item）;
PC.get（item）;
PC.put（item）;
untillfalse;
printitem;
Untillfalse;
End;
练习四死锁
1、某系统采用死锁检测手段发现死锁，设系统中资源类集合为{A，B，C}，资源类A中共有17个实例，资源类B中共有5个实例，资源类C中共有20个实例．又设系统中进程集合为{p1,p2,p3,p4,p5},T0时刻系统状态如下：
Allocation
Need
Available
ABC
ABC
ABC
p1:
212
347
p2:
402
134
p3:
405
006
p4:
204
221
p5:
314
110
在T0时刻是否安全，请给出安全系列
在T0时刻若进程P2请求资源（034），能否实现分配，为什么？
在
（2）的基础上，若进程P4请求资源（201），能否实现分配，为什么？
在（3）的基础上，若进程P1请求资源（020），能否实现分配，为什么？
（1）由已知可知，系统剩余资源为（233）
Allocation
WorkFinish
ABC
ABC
ABC
ABC
p1:
212
233
p2:
402
405
204
221
p5:
314
WorkAllocation
Need
Work+AllocationFinish
ABCABC
ABC
A
BC
7411212
347
9513true3
9513402
13515true4
13515405
00617520true5
233204
221437true1
437314
1107411true2
可以找到一个系列p4,p5,p1,p2,p3
（2）在T0时刻若进程P2请求资源（034），因请求资源大于剩余资源（233），不能分配
（3）在
（2）的基础上，若进程P4请求资源（201），由于请求资源（201）<
需求资源（221），
请求资源（201）<
剩余资源（233），进行试分配
Allocation
Need
ABC
032
020
再使用安全性检测算法，得到
WorkAllocation
Work+AllocationFinish
ABCABC
7411212
9513true3
134
13515true4
00617520true5
032405
020437true1
1107411true2
（4）在（3）的基础上，若进程P1请求资源（020）,由于请求资源（020））<
需求资源（347），请求资源（020））<
剩余资源（032），进行试分配
Allocation
Available
232
327
012
由于资源（012）不能满足任何进程故不能分配
2、有三类资源R1,R2,R3，R1和R2资源数分别为２，R3为１，有四个进程P1,P2,P3,P4，每个进程占用资源和等待资源的情况如下：
进程 已占资源类 已占用个数 等待的资源
P1R3,R21,1R1
P2R11-
P3R11R2
P4R21R3
请画出资源分配图，使用资源分配图的约简证明是否产生死锁。
（1）该图中非孤立节点且没有请求边的是P2
（2）去掉分配边成为孤立节点
（3）寻找请求边可以满足的节点，并将请求边改为分配边
（4）没有请求边的是P1，去掉分配边成为孤立节点
（5）寻找请求边可以满足的节点，并将请求边改为分配边
（6）没有请求边的是P3,P4，去掉分配边成为孤立节点
（7）最后全部为孤立节点，系统没有死锁
3、在A、B两车站之间为单轨，且在中间有一个小站C，小站C为双轨道，给出一个无死锁、无饿死、并发度最高的算法，使用PV实现。
解：
C1
AB
C2
若AB方向火车在小站C走上边轨道，BA方向走下边轨道，则：
当同时不超过3辆火车时，不会发生死锁设信号量train=3
AC、BC为单轨，设信号量ac=1bc=1
C站：
c1=1c2=1
A到BB到C
P（train）P（train）
p（ac）p（bc）
ac上行驶bc上行驶
p（c1）p（c2）
进入C小站进入C小站
v（ac）v（bc）
p（bc）p（ac）
出C站出C站
v（c1）v（c2）
bc上行驶ac上行驶
到达B站到达A站
v（bc）v（ac）
v（train）v（train）
若AB和BA方向在小站C不规定轨道，则：
当同时不超过2辆火车时，不会发生死锁设信号量train=2
A到BB到C
练习五存储
1、一个物理内存为64MB的计算机系统，该系统的内存管理模式为页式，页长为4KB，用户程序的一个逻辑地址为6D9C（16进制），进程页表如下
进程页表
4
2
22
16
222
18
3
9
11
126
30
12
0
…
请计算：
升级会员 