[理学]04新2.ppt

第四章 互斥、同步与通讯 4.1并发进程(concurrent processes) 4.2进程互斥(mutual exclusion) 4.3进程同步(synchronization)（重点） 4.4进程高级通讯(communication) 4.1并发进程 4.1.1前趋图的定义 前趋图（precedence graph） 有向无环图，图中每个结点表示一个语句、一个计算步骤、或一个进程。 结点间的有向边表示偏序或前趋（precedence relation)关系“→” 。 →={（Pi，Pj）| Pj启动之前Pi必须已经完成}。 （Pi，Pj）∈→可记作Pi→Pj, 称Pi是Pj的前趋，Pj是Pi的后继。 在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。 每个结点可以有一个权重(weight)，它可以表示该结点所包含的程序量或计算时间。 4.1并发进程 前趋图的例子 P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P5，P4→P6，P5→P7，P6→P7 4.1.2顺序程序及其特性 4.1.2.1 程序的顺序执行 (1)内部顺序性：对于一个进程来说，它的所有指令是按序执行的。 S1：a:=x+y S2：b:=a-z S3：c:=a+b S4：d:=c+5 4.1.2顺序程序及其特性 (2)外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。 例: 输入(I)、计算(C)、打印(P)三个活动构成的进程，每个进程的内部活动是顺序的，即Ii→Ci→Pi，多个进程的活动也是顺序的。 4.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； 4.1.3 并发程序及其特性 4.1.3.1 程序的并发执行 (2)外部并发性: 指多个程序活动的重叠执行。 4.1.3 并发程序及其特性 4.1.3.2 并发程序的特性 （1）并发性：程序并发执行对应某一种交叉，不同的交叉可能导致不同的计算结果，操作系统应当保证只产生导致正确结果的交叉，去除那些可能导致不正确结果的交叉。 （2）非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响。 （3）不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果。 4.1.3 并发程序及其特性 不可再现性的例子 进程P： 进程Q： A1: N=0； B1: PRINT（N）； A2: N=:N+1； B2: N:=0； A3: GOTO A2； B3: GOTO B1； 此例中进程P累积计数，进程Q将累计的结果打印出来。希望打印出的数是累计数的和。 两个进程并发执行时有许多可能的交叉: 如进程P循环5次进程Q循环1次，然后进程P又循环3次进程Q循环1次，则输出结果是5，3； 如进程P循环2次进程Q循环1次，然后进程P又循环6次进程Q循环1次，则输出结果是2，6。两次执行结果完全不同。 进程Q执行完B1后被中断，进程P对N执行加1操作，然后进程Q执行B2，在这种情况下进程P的累计数将被丢失。 4.1.4 程序并发执行的条件 在失去封闭性的条件下，保持可再现性。 R(pi)={a1,a2,…,am}表示程序pi在执行期间所需读取的所有变量的集合，称为“读集”； W(pi)={b1,b2,…,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+y S2: b:=z+1 S3: c:=a-b S4: w:=c+1 R(S1)={x,y}，R(S2)={z}，R(S3)={a,b}，R(S4)={c} W(S1