04第四章+互斥同步与通讯（1）1

《04第四章+互斥同步与通讯（1）1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章互斥、同步与通讯并发进程(concurrentprocesses)进程互斥(mutualexclusion)进程同步(synchronization)进程高级通讯(communication)4.1并发进程4.1.1前趋图的定义前趋图（precedencegraph）有向无环图，图中每个结点表示一个语句、一个计算步骤、或一个进程。结点间的有向边表示偏序或前趋（precedencerelation)关系“→”。→={（Pi，Pj）

2、Pj启动之前Pi必须已经完成}。（Pi，Pj）∈→可记作Pi→Pj,称Pi是Pj的前趋，Pj是Pi的后继。在前趋图中，没有前趋的结点

3、称为初始结点，没有后继的结点称为终止结点。每个结点可以有一个权重(weight)，它可以表示该结点所包含的程序量或计算时间。4.1并发进程前趋图的例子P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P5，P4→P6，P5→P7，P6→P714326574.1.2顺序程序及其特性4.1.2.1程序的顺序执行(1)内部顺序性：对于一个进程来说，它的所有指令是按序执行的。S1：a:=x+yS2：b:=a-zS3：c:=a+bS4：d:=c+5S1S2S3S44.1.2顺序程序及其特性(2)外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。例:输入

4、(I)、计算(C)、打印(P)三个活动构成的进程，每个进程的内部活动是顺序的，即Ii→Ci→Pi，多个进程的活动也是顺序的。I1C1P1I2C2P24.1.2顺序程序及其特性4.1.2.2顺序程序特性:(1)连续性:指令逐条执行(2)封闭性:不受其它程序及外界因素影响(3)可再现性:结果与推进速度无关4.1.3并发程序及其特性4.1.3.1程序的并发执行(1)内部并发性:指一个程序内部的并发性。例：S1：a:=x+2；S2：b:=y+4；S3：c:=a+b；S4：d:=c+6；S5：e:=c-d；214354.1.3并发程序及其特性4.1.3.1程序的并发执行(2)

5、外部并发性:指多个程序之间的并发性。I1I2I3I4C1C2C3C4P1P2P3P44.1.3并发程序及其特性不可再现性的例子进程P：进程Q：A1:N:=0；B1:PRINT（N）；A2:N:=N+1；B2:N:=0；A3:GOTOA2；B3:GOTOB1；此例中进程P累积计数，进程Q将累计的结果打印出来。希望打印出的数是累计数的和。两个进程并发执行时有许多可能的交叉:如进程P循环5次进程Q循环1次，然后进程P又循环3次进程Q循环1次，则输出结果是5，3；如进程P循环2次进程Q循环1次，然后进程P又循环6次进程Q循环1次，则输出结果是2，6。两次执行结果完全不同。进

6、程Q执行完B1后被中断，进程P对N执行加1操作，然后进程Q执行B2，在这种情况下进程P的累计数将被丢失。4.1.3并发程序及其特性4.1.3.2并发程序的特性（1）间断性：程序交叉执行。（2）非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响。（3）不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果。4.1.4程序并发执行的条件在失去封闭性的条件下，保持可再现性。R(pi)={a1,a2,…,am}表示程序pi在执行期间所需读取的所有变量的集合，称为“读集”；W(pi)={b1,b2,…,

7、bn}表示程序pi在执行期间所需改变的所有变量的集合，称为“写集”。若有两条语句c=a+b和v=c-1，则它们的“读集”和“写集”分别为：R(c:=a+b)={a,b}，R(v:=c-1)={c}W(c:=a+b)={c}，W(v:=c-1)={v}4.1.4程序并发执行的条件若两个程序p1，p2满足如下条件，则能够保持可再现性，因而可以并发执行。该条件是1966年首先由Bernstein提出的，称为Bernstein条件。R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)=Φ4.1.4程序并发执行的条件例如，有如下四条语句：S1:a:=x+yS

8、2:b:=z+1S3:c:=a-bS4:w:=c+1R(S1)={x,y}，R(S2)={z}，R(S3)={a,b}，R(S4)={c}W(S1)={a}，W(S2)={b}，W(S3)={c}，W(S4)={w}可见，R(S1)∩W(S2)∪R(S2)∩W(S1)∪W(S1)∩W(S2)=Φ，因而S1和S2可以并发执行；而S1和S3不能并发执行，因为W(S1)∩R(S3)={a}；S2和S3也不能并发执行，因为W(S2)∩R(S3)={b}；同样，S3和S4不能并发执行，因为W(S3)∩R(S4)={c}。4.1.5与时间有关的错误例：图书借阅系统（x:某种