12操作系统复习题答案基本全部答案.docx
《12操作系统复习题答案基本全部答案.docx》由会员分享，可在线阅读，更多相关《12操作系统复习题答案基本全部答案.docx（42页珍藏版）》请在冰点文库上搜索。
12操作系统复习题答案基本全部答案
（一）进程同步
●进程同步1
进程P1和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后，才能执行P2的代码段S2.为描述这种同步关系，①：
试设计相应的信号量，②：
给出信号量的初始值，③：
给出进程P1和P2的结构
解答:
①信号量变量申明为
Typedefstruct{
intvalue;//信号量中的值，表示资源的数量
structPCB*L;//等待该信号量的队列
}semaphore;
设信号量semaphoresynch;
②初始值为：
synch.value=0
③进程P1和P2的结构为
P1:
{P2:
{
⋮⋮
S1wait（synch）;
signal（synch）;S2
⋮⋮
}}
●进程同步2
问题描述：
（理发店问题）一个理发店有一间配有n个椅子的等待室和一个有理发椅的理发室。
如果没有顾客，理发师就睡觉；如果顾客来了二所有的椅子都有人，顾客就离去；如果理发师在忙而有空的椅子，顾客就会坐在其中一个椅子；如果理发师在睡觉，顾客会摇醒他。
1给出同步关系
2设计描述同步关系的信号量；
3给出满足同步关系的进程结构（请完成满足同步关系的进程结构）。
解答：
①顾客customer应满足的同步关系为：
a:
顾客来时要等空的椅子，否则不进理发室
b:
座椅上的顾客要等理发椅空才有可能与别的顾客竞争理发椅，如果顾客坐上
理发椅，就要腾空其座椅给新来顾客，同时叫理发师给其理发。
c：
一旦顾客理发完，就要让别的等待顾客有机会理发。
理发师应满足的同步关系为：
一旦顾客唤醒，就给顾客理发，之后进入睡觉。
②信号量定义如下：
Typedefstruct{
intvalue;//信号量中的值，表示资源的数量
structPCB*L;//等待该信号量的队列
}semaphore;
互斥信号量定义如下：
Typedefstruct{
boolflag;
structPCB*L;
}binary_semaphore;
理发店问题的解决需要信号量和互斥信号量为：
semaphorechair;binary_semaphorebarber_chair,hair_cut;
它们的初始值为：
chair.value=n;barber_chair.flag=1;hair_cut.flag=0;
③顾客和理发师进程分别为：
customer{barber{
wait（chair）;do{
waitinginthechair；wait（hair_cut）;
wait（barber_chair）;cuttinghair；
signal（hair_cut）;signal（barber_chair）;
sittinginbarberchairforhaircut;}while
（1）
signal（chair）;}
}
●进程同步2
设公共汽车上，司机和售票员的活动分别为：
司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。
①给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。
②用信号量和wait,signal操作实现他们间的协调操作。
解答：
①根据一般的常识，有
售票员应满足的同步关系为：
当司机停车后，才将车门打开让顾客上下车。
司机的同步关系为：
当售票员关门后，才能开车.
②设互斥信号量binary_semaphorebus_closed,bus_stopped;初始值为bus_closed.flag=0;bus_stopped.flag=0;
//表达初始情况第一次用到信号量时情形为车门没有关，车是开着的
③进程为:
driver{busserver{
do{do{
wait（bus_closed）;closingthedoor;
busstartingup；signal（bus_closed）;
busisdriving；ticketselling;
busisparking；wait（bus_stopped）;
signal（bus_stopped）;openingthedoor;
}while
（1）gettingonoffthebus;
}}while
（1）
}
●进程同步3：
某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：
（1）每两个学生组成一组，各占一台机器，协同完成上机实习；
（2）只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；
（3）上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。
试用信号量机制（P/V操作）实现它们的同步关系。
解
（1）确定并发和顺序操作
在这个问题中，学生（student）、检查教师（teacher）和门卫（gategard）是并行操作的，因此,有多个学生（student）进程、一个检查教师（teacher）进程和一个门卫（gategard）进程。
（2）确定互斥和同步的规则
gateguard：
只有凑够两个学生，并且此时机房有空闲机器时，门卫才分配计算机给学生，允许该组学生进入机房；
student：
只有门卫分配完计算机后，学生才能进入机房上机操作。
只有老师检查完毕才能离开。
Teacher：
只有老师检查完学生的实习，才准许学生离开。
（3）每个进程的操作流程
设立有学生到达标志，通知gateguard进程；
学生是否可进入？
上机实习；
设立实习完成标志，通知教师；
教师是否可检查，等待教师检查完毕；
学生释放一台计算机资源；
repeat
是否有学生１实习完成？
是否有学生２实习完成？
（是否有一组学生实习完成）
检查学生实习结果；
检查完成，允许学生1离开；
检查完成，允许学生2离开；
untilfalse
repeat
等待学生1到达;
等待学生2到达;
是否有可用的计算机1;
是否有可用的计算机2;
分配计算机；
设置学生1可进入标志;
设置学生2可进入标志;
untilfalse
（4）确定信号量的个数和含义
student：
是否有学生;
computer：
是否有可用的计算机；
enter：
学生是否可以进入机房；
finish：
是否有学生完成实习；
test：
老师是否检查完一组学生。
（5）确定信号量的初值
在初始状态，各信号量的初值如下：
student=0学生没有到达;
compute=2m有2m个可用的计算机；
enter=0不允许学生进入机房，因为需要得到门卫允许；
finish=0没有学生实习完成；
test=0老师没有检查学生。
（6）确定P、V操作的位置
设立有学生到达标志，通知gateguard进程=>V（student）
学生是否可进入？
=>P（enter）
上机实习；
设立实习完成标志，通知教师=>V（finish）
教师是否可检查，等待教师检查完毕=>P（test（i））
学生释放一台计算机资源=>V（computer）
repeat
是否有学生１实习完成？
=>P（student）
是否有学生２实习完成？
=>P（student）
（是否有一组学生实习完成）
检查学生实习结果；
检查完成，允许学生1离开=>V（test（i））
检查完成，允许学生2离开=>V（test（i））
untilfalse
repeat
等待学生1到达=>P（student）
等待学生2到达=>P（student）
是否有可用的计算机1=>P（computer）
是否有可用的计算机2=>P（computer）
分配计算机；
设置学生1可进入标志=>V（enter）
设置学生2可进入标志=>V（enter）
untilfalse
（7）P、V操作实现
程序如下：
student:
=0;
computer:
=2m;
enter:
=0;
finish:
=0;
test（i）:
=0;
parbegin
Studenti:
Begin
V（student）;/*表示有学生到达，通知gateguard进程*/
P（enter）;/*学生是否可进入*/
上机实习；
V（finish）;/*实习结束，通知教师,有需要检查的学生*/
P（test（i））;/*等待教师检查完毕*/
V（computer）;/*释放计算机资源}
End;
.
Teacher:
Begin
repeat
P（finish）;/*是否有需要检查的学生，等待实习完成*/
P（finish）;/*是否有需要检查的学生，等待实习完成*/
选出可检查的第i组学生；
检查第i组学生实习结果；
V（test（i））;/*检查完成*/
V（test（i））;/*检查完成*/
untilfalse
End;
Gategard:
Begin
repeat.
P（student）;/*等待学生到达*/
P（student）;/*等待另一学生到达*/
P（computer）;/*是否有可用的计算机*/
P（computer）;/*是否有可用的计算机*/
分配计算机；
V（enter）;/*设置学生1可进入标志*/
V（enter）;/*设置学生2可进入标志*/
untilefalse
End;
Parend;
在student进程中，如果在一个学生到达后，立即向gateguard进程发信号，在gateguard进程为其分配计算机后，该学生才被允许进入机房，因此避免了让该学生争夺计算机的使用权和死锁的发生。
进程同步4：
多个进程对信号量S进行了5次P操作，2次V操作后，现在信号量的值是-3，与信号量S相关的处于阻塞状态的进程有几个？
信号量的初值是多少？
解
（1）因为S的当前值是-3，因此因为S处于阻塞状态的进程有3个；
（2）因为每进行一次P（S）操作，S的值都减1，每执行1次V操作S的值加1，故信号量的初值为-3+5-2=0;
进程同步5：
使用多个进程计算Y=F1（X）+F2（X）.
解
（1）确定并发和顺序操作
在这个问题中，F1（X）和F2（X）的计算是可以并行处理的，因此F1（X）和F2（X）可以分别出现在两个进程中。
（2）确定互斥或同步的规则
在F1（X）+F2（X）中，必须在F1（X）和F2（X）计算完毕，才能进行加法运算，因此本问题是同步问题。
（3）同步的操作流程
〈进程main〉
创立进程p1来计算F1（X）；
创立进程p2来计算F2（X）；
F1（X）计算是否完成？
没有，等待；①
F2（X）计算是否完成？
没有，等待；②
进行加法运算。
〈进程p1〉
y1=F1（X）；
设置F1（X）计算完成标志；③
〈进程p2〉
y1=F2（X）；
设置F2（X）计算完成标志。
④
（4）确定信号量的个数和含义
根据同步规则以及操作流程确定信号量的个数是2个，S1和S2：
S1含义是F1（X）计算是否完成；
S2含义是F2（X）计算是否完成。
（5）确定信号量的初值
S1=0；
S2=0。
（6）确定P、V操作的位置
上面①处是一个P操作，P（S1）；
上面②处是一个P操作，P（S2）；
上面③处是一个V操作，V（S1）；
上面④处是一个V操作，V（S2）。
解法1
Main（）
Publicy,y1,y2,.P1,P2
SemaphoreS1,S2
{
S1=0;
S2=0;
P1=Creat（N-F1,F1,x,……）;
P2=Creat（N-F2,F2,x,……）;
P（S1）;
P（S2）;
y=y1+y2;
}
ProcedureF1（x）
{
y1=计算1;
V（S1）；
}
ProcedureF2（x）
{
y2=计算2;
V（S2）
}
解法2
Main（）
Publicy,y1,y2,.P1,x
SemaphoreS1
{input（x）;
S1=0;
P1=Creat（N-F1,F1,x,……）;
Y2=F2（x）;
P（S1）;
y=y1+y2;
}
ProcedureF1（x）
{
y1=计算1;
V（S1）
}
采用2个进程和1个信号量来实现Y=F1（X）+F2（X）的时候，采用的方法是父进程创立子进程，F1（X）在子进程中计算，F2（X）在父进程中计算，因此F1（X）和F2（X）计算仍然是并发进行的。
S1信号量的含义为F1（X）是否完成。
改进的方法比原来的方法节约一个进程和一个信号量，但并发操作的程度并没有降低。
进程同步6：
例如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。
BUFF1的容量为m，BUFF2的容量是n,PUT、MOVE、GET每次操作一个数据，在操作的过程中要保证数据不丢失。
试用Ｐ、Ｖ原语协调PUT、MOVE的操作，并说明每个信号量的含义和初值。
GET
PUT
Buff1
Buff2
MOVE
图4.2进程操作图
解
（1）确定并发的操作
本问题是把2个消费者和生产者问题综合在一起。
多个PUT操作与一个MOVE操作并发进行，多个GET操作与一个MOVE操作并发进行。
因此本题涉及三类进程：
PUT类进程，有多个；GET类进程，有多个；MOVE类进程，有1个。
（2）操作规则
1）只有buff1有空间才能进行PUT操作；
2）只有buff1有数据，buff2有空间才能进行MOVE操作；
3）只有buff2有数据才能进行GET操作；
4）不允许多个进程同时操作buff1；
5）不允许多个进程同时操作buff2。
（3）操作流程
{
repeat
判断buff1是否有空间，没有则等待；
是否可操作buff1；
PUT；
设置buff1可操作标志；
设置buff1有数据的标志；
untilfalse
}
{
repeat
判断buff1是否有数据，没有则等待；
判断buff2是否有空间，没有则等待；
是否可操作buff1；
是否可操作buff2；
MOVE；
设置buff1可操作标志；
设置buff2可操作标志；
设置buff1有空间标志；
设置buff2有数据标志；
untilfalse
}
{
repeat
判断buff2是否有数据，没有则等待；
是否可操作buff2；
GET；
设置buff1可操作标志；
设置buff1有空间标志；
untilfalse
}
（4）信号量
设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如下：
1）full1表示buff1是否有数据，初值为0；
2）empty1表示buff1有空间，初值为m；
3）B-M1表示buff1是否可操作，初值为1；
4）Full2表示buff2是否有数据，初值为0；
5）Empty2表示buff2有空间，初值为n；
6）B-M2表示buff2是否可操作，初值为1；
（5）P、V操作实现
{
repeat
P（empty1）；/*判断buff1是否有空间，没有则等待*/
P（B-M1）；/*是否可操作buff1*/
PUT；
V（B-M1）；/*设置buff1可操作标志*/
V（full1）；/*设置buff1有数据的标志*/
untilfalse
}
{
repeat
P（full1）；/*判断buff1是否有数据，没有则等待*/
P（empty2）；/*判断buff2是否有空间，没有则等待*/
P（B-M1）；/*是否可操作buff1*/
P（B-M2）；/*是否可操作buff2*/
MOVE；
V（B-M1）；/*设置buff1可操作标志*/
V（B-M2）；/*设置buff2可操作标志*/
V（empty1）；/*设置buff1有空间标志*/
V（full2）；/*设置buff2有数据标志*/
untilfalse
}
{
repeat
P（empty2）；/*判断buff2是否有空间，没有则等待*/
P（B-M2）；/*是否可操作buff2*/
GET；
V（B-M2）；/*设置buff2可操作标志*/
V（full2）；/*设置buff2有数据的标志*/
untilfalse
}
进程同步7：
一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。
若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。
解〈购票者进程〉
{┋
P（S）；
进入售票厅；
购票；
退出售票厅；
V（S）；
}
信号量的初值
S=300
进程同步8：
针对如下所示的优先图解答下列问题：
S1
S4
S2
S3
S5
S6
图4.4进程优先图
（1）仅使用并发语句能否将其转换成正确的程序？
如果能则写出相应程序，如果不能则说明为什么？
（2）若可以使用信号量机构，该优先图将如何转换成正确的程序？
解
（1）如果仅用并发语句不能将其转换成程序。
S2
S5
S2
S4
S3
S5
S12
S4
因为S5有２个前趋，S4有２个前趋，S6有２个前趋。
（2）使用信号量机构，就可以将其转换成程序。
Vara,b,c,d,e,f,g,h:
Semaphores;
{初值均为0}
Parbegin
BeginS1;V（a）;V（b）;V（c）;End
BeginP（a）;S2;V（d）;V（e）;End
Begin P（b）;S3;V（f）;End
BeginP（c）;S4;V（h）;End
BeginP（d）;P（f）;S5;V（g）;End
BeginP（g）;P（h）;S6;End
Parend
（二）死锁
●死锁1：
5个进程，3种资源，某个时刻，资源分配情况如下：
AllocationMaxAvailable
ABCABCABC
P0010753,332
P1200322
P2302902
P3211222
P4002433
问：
系统是否处于安全状态？
如果P1再提出请求1个A类，2个C类资源，是否该批准？
解答：
由Allocation和Max矩阵得到，系统未来需求矩阵为：
Need=
在当前的资源分配状态可以有安全的分配序列{p1,p3,p4,p2,p0},具体分析如下：
①Available（3,3,2）可以满足P1的未来请求（1,2,2）,P1得到执行，释放资源；
②Available（5,3,2）可以满足P3的未来请求（0,1,1）,P3得到执行,释放资源；
③Available（7,4,3）可以满足P4的未来请求（4,3,1）,P4得到执行，释放资源；
④Available（7,4,5）可以满足P2的未来请求（6,0,0）,P2得到执行，释放资源；
⑤Available（9,4,5）可以满足P0的未来请求（6,4,3）,P0得到执行，释放资源。
所以，系统当前的状态是安全的。
对P1提出的分配请求（1,0,2），假设分配予以满足后，系统状态为：
Allocation=
，Need=
，Available=（2,3,0）,由于可用资源无法满足任何一个进程未来的请求，这样系统就处于不安全状态，所以，对进程P1的请求，不能予以满足。
解答：
●死锁2：
假设一个系统有某类资源m个，被n个进程共享，进程每次只请求和释放一个资源，证明只要系统满足下面两个条件，就不会发生死锁：
（1）每个进程需求资源的最大值在1到m之间；
（2）所有进程需要资源的最大值的和小于m+n。
解答：
由题目有条件①：
∑i=1MaxiNeedi=Maxi-Allocationi。
如果存在死锁，还有条件③：
∑i=1Allocationi=m
由①和②得：
∑i=1Needi+∑i=1Allocationi=∑i=1Maxi由③得：
∑i=1Needi+m●死锁3：
和死锁1相同，系统的资源数量为：
（10，5，7）。
经过一段时间的分配后，资源分配与占用情况见下表所示。
进程
MAXABC
AllocationABC
NeedABC
AvailableABC
P0
753
010
743
332
P1
322
200
122
P2
902
302
600
P3
222
211
011
P4
433
002
431
分析进程P0的请求（0,1,0）能否满足？
●死锁4：
假设系统有4个相容类型的资源被3个进程共享，每个进程最多需要2个资源，证明这个系统不会死锁。
证明：
每个进程请求共享资源的最大量相等，且为x，（0此刻，系统剩余的可用资源数为：
4-3*（x-1）。
此时不论x为1还是2，4–3*（x-1）≥1时，系统不会出现死锁的。
进程调度与死锁5：
有三个进程P1，P2和P3并发工作，进程P1需用资源S3和S1，进程P2需用资源S1和S2，进程P3需用资源S2和S3。
回答。
•
（1）若对资源分配不加限制，会发生什么情况?
为什么?
• （
升级会员 