第2章进程管理(1)

第二章进程描述与控制•前趋图和程序设计•进程•进程间的相互作用•进程间的通信•进程调度（CPU调度）•线程2.1前趋图和程序设计•前趋图的定义•程序顺序执行•并发程序执行•多道程序设计2.1.1前趋图的定义前趋图(procedencegraph)是一个有向无环图DAG(directedacyclicgraph)。图中的每一个顶点可表示一条语句、一个程序段或进程,弧则表示两顶点之间的偏序(partialorder)或前趋关系(procedencerelation)。无前趋的顶点为初始顶点,无后继的顶点称为终止顶点,每个顶点还有一个权值,它表示顶点执行所需的时间。如1352467它的每一种拓扑排序都是顺序执行时正确得到结果的顺序,有路经的两顶点必须按前趋关系顺序执行,无路经的两顶点则可以并发执行。2.1.2程序顺序执行程序顺序执行：程序执行时,必须按某种先后次序,只有当前操作完成后才能执行后继操作,它体现了某种算法。如：S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;各程序段与此相同,以ICP分别代表输入计算和输出,则前趋图：前趋图S1S2S3I1C1P1I2C2P2程序顺序执行的特征：•程序执行的顺序性:严格按所规定的顺序执行•程序执行的封闭性独占资源,执行过程和结果不受其它程序的影响•程序结果的可再现性(结果的确定性)只要初始状态相同,程序多次重复运行,其结果与程序执行速度无关(连续或间断),结果都应相同。2.1.3程序并发执行及其特征1.多个程序的并发执行：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态微观上各程序交替地间断运行。I1I2I3I4C1C2C3C4P1P2P3P4前趋关系:Ii→Ci,Pi→Pi+1Ci→Pi,Ii→Ii+1Ci→Ci+1Ii+1,Ci,Pi-1是重叠的•举例说明:假如系统中有两道程序AA和BB：programAA;programBB;beginbegin…A←N…B←NN:=N+1;A←A+1N:=N+1;B←B+1…N←A…N←BEnd;end;intN=1;是AA和BB都能访问的外部公共变量,这两个程序在并发执行,N:=N+1;可分解为3条机器指令,它们的执行顺序不同有可能导致N的值结果不同。时间T0T1T2T3T4T5程序AA←NA←A+1N←A程序BB←NB←B+1N←BN的值112223(a)顺序执行时间T0T1T2T3T4T5程序A程序BN的值111122(b)交叉执行时间T0T1T2T3T4T5程序A程序BN的值111122(c)交叉执行N←BB←B+1B←NA←NA←A+1N←AA←NN←AA←A+1N←BB←B+1B←N2.并发执行特征：（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并发执行可再现的条件:(Bernstein1966年)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;S3和S4写集交集不为空所以，S1和S3、S2和S3、S3和S4不能并发执行。2.1.4多道程序设计应考虑的问题•在多道程序环境下如何向用户提供服务•在并发程序之间如何正确传递消息（通讯）•如何对CPU进行调度,保证相对公平地得到CPU（CPU是一个只可调度,不可分配的资源）•如何管理其他资源各任务对资源使用上发生冲突时,如何处理竞争。对CPU通过调度来解决竞争问题,而对于其他资源通过申请→分配→使用→回收的办法进行管理。2.2进程•进程的概念•进程的状态及其转换•进程控制块（ProcessControlBlock）•进程的特征2.2.1进程的概念1.进程的定义：Process从不同的角度对进程的各种定义•进程是程序的一次执行•进程是可以和别的计算并发执行的计算•进程是一个数据结构及能在其上进行操作的程序•进程是程序及其数据在处理机上顺序执行的活动•进程是程序在某一数据集合上的运行过程进程是可以并发执行的程序在某个数据集合上的运行过程，是系统进行资源分配和调度的独立单位。•结构性：由程序+数据+进程控制块组成了进程实体,称之为进程映像。进程控制块是进程存在的标志。•动态性进程是进程实体的执行过程,它由创建而产生,由调度而执行,因某事件而暂停,由撤销而消亡。在生命周期内,进程在三种基本状态之间动态转换•并发性多个进程同时存于内存中,一起向前推进,并发执行•独立性进程是独立获得资源和独立调度的基本单位•异步性各进程都各自独立的不可预知的速度向前推进2.进程的基本特征3.程序与进程之间的区别：•进程更能真实地描述并发，而程序不能•进程是由程序、数据和进程控制块三部分组成的•程序是静态的，进程是动态的•进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的•一个程序可对应多个进程，反之亦然•进程具有创建其他进程的功能，而程序没有2.2.2进程的基本状态及其转换1.进程的三种基本状态：•运行态(Running):执行态进程占有CPU，并在CPU上运行。•就绪态(Ready):进程已经具备运行条件,但由于CPU忙而暂时不能运行的状态(当调度给其CPU时,立即可以运行)。•阻塞态(Blocked):等待态、封锁态、冻结态、睡眠态进程因等待某种事件的发生而暂时不能运行的状态。(即使CPU空闲,该进程也不可运行)。进程在生命期内处于且仅处于三种基本状态之一不同系统设置的进程状态数目不同。2.进程状态转换：在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换。①就绪→运行调度：调度程序选择一个新的进程运行②运行→就绪超时：运行进程用完时间片被中断,在抢占调度方式中,因为一高优先级进程进入就绪状态③运行→阻塞I/O请求：当进程发生I/O请求或等待某事件时④阻塞→就绪I/O完成：当I/O完成或所等待的事件发生时运行就绪阻塞进程的三种基本状态及其转换I/O完成P31图2-53.进程的挂起状态某些系统还增加了挂起状态，它引入的原因：由于终端用户、父进程及操作系统的需要,要将某进程静止下来不接受调度,增加了静止阻塞(Blockeds阻塞挂起)和静止就绪(Readys就绪挂起)态,原阻塞和就绪改称为活动阻塞(Blockeda)和活动就绪(Readya)态。1)运行或活动就绪→静止就绪,活动阻塞→静止阻塞通过挂起原语(suspend)2)静止就绪→活动就绪,静止阻塞→活动阻塞通过激活原语(activate)3)静止阻塞→静止就绪:当等待的事件发生时静止就绪静止阻塞超时执行活动就绪活动阻塞调度事件发生I/O完成事件发生I/O完成七状态进程模型终止创建释放许可RunningReadySuspendBlockedSuspendReadyBlockedDisatchTimeoutEventOccursEventOccursExitNewReleaseAdmit2.2.3进程控制块1.进程控制块的作用：系统为管理进程设置一个专门的数据结构—进程控制块(ProcessControlBlock),用它来记录进程的外部特征，描述进程的运动变化过程(从结构的观点上看,程序与进程的区别就在于有没有PCB)。进程与PCB一一对应,在进程的整个生命期内,PCB随进程的创建而产生随进程的终止而消失,系统利用PCB来控制和管理进程,系统根据PCB感知进程的存在,所以PCB是进程存在的唯一标志。存放控制进程所需的数据(进程属性)。2.PCB中的信息：•进程标识信息•处理器状态信息(现场信息)•进程调度信息•进程控制信息记录了进程的全貌，作为进程调度和进程控制的依据和操作对象。1)进程标识符(在PCB中)进程标识符用于唯一地标识一个进程•外部标识符由创建者提供，由字符、数字组成•内部标识符为了方便系统而设置，OS中，每个进程有唯一的标识符（PID）2)处理器状态信息(现场信息)进程走走停停必须保存处理器的状态信息即处理器现状,它由处理器寄存器内容组成。•通用寄存器(8—32个,RISC结构中超过100个)•指令计数器(下一条指令的地址)•状态寄存器(程序状态字PSW,如:EFLAGS寄存器)•用户栈指针(过程和系统调用参数及地址)3)进程调度信息调度信息•进程状态(如:运行，就绪，阻塞...)•进程优先级•该进程在等待的事件(阻塞原因)•调度所需其它信息(如:等待总时间,执行总时间)4)进程控制信息•程序和数据的地址程序和数据所在的内存(段/页表指针)或外存地址•进程间同步和通信机制需要的消息队列指针和信号量等•所需的和已分配到的资源清单及使用情况除CPU外的资源:文件，I/O设备...它们的时间使用史•数据结构信息进程可能需要有指向其他PCB的指针,父-子进程关系及其它结构3.进程控制块的组织方式PCB表:系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度（注:多道程序中的道数与系统并发度不同）PCB表组织方式有两种：链接方式、索引方式1)链接方式：对具有相同状态的进程，分别各自链接起来组成进程PCB链队列：运行队列、就绪队列、阻塞队列、空闲队列空闲指针运行指针就绪指针等待1指针等待2指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......6751821152)索引方式：对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址空闲指针运行指针就绪指针等待1指针等待2指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......342765CPU就绪队列阻塞队列1时间片完进程调度事件1出现后备队列完成阻塞队列2事件2出现阻塞队列3事件n出现…...等待事件1等待事件2等待事件n……