并行性互斥和同步内容提要.ppt

《并行性互斥和同步内容提要.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章并行性：互斥和同步—内容提要概论：并行时进程间的相互关系及相应的要解决的问题：互斥、同步与通信互斥：临界段互斥方法CPU空转：纯软件方法、特殊硬件指令辅助的软件方法CPU不空转：信号量以及检验该机制的经典问题（生产者/消费者，读者/写者）、管程通信UNIX的同步与通信习题概论并行操作的发展历史：多道程序、多处理器系统、分布式处理系统进程并行时涉及的主要问题：互斥、同步和通信进程间相互关系的类型：协同：互相知道对方的存在和名字。通信共享：互相知道对方的存在，不知名字。互斥与死锁竞争：不知道对方的存在，通过对硬件资源的竞

2、争相互制约。互斥与死锁。临界段临界段的提出例1：在Spooler中对in指针的竞争使用例2：两个有共享变量的进程在不同的执行时序中产生不同的结果临界段的概念临界段的互斥要求：竞争使用SPOOLER的in指针文件G文件F文件Tu345::::out3in6ProcessAProcessBA形成文件名a；A取in(6)指针；A时间片到；B形成文件名b；B取in(6)指针；将文件名b送入；in值加1(7);…;A按照in(6)送入文件名a，冲掉原内容b多处理器对共享变量的竞争使用问题：两个进程P1和P2对共享变量x的异步操作（都

3、执行x=x+1)，由于操作时序的变化会导致异常的结果P1:…,R1:=x;R1:=R1+1;x:=R1;…..P2:…,R2:=x;R2:=R2+1;x:=R2;…结果为x=v+1（错误结果）P1:…,R1:=x;R1:=R1+1;x:=R1;…..P2:…,R2:=x;R2:=R2+1;x:=R2;…结果为x=v+2（正确结果）临界段的定义和进程互斥使用临界段的原则临界段：进程中访问共享变量的代码段进程互斥使用临界段的原则：任何时候最多只允许一个进程进入临界段在解决临界段的互斥问题时，不应该依赖于CPU的运行速度或进程的

4、预期进展在临界区之外运行的进程不可以阻止其他进程进入临界区不应使要进入临界区的进程无限期地在临界区之外等待用软件实现互斥：解法1（错）varflag:array[0..1]ofboolean;Pi:beginrepeatwhileflag[j]doskip;skip表示不作为flag[i]:=true进程Pi的临界段代码CSi；flag[i]:=false;进程Pi的其他代码；forever;end用软件实现互斥：解法2（差）varflag:array[0..1]ofboolean;Pi:beginrepeatwhilet

5、urnidoskip;skip表示不作为进程Pi的临界段代码CSi；turn:=j;进程Pi的其他代码；forever;end用软件实现互斥：解法2的问题进程Pi临界段进程Pi非临界段进程Pj临界段进程Pj非临界段进程Pi临界段.进程Pi非临界段.进程Pi进不了临界段..用软件实现互斥：Dekker（难）varflag:array[0..1]ofboolean;turn:0..1;flag[0]:=flag[1]:=false;Pi:beginrepeatflag[i]:=true;表示想进临界区whileflag[j

6、]是否别人也想进临界区doifturn=jthenbeginflag[i]:=false;whileturn=jdoskip;等待别人出临界区flag[i]:=true;end临界段代码CSi;turn:=j;flag[i]:=false;进程i的其他代码foreverend实现互斥的硬件辅助机制中断屏蔽：在执行临界段期间关中断。不能够用于正确性无保证的用户进程，只能够用于操作系统；多CPU时无效。硬件指令：在一个存储周期内完成，从而不论在单或多CPU中都不会被打断。简便易行。TS(Test-and-Set)Swap“忙等

7、待”的缺点：浪费CPU的时间判断互斥方法是否成功的思路爱斯基莫人和他的冰屋：设冰屋中每次只能够钻进一个人。屋中有一块黑板，上面写着指示钻入人下一步行动的信息，钻入人可以修改黑板上的信息。如果i进屋看了对他的指示后出屋，然后按照此指示执行。但在i执行前，j钻入屋中，修改了黑板上的信息，导致了i执行的动作与现在黑板上的信息不一致，从而出错。关键是看板与执行之间不能被中断。支持互斥的指令使钻入人看完板后，马上修改板上内容，这相当于告诉对方：我已在执行了，请勿打扰！进程i进程jTS(Test-and-Set)的含义function

8、Test-and-Set(varflag:boolean):booleanbeginTest-and-Set:=flag;flag:=true;end采用以上形式是为了便于理解，真正的操作仅仅是一条硬件指令用Test-and-Set控制进出临界区CheckTSETflag检测flagJRNE,Check