第五章并发性：互斥和同步复习题：5.1列出与并发相关的四种设计问题答：进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题5.2列出并发的三种上下文答：多个应用程序，结构化应用程序，操作系统结构5.3执行并发进程的最基本要求是什么？答：加强互斥的能力5.4列出进程间的三种互相知道的程度，并简单地给出各自的定义答：进程间互相不知道对方：这是一些独立的进程，他们不会一起工作进程间间接知道对方：这些进程并不需要知道对方的进程ID号，但他们共享访问某些对彖，如一个I/O缓冲区进程间直接知道对方：这些进程可以通过进程ID号互相通信，用于合作完成某些活动5.5竞争进程和合作进程进程间有什么区别答：竞争进程需要同时访问相同的资源，像磁盘，文件或打印机合作进程要么共享访问一个共有的资源，像一个内存访问区，要么就与其他进程相互通信，在一些应用程序或活动上进行合作5.6列出与竞争进程相关的三种控制问题，并简单地给出各自的定义答：互斥：竞争进程仅可以访问一个临界资源（一次仅有一个进程可以访问临界资源），并发机制必须满足一次只有一个进程可以访问临界资源这个规则死锁：如果竞争进程需要唯一的访问多于一个资源，并且当一个进程控制着一个进程，且在等待另一个进程，死锁可能发生。
饥饿：一组进程的一个可能会无限期地拒绝进入到一个需要资源，因为其他成员组成垄断这个资源5.7列出对互斥的要求答：1•必须强制实施互斥：在具有关于相同资源或共享对彖的临界区的所有进程中，一次只允许一个进程进入临界区2.—个在临界区停止的进程必须不干涉其他进程3•绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或饥饿4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入5•对相关进程的速度和处理器的数目没有任何要求和限制6.—个进程驻留在临界区中的时间是有限的5.8在信号量上可以执行什么操作答：1.一个信号量可以初始化成非负数2.wait操作使信号量减1,如果值为负数，那么进程执行wait就会受阻3s®ud操作使信号量增加1,如果小于或等于0,则被wait操作阻塞的进程被解除阻塞5.9.二元信号量与一般信号量有什么区别答：二元信号量只能取0或1,而一般信号量可以取任何整数5.10强信号量与弱信号量有什么区别答：强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出弱信号量没有此规则5.11.什么是管程答：管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。
5.12对于消息，有阻塞和无阻塞有什么区别？答：5.13.通常与读者■写者问题相关联的有哪些条件？答：1.任意多的读进程可以同时读这个文件，2.—次只有一个写进程可以往文件中写，3.如果一个写进程正在往文件中写时，则禁止任何读进程读文件习题：5.1答：b.协同程序read读卡片，将字符赋给一个只有一个字大小的缓冲区is然后在赋给squash协同程协同程序Read在每副卡片图像的后面插入一个额外的空白协同程序squash不需要知道任何关于输入的八十个字符的结构，它简单的查找成对出现的星号，然后将更改够的字符串经由只有一个字符人小的缓冲sp,传递给协同程序pnnt最后协同程序print简单的接受到来的字符串，并将他们打印在包含125个字符的行中5.2.考虑一个并发程序，它有两个进程p和q,定义如下AJB.C.D和E是任意的原子语句假设住程序执行两个进程的parbegmVoidp()voidq(){A;{D;B；E;C；}}答:ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE;5.3考虑下面的程序constiiitn=50;iiittally;voidtotalQ{iiitcount;fbr(count=l;count<=n;count++){tally++；}}voidmain(){tally=0;paibegm(total(),totalQ;wiite(tally);}答：a.随意一看glly值的范闱好像是落在［50,100］这个区间里，因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑卜•面由这两进程按交替顺序执行载入,增加，存储的情况，同时变更这个共享变量的取值：1•进程A载入tally值glly值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).2. 进程B载入tally值(仍然是0),然后运行完成49次增加操作，在它已经将49这个值存储给共享变量tally后,失去处理器控制权.3. 进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个taUy值),此时被迫立即放弃处理器.4. 进程B重新开始，将1(当前的tally值)载入到它自己的寄存器中，但此时被迫放弃处理器(注意这是B的最后一次载入).5. 进程A被重新安排开始，但这次没有被中断，直到运行完成它剩余的49次载入，增加和存储操作，结果是此时tally值已经是50.6. 进程E在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果.一些认为会出现低于2这个值的结呆，这种情况不会出现.这样tally值的正确范围是[2,100].b.对一般有N个进程的情况下,tally值的最终范閑是[2,N*50],因为对其他所有进程来说，从最初开始运行到在第五步完成•但最后都被进程B破坏掉它们的最终结果.5.4•忙等待是否总是比阻塞等待效率低(根据处理器的使用时间)？请解释。
答:就一般情况来说是对的，因为忙等待消耗无用的指令周期•然而，有一种特殊情况，当进程执行到程序的某一点处，在此处要等待直到条件满足，而正好条件已满足，此时忙等待会立即有结果，然而阻塞等待会消耗操作系统资源在换出与换入进程上.5.5考虑下面的程序booleanblocked[2];iiitnnn;voidP(intid){Whih(true){While(tuin!=id);{Whil亡(block亡d[1-!id]/*donothing*/;Turn=id;}}VoidmainQ{Blocked[0]=false;Blocked[l]=false;Turn=0;Parbegin(P(0),P(l));}这是【HYNIA66】中提出的解决互斥问题的一种方法请举出证明该方法不正确的一个反例答：考虑这种情况:此时nun=0,进程P⑴使布尔变屋blocked[l]的值为在这时发现布尔变量blocked[0]的值为false,然后P(0)会将tme值赋予blocked[0]，此时turn=0,P(0)进入临界区,P⑴在将1赋值给tum后，也进入了临界区.5.6解决互斥的另一种软件方法是lampoil的面包店(bakery)算法，之所以起这个名字，是因为它的思想来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如下：Booleanchoosing[n];liltnumber[n];While(true)Choosmg[i]=tine;Number[i]=1+getniax(number[]ji)；A. Choosmg[i]=false;For(mtj=Oj
符号(a,b)<(c,d)被定义成(a,c)或(a=c且b
设计一个使用testset指令的算法，且保证任何一个等待进入临界区的进程在ml个tum内进入，n是要求访问临界区的进程数，tum是指一个进程离开临界区而另一个进程获准访问这个一个事件答：以下的程序由[SILB98]提供：varj:O..11-I;key:boolean;repeatwaitiiig[i]:=tme;kev:=tme;wliilewaitiiig[i]andkeydokey:=testset(lock);waitiiig[i]:=false;< criticalsection>j:=i+1modn;wliile(jHi)and(notwaitingfj])doj:=j+1modn;ifj=ithenlock:=falseelsewaiting:=false;< remaindersection>Until这个算法用最普通的数据结构：varwaitmg:array[0..n-1]ofbooleanLock：boolean这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting的循环队列5.8考虑下面关于信号量的定义：VoidsemWait⑸{If(s.count>0){s.count—；}Else{Placethisprocessins.queue;Block;}}VoidsemSign。