一年级上册生字描红.xls

第四章互斥、同步与通讯
并发进程(concurrent processes)
进程互斥(mutual exclusion)
进程同步(synchronization)
munication)


前趋图(precedence graph)
有向无环图,图中每个结点表示一个语句、一个计算步骤、或一个进程。
结点间的有向边表示偏序或前趋(precedence relation)关系“→”。
→={(Pi,Pj)| Pj启动之前Pi必须已经完成}。
(Pi,Pj)∈→可记作Pi→Pj, 称Pi是Pj的前趋,Pj是Pi的后继。
在前趋图中,没有前趋的结点称为初始结点,没有后继的结点称为终止结点。
每个结点可以有一个权重(weight),它可以表示该结点所包含的程序量或计算时间。

前趋图的例子
P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P5,P4→P6,P5→P7,P6→P7
1
4
3
2
6
5
7

程序的顺序执行
(1)内部顺序性:对于一个进程来说,它的所有指令是按序执行的。
S1:a:=x+y
S2:b:=a-z
S3:c:=a+b
S4:d:=c+5
S1
S2
S3
S4

(2)外部顺序性:对于多个进程来说,所有进程的活动是依次执行的。
例: 输入(I)、计算(C)、打印(P)三个活动构成的进程,每个进程的内部活动是顺序的,即Ii→Ci→Pi,多个进程的活动也是顺序的。
I1
C1
P1
I2
C2
P2

:
(1)连续性: 指令逐条执行
(2)封闭性: 不受其它程序及外界因素影响
(3)可再现性: 结果与推进速度无关
并发程序及其特性
程序的并发执行
(1)内部并发性: 指一个程序内部的并发性。例:
S1:a:=x+2;
S2:b:=y+4;
S3:c:=a+b;
S4:d:=c+6;
S5:e:=c-d;
2
1
4
3
5
并发程序及其特性
程序的并发执行
(2)外部并发性: 指多个程序之间的并发性。
I1
I2
I3
I4
C1
C2
C3
C4
P1
P2
P3
P4
并发程序及其特性