进程同步与通信.ppt

第4章 进程同步与通信、 进程死锁 4.1并发执行实现 一个程序内部常常存在并发成份，即存在着可并发执行的 程序段或语句。 例： read(a); 从设备1上输入信息a read(b); 从设备2上输入信息b c:=a+b; 计算C write(C)； 从设备上输出信息C 并发成分与其它语句之间存在着相互制约的关系，为描述 这些优先关系，定义一个描述工具：优先图。 S1 S2 S3 S4 4.1.1并发编程方 法 例1： Parbegin S1; S2; Parend; S3; S4; 例2： Parbegin read(a); read(b); Parend C:=a+b; Write(c); S1; Parbegin S3; Begin S2; S4; Parbegin S5; S6; Parend; End; Parend; S7; S1 S2 S4 S3 S6 S5 S7 例：并发程序 实现优先图 问题：在什么条件下程序中的两个语句能并发执行？对任 意语句Si定义两个操作： R（Si）：Si执行时进行读访问操作的变量 W（Si）：Si执行时进行写访问操作的变量 例如：R(read(a)=; W(read(a)=a; R(c:=a+b)=a,b; W(c:=a+b)=c; 程序中相邻语句S1、S2如果同时满足以下三个条件，则可 并发并结果正确： 1.R(S1) W(S2)= 2.W(S1)R(S2)= 3.W(S1)W(S2)= S1 S2 S4 S3 S6 S5 S7 例：并发程序不能实现的优先图 Fork和Join结构： Fork 指令：存在两个并发执行部分，其中一个是从标号L开始 的一组语句；一个是Fork指令后开始的一组语句。 Join指令：在Join指令之前的Count个并发成分在此合并。 fork S1S2 join S3 S0 Count:=2; S0; Fork L1; S1; Goto L2; L1:S2; L2:join count; S3; 说明：Fork指令将原来顺序执行的活动分为两个并发执行的 活动。这两个并发活动必须在特定的位置上合并，先执行 到Join指令的将被停止，等到另一个并发活动也执行到 Join指令时，程序才重新开始顺序执行Join指令后续的语 句。为了动态实现合并，可以设想Join指令完成以下动作 ： count:=count-1; If count 0 then quit; 其中，quit代表停止某个并发活动的操作。 为保证正确性，该语句必须作为原语操作。 例1：read(a); read(b); c:=a+b; write(c); 程序可改写为： count:=2; fork L1; read(a); goto L2 L1:read(b); L2:join count c:=a+b; write(c) S1 S2 S4 S3 S6 S5 S7 例2： S1; count:=3; fork L1; S2; S4; fork L2; S5; goto L3; L2: S6; goto L3; L1:S3; L3:join count; S7; S1; count1:=2; count2:=2; fork L1; S2; S4; fork L2; S5; goto L3; L1: S3; L2: join count1; S6; L3: join count2; S7; S1 S2 S4 S3 S6 S5 S7 例3： 补充作业：分别用并发语句和Fork/Join将下图转换成一个程 序。 S1 S2 S4S3 S6 S5 4.2进程的同步与互斥 进程间存在的制约关系分为两类： 同步关系（直接制约关系）：为完成同一任务的伙伴进 程间，因协调工作次序而等待所产生的制约关系。 互斥关系（间接制约关系）：进程间因相互竞争使用独 占型资源（互斥资源）所产生的制约关系。 4.2.1 临界段问题 例1：进程P1、P2共享打印机资源。 入口码 P1 使用打印机 出口码 入口码 P2 使用打印机 出口码 例2：有限缓冲区的生产者/消费者问题。生产者产生产品 放入缓冲区，消费者从缓冲区取出产品。 NEXT INST NEXT INST NEXT INST A INST First 一个生产者和一个消费者通过一个有限缓冲区联系起来， 生产者和消费者均从队列头上加入/取出产品。 生产者: begin 生产一个产品nextp； new(p); p.inst:=nextp; p.next:=first; first:=p; end; 消费者: begin c:=first; first:=first.next; nextc:=c.inst; dispost(c); end; parbegin parend 给出临界段问题的描述： 临界资源（CR）：一次仅允许一个进程使用的 资源。 临界段（CS）：各进程必须互斥执行的程序段 ，该程序段实施对临界资源的操作。 实现临界段互斥的软件算法： 考虑两个进程P0、P1之间的互斥问题，用Pi表示其中一个进 程，Pj表示另一个进程。软件算法是指在临界段的入口码 和出口码设计相应代码，实现互斥执行临界段。 算法1：设置共享整型变量turn，取值为0或1。若turn=i，则 进程Pi获准进入临界段。 进程Pi: while turn i do skip; cs; turn:=j; 问题：若某时刻turn=0，且P0不在临界段内，则P1无法进入 CS。 算法2：将变量turn替换成数组flagi，元素初值为 false。如果flagi=true，表示进程Pi正在执行其临界段 。 进程Pi: while flag j do skip; flagi:=true; cs; flagi:=false; 问题：不能保证互斥。该算法的正确性欲进程执行速度有 关。 算法3：在算法2的基础上对调语句的顺序，并把 flagi=true看作进程欲进入临界段，或正在临界段内执 行的标志。 进程Pi: flagi:=true; while flag j do skip; cs; flagi:=false; 问题：进程会无休止地循环等待对方。 算法4：算法3的问题在于进程Pi在置flagi为true时具 有一定的盲目性，在不了解对方的情况下单方面将flagi 置成了true。对算法3的问题进行改进。 进程Pi:flagi:=true; while flag j do begin flagi:=false; while flag j do skip; flagi:=true; end; cs; flagi:=false; 问题：如果两个进程同时以相同的速度执行，仍会产生问 题。 算法5：正确的算法如下： 进程间共享两个公共变量flag数组、变量turn，并将flag中 两个元素初值置为false，turn的初值任意（为0或为1） 。 进程Pi: flagi:=true; while flag j do if turn=j then begin flagi:=false; while turn=j do skip; flagi:=true; end; cs; turn:=j; flagi:=false; 例：下面的算法是解决两个进程临界段问题的解法，试 判断其正确性，如果不正确，举例说明。 两个进程P0，P1共享如下变量： Var flag:array01of boolean; Turn:0,1; 见下页 其中flag数组元素初值均为false,turn 的初值为0或1。 进程Pi（i=0或1，j=1-i）所对应的程序表示为： flagi:=true; while turni do begin while falgi do skip; turn:=i; end; cs flagi:=false; 4.2.2实现临界段问题的硬件方法 1.屏蔽中断方法 可利用中断开放和中断屏蔽指令编写临界段部分代码，以 避免两个进程同时处于临界段。 进程P1: disableInterrupt(); Balance=balance+amount; enableInterrupt(); 进程P2: disableInterrupt(); Balance=balance-amount; enableInterrupt(); 2.Test_and_Set指令 功能如下： Boolean Test_and_Set(boolean target=true; return rv; 通过说明一个布尔变量Lock，初值为false解决互斥问题。 while(Test_and_Set(Lock); cs Lock=false; 3.Swap指令 功能如下： Void Swap(boolean a=b; b=temp; 全局布尔变量Lock初值为false,每一进程设一局部布尔变量 Key. Key=true; while(Key=ture) Swap(Lock,Key); cs; Lock=false; 4.2.3 信号量 信号量可用来解决互斥与同步问题。 信号量由P、V操作两部分组成。信号量S为一整型变量， 只能被两个标准原语所访问(P167)。 P(s): While s=1 then y:=y+1； (5)z:=y end 例2：说明信号量值的物理意义（0,=0,，使得Pi以后还需要的资源可以通过 系统现有空闲资源加上所有Pj(j称为安全序列。 银行家例子中，当P第一次申请资金4时，安全序列为 或或，当Q申请资金2时，安 全序列为或。若此时申请资金3，则 不存在安全序列。若R申请资金2，则安全序列为 。 4.4.5死锁检测和恢复 化简资源分配图以检测系统中有无进程处于死锁状态。 P1 P2 P3 P3 P1P1 P2 P3 例1：一台计算机有8台磁带机。它们由N个进程竞争 使用，每个进程可能需要3台磁带机。请问N为多 少时，系统没有死锁危险，并说明其原因。 例2：某系统有三个并发进程，都需要同类资源4个 ，试问该系统不会发生死锁的最少资源数是（） 。 (1)9 （2）10 （3）11 （4）12 例3：假设系统由相同类型的m个资源组成，有n个进程， 每个进程至少请求一个资源。证明：当n个进程最多需 要的资源数之和小于m+n时，该系统无死锁。 答：假设每个进程需要资源数为x，则n个进程共需资源数 n*x；根据死锁发生的必要条件分析可知：最有可能发 生死锁的情况是每个进程都占有x-1个资源，并同时申请 最后一个资源。此时只要再增加一个资源，就肯定不会 死锁(因为增加的这一个资源至少可以满足其中一个进程 的要求，该进程满足后会释放占有资源，其它进程就可 以继续运行)。由此可得如下表达式：n*(x-1)+1m为无 死锁条件，n*(x-1)+1m n*xm+n-1m+n，得证. 例4：假设计算机系统可供用户使用的内存共150MB，目 前分配给3个进程的数量如下表所示。这时，第4个进程 产生，它最终需要内存60MB，目前的申请数为25MB。 进程 最大需要内存数 已经得到内存数 1 70MB 45MB 2 60MB 40MB 3 60MB 15MB 应用关于死锁问题的银行家算法 ,回答是否可以分配给第4 个进程25MB内存，为什么？ 例5：设系统有3种类型的资源，数量为（4,2,2），系统中 有进程A、B、C。按如下顺序请求资源： 进程A申请（2,2,1） 进程B申请（1,0,1） 进程A申请（0,0,1） 进程C申请（2,0,0） 该系统按资源剥夺法分配资源，试列出资源分配过程。指 出哪些进程需要等待资源，哪些资源被剥夺，进程