操作系统 习题及答案 第八章 进程同步机制与死锁

第八章进程同步机制与死锁习题1．何谓与时间有关的错误？举例说明之。并发进程执行时一定会产生与时间有关的错误吗？为什么？在并发程序中共享了公共变量，使得程序的计算结果与并发程序执行的速度有关。这种错误的结果又往往是与时间有关的，所以，把它称为“与时间有关的错误”。也就是，程序的正确性和结果受到程序执行的具体时序和时间点的影响，导致不同的执行时机产生不同的结果。例如，两个并发程序A和B共享一个公共变量n，程序A每执行一次循环都要作n=n+1操作，程序B则在每一次循环中打印出n的值并将n重新置0。程序A和B的语句在时间上可任意穿插或交叉执行，则程序A的①n=n+1操作可能在程序B的②print（n）和③n=0操作之前，也可能在它们之后或它们之间（即①出现在②之后，而在③之前），设在开始某个循环之前n的值为5，则对于上面三种情形，执行完一个循环后，打印机印出的值分别为6、5和5，而执行后的n值分别为0，1，0。这样，相同的程序在可能的三种情况下，由于程序执行的具体时序而产生了三组不同的结果。这就是与时间有关的错误。并发程序执行时不一定会产生与时间有关的错误。并发执行的程序有可能是无关进程，并且正确设计和实现的并发系统可以有效避免与时间有关的错误。2．什么是临界区？若系统中某些资源一次只允许一个进程使用，则这类资源称为临界资源，在进程中访问临界资源的程序称为临界区。3．若用Ｐ、Ｖ操作管理某一组相关临界区，其信号量Ｓ的值在[-1,1]之间变化，当S=-1，S=0，S=1时，它们各自的物理含义是什么？当S=-1时，表示当前有进程正在该临界区执行，另一个访问相同临界区的进程正在等待（等待队列进程数目是1）。当S=0时，表示当前有一个进程正在该临界区执行，没有进程等待访问该临界区。当S=1时，表示当前空闲资源数为1，可以允许进程进入该临界区。4．两个并发执行的进程A和B的程序如下：进程AWhile（true）{N=N+5;};进程BWhile（true）{打印N的值;N=0;};其中，N为整数，初值为４。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。可能的打印值为19、24.正确的打印值为24.P、V操作管理如下：初始时，设置两个信号量：S1=1，S2=0。进程A：While（true）{P(S1);N=N+5;V(S2);};进程B：While（true）{P(S2);打印N的值;N=0;V(S1);};5．a，b两点之间有一段单行车道，现在设计一个自动管理系统，管理规则如下：允许同方向的车同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入；当某方向在ab段行驶的车辆驶出了ab段且暂无同方向车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请编写程序，用P、V操作实现对ab段的正确管理以保证行驶安全。初始化全局变量Ca=0,Cb=0分别表示从ab路段上从a点驶入的车辆数和ab路段上从b点驶入的车辆数。初始化三个信号量Sa=1,Sb=1,Sr=1.其中Sa控制Ca的访问，Sb控制Cb的访问，Sr表示当前ab路段是否已有车辆的信号量。对于从a点驶入的车辆，运行以下程序：P(Sa);//请求访问从a点驶入的车辆数if(Ca==0)P(Sr);//ab路段没有从a点驶入的车辆，需要获得驶入权限Ca=Ca+1;V(Sa);从a点驶向b点;P(Sa);//请求访问从a点驶入的车辆数Ca=Ca-1;if(Ca==0)V(Sr);V(Sa);类似地，对于从b点驶入的车辆，运行以下程序：P(Sb);if(Cb==0)P(Sr);Cb=Cb+1;V(Sb);从b点驶向a点;P(Sb);Cb=Cb-1;if(Cb==0)V(Sr);V(Sb);6．有三个并发进程R、M、P，它们共享一个缓冲器B。进程R负责从输入设备读信息，每读出一个记录后把它存放在缓冲器B中，进程M在缓冲器B中加工进程R存入的记录，进程P把加工后的记录打印输出。缓冲器B中每次只能存储一个记录，当记录被加工输出后，缓冲器B中又可存储一个新记录。请用P、V操作为同步机制写出它们并发执行时能正确工作的程序。初始化三个信号量empty=1,full=0,processed=0.其中empty表示B为空的信号量，full表示B为满的信号量，processed表示B中元素为已处理的信号量。进程R：While(true){ P(empty);//申请读入缓冲器 读出记录存放入缓冲器B; V(full);}进程M：While(true){ P(full);//申请加工缓冲器中的数据在缓冲器B中加工进程R存入的记录; P(processed);}进程P:While(true){ P(processed);//申请获取加工后的数据 把加工后的记录打印输出; V(empty);}7．在公共汽车上，司机和售票员的工作流程如下所示。为保证乘客的安全，司机和售票员应密切配合协调工作，请编写程序，用P、V操作来实现司机与售票员之间的同步。司机售票员启动车辆；关门；正常行驶；售票；到站停车；开门；初始化信号量S1=0,S2=0,其中S1表示司机对售票员行动的信号，S2表示售票员对司机行动的信号。司机：While(true){ P(S2);//等待售票员关门 启动车辆; 正常行驶; 到站停车; V(S1);//提示售票员开门}售票员：While(true){ 关门; V(S2);//提示司机已关门 售票; P(S1);//等待司机到站停车 开门;}8．某银行有人民币储蓄业务，由n个柜台人员负责。每个顾客进入银行后先取一个号，并且等着叫号。当一个柜台人员空闲下来，就叫下一个号。试用P，V操作正确编写柜台人员和顾客进程的程序。初始化信号量fnumber=1，cnumber=1，customer=0, counter=n.其中fnumber控制取号机资源，cnumber控制叫号机，customer表示当前顾客量，counter表示空闲柜台人员数。每个柜台人员进程程序：While(true){ P(customer);//等待有顾客 P(cnumber);//申请叫号 叫号; V(cnumber); 为顾客办理业务; V(counter);//提示柜台空闲}每个顾客进程程序：P(fnumber);//申请取号取号;V(fnumber);V(customer);//提示有顾客P(counter);//等待空闲柜台办理业务;9．设有A、B、C三个进程共享一个存储资源F。A对F只读不写，B对F只写不读，C对F先读后写。（当一个进程写F时，其他进程既不能读F，也不能写F，但多个进程同时读F是允许的）。试利用或P、V操作，写出A、B、C三个进程的框图，要求：①执行正确；②正常运行时不产生死锁；③使用F的并发度要高。使用两个信号量来实现这个读写锁：mutex和writelock。mutex用于读者之间的互斥，保证对读者计数器的访问是互斥的；writelock用于写操作的互斥。进程A读F框图：进程B写F框图：进程C框图：先按照进程A再按照进程B10．设有两个优先级相同的进程P1和P2，如下所示。信号量S1和S2的初值均为０，试问P1、P2并发执行后，x、y、z的值各是多少？进程P1：进程P2：y=1； x=1；y=y+2； x=x+1；V(S1)； P(S1)；z=y+1； x=x+y；P(S2)； V(S2)；y=z+y； z=x+z；有以下几种情况：x=5,y=7,z=9或x=5,y=12,z=9或x=5,y=7,z=4.11．设缓冲区大小为n，指出以下生产者-消费者问题解法中的错误，并改正。Producer() //生产者进程{while(true){P(mutrx)；P(empty)；Buffer(in)=nextp；in=(in+1)%n；V(mutex)；}}Consumer() //消费者进程{while(true){P(mutex)；P(full)；nextc=buffer(out)；out=(out+1)%n；V(mutex)；消费产品nextc；}}Producer()//生产者进程{while(true){P(empty);//确保有空位P(mutex);//进入临界区Buffer[in]=nextp;//生产产品in=(in+1)%n;//移动到下一个位置V(mutex);//离开临界区V(full);//增加可消费产品的计数}}Consumer()//消费者进程{while(true){P(full);//确保有产品可消费P(mutex);//进入临界区nextc=Buffer[out];//消费产品out=(out+1)%n;//移动到下一个位置V(mutex);//离开临界区V(empty);//增加空位计数消费产品nextc;}}12．有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列出一个表目，包括座位号、姓名，读者离开时撤销登记信息。阅览室有100个座位。试用P、V操作描述这些进程间的同步关系。由于每个读者都会进行一样的操作：登记->进入->阅读->撤销登记->离开，所以建立一个读者模型即可。临界资源有：座位，登记表。读者间有座位和登记表的互斥关系，所以设信号量empty表示空座位的数量，初始为100，mutex表示对登记表的互斥访问，初始为1。Semaphoremutex=1,empty=100;Reader()：While(true){P(empty)//申请空座位P(mutex)//申请登记表//登记V(mutex)//释放登记表//进入阅读P(mutex)//申请登记表//撤销登记V(mutex)//释放登记表V(empty)//释放座位}13．有两个合作进程P1、P2，它们从一台输入/输出设备读入数据，P1进程读入数据a，P2进程读入数据b，输入设备是一台独占设备。两个进程做如下计算：P1：x=a+b；P2：y=a-b；计算完成后结果x、y由进程P1输出。用信号量实现进程P1、P2的同步算法。semaphoreS1=1，S2=0；semaphoreSb=0，Sy=0；P1(){ P(S1); 从输入设备输入数据a; V(S2); P(Sb); x=a+b; P(Sy); 使用打印机打印出x,y的结果;}P2(){ P(S2); 从输入设备输入数据b; V(Sb); y=a+b; V(Sy);}14．考虑交通死锁情况，说明其产生死锁的四个必要条件；给出一种可以避免死锁发生的简单方法。（1）该实例中死锁的四个必要条件：四个交叉路口在同一个时间点只能通过一辆车（互斥）；车1占据路口一并等待车3通过路口三、车3占据路口三并等待车4通过路口四、车4占据路口四并等待车2通过路口二、车2占据路口二并等待车1通过路口一（即占有并等待）；当路口有车辆时其它车辆无法经过该路口（非抢占）；车1等待的路口三正在被车3占有、车3等待的路口四正在被车4占用、车4等待的路口二正在被车2占有、车2等待的路口一正在被车1占有（循环等待）（2）可以设置红绿信号灯，前一分钟可以让横向车通过，后一分钟可以让纵向车通过；每个一分钟进行一次轮转15．死锁和“饥饿”有什么相同点和不同点？相同点：二者都是由于竞争资源而引起的，与资源的分配策略有关，因而防止饿死与死锁可从公平性方面考虑如FCFS先到先服务算法。不同点：①从进程状态考虑，死锁进程都处于等待态（等待某一不可被剥夺资源被释放）,饿死进程可能处于忙式等待(就绪队列上等待可剥夺处理机资源)。（忙式等待：不进入等待状态的等待实际状态为”运行“或者”就绪“忙式等待空耗处理器资源因而是低效的,进程无法向前推进等待某一事件，但不主动放弃处理器而是不断循环检测资源是否可用）。②死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源。③死锁一定发生了循环等待，而饿死则不然，这也表明通过资源分配图可以检测死锁存在与否，但不能检测是否有进程饿死。④死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。16．试叙述死锁产生的原因、必要条件和解决死锁的方法。原因1.竞争不可抢占性资源线程A已经获得资源1，还想去获得资源2，进程B已经获得资源2，想去获得资源1，但是1和2都是不可抢占的，发生死锁2.竞争可消耗资源引起死锁进程间通信，如果顺序不当，会产生死锁，比如线程A发消息m1给线程B，接收线程C的消息m3，线程B接收线程A的m1，发m2给线程C，以此类推，如果进程之间是先发信息的那么可以完成通信，但是如果是先发信息就会产生死锁3.进程推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁必要条件1.互斥条件：线程对资源的占有是排他性的，一个资源只能被一个线程占有，直到释放2.请求和保持条件：一个线程对请求被占有资源发生阻塞时，对已经获得的资源不释放3.不可剥夺：一个线程在释放资源之前，其他的线程无法剥夺占用4.循环等待：若干个执行流请求资源的情况形成了一个闭环，发生死锁时，线程进入死循环，永久阻塞解决方法给死锁线程分配足够多的资源终止系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来17．试举出日常生活中死锁的例子，并说明之。14题的交通死锁的例子18．有3个进程共享4个资源，进程对资源的分配与释放只能一次一个，每个进程最多需要2个资源。试问该系统会发生死锁吗？该系统不会发生死锁因为最坏的情况是每个进程都占有一个资源，申请第二个资源，而此时系统中剩下一个资源，不管哪个进程得到该资源，都能满足资源的需求，因此他能在有限的时间内从而释放他占有的两个资源，这两个资源又可以分配给另外两个进程，使他们运行结束，所以该系统不会发生死锁。19．假设系统中有6个资源r1，r2，r3，r4，r5和r6，有3个进程P1，P2和P3，其活动分别为：P1： P2： P3：申请r1； 申请r2； 申请r3；申请r2； 申请r3； 申请r4；释放r1； 释放r2； 释放r3；释放r2； 释放r3； 释放r4；申请r5； 申请r4； 申请r6；申请r6； 申请r1； 申请r5；释放r5； 释放r4； 释放r6；释放r6； 释放r1； 释放r5；请分析当三个进程并发执行时，是否会发生死锁现象，请给出原因。可能会发生死锁现象，当执行顺序出现：P1申请r5；P3申请r6；P1申请r6；P3申请r5；时出现循环等待，发生死锁现象。20．考虑这样一种资源分配策略：对资源的申请和释放可以在任何时刻进行。如果一个进程的资源得不到满足，则考查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则把这些资源取出分给申请进程。 例如，考虑一个有三类资源的系统，Available=（4，2，2）。进程A申请（2，2，1），可以满足；进程B申请（1，0，1），可以满足；若A再申请（0，0，1），则被阻塞（无资源可分）。此时，若C申请（2，0，0），它可以分得剩余资源（1，0，0），并从A已分得的资源中获得一个资源，于是，进程A的分配向量变成：Available=（1，2，1），而需求向量变成：Need=（1，0，1）。（1）这种分配方式会导致死锁吗？若会，举一个例子；若不会，说明死锁的哪一个必要条件不成立。（2）会导致某些进程的无限等待吗？（1）不会导致死锁，死锁的“不可剥夺条件”被破坏（2）可能导致进程的无限等待。如果一个进程反复地因为其他进程的需求而被剥夺资源，而它的资源需求始终得不到完全满足，那么会陷入一种被持续阻塞的状态。21．假定一个系统有四种资源，R={6，4，4，2}，当前系统状态如下图所示。该状态安全吗？请阐述理由。资源申请进程目前占有量最大需求量尚需要量ABCDABCDP120113211P211001202P311001120P410103210P501012101系统剩余资源量ABCD图8-18题21图进程资源申请目前占有量最大需求量尚需求量ABCDABCDABCDP1201132111200P2110012020102P3110011200020P4101032102200P5010121012000系统剩余资源1120答：系统剩余资源1120能满足进程P3的需求，故分配给P3后P3释放资源，系统剩余资源分别为2220，可满足P1，分配给P1后P1释放资源，系统剩余资源分别为4232，依次类推可满足所有进程需求，所以该状态是安全状态。22．一个计算机系统有某种资源6个，供n个进程使用，每个进程至少需要2个资源。当n为何值时，系统不会发生死锁？有m个资源，每个进程最多需要x个资源，则最多允许几个进程参与竞争，确保不会发生死锁？进程数使用n表示当n(x-1)+1<=m时，此时不会发生死锁n<=(m-1)/(x-1)=5/1=523．设系统有三种类型的资源，数量为（4，2，2）。系统中有进程P1、P2、P3按如下顺序请求资源；进程P1申请（2，2，1）

