操作系统第4章习题带答案

第四章 一、问答题

1、同步机制应遵循的准则是什么？

2、死锁产生的4个必要条件是什么？它们是彼此独立的吗？ 3、简述死锁的定义和死锁产生的原因。 4、简述死锁定理和解除死锁的方法。

5、什么是安全状态？怎么判断系统是否处于安全状态？ 6、同步机制应遵循的准则是什么？

7、死锁产生的4个必要条件是什么？它们是彼此独立的吗？ 二、计算题（共20分）

1、当前系统中出现下述资源分配情况：

P0 P1 P2 P3 P4 Allocation 0 1 1 0 0 0 0 3 3 0 3 0 5 3 1 2 0 4 2 4 0 1 2 0 0 Need 0 7 3 6 6 1 5 5 5 5 2 0 6 2 6 1 Available 6 2 2 利用银行家算法，试问如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？

答：Request（1，2，2，2）<=(2,3,5,6)申请合法

Request（1，2，2，2）<=Available，开始试探性分配，Available=(0,4,0,0) 测试系统是否安全：work= Available,finish=1 没有进程的need满足<=work 系统处于不安全状态，系统拒绝此次资源分配。

2、当前某系统有同类资源7个，进程P，Q所需资源总数分别为5，4。它们向系统申请资源的次序和数量如表所示。回答：

次序 进程 申请量 1 2 3 4 5 6

Q P Q P P Q 2 1 1 3 2 1 问：采用死锁避免的方法进行资源分配，请你写出系统完成第3次分配后各进程占有资源量，在以后各次的申请中，哪次的申请要求可先得到满足? 答：第1次申请，Q申请资源2，系统安全，分配 第2次申请，P申请资源1，系统安全，分配

第3次申请，Q申请资源1，系统安全，分配

资源剩余3个，P占有1个资源，Q占有3个资源，第4次分配不安全，拒绝，第5分配系统安全，满足。

3、一个计算机系统有6个磁带驱动器和4个进程。每个进程最多需要n个磁带驱动器。问当n为什么值时，系统不会发生死锁？并说明理由 答：n=2 理由同第4题

(进程资源最大需求－1)×进程数量＋1≤系统资源数量

4、 若系统有某类资源m×n+1个，允许进程执行过程中动态申请该类资源，但在该系统上运行的每一个进程对该资源的占有量任何时刻都不会超过m+1个。当进程申请资源时只要有资源尚未分配完则满足它的申请，但用限制系统中可同时执行的进程数来防止发生死锁，你认为进程调度允许同时执行的最大进程数应该是多少？并说明原因。

答；假设系统中有x个进程的进程，则资源至少要有m×x+1个才不会产生死锁，由于系统资源有m×n+1个，则可列出不等式：m×x+1≤m×n+1解不等式，得到x≤n，所以系统允许同时执行的最大进程数为n。

证明：假设在系统允许同时执行的最大进程数为n时，仍然出现了死锁，此时应该存在一组进程都在等待资源，而且系统已无资源可用。则此时该组进程最多n个，每个进程没有执行完时最多占用m个资源，所以现在系统分配出去的资源最多m×n，少于系统资源m×n+1，所以不可能有死锁出现。

若系统进程数量为n+1，每个进程占有最大资源数量为m+1，则会出现死锁。

例如，当其中n个进程均占有m个资源，剩下的一个进程占有了最后一个资源，所有进程都都还需要资源才可运行完，而此时系统已经无资源可用，产生死锁。 因此，系统允许同时执行的最大进程数为n时系统不会有死锁发生

5、设系统中有3种类型的资源A、B、C和5个进程P0、P1、P2、P3、P4，A资源的数量为10，B资源的数量为5，C资源的数量为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。（12分）

P0P1 P2 P3 P4 A 7 3 9 2 4 Max B 5 2 0 2 3 C 3 2 2 2 3 Allocation A B C 0 2 3 2 0 1 0 0 1 0 0 0 2 1 2 A 7 1 6 0 4 Need B 4 2 0 1 3 C 3 2 0 1 1 Available A B C 3 3 2 ①. T0时刻是否为安全状态？若是，请给出安全序列。

②在T0时刻若进程P1发出资源请求Request（1，0，2），是否能够实施资源分配？

③在②的基础上P4发出资源请求Request（3，3，0），是否能够实施资源分配？ ④在③的基础上P0发出资源请求Request（0，2，0），是否能够实施资源分配? 见课本

五、应用题

1、如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可以将从输入设备上读入的数存放到缓冲器中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。

semaphore S=1,SO=SE=0;

buffer B;

void R1（） {int x; while(1)

{从输入设备上读一个数;

x=接收的数; wait(S); B=x;

if B=奇数 then signal(SO); else signal(SE); } }

void W1() {int y; while(1) { wait(SO); y=B;

signal(S); {打印y中数}; } }

