| 失效链接处理 |
|
《多处理器编程艺术》课后答案 PDF 下载
本站整理下载：
相关截图：
主要内容：
10. 互斥是通过每个线程看到的各⾃的view得到关于global的关于critical area的owner的⼀致看法实现的。根据2.8的证明，锁
的实现必须有写的动作，如果第⼀条指令是读，且只依据这⼀条指令是不能区分先后的；如果写了之后没有读，线程不能
得到view，和没写⼀样；如果又写又读，并得到某些顺序则它实际就是个gate。
11. 满⾜互斥。假设不成⽴。假设 CS(A)-->CS(B) => R(A)(turn=A) --> R(B)(turn=B) && W(A)(turn=A)-->W(B)(turn=B) &&
R(A)(turn=A)-->W(B)(turn=B)；否则turn由B改变后不能再变成A。所以有 W(A)(busy=true)-->R(A)(turn=A)-->W(B)(turn=B)--
>R(B)(busy=false) => W(A)(busy=true)->R(B)(busy=false). ⽭盾。
不满⾜⽆饥饿，因为某个线程A执⾏完turn=A之后，等待busy = false的时候，别的线程可能⽆限次的turn=X-->busy==false--
>busy=true。
不满⾜⽆死锁。可能有 W(A)(turn=A)-->W(B)(turn=B)-->R(A)(busy=false)-->W(A)(busy=true)-->R(B)(busy=false). A waits
turn==A, B waits busy == false.
12. 假设线程A在第k层停住，只要有>2(除A外)个线程进⼊第k层，到得早的线程必然有 victim != me。
13. ⽤归纳法。假设k层的这种锁满⾜互斥，当树⾼增加到k+1层时，因为Peterson锁满⾜互斥，使得k+1层上的线程只能在
每个k层节点上推举出⼀个线程，结果是构成⼀个k层的树，根据假设它满⾜互斥。同理它也⽆饥饿。
满⾜⽆死锁，因为获得锁的过程是⼆叉树从叶⼦节点到跟节点的⽅向，整个图不能找出任⼀个有向环，不满⾜死锁的条件。
上界为n。⾸先上界>=n(包括⾃⼰这⼀次)，否则不满⾜互斥。假设h=k(根节点h=0)时上界为n=(2^k)，当叶节点为2n，h=k+1
时，某个叶节点A可能兄弟节点赢，兄弟节点在h=k层上等2^k次加解锁；根据Peterson锁的性质，下次兄弟节点参与竞争是
必然是A赢，则A在h=k层上再等待2^k次；即2^(k+1)次，必然得到锁。或者这样考虑，如果⼀个线程A抢锁成功，则它下⼀
次再参与的时候必然⽐其它在它第⼆次抢锁开始之前参与的线程B（包括第⼀次抢锁）要后得到锁。因为叶结点为n，所以
最多有n个线程在它之前。同时，放锁之后下⼀次抢锁必然输给A。所以界是n。
14. 将filter锁减少l层。根据section 2.4的证明第l层的过程，得知第l层满⾜l-Exclusion和l-Starvation-Freedom的性质。
15. 不满⾜互斥。⽐如2个线程以这个顺序执⾏lock：W(A)(x=A)-->W(B)(x=B)-->R(A)(y==-1)-->R(B)(y==-1)-->W(A)(y=A)--
>W(B)(y=B)-->R(B)(x==B)-->CS(B)-->R(A)(x!=A)-->（A）(lock.lock())-->CS(A)。因为B进⼊CS时没有经过lock => lock不知道
还有⼀个竞争者 => lock同意A进⼊CS。⽽且因为B没有经过lock，它在执⾏unlock-->lock.unlock()的时候也可能会出问题。
16. 因为W(A)(last = A) -->R(A)(goRight == false)-->W(A)(goRIght = true) --> R(A)(last == A); W(B)(last = B) -->R(B)(goRight
== false)-->W(B)(goRIght = true) --> R(B)(last == B); 假设A先，有 W(A)(last = A) --> R(A)(last == A)-->W(B)(last = B) -->
R(B)(last == B)，也有 W(A)(goRight = true) --> R(A)(last == A) --> W(B)(last = B)--> R(B)(goRight == false)。⽭盾。这个过程
类似于11题。所以最多只有⼀个线程获得STOP。
因为任意的线程X都有W(X)(last = X)-->R(X)(last != X)，即对所有的线程X都存在Y使得W(X)(last = X) --> W(Y)(last = Y)。
因为在W(X)(last = X)这个点上可以将所有线程按照时间排成完全有序的序列，则随后⼀个线程找不到⽐它后来的线程，所
以最多只有n-1个得到DOWN。
因为有R(X)(goRIght == true) --> RIGHT(X)，⽽且goRight初始值为false，必然有线程Y: R(Y)(goRight == false）--> W(Y)
(goRight = true)。即R(Y)(goRight == false) --> W(Y)(goRIght = true) --> STOP(Y) || DOWN(Y)。所以最多只有⼀个n-1个线程
得到RIGHT。
17. 因为每个Bouncer对象都最多有n-1个线程得到RIGHT，最多n-1个线程得到DOWN，即数组中任意Bouncer对象的右边对
象和下⾯的对象都要⽐该Bouncer对象少⾄少⼀个竞争者。所以线程沿着Bouncer的计算结果移动时，或者得到STOP，或者
是剩下的最后⼀个参与者，也得到STOP。所以必然停在某⼀个Bouncer。
因为每⼀步最多有n-1个遗留的线程，但不能确定是往DOWN还是RIGHT，所以得到的布局是如图2-18所⽰n * n的三⾓形。
18. 如图所⽰：
• A, B在A0上，C在B0上。C观察后准备移到A2，以决定A，B。然后C休眠。
• B移到A2上
• A移到A1上
• A，B在圈A上转，直到A在A1，B在A0。C醒来，转移到A2。A上形成了⼀个circle。
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