进程P2申请（1，0，1）

进程P1申请（0，0，1）

进程P3申请（2，0，0）该系统按照死锁预防中破坏“不可剥夺”条件的方案二，对上述申请序列，给出资源分配过程。指出哪些进程需要等待资源，哪些资源被剥夺。进程可能进入无限等待状态吗？进程P1申请（2，2，1），剩余（2，0，1）进程P2申请（1，0，1），剩余（1，0，0）进程P1申请（0，0，1），剥夺P2的第三种资源，之后还给P2最后进程P3申请24．在实际的计算机系统中，资源数和进程数是动态变化的。当系统处于安全状态时，如下变化是否可能使系统进入非安全状态？（1）增加Available （2）减少Available （3）增加Max（4）减少Max （5）增加进程数 （6）减少进程数（2）（3）（5）25．假设一条河上有一座由若干个桥墩组成的桥，若一个桥墩一次只能站一个人，想要过河的人总是沿着自己过河的方向前进而不后退，且没有规定河两岸的人应该谁先过河。显然，如果有两个人P1和P2同时从两岸沿此桥过河，就会发生死锁。请给出解决死锁的各种可能的方法，并阐述理由。题意分析需要保证：同一时刻两个方向只能有一个方向的人再前进。只要方向1上还有人未通过，则方向2的人就不能上桥。同一个方向上能有多个人等待过桥，但是每次只能过一个人，其他人可以排队。方向2的人想上桥通过，必须等方向1的全部人都通过才可以。反之也成立。通过上述分析我们不难发现，过桥问题实际就是读者写者的读者优先算法的一个变形。只能有一个方向的人过桥，等价于读者与写者只能有一种人在工作。通过互斥信号量解决二者之间的互斥关系。过桥问题通过mutex来实现两个方向上的互斥，mutex设置为1，表示将方向锁定。任意一个方向都有可能有很多人，所以设置count1/2变量来对每个方向上的人进行计数，只有第一个上桥的人才需要对方向上锁，最后一个离开桥的人对方向解锁。类比读者写者问题，只有第一个读者才需要对读写进程进行加锁，只有最后一个读者才对读写进程进行解锁。都是通过count变量来实现。依据双标志先检查法的不足，如果检查和上锁不是一气呵成的，则可能会违法忙则等待，同一时刻有多个进程进入临界区。因此必须设置一个互斥信号量来保证对检查和上锁一气呵成，因此出现了Scount1/2信号量，保证对对应的count变量的检查和上锁是一气呵成的。由于有n个桥墩，每个人只能站一个，因此最多允许一个方向上的N个人申请，所以共享变量Scount=N。此处不再区分到底是哪个方向优先问题，两个方向的优先级是通过哪一个先抢占处理机来决定的，并非人为决定。Semaphoremutex=1,//对方向锁定的互斥信号量scount1=1,//确保方向1对count1的检查和上锁是原子操作scount2=1,//确保方向2对count2的检查和上锁是原子操作scount=N;//一共有多少个桥墩intcount1=0,//1方向上有多少人count2=0;//2方向上有多少人//方向1voiddirect1(inti){wait(scount1);if(count1==0)wait(mutex);count1++;signal(scount1);wait(scount);上桥，过桥，下桥；signal(scount);wait(scount1);count1--;if(count1==0)signal(mutex);signal(scount1);}//方向2voiddirect2(inti){wait(scount2);if(count2==0)wait(mutex);count2++;signal(scount2);wait(scount);上桥，过桥，下桥；signal(scount);wait(scount2);count2--;if(count2==0)signal(mutex);signal(scount2);}//main执行main(){cobegin{direct1(1);…direct1(n);direct2(1);…direct2(m);}}26．有3个进程P1，P2，和P3并发执行，进程P1需使用资源r3和r1，进程P2需使用资源r1和r2，进程P3需使用资源r2和r1。（1）若对资源分配不加限制，会发生什么情况，为什么？（2）为保证进程能执行到结束，应采用怎样的资源分配策略？（1）可能会发生死锁。例如：P1持有r3并等待r1，P2持有r1并等待r2，P3持有r2并等待r1，此时产生循环等待现象。（2）静态分配资源、按序申请资源或采用银行家算法进行资源分配。27．某系统当前有同类资源10个，进程P，Q，R所需资源总数分别为8，4，9。它们向系统申请资源的次序和数量如下图所示。（1）系统采用银行家算法分配资源，请给出系统完成第6次分配后各进程的状态及所占资源量。（2）在以后各次的申请中，哪次的申请要求可先得到满足？次序进程申请量次序进程申请量1R26Q22P47R33Q28P24P29R35R1图8-19题27图（1）初始状态：maxallocationneedavailableP80810Q404R9091:R申请2个，可以满足maxallocationneedavailableP8088Q404R9272:P申请4个，可以满足maxallocationneedavailableP8444Q404R9273:Q申请2个，可以满足maxallocationneedavailableP8442Q422R9274:P申请2个，若分配，会得到以下状态，无法找到