void W2() {int z; while(1)

{ wait(SE); z=B;

signal(S); 打印z中数 ;

} } main() {

cobegin{ R(); W1(); W2();

}

2、设计一种可以避免死锁的资源分配算法，要求写明数据结构和相应方案或算法。

参考课本上方案

3、复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。如果没有顾客，则操作员休息。当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子则必须离开复印室。利用信号量机制解决该同步互斥问题。

设置3个信号量：customers表示正在等待复印的顾客数量（不包括正在复印的顾客）；operator记录正在等候顾客的操作员数，只有1和0；mutex用于对变量waiting的互斥访问。1个变量：waiting表示等待的顾客数量。

semaphore customers=0,operator=0,mutex=1; waiting=0；

process operator( )//操作员进程 { while(1) {

wait(customers); //等待顾客到来 复印；

signal(operator); //通知顾客已经完成复印

} }

process cusotmeri( )//顾客进程i {

wait(mutex); if(waiting<5) {

waiting++;

signal(customers); signal(mutex);

wait(operator);

wait(mutex); waiting--;

signal(mutex);

} else {

signal(mutex); 离开复印室； } }

main( ) {

cobegin

{ operator( ); customeri( ); } }

4、a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量机制为工具，对ab段实现正确管理以保证行驶安全。

Semaphore S1=1,S2=1,Sab=1; int ab=ba=0;

void Pab () {

while(1) {

wait(S1);

if(ab==0)

wait(Sab); ab=ab+1;

signal(S1);

车辆从a点驶向b点; wait(S1); ab=ab-1; if(ab==0)

signal(Sab);

signal(S1); }

}

void Pba ()

{

while(1) {

wait(S2); if(ba==0)

wait(Sab);

ba=ba+1; signal(S2);

车辆从b点驶向a点; wait(S2); ba=ba-1; if(ba==0)

signal(Sab);

signal(S2); }

}

main() {

cobegin{

Pab (); Pba (); }

}

5、某系统五个合作的进程前驱图如下，请用信号量方法控制它们的执行，以确保它们的执行顺序，请写出类c算法。

P1 P2 P4 P5 P3 参考解题方案

5、一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。

假设桥墩数量为k

semaphore s, scounteast, scountwest, scount; s=1, scounteast=1, scountwest=1, scount=k; int Counteast=0, Countwest=0; void east(int i) {

wait(scounteast); if(Counteast==0) wait(s); Counteast++;

signal(scounteast); wait(scount4); 上桥，过桥，下桥； signal(scount4);

wait(scounteast); Counteast--;

if(Counteast==0) signal(s);

signal(scounteast); }

void west(int i) {

wait(scountwest); if(Countwest==0) wait(s); Countwest++;

signal(scountwest); wait(scount4); 上桥，过桥，下桥； signal(scount4);

wait(scountwest); Countwest--;

if(Countwest==0)

signal(s);

signal(scountwest); }

main() {

cobegin{ east(1); ...

east(n); west(1); ...

west(m); } }

6、现有四个进程R1、R2、W1、W2，它们共享可以存放一个数的缓冲器B。进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。为防止数据的丢失和重复打印，问怎样用wait,signal操作来协调这四个进程的并发执行。

semaphore S=1,S1=S2=0; buffer B;

void R1（） {int x; while(1)

{接收来自键盘的数; x=接收的数; wait(S); B=x;

signal(S1); } }

void R2() {int y; while(1)

{从磁盘上读一个数;

y=接收的数; wait(S); B=y;

signal(S2); } }

void W1() {int k; while(1) {wait(Sl);

k=B;

signal(S); 打印k中数; }

}

