精选课件并行性互斥和同步内容提要.pptVIP

第5章 并行性：互斥和同步—内容提要 概论：并行时进程间的相互关系及相应的要解决的问题：互斥、同步与通信 互斥： 临界段 互斥方法 CPU空转：纯软件方法、特殊硬件指令辅助的软件方法 CPU不空转：信号量以及检验该机制的经典问题（生产者/消费者，读者/写者） 、管程 通信 UNIX的同步与通信 习题 概论 并行操作的发展历史：多道程序、多处理器系统、分布式处理系统 进程并行时涉及的主要问题：互斥、同步和通信 进程间相互关系的类型： 协同：互相知道对方的存在和名字。通信 共享：互相知道对方的存在，不知名字。互斥与死锁 竞争：不知道对方的存在，通过对硬件资源的竞争相互制约。互斥与死锁。 临界段 临界段的提出 例1：在Spooler中对in指针的竞争使用 例2：两个有共享变量的进程在不同的执行时序中产生不同的结果 临界段的概念 临界段的互斥要求： 竞争使用SPOOLER的in指针 多处理器对共享变量的竞争使用 问题：两个进程P1和P2对共享变量x的异步操作（都执行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的运行速度或进程的预期进展 在临界区之外运行的进程不可以阻止其他进程进入临界区 不应使要进入临界区的进程无限期地在临界区之外等待 用软件实现互斥：解法1（错） var flag:array[0..1] of boolean; Pi:begin repeat while flag[j] do skip;skip表示不作为 flag[i]:=true 进程Pi的临界段代码CSi； flag[i]:=false; 进程Pi的其他代码； forever; end 用软件实现互斥：解法2（差） var flag:array[0..1] of boolean; Pi:begin repeat while turn? ?i do skip;skip表示不作为 进程Pi的临界段代码CSi； turn:=j; 进程Pi的其他代码； forever; end 用软件实现互斥：解法2的问题 进程Pi临界段 进程Pi非临界段 进程Pj临界段 进程Pj非临界段 进程Pi临界段 . 进程Pi非临界段 . 进程Pi进不了临界段 . . 用软件实现互斥：Dekker（难） var flag:array[0..1] of boolean; turn:0..1; flag[0]:=flag[1]:=false; Pi:begin repeat flag[i]:=true;表示想进临界区 while flag[j] 是否别人也想进临界区 do if turn=j then begin flag[i]:=false; while turn=j do skip;等待别人出临界区 flag[i]:=true; end 临界段代码CSi; turn:=j; flag[i]:=false; 进程i的其他代码 forever end 实现互斥的硬件辅助机制 中断屏蔽：在执行临界段期间关中断。不能够用于正确性无保证的用户进程，只能够用于操作系统；多CPU时无效。 硬件指令：在一个存储周期内完成，从而不论在单或多CPU中都不会被打断。简便易行。 TS(Test-and-Set) Swap “忙等待”的缺点：浪费CPU的时间 判断互斥方法是否成功的思路 爱斯基莫人和他的冰屋：设冰屋中每次只能够钻进一个人。屋中有一块黑板，上面写着指示钻入人下一步行动的信息，钻入人可以修改黑板上的信息。 如果i进屋看了对他的指示后出屋，然后按照此指示执行。但在i执行前，j钻入屋中，修改了黑板上的信息，导致了i执行的动作与现在黑板上的信息不一致，从而出错。关键是看板与执行之间不能被中断。支持互斥的指令使钻入人看完板后，马上修改板上内容，这相当于告诉对方：我已在执行了，请勿打扰！ TS(Test-and-Set)的含义 function Test-and-S