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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第5章 并行性：互斥和同步内容提要,概论,：并行时进程间的相互关系及相应的要解决的问题：互斥、同步与通信,互斥：,临界段,互斥方法,CPU,空转：,纯软件方法,、,特殊硬件指令辅助的软件方法,CPU,不空转：,信号量,以及,检验该机制的经典问题（生产者/消费者，读者/写者）,、,管程,通信,UNIX,的同步与通信,习题,概论,并行操作的发展历史：多道程序、多处理器系统、分布式处理系统,进程并行时涉及的主要问题：互斥、同步和通信,进程间相互关系的类型：,协同：互相知道对方的存在和名字。通信,共享：互相知道对方的存在，不知名字。互斥与死锁,竞争：不知道对方的存在，通过对硬件资源的竞争相互制约。互斥与死锁。,临界段,临界段的提出,例1,：在,Spooler,中对,in,指针的竞争使用,例2,：两个有共享变量的进程在不同的执行时序中产生不同的结果,临界段的概念,临界段的互斥要求：,竞争使用,SPOOLER,的,in,指针,文件,G,文件,F,文件,Tu,3,4,5,:,:,:,:,out,3,in,6,Process A,Process B,A,形成文件名a；A,取,in(6),指针；,A,时间片到；,B,形成文件名,b；B,取,in(6),指针；将文件名,b,送入；,in,值加1(7);,A,按照,in(6),送入文件名,a，,冲掉原内容,b,多处理器对共享变量的竞争使用,问题：两个进程,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:array0.1 of,boolean,;,Pi:begin,repeat,while flagj do skip;skip,表示不作为,flagi:=true,进程,Pi,的临界段代码,CSi,；,flagi:=false;,进程,Pi,的其他代码；,forever;,end,用软件实现互斥：解法2（差,）,var,flag:array0.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:array0.1 of,boolean,;,turn:0.1;,flag0:=flag1:=false;,Pi:begin,repeat,flagi:=true;,表示想进临界区,while flagj,是否别人也想进临界区,do if turn=j,then begin,flagi:=false;,while turn=j do skip;,等待别人出临界区,flagi:=true;,end,临界段代码,CSi,;,turn:=j;,flagi:=false;,进程,i,的其他代码,forever,end,实现互斥的硬件辅助机制,中断屏蔽：在执行临界段期间关中断。不能够用于正确性无保证的用户进程，只能够用于操作系统；多,CPU,时无效。,硬件指令,：在一个存储周期内完成，从而不论在单或多,CPU,中都不会被打断。简便易行。,TS(Test-and-Set),Swap,“,忙等待”的缺点：浪费,CPU,的时间,判断互斥方法是否成功的思路,爱斯基莫人和他的冰屋：设冰屋中每次只能够钻进一个人。屋中有一块黑板，上面写着指示钻入人下一步行动的信息，钻入人可以修改黑板上的信息。,如果,i,进屋看了对他的指示后出屋，然后按照此指示执行。但在,i,执行前，,j,钻入屋中，修改了黑板上的信息，导致了,i,执行的动作与现在黑板上的信息不一致，从而出错。,关键是看板与执行之间不能被中断。支持互斥的指令使钻入人看完板后，马上修改板上内容，这相当于告诉对方：我已在执行了，请勿打扰！,进程,i,进程,j,TS(Test-and-Set),的含义,function,Test-and-Set(,var,flag:,boolean,):,boolean,begin,Test-and-Set:=flag;,flag:=true;,end,采用以上形式是为了便于理解，真正的操作仅仅是一条硬件指令,用,Test-and-Set,控制进出临界区,Check TSET flag,检测,flag,JR NE,Check,非零转移,临界段,CS,(PSW,中,Z=0),CLR flag,清flag,位,用,Swap,指令控制进出临界区,MOV AL 0,0,AL,寄存器,Again:XCHG AL,flag,交换,AL,和,flag,内容,TEST AL,AL,已在临界段时内容为0,JZ Again,AL,为零时，转移,临界段,CS,MOV flag,1,退出临界段，重建,AL,为1,“信号量”是什么？,信号量被定义为一个特殊的整型变量，在它上面可以执行如下三种操作：,可被初始化为一个非负整数,Wait,操作将信号量减1后，若该值为负，则使调用进程等待,Signal,操作将信号量值增1后，若该值非正，则唤醒一个在此信号量上等待的进程,特别注意：,Wait,和,Signal,都是不可被打断的操作,一般信号量上的同步原语（信号量值可为负整数）,物理意义：,S0,时为资源数，,S=0,时为等待进程数,Wait(S):,S.value:=S.value-1;,if S.value0,then begin,Insert(CALLER,S.L);,插入信号量,S,的等待队列,Block(CALLER);,阻塞,end,Signal(S):,S.value:=S.value+1;,if S.value=0,then begin,Remove(S.L,id);,从信号量,S,的等待队列中取出,Wakeup(id);,唤醒这个取出的进程,end,注意：这里仅仅是关于信号量含义的解释真正信号量的实现必须保证信号量执行的过程中不能够被打断。,二元信号量的同步原语（信号量值为1或0）,WaitB,(S):,if S.value=1,then,S.value:=0,else begin,Insert(CALLER,S.L);,插入信号量,S,的等待队列,Block(CALLER);,阻塞,end,SignalB,(S):,if S.L queue is empty;,then S.value:=1,else begin,Remove(S.L,id);,从信号量,S,的等待队列中取出,Wakeup(id);,唤醒这个取出的进程,end,注意：这里仅仅是关于信号量含义的解释。真正信号量的实现必须保证信号量执行的过程中不能够被打断,同步原语的不可分割性,信号量本身是共享变量，因此对它的操作代码是临界段。,信号量原语的实现应该是原子操作,保证进程间互斥地使用同步原语,整体操作，不可分割,如何实现对信号量的原子操作,软件互斥：复杂、低效、适合单,CPU,开关中断：方便、用于,OS、,适合单,CPU,硬件指令：方便、适合多,CPU,用硬件或固件直接实现,用硬件指令实现信号量的过程,Wait(S):,While TS(lock)do skip;,上锁,对信号量的操作；,lock:=false;,开锁,Signal(S):,While TS(lock)do skip;,上锁,对信号量的操作；,lock:=false;,开锁,用信号量实现进程间互斥,var mutex,:Shared Semaphore;,begin,mutex,:=1;,parbegin,P1:.,P2:.,.,Pi:repeat,Wait(,mutex,);,“,进程,Pi,的临界段代码,CSi,”,Signal(,mutex,);,“,进程,Pi,的其他部分代码”,forever,.,Pn,:.,parend,end,生产者和消费者问题中的环形缓冲区,C,P,满,空,生产者和消费者问题的程序,Procedure producerProcedure consumer,beginbegin,repeat repeat,生产数据；,Wait(F);,Wait(E);Wait(,mutex,);,Wait(,mutex,);,“,分给满缓冲区调整,C,指针”；,“,分给空缓冲区调整,P,指针”,Signal(,mutex,);,Signal(,mutex,);,“,从满缓冲区取出数据”；,“,向空缓冲区装入数据”,Signal(E);,Signal(F);,“,消耗或处理数据”；,forever forever,endend,这里,mutex,用于针对使用共享变量,P,和,C,的互斥（请问谁共享它们？）,E,表示仓库中的空格数，初值为,N。F,表示仓库中的满格的个数，初值为0。,阅读者和写入者问题程序,Readeri,:,Writeri,beginbegin,Wait(,mutex,);Wait(,wrt,);,readcount,:=,readcount,+1;,“,写数据集”；,if,readcount,=1 then Signal(,wrt,);,Wait(,wrt,);end,Signal(,mutex,);,“,读数据集”；,Wait(,mutex,);,readcount,:=,readcount,-1;,if,readcount,=0 then,Signal(,wrt,);,signal(,mutex,);,end,这个算法对写入者不公平，为什么？,你能否通过对此算法的修改，使写入者得到公平的待遇？,不容易写好使用信号量的程序,Wait(,mutex,);(1)Signal(,mutex,);(4),“,临界段”；(2)“临界段”；(5),Wait(,mutex,);(3)Wait(,mutex,);(6),若（1）（2）（4）（5）则同时进临界段,若（1）（2）（3）（4）（1）（5）（6）则死锁,管程（见,p.99,图5.3和用管程实现的生产者/消费者问题）,信号量编程十分复杂，一旦出错难以发现和纠正，且可能造成严重的后果,管程的定义,：管程是由局部于管程的数据和一个或多个内部过程所组成的模块，它具有以下特征：,管程内数据只能够由管程内过程访问,进程通过调用管程内过程共享管程中数据,任何时候只能有一个进程使用管程中过程,管程的实现需要特殊的编译系统。,“一个有护士看门的一位全科医生的诊室”,只放一个病人进入诊室看病,病人在诊室内等待(,WaitC,),相关病人的诊断结果时，可以再进一位病人。,病人唤醒(,SignalC,),相关的其他病人，自己退出。,管程的应用：见教材,p.99,的生产者/消费者例,管程的结构,局部数据,条件变量,初始化程序,过程1,过程,n,条件,c1,队列,条件,cn,队列,进程等待队列,SignalC,(c1),SignalC,(,cn,),WaitC,(c1),WaitC,(,cn,),进程间的通信,进程通信：进程间交换一定数量的信息,进程通信的实现（多发送者/单接收者）,同步机制和数据结构,消息和消息缓冲区,消息队列,同步（指针操作互斥和空/满同步）,通信原语,Send（,目标进程,id，,消息）的工作流程,Receive（,源进程,id，,消息）的工作流程,间接通信模式：信箱，一对一、多对一(,C/S),和一对多（广播），静态连接和动态连接,其他通信模式：非阻塞发送/阻塞接收(,SPOOL)、,非阻塞发送/非阻塞接收(,E-mail)、,阻塞发送/阻塞接收(,OS,内部）,M1,M2,M3,队列头,Send（,目标进程,id，,消息）工作流程,申请消息缓冲区,将消息正文传送到消息缓冲区正文部分,向消息缓冲区填写消息头部,查寻目标进程,PCB,并对互斥信号量,mutex,执行,Wait,操作（对消息队列指针操作的互斥）,将消息缓冲区链入消息队列,对等待信号量,Swait,做,Signal,操作（,Swait,的值是已发出的消息个数。唤醒接收进程。）,对互斥信号量,mutex,做,Signal,操作,Receive（,源进程,id，,消息）工作流程,对自己,PCB,中的,Swait,信号量做,Wait,操作（等待发送进程发来的消息）,对互斥信号量,mutex,执行,Wait,操作（对消息队列指针操作的互斥）,将消息队列中的第一个消息（头指针所指向的）移入进程工作区,将消息队列头指针指向下一个消息,释放原第一个消息的消息缓冲区,对,mutex,执行,Signal,操作,UNIX,的进程同步与通信,Pipes,管道,消息,共享主存段,信号量,信号（或称软中断）：用于在进程之间发送少量信息并进行适当处理。可以在同组进程之间，而内核也可以发信号给进程。软中断信号是指向某个进程的,proc（PCB,常驻内存部分）的,p_,sig,送入一个0 19之间的整数，这些不同的整数代表了不同的信息。,Pipes,管道,管道是什么：两个进程间打开的文件，允许两个进程间按先进先出方式传送数据，一个进程写入，另一个进程读出，,OS,负责彼此间的同步执行。,管道的种类：无名管道/有名管道,与管道有关的系统调用：,创建：有名,pipe(,fdp,);,无名,mknod,(),打开；有名已打开；无名,open(),使用及使用中的同步,打开同步,读写同步,关闭同步,UNIX,中的消息：用以下的数据结构完成“建立消息队列、发送或接收消息等系统调用,队列头,消息队列头表,消息队列头结构,消息头表（每个入口是一个消息头结构）,消息缓冲池（放置正文）,指向正文所在位置,指向该队列的第一个“消息头结构”,共享主存段,使用共享主存段的过程：通信进程在使用共享主存段之前先提出申请，系统分配给它，并返回一个共享主存段标识号。一个共享主存段建立后被附加到进程的虚拟空间，进程可附加多个共享主存段。,数据结构,共享主存控制块（又称共享主存段头结构）：每个共享主存段都有一个这样的控制块，用于描述该主存段，并保留对它进行管理和控制的信息。,共享主存段的数据结构：包括该段的页表和允许的存取权限。,共享主存段的系统调用：申请一个共享主存段；将共享段附加到申请通信的进程地址空间；解除共享段和进程之间的连接。,信号量,UNIX System,对信号量技术进行了扩充，它允许对一组信号量进行相同或不同的操作，而且对信号量的值也不仅仅是加1或减1的操作。,数据结构,信号量的数据结构,信号量标识的数据结构和信号量标识表：系统中每组信号量又称信号量集合，包含一个或多个信号量。每个信号量集合都有一个信号量标识的数据结构，用于描述该组信号量的位置和访问控制信息。信号量标识表是信号量标识组成的数组,系统调用,信号量的建立：申请建立一个信号量的集合,对信号量的操作：对指定信号量集合中的一个或多个进行,wait,或,signal,操作。操作对象和操作的内容都由该系统调用中的参数规定。,创建或修改恢复表：恢复表用于进程终止时复原信号量的值,对信号量执行控制操作：读取和修改信号量集合的有关状态信息，或撤消信号量集合。,习题,5.1 5.7,5.11 5.13,5.14 5.18,讨论题：5.19 5.20,对阅读者和写入者问题的修改,Readeri,:,Writeri,beginbegin,Wait(writer);Wait(writer);,Signal(writer);,Wait(,wrt,);,Wait(,mutex,);,“,写数据集”；,readcount,:=,readcount,+1;Signal(,wrt,);,if,readcount,=1 then,Signal(writer);,Wait(,wrt,);end,Signal(,mutex,);,“,读数据集”；,Wait(,mutex,);,readcount,:=,readcount,-1;,if,readcount,=0 then,Signal(,wrt,);,signal(,mutex,);,end,修改目的：使写者能够有跟读者一样的排队权。,