进程同步与通信

《进程同步与通信》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章进程同步与通信、进程死锁4.1并发执行实现一个程序内部常常存在并发成份，即存在着可并发执行的程序段或语句。例：read(a);从设备1上输入信息aread(b);从设备2上输入信息bc:=a+b;计算Cwrite(C)；从设备上输出信息C并发成分与其它语句之间存在着相互制约的关系，为描述这些优先关系，定义一个描述工具：优先图。S1S2S3S44.1.1并发编程方法例1：ParbeginS1;S2;Parend;S3;S4;例2：Parbeginread(a);read(b);ParendC:=a+b;Write(c);S1;Parb

2、eginS3;BeginS2;S4;ParbeginS5;S6;Parend;End;Parend;S7;S1S2S4S3S6S5S7例：并发程序实现优先图问题：在什么条件下程序中的两个语句能并发执行？对任意语句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

3、(S1)∩R(S2)={}3.W(S1)∩W(S2)={}S1S2S4S3S6S5S7例：并发程序不能实现的优先图Fork和Join结构：Fork指令：存在两个并发执行部分，其中一个是从标号L开始的一组语句；一个是Fork指令后开始的一组语句。Join指令：在Join指令之前的Count个并发成分在此合并。forkS1S2joinS3S0Count:=2;S0;ForkL1;S1;GotoL2;L1:S2;L2:joincount;S3;说明：Fork指令将原来顺序执行的活动分为两个并发执行的活动。这两个并发活动必须在特定的位置上合并，先执

4、行到Join指令的将被停止，等到另一个并发活动也执行到Join指令时，程序才重新开始顺序执行Join指令后续的语句。为了动态实现合并，可以设想Join指令完成以下动作：count:=count-1;Ifcount≠0thenquit;其中，quit代表停止某个并发活动的操作。为保证正确性，该语句必须作为原语操作。例1：read(a);read(b);c:=a+b;write(c);程序可改写为：count:=2;forkL1;read(a);gotoL2L1:read(b);L2:joincountc:=a+b;write(c)S1S2S4

5、S3S6S5S7例2：S1;count:=3;forkL1;S2;S4;forkL2;S5;gotoL3;L2:S6;gotoL3;L1:S3;L3:joincount;S7;S1;count1:=2;count2:=2;forkL1;S2;S4;forkL2;S5;gotoL3;L1:S3;L2:joincount1;S6;L3:joincount2;S7;S1S2S4S3S6S5S7例3：补充作业：分别用并发语句和Fork/Join将下图转换成一个程序。S1S2S4S3S6S54.2进程的同步与互斥进程间存在的制约关系分为两类：同步关系

6、（直接制约关系）：为完成同一任务的伙伴进程间，因协调工作次序而等待所产生的制约关系。互斥关系（间接制约关系）：进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。4.2.1临界段问题例1：进程P1、P2共享打印机资源。入口码P1使用打印机出口码入口码P2使用打印机出口码例2：有限缓冲区的生产者/消费者问题。生产者产生产品放入缓冲区，消费者从缓冲区取出产品。NEXTINSTNEXTINSTNEXTINSTAINSTFirst一个生产者和一个消费者通过一个有限缓冲区联系起来，生产者和消费者均从队列头上加入/取出产品。生产者:begin生

7、产一个产品nextp；new(p);p.inst:=nextp;p.next:=first;first:=p;end;消费者:beginc:=first;first:=first.next;nextc:=c.inst;dispost(c);end;parbeginparend给出临界段问题的描述：临界资源（CR）：一次仅允许一个进程使用的资源。临界段（CS）：各进程必须互斥执行的程序段，该程序段实施对临界资源的操作。※实现临界段互斥的软件算法：考虑两个进程P0、P1之间的互斥问题，用Pi表示其中一个进程，Pj表示另一个进程。软件算法是指在临

8、界段的入口码和出口码设计相应代码，实现互斥执行临界段。算法1：设置共享整型变量turn，取值为0或1。若turn=i，则进程Pi获准进入临界段。进程Pi:whileturn≠id