第5章 并发性：互斥和同步
5.1
答：b.协同程序read读卡片，将字符赋给一个只有一个字大小的缓冲区rs然后在赋给squash协同程。协同程序Read在每副卡片图像的后面插入一个额外的空白。协同程序squash不需要知道任何关于输入的八十个字符的结构，它简单的查找成对出现的星号，然后将更改够的字符串经由只有一个字符大小的缓冲sp，传递给协同程序print。最后协同程序print简单的接受到来的字符串，并将他们打印在包含125个字符的行中。
5.2．考虑一个并发程序，它有两个进程p和q，定义如下。A.B.C.D和E是任意的原子语句。假设住程序执行两个进程的parbegin Void p() void q() { A; { D; B; E; C; } }
答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3考虑下面的程序
const int n=50; int tally;
void total() { int count;
for(count =1;count <=n;count ++)
21
{tally++; } }
void main() {
tally =0;
parbegin(total(),total(); write(tally);
}
答：a.随意一看,tally值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量的取值:
1.进程A载入tally值,tally值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).
2.进程B载入tally值(仍然是0),然后运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权.
3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器.
4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入).
5.进程A被重新安排开始,但这次没有被中断,直到运行完成它剩余的49
22
次载入,增加和存储操作,结果是此时tally值已经是50.
6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果.
一些认为会出现低于2这个值的结果,这种情况不会出现.这样tally值的正确范围是[2,100].
b.对一般有N个进程的情况下,tally值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果.
5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。 答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有结果,然而阻塞等待会消耗操作系统资源在换出与换入进程上. 5.5考虑下面的程序
boolean blocked[2]; int rurn; void P(int id) {
While (true) {
While(turn!=id); {
While(blocked[1-!id]
23
/*do nothing*/; Turn =id; } }
Void main () {
Blocked[0]=false; Blocked[1]=false; 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)
24
{
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.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在 25