Turn=0;
Parbegin(P(0),P(1)); }
这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。
答：考虑这种情况:此时turn=0,进程P(1)使布尔变量blocked[1]的值为true,在这时发现布尔变量blocked[0]的值为false,然后P(0)会将true值赋予blocked[0]
,此时turn=0,P(0)进入临界区,P(1)在将1赋值给turn后,也进入了临界区.
5.6解决互斥的另一种软件方法是lamport的面包店（bakery）算法，之所以起这个名字，是因为它的思想来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如下：
Boolean choosing[n]; Int number[n]; While (true)
{ Choosing[i]=true;
Number[i]=1+getmax(number[],n)； Choosing[i]=false; For(int j=0;j While (choosing[j]) {} While ((number[j]!=0)&&(number[j],j)<(number[i],i) {} } /*critical section*/ Number[i]=0; /*remainder*/; } 数组choosing和number分别被初始化成false和0，每个数组的第i个元素可以由进程i读或写，但其他进程只能读。符号（a，b）<（c，d）被定义成 （a，c）或（a=c且b 答：a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加1得到的.有最小票号的进程有最高的优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时,重新设置它的票号为0. b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以避免. c.为了说明互斥,我们首先需要证明下面的定理:如果Pi在它的临界区,Pk已经计算出来它的number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) < ( number[k], k ).为证明定理,定义下面一些时间量: Tw1:Pi最后一次读choosing[k], 当 j=k,在它的第一次等待时,因此我们在Tw1处有choosing[k] = false. Tw2:Pi开始它的最后执行, 当j=k,在它的第二次while循环时,因此我们有Tw1 < Tw2. 11 Tk1:Pk在开始repeat循环时;Tk2:Pk完成number[k]的计算; Tk3: Pk设置choosing[k]为false时.我们有Tk1 因为在Tw1处,choosing[k]=false,我们要么有Tw1 5.7当按图5.2的形式使用一个专门机器指令提供互斥时，对进程在允许访问临界区之前必须等待多久没有控制。设计一个使用testset指令的算法，且保证任何一个等待进入临界区的进程在n-1个turn内进入，n是要求访问临界区的进程数，turn是指一个进程离开临界区而另一个进程获准访问这个一个事件。 答：以下的程序由[SILB98]提供： var j: 0..n-1; key: boolean; repeat waiting[i] := true; key := true; while waiting[i] and key do key := testset(lock); waiting[i] := false; < critical section > j := i + 1 mod n; while (j ≠ i) and (not waiting[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remainder section > Until 这个算法用最普通的数据结构：var waiting: array [0..n – 1] of boolean Lock：boolean 这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting的循环队列 5.8考虑下面关于信号量的定义： Void semWait(s) { If (s.count>0) { s.count--; } Else { Place this process in s.queue; Block; } } Void semSignal(s) { If (there is at liast one process blocked on semaphore) { 12 Remove a process P from s.queue; Place process P on ready list; } Else s.count++; } 比较这个定义和图5.3中的定义，注意有这样的一个区别：在前面的定义中，信号量永远不会取负值。当在程序中分别使用这两种定义时，其效果有什么不同？也就是说，是否可以在不改变程序意义的前提下，用一个定义代替另一个？ 答：这两个定义是等价的，在图5.3的定义中，当信号量的值为负值时，它的值代表了有多少个进程在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。 5.9可以用二元信号量实现一般信号量。我们使用semWaitB操作和semSignalB操作以及两个二元信号量delay和mutex。考虑下面的代码 Void semWait(semaphor s) { semWaitB(mutex); s--; if (s<0) { semSignalB(mutex); semWaitB(delay); } Else Semsignalb(mutex) } Void semSignal(semaphore s); { semWaitB(mutex); s++; if(s<=0) semSignalB(delay); semSignalB(mutex); } 最初。S被设置成期待的信号量值，每个semwait操作将信号量减1，每个semsignal操作将信号量加1.二元信号量mutex被初始化成1，确保在更新在更新s时保证互斥，二元信号量delay被初始化成0，用于挂起进程， 上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在s初始化为0时调用semwait（s）,当第一个刚刚执行了semsignalb（mutex）但还没有执行semwaitb（delay），第二个调用semwait（s）并到达同一点。现在需要做的就是移动程序的一行. 答：假设两个进程，每个都在s被初始化成0时调用semWait（s），当第一个刚执行了semSignalB（mutex）但还没有执行semWaitB（delay）时，第二个调用semWait（s）并到达同一点。因为s=-2 mutex没有锁定，假如有另外两个进程同时成功的调用semSignal（s），他们接着就会调用semsignalb（delay），但是第二个semsignalb没有被定义。 解决方法就是移动semWait程序中end前的else一行到semSignal程序中最后一行之前。因此semWait中的最后一个semSignalB(mutex)变成无条件的，semSignal中的semSignalb(mutex)变成了有条件的。 13 5.10 1978年，dijkstra提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于数目未知但有限的进程且可以避免饥饿。1979年，j.m.morris提出 了一个使用三个弱信号量的算法，反驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在semwait（s）操作上等待，另一个进程正在执行semsignal（s），则信号量s的值未被修改，一个等待进程被解除阻塞，并且这并不取决于semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。因此，信号量A和B被初始化为1，而信号量M和计数器NA，NM被初始化成0.一个试图进入临界区的进程必须通过两个分别由信号量A和M表示路障，计数器NA和NM分别含有准备通过路障A以及通过路障A但还没有通过路障M的进程数。在协议的第二部分，在M上阻塞的NM个进程将使用类似于第一部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: semaphore; na, nm: 0 ? +∞; a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na – 1; if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) endif; semWait(m); nm ← nm – 1; if nm = 0 then semSignal(a) else semSignal(m) endif; 5.11下面的问题曾被用于一个测试中： 侏罗纪公园有一个恐龙博物馆和一个公园，有m个旅客和n辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客进程和n个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p和v分别对应于semwait和semsignal。 Resource Jurassic_Park() Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers) Do true->nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od End passenger Process car(j:=1 to num_cars) Do true->V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released) Od End car End Jurassic_Park 答：这段代码有一个重要问题.在process car中的代码 V(passenger_released)能够解除下面一种旅 14 客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客. 5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。 答： 1 2 3 4 5 6 7 8 9 10 Producer SemWaitB(S) n++ If(n==1) (semSignalB(delay)) semSignalB(s) semWaitB(s) Consumer semWaitB(delay) semWaitB(s) n-- If(n==0) (semWaitB(delay)) s 1 0 0 0 1 1 0 n 0 0 1 1 1 1 1 0 delay 0 0 0 1 1 0 0 0 生产者和消费者都被阻塞。 5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下： 生产者：append;semSignal;produce;···append;semSignal 消费者：consume;take;semWait;consume;take;semWait; 生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。 构造一个新程序使得能在这种情况下更加有效。 提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图5.10中的局部变量m。 答： 这个程序来自于[BEN82] program producerconsumer; var n: integer; s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0); procedure producer; begin repeat produce; semWaitB(s); append; n := n + 1; if n=0 then semSignalB(delay); semSignalB(s) forever end; procedure consumer; 15 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《操作系统精髓与设计原理·第五版》习题答案(3)在线全文阅读。
相关推荐：