《多处理器编程的艺术》习题参考答案
（1）只保证互斥
void philosopher(int i) /*i：哲学家编号，从0 到4*/
{
while (TRUE)
{
think(); /*哲学家正在思考*/
take_fork(i); /*取左侧的筷子*/
take_fork((i+1) % N); /*取右侧筷子；%为取模运算*/
eat(); /*吃饭*/
put_fork(i); /*把左侧筷子放回桌子*/
put_fork((i+1) % N); /*把右侧筷子放回桌子*/
}
}
void take_fork(int i)
{
P(mutex);
Fork_available_state[i] = false;
V(mutex);
}
void put_forks(int i)
{
P(mutex);
Fork_available_state[i] = true;
V(mutex);
}
（2）互斥、无死锁、高并行，但不保证无饥饿
#define N /* 哲学家人数*/
#define LEFT (i-1+N)%N /* i的左邻号码 */
#define RIGHT (i+1)%N /* i的右邻号码 */
typedef enum { THINKING, HUNGRY, EATING } phil_state; /*哲学家状态*/
monitor dp /*管程*/
{
phil_state state[N];
semaphore mutex =1;
semaphore s[N]; /*每个哲学家一个信号量，初始值为0*/
void test(int i)
{
if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING )
{
state[i] = EATING;
V(s[i]);
}
}
void get_forks(int i)
{
P(mutex);
state[i] = HUNGRY;
test(i); /*试图得到两支筷子*/
V(mutex);
P(s[i]); /*得不到筷子则阻塞*/
}
void put_forks(int i)
{
P(mutex);
state[i]= THINKING;
test(LEFT(i)); /*看左邻是否进餐*/
test(RIGHT(i)); /*看右邻是否进餐*/
V(mutex);
}
}
哲学家进程如下：
void philosopher(int process)
{
while(true)
{
think();
get_forks(process);
eat();
put_forks(process);
}
}
（3）使用全局Filter锁。保证互斥、无死锁、无饥饿，但是每次只有一个哲学家就餐，并行度低
public class Philosopher {
public static final int N = 5;
Lock mutex;
public Philosopher() {
mutex = new Filter(N);
}
public void DiningPhilosophers(int process, Random random)throws InterruptedException {
while (true) {
System.out.println("philosopher " + process + " is hungry");
Thread.sleep(Math.abs(random.nextLong() % 1000));
mutex.lock();
System.out.println("philosopher " + process + " is eating");
Thread.sleep(Math.abs(random.nextLong() % 1000));
System.out.println("philosopher " + process + " is thinking");
mutex.unlock();
}
}
}
（4）Chandy/Misra解法。互斥、无死锁、无饥饿、高并行 1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。
与资源分级解法不同的是，这里编号可以是任意的。
[初始化]对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
[1]当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
[2]当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
[3]当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。
这个解法允许很大的并行性，适用于任意大的问题
（1）按到达的顺序为赞助人服务。 满足活性，一定会出现的“好事”：先到先得到服务。
（2）升上去的东西都必须降下来。 满足安全性，不会出现的“坏事”：不存在不降下来的情况。
（3）如果有两个或多个进程正在等待进入自己的临界区，则至少有一个会成功。 满足安全性，不会出现的“坏事”：不会存在几个进行一起发出请求，却都不允许的情况。
（4）如果发生一个中断，则在一秒内要输出一条消息。 满足活性：发生中断则会在一秒内输出消息，一定会发生的“好事”。
（5）如果发生一个中断，则要输出一条消息。 满足安全性：发生中断则输出消息，不发生中断就不会输出消息，“不好的事情”不会发生。
（6）生活费决不下降。 满足安全性，不会出现的“坏事”：生活费下降。
（7）有两件事是肯定的：死亡和税。 满足安全性：不死和不交税这种“坏事”不会发生。
（8）你总是能够分辨一个哈佛人。 满足安全性，一定不会出现的“坏事”：没有可以分辨一个哈佛人。
如Bob看不到Alice窗台上的啤酒瓶状态，可采用以下的协议：
[初始化]Bob在Alice的窗台上摆放一个啤酒瓶，并用绳子将其绑住拉入自己房间，同时，Alice也在Bob的窗台上摆放一个啤酒瓶，并用绳子将其绑住拉入自己房间。Bob要将食物放到院子中时，拉动绳子将Alice窗台上的啤酒瓶打翻。
当Alice要把宠物放入院子时，她的行为步骤如下： [1]等到自己窗台上啤酒瓶被打翻。 [2]将宠物放出去。 [3]当宠物返回屋子后，检查食物是否被吃完。如果没吃完，不进行任何行为；如果吃完了，则将自己窗台上的啤酒瓶摆正，并拉动连着Bob窗台上啤酒瓶的绳子，将其啤酒瓶打翻。
当Bob要将食物放入院中时，他的行为步骤如下： [1]等到自己窗台上的啤酒瓶被打翻。 [2]将食物放到院子中。 [3]将自己窗台的啤酒瓶摆正，并拉动绳子，将Alice窗台上的啤酒瓶打翻。
采用这种协议，可在双方都看不到对方窗台上啤酒瓶的状态时，只通过观察自己窗台上啤酒瓶的状态就可确认是否可以进入院子，当自己窗台上的啤酒瓶状态为打翻时，可以继续自己的动作，当状态为摆正时，则不能进入院子中。
简版：
（1）将一名囚犯作为计数者，负责将“开”的开关置为“关”，计数+1.其余p-1个人只能将为“关”的开关置为“开”一次。当计数者计数为p-1时，宣布获胜。
（2）将一名囚犯作为计数者，负责将“开”的开关置为“关”，计数+1.其余p-1个人只能将为“关”的开关置为“开”两次。当计数者计数为2p-2时，宣布获胜。
详细:
（1）在开关的初始状态为关的情况下，成功取胜的策略： 共同协商在P个人中选择其中的一个人A作为宣布“我们所有的人都已经至少到过这个开关房间一次了。”
A进入房间的行为： [1]如A第一次进入开关房间的时候，将灯打开，并计数N=1。 [2]如A并不是第一次进入开关房间，若灯的状态为开，则计数N不变，若灯的状态为关，则计数N=N+1，此时若N=P，则A可以宣布所有人均已到过开关房间，若N<P，则将灯的状态置为开。
除A外其他任意人X进入房间的行为： [1]如X进入开关房间时灯的状态为关，则不拨动灯的开关，即不改变灯的状态； [2]如X进入开关房间时灯的状态为开，若X从未拨动灯的状态，则拨动灯的开关，即将灯的状态变为关，若X曾改变过灯的状态，则不再拨动灯的开关，即不改变灯的状态。
最终当A宣布所有人均进入过开关房间时，即可确认所有人均进入过该房间，可以取胜。
（2）在开关的初始状态未知的情况下，成功取胜的策略： 共同协商在P个人中选择其中的一个人A作为宣布“我们所有的人都已经至少到过这个开关房间一次了。”
A进入房间的行为： [1]如A第一次进入开关房间，计数N=2。 [2]当A进入房间时，若灯的状态为开，则计数N不变，若灯的状态为关，则计数N=N+1，此时若N=2P，则A可以宣布所有人均已到过开关房间，若N<2P，则将灯的状态置为开。
除A外其他任意人X进入房间的行为： [1]如X进入开关房间时灯的状态为关，则不拨动灯的开关，即不改变灯的状态； [2]如X进入开关房间时灯的状态为开，若X从未拨动过开关或只拨动过一次开关，则拨动灯的开关，即将灯的状态变为关，若X已经拨动过两次灯的开关，则不再拨动灯的开关，即不改变灯的状态。
最终当A宣布所有人均进入过开关房间时，即可确认所有人均进入过该房间，可以取胜。
简版：
将蓝色记为0，红色记为1。因为最后一个人能看到前面p-1个人帽子的颜色，处于倒数第m的人肯定知道： （1）前面（p-m）个人的帽子颜色 （2）后面（m-1）个人的回答
策略:最后一个人说出前面各帽子异或后的结果，他有50%的概率说对自己的颜色。处于倒数第m的人根据信息1和2，将前面的帽子颜色异或，再与上（m-1）个人回答的结果异或，就是自己的帽子颜色。
详细： 提前进行约定，在猜测自己帽子颜色时每个人的行为： （1）如站在队伍的最后一个，通过看前面所有人的帽子，给出提示，当在他前面的所有人的帽子中红色帽子的总数为奇数，则说自己帽子的颜色为红色，否则说自己帽子的颜色为蓝色。 （2）如并非站在队尾，记住队尾的人所说的帽子的颜色，如为红色，则记住红色帽子状态为奇数，否则，为偶数，在队尾的人到自己之间，如听到红色，则将红色帽子的状态改变，即奇变偶，偶变奇，轮到自己时，数前面所有的红色帽子的总数，如奇偶状态和自己记住的状态一致，则说自己帽子的颜色为蓝色，如奇偶状态不同，则说自己帽子的颜色为红色。
（1）设程序总运行时间为1，则可并行部分执行时间为0.6 总加速比S=1/(1-p+p/n) =1/(0.4+0.6/n) 则总加速比的上限为2.5 （2）无解 （3）设M占的比例为x，解得x=3/(n-1)
根据Amdahl定律：S=1/(1-p+p/n) （1） 当n=2时，S2=1/(1-p+p/2)，解得 p=2(1-1/S2) 带入（1）可得 在n个处理器上运行时程序的加速比Sn=n/(2 - 2/S2 + 2n/S2 - n)
单处理器每秒执行5亿万条指令，多处理机器中每个处理器每秒可执行1亿万条指令，并行时间若达到100%，则处理5亿万条指令需要0.5秒，加速比S=2。但是实际上并行时间是无法达到100%。
设程序中串行时间为p，S=1/(1-p+p/10) =2，解出p=5/9
（1）若多处理器机器中串行时间达到总时间的，则购买两种机器都行 （2）若多处理器机器中串行时间小于总时间的，则购买多处理器机器 （3）若多处理器机器中串行时间大于总时间的，则购买单处理器机器
存在定义Peterson算法门廊的方法，可以使得对于某个值r，该算法能够支持r-有界等待。
Peterson算法是用于实现两个并发线程同步执行的锁算法，算法是先来先服务的，定义
class Peterson implements Lock {
private boolean[] flag = new boolean[2];
private int victim;
public void lock() {
int i = ThreadID.get();
int j = 1-i;
flag[i] = true;
victim = i;
//之前的为门廊区
while (flag[j] && victim == i) {};
// 等待区
}
public void unlock() {
int i = ThreadID.get();
flag[i] = false;
}
门廊区的执行区间DA 由有限个操作步组成，如果线程A门廊区的结束在线程B门廊区的开始之前完成，那么线程A必定不会被线程B赶超，这样就解决了线程进入临界区的先后问题。
如果对不同的单元操作（读或写），谁也不知道谁先谁后；
如果对相同的单元进行同样的操作，谁也不知道谁先谁后；
如果对相同的单元进行不同的操作，只有一个知道自己的先后，另一个不知谁先谁后。
（1）满足互斥。
一旦有某个线程运行完L10，busy=true，其他线程将不能再运行到L10，运行完L10的线程可以为无限个。
假设线程A,B是在临界区的两个线程，则它们都经过了turn！=me的判断，且判断结果均为false。
A线程判断时turn==A，B线程判断时turn==B，假定A线程的判断在B线程之前，由于turn==A，A线程通过检验，B没有通过检验而回到L7，此时turn的值要变成B需要B线程运行L8，而busy=true，B线程再也不能运行到L11，则只有一个线程在临界区内，假设不成立。
故该协议满足互斥特性。
（2）死锁
线程A运行到L11的这段时间没有其他线程运行，此时turn=A，busy=true，其他线程此时运行，turn=B，发现busy=true，而在L7-L9之间无限循环。
而线程A检测turn！=A为真，继续从L6运行，至L9，发现busy=true，也在L7-L9之间无限循环。这样，造成了死锁。
（3）既然死锁了，当然也饥饿。
证明过滤锁允许某些线程任意次数地超过其他线程。
证明: 因为过滤锁进入下一层的次序是不一定的，它满足无饥饿但不满足先来先服务的原则。
在X层的线程最多有N-X个，F线程是其中比较特殊的（它运行速度慢），它能向下一层演进，但它不能阻塞同层其他线程的演进。
A是这一层的留守线程。
假设其他线程一个一个完成操作，并再次进入X层（某些线程被替换了），某个线程代替A线程成为留守线程，则A线程能在F线程前完成操作。
同样的，完成操作的A再次进入X层并再次超越F（留守线程改变了，只要不是A就行）。
故过滤锁允许某些线程（A）任意次数地超过其他线程（F等）。
（1）互斥
证明：因为Peterson锁具有互斥性，从叶子节点开始，每向上一层可以考虑为两个叶子节点争夺的临界区间。
假设叶子节点有n个线程同时发起请求，则有n/2个线程获得peterson锁进入上一层，即临界区间。
以此类推，每向上一层均去掉1/2的线程。
在这期间，每一次选择均使用Peterson锁，均具有互斥性，直至达到根节点，在两个线程中选择其一，根据Peterson所得互斥性也只有一个线程可以进入最终的临界区间。
所以，树—锁请求满足互斥性。
（2）无饥饿
证明：假设不成立，则存在线程A一直在执行lock()方法，那么它必定在执行while语句，等待有相同父节点的兄弟节点B释放临界资源。
此时B若可以进入最终的临界区间，在访问过后就会释放锁，A可以获得锁；若无法进入最终临界区间，则也在等待上一层中的兄弟节点释放资源，层层递推，直至争夺根节点的两个线程。
由于最终的两个线程也遵循Peterson锁，而Peterson锁满足无饥饿。所以，最终有一个线程可以无需等待其他线程访问临界区间，最终释放锁，不会产生饥饿，
所以，整个树—锁请求满足无饥饿。
（3）无死锁
证明： 因为树—锁请求满足无饥饿，所以满足无死锁。
存在上界，2*（N-1）。
提示：原来的过滤锁是1-互斥算法
class PFilter implement Lock{
int[] level;
int[] victim;
public PFilter(int n){
level=new int[n-ρ+1];
victim=new int [n-ρ+1];
for(int i=0;i< n-ρ+1;i++){
level[i]=0;
}
}
public void lock(){
int me=ThreadID.get();
for(int i=1;i< n-ρ+1;i++){
level[me]=i;
victim[i]=me;
while((ヨk!=me)(level[k]>=i&&victim[i]==me)) {};
}
}
public void unlock(){
int me=ThreadID.get();
level[me]=0;
}
}
（1）不满足互斥性
证明：假设有线程A、B同时调用FastPath锁，最终x=A，A、B同时进行判断while（y！ =-1），此时若临界区间并无线程，y=-1，继续执行。因为x=A，最终结果为A通过FastPath()方法获得锁，而B调用lock.lock（）方法进入slowpath部分。
因为基本的lock部分没有接口显示是否有进程通过FastPath方法获得锁，所以，线程B也可以获得锁，此时A、B两线程均可进入临界区间，不满足互斥性。
（2）满足无饥饿性
证明：当多线程同时调用FastPath锁，如有线程可以通过FastPath获得锁，则已有一个线程可以获得锁，如无线程可以通过FastPath获得锁，则进入基本的lock锁部分。
因为lock锁具有无饥饿性，也至少有一个线程可以获得锁，综上所述，调用FastPath()方法的多个线程可以获得锁，满足无饥饿性。
（3）在无争用的情况下能在常数步内获得锁
证明：当临界区间没有被线程访问时，且只有一个线程调用FastPath()方法时，y=-1且x的值一直为该线程的ID，无需进入基本的lock类，也无需等待，可以直接获得锁，该方法内不存在循环，故可以在常数步内获得锁。
（1）因为初始时，goright=false，一定有某个线程运行到L13，指定第一个运行完L13的线程为A。此时，goRight=true，这之后，运行L11的线程最多为N-1。
（2）设运行完L13的线程数为x，最多有N个线程运行到L13，（1<=x<=N）。
若线程B在x中，则B运行L14之后得到STOP，此时得到DOWN的线程有x-1个，（N-x）个线程得到RIGHT。若线程B不在x中，则无线程得到STOP，得到DOWN的线程有x个，（N-x）个线程得到RIGHT。
综上所述：最多只有一个线程获得STOP，最多只有N-1个线程获得DOWN，最多只有N-1个线程获得RIGHT。
所有线程获得的标识符只有STOP,DOWN,RIGHT三种，而得到STOP的线程最多只有一个，指定得到STOP的线程的id为0，得到RIGHT和DOWN的线程都会前进一步，故没有任何两个线程的id相同。
Bouncer对象个数 N(N+1)/2
证明：初始时，A12->B10->C21,AB同时更新，则C21->(A22,B22)，此时，C更新，变成C20。
我们有C21->(A22,B22)->C20->C21。C的最新的label比老的label还要老，反例。
根据提示，我们可以这样标号：(n,<n-1,n-2,...,0>) ，其中n表示标号，取值为0到n-1，后面,<n-1,n-2,...,0>表示二进制比特位表示，各位相应为1或0。 定义大小如下： A=(a,<an-1,an-2,...,a0>) B=(b,<bn-1,bn-2,...,b0>) 当a=b时，<n-1,n-2,...,0>表示的二进制数大 ，谁就大。 当a<b时，若<n-1,n-2,...,0>相应位上Ab=Ba ，则A>B。 当a<b时，若<n-1,n-2,...,0>相应位上Ab！=Ba ，则A<B。
略。
证明：假设结论不成立，即系统中每个对象都满足静态一致性，而整个系统不满足静态一致性。
因为每个对象都满足静态一致性，所以在某一时刻，系统中存在的每一个对象均变为静态的，即是说此时这些对象到此刻为止的执行等价于目前已完成的所有方法调用的某种顺序执行的，每个对象都不再存在未决的方法调用，故此时系统中都不存在未决的方法调用，与假设矛盾，故静态一致性是复合的。
（1）如果两个寄存器是静态一致的，则存储器对象也是静态一致的。
证明： 因为静态一致性是可复合的，所以能够用两个满足静态一致性的寄存器组成一个存储器，且保证该存储器也满足静态一致性。
（2）如果该存储器是静态一致的，每个寄存器不一定是静态一致的。
证明 ：假设存储器C由寄存器A和寄存器B组成，且A满足静态一致性而B不满足静态一致性，在某时C满足静态一致性，此时只要保证只有A中的数据被方法调用，而B中的数据没有改变，即可保证C满足静态一致性。
（1）某执行是静态一致的但不是顺序一致的
A r.write(1) r.read(2) r.read(1)
B r.write(2)
所有调用都不是未决的，写入1、2是并发的，先读出2，说明先写入的1，然后再写入2，且覆盖原来1的值，此时不能再读出1，与执行情况矛盾，所以该执行是静态一致的却不是顺序一致的。
（2）某执行是顺序一致的但不是静态一致的：
A q.enq(1) q.dep(2)
B q.enq(2)
1先于2入队，但先读出的是2，说明2在1的前面，所以该执行不是静态一致的，由于这些调用按照程序次序是相互无关的，所以该执行与程序次序相一致，所以是顺序一致的。
均是静态一致，顺序一致，可线性化的。
证明：存在可线性化的点。
不相同。
可线性化定义中除去L2，剩下的条件为L1：经历H存在有一个扩展H’及一个合法的顺序经历S且complete（H’）与S等价。
反例，满足L1，但不满足顺序一致。
A r.write(1) r.write(2)
B r.read(2) r.read(1)
证明：H是可线性化的，则存在有一个扩展H’及一个合法的顺序经历S且complete（H’）与S等价（L1），且若在H中方法调用m0先于m1，那么在S中也是这样（L2）。
H|x是对象x的一个子经历，s0是S中去掉其他对象的顺序经历，s0是合法的。则complete（H’|x）与s0等价（L1）。对于H|x中方法调用m0先于m1，H中方法调用m0先于m1，那么在S中也是这样，则在s0中也是这样（L2）。
以下反例不满足可线性化性的L2： 线程1做enq(1)操作，在L10处休眠，线程2做enq(2)操作，在线程1运行L10前完成，线程3进行出队，发现线程1还没写，于是返回null。 现在线程1醒来，运行完L10结束。
1 |---q.enq(1)-----------------------|
2 |--q.enq(2)-|
3 |-q.dep(null)-|
可能存在被0除的情况。
v的类型为volatile，在Java存储器模型中是保证可见性的。读取时原工作区被置为无效，从存储器中直接读取，被写入的值也会被立刻写回存储器。
假设有线程A先执行了writer方法，另一个线程B接着执行了reader方法，因为v的类型为volatile，故此时存储器中v的值立刻被改写为true，且线程B读到的v的值也为true。
因为x的类型为int，在程序中也没有其他限制，故x的读写并不是立即可见的。
因为每个线程具有一个私有的内存工作区，存放着该线程已读/写的域的cache拷贝，所以，虽然对x赋值发生在v之前，但有可能x的值还储存在线程A的私有内存工作区中，还有将x的更新立刻传送到存储器中，存储器的x的值仍为0，此时调用reader方法，则可能出现如下情形：x=0且v=true，此时，发生了被0除的情况。
不等价。
因为对象x执行无限个操作步的线程都要完成无限个方法调用，而如果要保证无锁，则要求一个方法的无限次调用都能够在有限步内完成，与题目矛盾。
等价。
因为对象x在一个无限经历H中有无限个方法调用被完成，如x存在锁，则在x请求锁时可能会发生等待，且如果请求锁不成功，则该调用无法完成，无法实现完成无限个方法调用。
是无等待的，且是有界无等待的，因为每次调用m，均可在有限步内完成，所以是无等待的，而步数的限制为2^i，这个界限依赖于调用的次数i。
（1）线程A、B同时调用enq方法向数组中存放元素，因为enq方法的两个步骤不是原子的，故A、B线程可以都执行了int i=tail.getAndIncrement()而都没有执行items[i].set(x)。假设A比B先执行完L15，线程C调用deq()，在读线程A要写的槽时，发现为null，C继续前进。此时，线程A执行完L16，完成enq()调用。在C读下一个槽之前，线程B在A之后完成enq()调用。最终，线程C读取B写入的值，返回。若可行性化的点在L15，则线程C读取的应该是A的值。故enq()的可线性化点不可能在第15行出现。
（2）同上例，若可线性化的点在L16，则线程C读取的应该是A的值，故enq()的可线性化点不可能在第16行出现。
（3）虽然enq()方法没有单个可线性化点，但是enq()是可线性化的。它的可线性化的点由deq()调用的返回值确定，即L23。
证明：与静态一致性一样，顺序一致性是非阻塞的。阻塞只可能在方法的未决的情况下发生，在并发执行中，对于完全方法的任何一个未决调用，都必定存在一个静态一致的响应，而静态一致是非阻塞的，所以，顺序一致也是非阻塞的。
True。
如果按照图4-6所示的MRSW安全布尔寄存器的构造，只将其中的SRSW安全布尔寄存器数组用一个M-值的SRSW安全寄存器数组替换掉，而不改变对数组的read()和write()方法，即使将原来的每一个布尔寄存器替换为一个大小为M的布尔寄存器数组。在这种情况下若线程的read()调用不与任何的write()调用重叠，那么该read()调用会返回最近一次写入的在区间0-M内的值。对于重叠的方法调用，由于M-值寄存器是安全的，read()调用可以返回任何值。故该构造是一个M-值的MRSW安全寄存器。
True。
如果按照图4-6所示的MRSW安全布尔寄存器的构造，并用SRSW规则布尔寄存器数组替换SRSW安全布尔寄存器数组，可以得知：如果线程的read()调用不与任何write()调用重叠，则返回最近一次写入的值。若调用间有重叠，如旧值与新值一样，因为寄存器是规则的，所以，均返回该值，如旧值与新值不同，则返回旧值或新值。故该构造是一个MRSW规则的布尔寄存器。
False。
如果按照图4-12中原子的MRSW构造，并用SRSW规则寄存器替换SRSW原子寄存器，可以得知：如果线程的read()调用不与任何write()调用重叠，则返回最近一次写入的值。若调用间有重叠，当有几个线程同时读的时候，如对第一个线程的写还没有完成，此时，几个线程均只能通过读这一个待定的值来返回，此时，因为是规则寄存器，所以可能返回新值也可能返回旧值，不满足原子性。
A r.write(1) r.write(2)
B r.read(2) r.read(1)
True。
如果按照图4-6所示的MRSW安全布尔构造，并用M-值SRSW规则寄存器数组替代SRSW安全布尔寄存器数组，可以得知：如果线程的read()调用不与任何write()调用重叠，则返回最近一次写入的值。若调用间有重叠，则read()方法只会返回新值或上一个旧值，因为是单线程写，所以不会返回更远的旧值。
故该构造是一个M-值MRSW规则寄存器。
False。
如果按照图4-7所示的MRSW规则布尔构造，并用一个M-值MRSW安全寄存器替换MRSW安全布尔寄存器，可以得知：如果线程的read()调用不与任何write()调用重叠，则返回最近一次写入的值。若调用间有重叠，则考虑以下两种情况。如果要被写入的新值与旧值相同，那么写者不对寄存器写，可以读到正确的值。如果要被写入的新值与旧值不相同，因为M-值MRSW是安全的，所以返回的值是任意的数字，而不一定是新的或者旧的的值。故该构造产生的不是一个M-值MRSW规则寄存器。
能。
假设A、B两个线程一起申请锁，且此时均已执行了flag[i]=true，即flag[A]=true而同时flag[B]=true，此时，执行writeA(victim=A)，完成，进入while循环，A发现flag[B]=true;若此时读victim与B执行writeB(victim=B)重叠，则A 可能读到victim==A。但是，一旦B写victim完成，A的读与B的写不重叠了，A只能读到victim==B,于是A获得锁。
若write()调用彼此间没有重叠：
（1）这个寄存器是规则的。 当有处理器Pi调用write()方法，且方法未结束，即此时Pi已经将寄存器中的v写为x，且已经传递到Pi+p mod n，此时若有处理器Pm要读寄存器的内容，要通过读取处理器的本地存储器中的拷贝来实现，此时若m大于i且小于等于i+n读到的值为x，否则读到的仍为旧值。如果i+p mod n=i，则此时write()方法已经执行完成，无论哪个处理器进行读，读到的均是已经写入本地存储器中的拷贝x，故寄存器是规则的。
（2）是原子的。 假设处理器Pi调用write()方法，该寄存器是规则的，只需证明条件3。如方法结束了，所有处理器读到的都是新的值。如方法未结束，即此时Pi已经将寄存器中的v写为x，且已经传递到Pi+p mod n，考虑每一个处理器的读实现，如果此时该处理器已经被传递到了，则读到的是新的值，否则为旧值。且读到旧值只可能在读到新值之前，即只要读到新值就不会再读到旧值。
若有多个处理器同时调用write() 这个寄存器不是原子的。假设写入0和1，处理器P4先写入0，处理器P2后写入1，则处理器P3先写入1后写入0，处理器P5先写入0，后写入1，无法确定顺序，故不是原子的。
public int read(){
private boolean[] result=new boolean[N];
for(int i=0;i<N;i++){
if(b[N+i]==b[2*N+i]){
result[i]=b[2*N+i]
}else{
break;
}
}
if(i==N){
return BoolToInt(result);
}
for(int i=0;i<N;i++){
result[i]=b[i];
}
return BoolToInt(result);
}
证明：如果用SRSW规则寄存器代替SRSW安全布尔寄存器组成MRSW寄存器，可以得知：如果一个read()调用不与任何write()调用重叠，则返回最近一次写入的值。若调用有重叠，因为组件寄存器为SRSW规则寄存器，read()调用的结果为刚被写入的新值或旧值。故该寄存器是一个正确的MRSW规则寄存器。
略。
略。
寄存器类别 是否互斥 是否先来先服务
安全寄存器 X Y
规则寄存器 X Y
环绕寄存器 X X
证明：考虑其他n-2个线程处于休假状态：他们都不去决定输入，考虑两个活跃的线程A、b，线程A输入为0，线程B输入为1为初始状态。如果A在B开始之前完成协议，则A决定0，因为A必须决定某个线程的输入，而0是它所看到的唯一输入。对称的，如果B在A开始之前完成协议，那么B决定1，因为它必须决定某个线程的输入，并且1是它所看到的唯一的输入。由此可见，n个线程中只要有两个线程的输入值不同时，初始状态是二价的。
证明：略。
证明： 假设命题不成立，即当处于临界状态时，后继状态只有0-价的或是只有1-价的。因为此时处于临界状态，所以当再有一个线程迁移时，该协议状态才会变成单价的，如后继状态只有0-价的或是1-价的，则该协议已经变成单价的，不满足临界状态的条件，产生矛盾，证明命题成立。
证明：假设当原子寄存器的二进制一致性对于双线程是不可能的，而同时它对于n线程是可能的。因为满足n线程的一致性，所以可以将n个线程进行线性化，确定其顺序，因为n>2，所以至少为3，当已经确定了n-2个线程的顺序以后，此时还余两个线程，因为它对于n线程是满足一致性的，所以最后两个线程也可以成功获得一致性，根据已知，原子寄存器的二进制一致性对于双线程是不可能的，得到矛盾。
证明 ：因为采用原子寄存器的二进制一致性对于n线程是不可能的，所以最终可能出现这种情形：同一个线程既要决定结果是1-价的又要决定结果是0-价的，而此时如果是k值，可能会出现要决定更多的价的情况，而此时，明显是不满足一致性的。
证明：consensus 2 T2[n+1];
public void decide(int k){
for(int i=n;i>k;i--){
T2[i].decide(0);
}
T2[k].decide(1);
for(int i=n;i>=0;i--){
if(T2[i].decide(0)==1){
return Xi;
}
}
}
（1）Stack类的一致数至少为2。 证明: 栈中存放着整数，用push()方法将值WIN和LOSE先后压入栈中，WIN的值为0，表示第一个线程，LOSE的值为1，表示第二个线程，用decide()首先调用propose(v)，将值v存放在输入指定值的共享数组proposed[]中，然后用pop()方法将栈顶取出。如果这一项的值为WIN，则首先选中另一个线程，调用线程按照数组proposed[]中的声明返回这个被选中线程的输入。如果这一项的值为LOSE，则本身的线程被选中，并且决定它自己的值。由于不存在环路，所以该协议是无等待的，所以Stack类的一致数至少为2。
（2）Stack类的一致数为2。 证明:假设Stack的一致数为3，则Stack类可以支持3线程的一致性，则有可能出现如下情况，假设存在线程A、B、C，该协议有一个临界状态s。假设A的下一个迁移是该协议到达一个0-价状态，而B的下一个迁移将使该协议到达一个1-价状态。假设A、B同时调用pop()，如果A先从栈中取值然后B才进行取值，则协议状态为s’，如果出栈顺序相反，则协议状态为s’’。此时分别让线程C进行独奏，而对于C来说，s’和s’’是不可区分的，所以在两种状态下C都必须决定相同的值，得到矛盾。
综上所述，Stack类不能满足一致数为3的协议，而其一致数最少为2，故Stack类的一致数为2。
证明:假设FIFO Queue类增加一个peek()方法，该方法返回但不删除队首元素，即下一个线程在调用时仍然可以读取到上一个调用线程的信息，以确定上一个进行调用的线程，既可以确定顺序，获得一致性。所以扩展后的队列具有无限一致数。
这是一个3-哲学家就餐问题，问题的要求是保证一个哲学家就餐，而其他哲学家知道就餐的哲学家是谁。
不可以：只提供CAS，考虑到每个人都抢到一支筷子，满足不了条件。
考虑临界状态S，A迁移使S进入0价状态S’，B迁移使S进入1价状态S’’。对Rab的任意操作，对Rbc、Rac的读操作对于C线程是不可见的，它无法区分S’和S’’。
A、B线程只能对Rbc、Rac的写操作，假设线程A写使S进0价状态，B写使S进入1价状态，但是在A写后，B再写，到达S’，B写后，A再写，到达S”，C无法区分这两种状态。
可以：使用的是DACS，保证一个哲学家拿到筷子区就餐。
public class TRMWConsensus extends ConsensusProtocol<T>{
Rab=-1;Rbc=-1;Rac=-1;
public T decide(T value)
{
int i=ThreadID.get();
int j=(i+1)%3;
int k=(i+2)%3;
Xi=value;
If(DACS(Rij,Rit,-1,-1,i,i))
{
return Xi;
}
int k=Rij+Rit+1;
return Xk;
}
}
略。
（1）证明：当第一个线程A首先执行完成write(v)的条件后检测到原StickyBit类的对象的状态为⊥，然后将其状态变为v，且以后都不再改变。故返回时若返回值为true，说明是第一个执行的线程，若返回值为false，说明状态值没有改变，则读取上一个线程的索引值，可以确定顺序，由于所有线程的执行都无需等待其他线程执行结束，故是无等待的二进制一致性。
（2）
propose[m];
for(int i=0;i<m;i++){
propose[i]=Thread(i).input;
}
public class StickyBitConsensus extends ConsensusProtocol<T>{
StrickBit[log2m];
public T decide(T value){
int j=ThreadID.get();
BitArray[log2m]=j.ToBit();
for(int i=0;i<log2m;i++)
{
if(BitArray[i]==1){
StrickBit[log2m].decide(1);
}else{
StrickBit[log2m].decide(0);
}
}
int k=StrickBit[log2m].Toint();
return Propose[k];
}
}
当k>1时，SetAgree的一致数应该与k的值一致。
这种近似一致对象的一致数是ε。
（1）A类型的广播不能保证一致性。因为A类型的广播不同线程广播的消息可以被不同线程以不同的次序接收，假设此时有线程A广播M1线程B广播M2，而不同的接收端有可能出现下面的情形：线程C先接收到M1再接收到M2，线程D先接收到M2再接收到M1，无法对M1和M2的传播顺序进行确认。
（2）B类型的广播能保证一致性。因为B类型的广播当P广播M1，Q广播M2时，无论广播的先后，所有线程接收到的顺序皆为M1和M2，大家确认相同的顺序。
（3）可行
yA=xA;
if yB==⊥
return yA;
if yB==0
return yA;
return 1;
yB=xB;
if yA==⊥
return yB;
if yA==0
return 0;
return yB;
如果共享状态是一个一致对象，说明它满足一致性，在多个线程即将达到一致而未达到一致之前，处于临界状态，所以不能用临界状态证明一致性的不可能性。
略。
等价于用足够多个n线程二值一致性对象解决n值的n一致性问题。参见题52。
（1）参见题52 （2）参见题58
有限个线程，decide()只执行一次，无锁和无等待等价。读写寄存器的一致数为1，不可能实现多于2个线程的一致性协议。
问题在于peek，让两个线程看到的head可能不同。
class NewCompareAndSet extends ConsensusProtocol{
private final int FIRST=0;
private int f;
private AtomicInteger r=new AtomicInteger(FIRST);
public Object decide(Object value){
propose(value);
int i=ThreadID.get();（1~n）
if(r.compareAndSet(FIRST,i)){
f=propose[i];
return proposed[FIRST];
}else{
return f;
}
}
}
证明：在n-界compareAndSet()中，当正好有n个线程发生调用的时候，不会发生错误状态，可以根据返回的状态确定线程的顺序，所以一致数至少为n，当再有更多的线程进行调用时，返回的值均为⊥，当正好有n+1个线程进行调用时仍可以确定n+1个线程的顺序，但是当调用的线程数大于n+1的时候，只能确定n个线程的顺序，故n-界compareAndSet()对象的一致数恰好为n。
public class ComAssign23{
int[] r=new int[3];
public ComAssign23(int init){
for(int i=0;i<r.length;i++)
r[i]=init;
}
public void assign(T v0,T v1,int i0,int i1){
r[i0].compareAndSet(r[i0].get(),v0);
r[i1].compareAndSet(r[i1].get(),v1);
}
public int read(int i){
return r[i];
}
}
略。
证明：因为能够支持compareAndSet()和get()方法的寄存器，其一致性是无限的，而get()方法只是取在执行compareAndSet()方法时的代替期望值的新值，即索引值，可以通过这个值来确定调用的线程，get()方法只是将取这个值的过程作为对象的一个函数进行调用，即使不通过get() 方法的调用，也可以返回这个值，所以仅支持compareAndSet()方法的寄存器具有无限的一致数。
赋值语句L14，prefer[i]=prefer[j]不是原子语句，他们可能永远都不能决定同一个输入，与无等待相悖。
无障碍是非阻塞演进性条件。
非确定对象实现的集合，删除是不确定的：
P1 |--insert(2)--| |--remove(1或2)---|
P2 |--insert(1)--| |--remove(1或2)---|
若先插入1和2，第一个删除1，第二个删除先帮助第一个把1删除了，然后再做自己的删除1操作，两个操作都删除了1。
增加一个表决对象，先表决做哪个操作，然后再发布所做操作及结果。
无等待的构造将会出现问题，因为有可能帮助了tail，这是不合法的。
Apply方法就是CAS方法，返回值是TRUE。Read方法是max(head)指向的值。
可行。自己先完成意味着别人先帮自己完成；自己先帮别人完成意味着别人先自己完成。
Head的作用是加速，可去掉从tail开始反向遍历。
（1）L10中线程A去帮助其他线程，结束后将自己的指针head[A]=after指向别人的结点。在检查L10的循环条件时，发现自己已经由别人帮助完成了。于是，没有L28行，它就不再指向自己的结点。
（2）没关系，因为扫描整个数组一定能发现自己的seq
当seq达到一个上界时，使这个seq达到上界的线程将自己的操作结果告知tail，并更新tail指向自己。回收其他日志结点。
使用事务内存或者同时对多个对象原子操作，类似于多赋值对象。
等待20ms后立即调度
调度时需保存数据，既然调度时间可以忽略，则说明内存速度很快，故无需缓存。
高速缓存逻辑上存在于处理器和主存之间，为了解决系统结构中每一次访问主存都要花费数百个时钟周期影响响应速度的问题而引入的。而上下文切换是指处理器执行一个线程一段时间，然后不管该线程转去执行另一个线程。当上下文切换的代价可以忽略，即忽略了再次访问主存的时间，在逻辑上，可以认为调用线程可以立即执行，即无需考虑处理器和主存之间调用的时间问题，甚至可以认为所有的线程都处于高速缓存中，而此时结构中并不需要高速缓存，就可以实现高速缓存的功能，所以，处理器中不需要存在高速缓存。
（1）以32个字为一个单位，即一个缓存块中的地址需要5位，所以低5为作为块内地址，高位即可作为块的地址，低5位均置0，高位仍未高位，可以作为子网掩码，来进行地址a的地址映射。
（2）最好命中率：因为64/32=2，所以数组中所有内容可以被分为两块，装入高速缓存，即只有两块首次进入缓存块时没有命中，所以命中率为(644-2)/(644)=254/256=99.2%。 最坏命中率：将数组中每个字放入不同的缓存块，因为只有16个缓存块，不足以储存64个地址，故每次调用时均无法在缓存中找到，所以命中率为0/(64*4)=0。
（3）最好命中率：因为512/32=16，所以数组中所有内容可以被分为16块，装入高速缓存，即只有16块首次进入缓存块时没有命中，所以命中率为(5124-16)/(5124)=2032/2048=99.2%。 最坏命中率：将数组中每个字放入不同的缓存块，因为只有16个缓存块，不足以储存512个地址，故每次调用时均无法在缓存中找到，所以命中率为0/(512*4)=0。
32，1024。
因为结构为16个缓存块的直接映射高速缓存，且每个缓存块包含32个字，同时内存中数组的存储方式为a[0,0]的下一个元素是a[0,1]，即为按行存储，先储存第0行内容，再储存第1行内容，以此类推，直至储存完第31行，故与缓存的直接映射为每一行内容储存在一个高速缓存块内。所以，列优先遍历中一行行的进行遍历，只有每一行第一次进入高速缓存时，没有命中，故缺失个数为32。
行优先遍历中一列列的进行遍历，因为有32行而只有16个缓存块，按现成的顺序，下一次执行同行字的时候，该行的缓存已经被替换出去，即每一次读取高速缓存中都无法命中，所以缺失的个数为32*32=1024。
写回，通知他人失效。
独占模式：cache行只存在于当前的cache中，但却是clean的；它和主存中的数据是一致的。在任何时刻，回应一个读请求，它可能被改变为共享状态；同样的，当对它进行写操作时，可以被变成修改状态。
修改模式：该cache行只存在于当前的cache中，并且是dirty的，和内存中的值相比它是已经被修改过的。在允许任何其他读操作之前，cache需要将数据写回到主存。写回将该行的状态变为独占(Exclusive)。
共享模式：该状态说明这个cache行可能被存储在系统中其他的cache中，并且是clean的，和主存中的内容是一致的。这个cache行可以在任何时候被丢弃。
public class TASLock implements Lock {
volatile public int state = 0;
private static final AtomicIntegerFieldUpdater<TASLock> updater
=AtomicIntegerFieldUpdater.newUpdater(TASLock.class, "state");
public void lock() {
while (updater.getAndSet(this, 1) != 0) {} // spin
}
public void unlock() {
updater.set(this, 0);
}
}
public class TTASLock implements Lock {
volatile public int state = 0;
private static final AtomicIntegerFieldUpdater<TTASLock> updater
= AtomicIntegerFieldUpdater.newUpdater(TTASLock.class, "state");
public void lock() {
while (true) {
while (updater.get(this) != 0) {}; // spin
if (updater.getAndSet(this, 1) == 0)
return;
}
}
public void unlock() {
updater.set(this, 0);
}
}