进程描述与控制 前趋图和程序设计 进程 进程间的相互作用 进程间的通信 进程调cpu调 线程.pptxVIP

进程描述与控制 前趋图和程序设计 进程 进程间的相互作用 进程间的通信 进程调CPU调 线程;2.1 前趋图和程序设计;2.1.1 前趋图的定义;2.1.2 程序顺序执行;程序顺序执行的特征： 程序执行的顺序性:严格按所规定的顺序执行 程序执行的封闭性 独占资源,执行过程和结果不受其它程序的影响 程序结果的可再现性(结果的确定性) 只要初始状态相同,程序多次重复运行,其结果与程序执行速度无关(连续或间断),结果都应相同。;2.1.3 程序并发执行及其特征; 举例说明: 假如系统中有两道程序AA和BB： program AA; program BB; begin begin … A←N … B←N N:=N+1; A←A+1 N:=N+1; B←B+1 … N←A … N←B End; end; int N=1; 是AA和BB都能访问的外部公共变量,这两个程序在并发执行, N:=N+1;可分解为3条机器指令,它们的执行顺序不同有可能导致N的值结果不同。;时间 T0 T1 T2 T3 T4 T5;2.并发执行特征： （1）在并发环境下程序的执行是间断性的 执行——停——执行 （2）失去封闭性 并发程序共享系统中的资源,资源状态将由多个程序改变, 某程序执行过程和结果会受其它程序的影响。 （3）程序结果的不可再现性 由于失去封闭性, 并发程序执行的结果不可再现, 与其执行的相对速度有关, 是不确定的。 （4）相互制约性（2） 并发的程序之间相互制约 可分为直接制约和间接制约; 间接制约关系, 是因为共享使用户斥资源引起的 例如: 系统中并发执行的程序段 A 和 B 在运行过程中都希望使用打印机输出计算结果, 若系统只有一台打印机, 分得打印机的程序段 ( 假设A得到 ) 可以继续运行, 而没有得到打印机的程序段B 就不得不暂停, 等到有可用打印机时才能继续执行。 直接制约关系, 是由于各并发执行的程序段之间需要协调共同完成同一个任务而引起的。 例如: 某程序段A在运行过程中要在某些同步点上等待另一程序段 B 为它提供消息, 在未获得消息前, A 处于等待状态, 获得消息后, A才能继续运行。;(5) 程序与CPU执行的活动之间不再一一对应 程序与CPU执行的活动, 这是两个不同的概念; 程序是完成某一特定功能的指令序列, 是静态的概念; 而CPU 执行的活动是一个动态概念, 它是程序的执行过程。程序在顺序执行(即单道运行)时, 程序与CPU执行的活动是一一对应的, 而在程序并发执行(即多道程序)时, 这种关系不再存在。 例如, 在分时系统中, 多个用户都调用C编译对自己的源程序进行编译, 实际系统只保留一个编译程序, 多个用户通过共享执行它完成各自源程序的编译工作。;3.并发执行的条件(保持可再现性)： 引入并发是为了提高资源利用率, 从而提高系统效率 (注意并发与并行概念的区别) 。但必须在一定的条件下才能保持它们的可再现性。 例如: S1 : a:=a+x; S2 : b:=x+1; S3 : c:=a-b; S4 : c:=x; S1和S2、S1和S4、S2和S4能并发执行 S1和S3、S2和S3、S3和S4不能并发执行;定义： R(p)={a1, a2, …am,} 程序p引用的所有变量集合(读集) W(p)={b1,b2, …bn,}程序p要改的所有变量集合(写集) 程序p1和p2并发执行可再现的条件: ( Bernstein 1966年) R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={ } 即两程序之间写集的交集和读集与写集的交集都为空 S1 : a:=a+x; S1和S2,S1和S4,S2和S4能并发 S2 : b:=x+1; S3 : c:=a-b; S1和S3、S2和S3读写交集不为空 S4 : c:=x;