并行性互斥和同步内容提要.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,修改目的：使写者能够有跟读者一样的排队权。,