问答题 Peterson解决进程互斥问题的算法如下：
bloolean flag[2]={false, flase};
pi: repeat
flag[i]: =j;
while (flag[j] and turn=j) do no_op;
critical* section
flag[i] :=false;
emainder section
until flase;
请回答下列问题：
问答题 分析说明上述算法是否满足临界区调度的原则?
【正确答案】临界区调度的原则如下： Peterson方案满足空闲让进、有限等待、让权等待，不满足忙则等待。在使用共享变量(即在进入其临界区)之前，各进程使用其进程号0或1作为参数来调用Peterson过程。该过程在需要时将使用进程等待，直到能安全地进入。进程在完成对共享变量的操作之后退出。
【答案解析】
问答题 以两个进程访问同一个临界资源为例，分析上述算法实现互斥的原理。
【正确答案】假设起初没有任何进程处于临界区，现在进程0通过将数组flag和turn置位标志自己想进入临界区。由于进程1并未进入临界区，所以整个过程很快正常完成。如果进程1现在想进入临界区，它将在while处等待，直到进程0将自己的flag置为0。现在考虑两个进程几乎同时进入临界区的情况，它们都将自己的进程号存入turn，但只有后一个存进去的进程号才是有效的，前一个无效。
【答案解析】
问答题 分析上述算法的特点。
【正确答案】荷兰数学家T.Dekker首先将轮换法和锁变量及警告变量结合的思想相结合，解除了一个不需要严格轮换的软件互斥解法，Peterson比该算法要简单得多。该方案的特点是简单、有效。
【答案解析】
问答题 假设内存有64个存储块，其编号为0，1，…，63，每个存储块使用与否，采用位图(一个64位的标志字flag)表示，flag的每一位对应一个存储块。当某一位(bit)置1时，表示该块已分配。置0表示该存储块空闲，有两个进程： get进程负责存储块的分配，每次分配一个块，其分配动作是：找出标志字的某个为0的位，把它置1，然后将其所代表的块分配。 put进程负责存储块的回收，每次回收一个块，其回收动作是：找出回收块，然后将其标志字置为0。put进程和get进程需要互斥访问位图。 试用信号量机制的P、V操作(或wait(S)：signal(S))写出两个进程间的同步算法。(要求注明信号量初值)
【正确答案】①get进程分配完64个存储区域后，再执行分配时必须等待put进程回收区域，而put进程无须等待分配进程get；get与put共享64位的标志字，它们必须互斥访问。 ②mutex是互斥信号量，初值是1，对64位标志字进行保护；S是标志字的同步信号量，初值为64，表示系统开始时64个区间均空闲，可供分配。 根据以上分析，可得出如下的程序： typedef int Semaphore; Semaphore S=64; Semaphore mutex=1; COBEGIN process get BEGIN while(true) BEGIN P(s) P(mutex); 查找标志字“0”的位(n)，修改该位为“1” V(mutex); 分配该区域(n); END END process_put BEGIN While(ture) BEGIN 回收某区域 P(mutex); 查找，修改标志字对应位为“0” V(mutex); V(S); END END
【答案解析】
问答题 给定全局数据a[n]、b[n]，并有T1～Tn-1共n-1个线程，线程代码如下： Ti(){ a=g(a, a[i-1]); b=f(a); } 其中g和f函数的作用是通过输入参数，进行一系列运算后返回。相当于Ti以a和a[i-1]为输入参数，a和b为输出。 要求使用PV原语，实现T1～Ti-1的并发互斥，尽量保证最大程度的并发。 (a[i-1]为Ti-1线程的结果)
【正确答案】这个操作实际上是一个生产者消费者问题，Ti看成是Ti+1的生产者，Ti+1看成是Ti的消费者。可设置数组empty[n]，初始empty[0]=1，其他为0，用来标示a[i]中的数据是否产生完毕，mutex标识a是否被访问，初始为1，则使用PV操作后，程序段可表示如下： Ti(){ P(mutex); P(empty[i-1]); a=g(a，a[i-1]); b=f(a); V(empty[i%n]); //对n求余，是为了处理i==n的情况，因为empty[n]是非法的 V(mutex); }
【答案解析】
问答题 试修改下面消费者一生产者问题解法中的错误。 Producer: begin repeat produce an item in nextp; wait(mutex); wait(empty); buffer (in):=nextp; signal (mutex); until false; end Consumer: begin repeat wait(mutex); wait(full); nextc:=buffer(out); out:=out+1; signal(mutex); consume item in nextc; until false; end
【正确答案】修改后的程序如下：
Producer:
begin
repeat
…
produce an item in nextp;
wait(empty); //必须先申请资源后申请互斥信号，以免死锁
wait(mutex);
buffer(in):=nextp;
signal(mutex);
signal(full); //产品置入缓冲区后，应将full加1，表示缓冲区多了一个产品
until false：
end
consumer:
begin
repeat
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=out+1;
signal(mutex);
signal(empty);
consume item in nextc;
until false;
end
【答案解析】