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

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

2、段的提出 例1：在Spooler中对in指针的竞争使用 例2：两个有共享变量的进程在不同的执行时序中产生不同的结果 临界段的概念 临界段的互斥要求：,竞争使用SPOOLER的in指针,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:=R

3、1+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

4、 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临界段

5、 进程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

6、; flagi:=false; 进程i的其他代码 forever end,实现互斥的硬件辅助机制,中断屏蔽：在执行临界段期间关中断。不能够用于正确性无保证的用户进程，只能够用于操作系统；多CPU时无效。 硬件指令：在一个存储周期内完成，从而不论在单或多CPU中都不会被打断。简便易行。 TS(Test-and-Set) Swap “忙等待”的缺点：浪费CPU的时间,判断互斥方法是否成功的思路,爱斯基莫人和他的冰屋：设冰屋中每次只能够钻进一个人。屋中有一块黑板，上面写着指示钻入人下一步行动的信息，钻入人可以修改黑板上的信息。 如果i进屋看了对他的指示后出屋，然后按照此指示执行。但在i执行前，j钻入

7、屋中，修改了黑板上的信息，导致了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,

8、Check非零转移 临界段CS(PSW中Z=0) CLR flag清flag位,用Swap指令控制进出临界区,MOV AL 00AL寄存器 Again:XCHG AL, flag 交换AL和flag内容 TEST AL, AL 已在临界段时内容为0 JZ AgainAL为零时，转移 临界段CS MOV flag, 1退出临界段，重建AL为1,“信号量”是什么？,信号量被定义为一个特殊的整型变量，在它上面可以执行如下三种操作： 可被初始化为一个非负整数 Wait操作将信号量减1后，若该值为负，则使调用进程等待 Signal操作将信号量值增1后，若该值非正，则唤醒一个在此信号量上等待的进程 特别注

9、意：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 注意：这里仅仅是关于信号量含义

10、的解释。真正信号量的实现必须保证信号量执行的过程中不能够被打断。,二元信号量的同步原语（信号量值为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 注意：这里仅仅是关于信号量含义的解释。真正信号量的实

11、现必须保证信号量执行的过程中不能够被打断,同步原语的不可分割性,信号量本身是共享变量，因此对它的操作代码是临界段。 信号量原语的实现应该是原子操作 保证进程间互斥地使用同步原语 整体操作，不可分割 如何实现对信号量的原子操作 软件互斥：复杂、低效、适合单CPU 开关中断：方便、用于OS、适合单CPU 硬件指令：方便、适合多CPU 用硬件或固件直接实现,用硬件指令实现信号量的过程,Wait(S): While TS(lock) do skip; 上锁 对信号量的操作； lock:=false; 开锁 Signal(S): While TS(lock) do skip; 上锁 对信号量的操作； l

12、ock:=false; 开锁,用信号量实现进程间互斥,var mutex: Shared Semaphore; begin mutex:=1; parbegin P1:. P2:. . Pi:repeat Wait(mutex); “进程Pi的临界段代码CSi” Signal(mutex); “进程Pi的其他部分代码” forever . Pn:. parend end,生产者和消费者问题中的环形缓冲区,生产者和消费者问题的程序,Procedure producerProcedure consumer beginbegin repeat repeat 生产数据； Wait(F); Wait(E

13、); 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);

14、 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)

15、 Wait(mutex);(3)Wait(mutex);(6) 若（1）（2）（4）（5）则同时进临界段 若（1）（2）（3）（4）（1）（5）（6）则死锁,管程（见p.99图5.3和用管程实现的生产者/消费者问题）,信号量编程十分复杂，一旦出错难以发现和纠正，且可能造成严重的后果 管程的定义：管程是由局部于管程的数据和一个或多个内部过程所组成的模块，它具有以下特征： 管程内数据只能够由管程内过程访问 进程通过调用管程内过程共享管程中数据 任何时候只能有一个进程使用管程中过程 管程的实现需要特殊的编译系统。 “一个有护士看门的一位全科医生的诊室” 只放一个病人进入诊室看病 病人在诊室内等待(W

16、aitC)相关病人的诊断结果时，可以再进一位病人。 病人唤醒(SignalC)相关的其他病人，自己退出。 管程的应用：见教材p.99的生产者/消费者例,管程的结构,进程等待队列,SignalC(c1),SignalC(cn),WaitC(c1),WaitC(cn),进程间的通信,进程通信：进程间交换一定数量的信息 进程通信的实现（多发送者/单接收者） 同步机制和数据结构 消息和消息缓冲区 消息队列 同步（指针操作互斥和空/满同步） 通信原语 Send（目标进程id，消息）的工作流程 Receive（源进程id，消息）的工作流程 间接通信模式：信箱，一对一、多对一(C/S)和一对多（广播），静态

17、连接和动态连接 其他通信模式：非阻塞发送/阻塞接收(SPOOL)、非阻塞发送/非阻塞接收(E-mail)、阻塞发送/阻塞接收(OS内部）,队列头,Send（目标进程id，消息）工作流程,申请消息缓冲区 将消息正文传送到消息缓冲区正文部分 向消息缓冲区填写消息头部 查寻目标进程PCB并对互斥信号量mutex执行Wait操作（对消息队列指针操作的互斥） 将消息缓冲区链入消息队列 对等待信号量Swait做Signal操作（Swait的值是已发出的消息个数。唤醒接收进程。） 对互斥信号量mutex做Signal操作,Receive（源进程id，消息）工作流程,对自己PCB中的Swait信号量做Wait

18、操作（等待发送进程发来的消息） 对互斥信号量mutex执行Wait操作（对消息队列指针操作的互斥） 将消息队列中的第一个消息（头指针所指向的）移入进程工作区 将消息队列头指针指向下一个消息 释放原第一个消息的消息缓冲区 对mutex执行Signal操作,UNIX的进程同步与通信,Pipes管道 消息 共享主存段 信号量 信号（或称软中断）：用于在进程之间发送少量信息并进行适当处理。可以在同组进程之间，而内核也可以发信号给进程。软中断信号是指向某个进程的proc（PCB常驻内存部分）的p_sig送入一个0 19之间的整数，这些不同的整数代表了不同的信息。,Pipes管道,管道是什么：两个进程间打

19、开的文件，允许两个进程间按先进先出方式传送数据，一个进程写入，另一个进程读出，OS负责彼此间的同步执行。 管道的种类：无名管道/有名管道 与管道有关的系统调用： 创建：有名pipe(fdp);无名mknod() 打开；有名已打开；无名open() 使用及使用中的同步 打开同步 读写同步 关闭同步,UNIX中的消息：用以下的数据结构完成“建立消息队列、发送或接收消息等系统调用,消息队列头表,消息队列头结构,消息头表（每个入口是一个消息头结构）,消息缓冲池（放置正文）,指向正文所在位置,指向该队列的第一个“消息头结构”,共享主存段,使用共享主存段的过程：通信进程在使用共享主存段之前先提出申请，系统分配给它，并返回一个共享主存段标识号。一个共享主存段建立后被附加到进程的虚拟空间，进程可附加多个共享主存段。 数据结构 共享主存控制块（又称共享主存段头结构）：每个共享主存段都有一个这样的控制块，用于描述该主存段，并保留对它进行管理和控制的信息。 共享主存段的数据结构：包括该段的页表和允许的存取权限。 共享主存段的系统调用：申请一个共享主存段；将共享段附加到申请通信的进程地址空间；解除共享段和进程之间的连接。,信号量,UNIX System 对信号量技术进行了扩充，它允许对一组信号量进行相同或不同的操作，而且对信号量的值也不仅仅是加1或减