发布时间 : 星期五 文章操作系统精髓与设计原理-第5章 并发性 - 互斥和同步更新完毕开始阅读ab2237da50e2524de5187e38
前必须等待多久没有控制。设计一个使用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) {
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)变成了有条件的。
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)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客.
5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。
答： Producer Consumer s n delay 1 1 0 0 2 SemWaitB(S) 0 0 0 3 n++ 0 1 0 4 If(n==1) 0 1 1 (semSignalB(delay)) 5 semSignalB(s) 1 1 1 6 semWaitB(delay) 1 1 0 7 semWaitB(s) 0 1 0 8 n-- 0 0 9 semWaitB(s) If(n==0) (semWaitB(delay)) 10 生产者和消费者都被阻塞。 5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：
生产者：append;semSignal;produce;···append;semSignal 消费者：consume;take;semWait;consume;take;semWait;
生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。
构造一个新程序使得能在这种情况下更加有效。