void W2() {int j; while(1) {wait(S2); j=B;

signal(S); 打印j中数; } } main() {

cobegin{ R1(); R2(); W1(); W2(); }

7、系统中有4种类型的资源A、B、C、D和5个进程P0、P1、P2、P3、P4，当前系统出现下表所示资源分配情况：

P0 P1 P2 P3 P4

试问：

①该状态是否安全？分析说明。

②如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？

Allocation A 0 1 1 0 0 B 0 0 3 3 0 C 3 0 5 3 1 D 2 0 4 2 4 A 0 1 2 0 0 Need B 0 7 3 6 6 C 1 5 5 5 5 D 2 0 6 2 6 A 1 Available B 6 C 2 D 2 （1）利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全性分析情况，如表1-4-7所示。

表1-4-7

P0 P3 P4 P1 P2 1 1 1 1 2 Work 6 6 9 9 9 2 5 8 9 9 2 4 6 10 10 0 0 0 1 2 Need 0 6 6 7 3 1 5 5 5 5 2 2 6 0 6 0 0 0 1 1 Allocation 0 3 0 0 3 3 3 1 0 5 2 2 4 0 4 1 1 1 2 3 Work+Allocation 6 9 9 9 12 5 8 9 9 14 4 6 10 10 14 Finish True True True True True 从上述分析中可以看出，此时存在一个安全序列{P0，P3，P4，P1，P2}，故该状态是安全的。

（2）P2提出请求Request（1，2，2，2），按银行家算法进行检查：

Request(1,2,2,2)≤Need(2,3,5,6)

Request(1,2,2,2)≤Available(1,6,2,2)

试探分配并修改相应的数据结构，资源分配情况如表1-4-8所示。

表1-4-8

P0 P1 P2 P3 P4 0 1 2 0 0 Allocation 0 0 5 3 0 3 0 7 3 1 2 0 6 2 4 0 1 1 0 0 0 7 1 6 6 Need 1 5 3 5 5 2 0 4 2 6 0 — — — — Available 4 — — — — 0 — — — — 0 — — — — 再利用安全性算法检查系统状态是否安全，资源向量Available（0，4，0，0）已不能满足任何进程的需要，故系统进入不安全状态，所以系统不能将资源分配给进程P2。

8、某寺庙有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸给老和尚饮用。水缸可容水10桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3个。若每次入、取水仅为1桶，而且不可同时进行。试用记录型信号量机制写出小和尚和老和尚的活动过程。

互斥资源有水缸和水井，分别用mutex1和mutex2来互斥。水桶总数仅3只，由信号量count控制，信号量empty和full控制入水和出水量。

semaphore mutex1,mutex2,empty,full,count; mutex1=1; mutex2=1; count=3; empty=10; full=0;

process young_monk（int i）(i=1、2、……) {

While(1)

{wait(empty); wait(count); wait(mutex1);

从井中取水;

signal(mutex1); wait(mutex2); 倒水入缸;

signal(mutex2); signal(count); signal(full); } }

process old_monk(int j)j(j=1、2……) {

While(1)

{wait(full); wait(count); wait(mutex2);

从缸中取水;

signal(mutex2); signal(count); signal(empty);

} } main() {

cobegin{

young_monk(i); old_monk(j); } }

9、考虑三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷，做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计一个同步算法来描述他们的活动。 Semaphore SA=SB=SC=0,SD=1; i:integer; void smokerA() {while (1) {wait(SA);

制烟; signal(SD); 吸烟； } }

void smokerB() {while (1) {wait(SB); 制烟; signal(SD); 吸烟； } }

void smokerC() {while (1) {wait(SC); 制烟; signal(SD); 吸烟； } }

Void provider( ) { while(1) {

i=random(2);//0代表纸和火柴的组合，1代表烟草和火柴的组合，2代表烟草和纸的组合

wait(SD); 把i放到桌子上； switch(i)

{case 0: signal(SA); case 1: signal (SB); case 2: signal (SC); } } }

Main() {

cobegin{ somkerA(); somkerB(); somkerC(); provider(); } }

10、假定有一个信箱可存放N封信，当信箱不满时发信者可把信件送入信箱；当信箱中有信时收信者可从信箱中取信。用指针R，K分别表示可存信和取信的位置， 请用信号量来管理这个信箱，使发信者和收信者能正确工作。 参考课本生产者消费者问题

11、n个进程共享某种资源R，该资源共有m个，每个进程一次一个地申请或释放资源。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m＋n，试证明在这个系统中不可能发生死锁。

答：设max(i)表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：

max(1)+…+max(n)=need(1)+…+need(n)+alloc(1)+…+alloc(n)=n 两式相加，

max(1)+…+max(n)=need(1)+…+need(n)+alloc(1)+…+alloc(n)〉=m+n 这与前面的假设矛盾，从而证明了在这个系统中不会发生死锁。

12、一个数据文件或记录（统称数据对象），可被多个进程共享。有些读进程要求读，而另一些写进程对数据对象进行写或修改。允许多个写进程同时读一个共享对象，决不允许一个写进程和其他读进程或写进程同时访问共享对象。请用信号量或管程为工具，实现读写进程并发的正确管理。

参考课本，题目中没有具体尤其哦球，所以读者优先和写者优先均可

13、有一个仓库，可以存放A和B两种产品，但要求：1）每次只能存入一种产品（A或B）；2）-N＜A产品数量—B产品数量＜M。其中，N和M是正整数。试用同步算法描述产品A与产品B的入库过程。

【分析】A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上。设置2个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允许sa个A产品入库；sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和A产品不入库的情况下，还可以允许sb个B产品入库。初始时，sa为M一1，sb为N一1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。

semaphore mutex=1，sa=M-1， sb=N-1; process puta() { while(1)

{ 准备一个产品； wait(sa);

wait(mutex); 将产品入库； signal(mutex); signal(sb); }

}

process puta() { while(1)

{ 准备一个产品；

wait(sb); wait(mutex); 将产品入库； signal(mutex); signal(sa); } }

main() {cobegin{

{puta(); Putb(); } }

14在一个系统中，不采用死锁避免和预防措施，但当死锁发生后需要能够检测出来，请设计一个可行的死锁检测方案。 参考课本课本方案

15、一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果等候室的所有沙发都已经占用，便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待。如果理发师因无顾客正在睡觉，则由新

到的顾客唤醒理发师为其理发。请用信号量机制解决该问题 参考课本（嗜睡理发师问题）

16、有一个可以存放n整数的循环缓冲，今有m个输入进程，每个输入进程每次读入一个数据放入缓冲中；还有k个输出进程，每个输出进程每次可以从缓冲中读出一个数据输出；不允许有两个或两个以上的输入进程（或输出进程）同时去存数据（或取数据）,但允许有一个输入进程在存数据时有一个输出进程可以取数据。试用请用信号量为工具协调它们的工作，写出算法。 参考课本（消费者生产者问题）

17、某系统中由5种资源，数量为[5，6，8，6，4]，某个时刻进程和资源的使用情况如下：

进程名 占有资源(向量) 运行完还需资源数量（向量） P1 [0，2，1，1，1] [1，0，2，1，1] P2 [2，0，1，1，1] [0，3，2，1，0] P3 [0，1，0，1，1] [0，3，3，2，2] P4 [0，3，1，2，0] [1，0，1，2，1]

如此时进程P1提出申请资源[1,0,0,0,1]，如系统满足其要求，系统是否安全？请设计一安全检测方案。 18、司机与售票员问题：

司机与售票员之间的同步关系如下所示，当司机停车后售票员才能开门，售票员关门后司机才能开车，请用信号量给出同步算法。司机与售票员的活动程序如下：

司机： 售票员：

L：车在行进中； M：买票； 停车； 开门； 开车； 关门；

goto L； goto M。

在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员在关车门之后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门

的动作也必须与司机停车取得同步。在本题中，设置两个信号量：S1、S2，S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0。

【答案】则该问题描述如下： semaphoere S1=S2=0; void Driver() {

while(1) {

wait(S1); 启动车辆； 正常行车； 到站停车； signal(S2); } }

void Busman() {

while(1) {

关车门；

signal(S1)； 售票；

wait(S2)； 开车门； } }

main() {

cobegin{ Driver(); Busman(); } } 19、写一个管程，用于实现读者——写者问题，要求写者优先。 参考课本（读者写者问题——写者优先）

20、用信号量机制解决读者——写者问题，要求写者优先。

此题是第二类读者-写者问题，即写者优先，与读者优先有一定差别。为了使写者优先，可在原来的读者优先算法的基础上增加一个互斥信号量s，初值为1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待完成；整型变量writecount，初值为0，用来对写者进行计数；互斥信号量mutex，初值为1，用来实现多个读者对写者writecount进行互斥访问。

【答案】

semaphore s,rmutex,wmutex,mutex; int readcount,writecount;

s=1;rmutex=1;wmutex=1;mutex=1; readcount=0;writecount=0; void reader(int i) { while(1) {

wait(s);

wait(rmutex);

if(readcount==0)wait(wmutex); readcount++;

signal(rmutex);

signal(s); // 在这里signal（s）位的是允许多个读者同时读 perform read operation;

wait(rmutex); readcount--;

if(readcount==0)signal(wmutex); signal(rmutex);

} }

void writer(int i) { while(1) {

wait(mutex);

if(writecount==0)wait(s); writecount++; signal(mutex);

wait(wmutex);

perform write operation; signal(wmutex);

wait(mutex); writecount--;

if(writecount==0)signal(s); signal(mutex); } }

main( ) {

cobegin

{ reader(1);

...

reader(n); writer(1); ...

writer(m); } }

21、一个数据文件或记录（统称数据对象），可被多个进程共享。有些读进程要求读，而另一些写进程对数据对象进行写或修改。允许多个读进程同时读一个共享对象，但限制同时读的进程数量不能超过n，不允许一个写进程和其他读进程或写进程同时访问共享对象。请用信号量或管程为工具，实现读写进程并发的正确管理。

读者优先，写者优先均可，下面是按照读者优先写的算法 semaphore rmutex=mutex=1，reader=n; int readcount=0;

void reader(int i) {

while(1) {

wait(rmutex);

if(readcount==0) wait(wmutex); readcount++; signal(mutex); wait(reader);

perform read operation; signal(reader); wait(rmutex); readcount--;

if(readcount==0) signal(mutex); signal(rmutex); } }

void writer(int j) {

while(1) {

wait(mutex);

perform write operation; signal(mutex); } } main() {

cobegin { reader(1);

… reader(n); writer(1); … writer(m); } }

本文来源：https://www.bwwdw.com/article/plc5.html