25第二章进程管理

第二章进程管理(1)第二章进程管理2.1前驱图和程序执行为了更好地描述程序的顺序执行和并发执行情况，引入前驱图的概念。•前趋图是一个有向无循环图，用于描述进程间执行的先后关系。图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边或前趋关系(Precedence_Relation)“→”。•→＝{(Pi,Pj|在Pj开始前Pi必须完成}如果Pi,Pj∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继。前趋图中必须不存在循环。2.1.1前驱图P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={P1,P2,P1,P3,P1,P4,P2,P5,P3,P5,P4,P6,P4,P7,P5,P8,P6,P8,P7,P9,P8,P9}2.1.2程序的顺序执行及特征•1.程序的顺序执行（只适用于单道程序）–程序段之间的顺序执行例如：进行计算。I:输入操作C:计算操作P:打印操作。–程序语句的顺序执行I1C1P1I2C2P2S1：a:=x+y；S2：b:=a-5；S3：c:=b+1；S1S2S32.程序的顺序执行时的特征•顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行；•封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源；•可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。2.1.3程序并发执行及特征1.并发环境在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的2.程序的并发执行在对一批程序进行处理时，可以并发执行。例如：输入、计算、打印三个程序对一个作业进行处理时执行顺序为：Ii→Ci→Pi.对一批作业进行处理时，存在以下的前趋关系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1I1I2I3I4C1C2C3C4P1P2P3P4例如：下述四条语句的程序段，S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b3.程序的并发执行的特征•间断性:由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约。•失去封闭性：程序并发执行时共享资源相互间有影响。•不可再现性：由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性。(例P35)例子一•进程A、B共享变量•N，初始值为5;•进程A•N=N+1;•进程B•Print(N)•N=0;•按照执行•N的值nn+10•按照执行•N的值n01•按照执行•N的值nn+10例子二•进程A.......•r=N;•r=r-1;•N=r;•...........进程B............r=N;r=r-1;N=r;...............售票进程A、B共享余票数变量N，N的初始值为20;2.2进程的描述2.2.1.进程的定义和特征1.定义为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。为了使参与并发的每一个程序都能独立运行，为之配置了一个专门的数据结构——进程控制块（ProcessControlBlock,PCB)•进程实体：PCB、程序段、数据段•对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。2.进程的特征•结构特征：为了控制和管理进程，系统为每个进程设立一个进程控制块——PCB。•动态性：进程的实质是程序的一次执行过程，•并发性：任何进程都可以同其他进程一起向前推进•独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；•异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进3.进程与程序的区别•程序是静态的，进程是动态的;•进程更能真实地描述并发,而程序不能;•一个程序可对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程。反之亦然，即一个进程可以涉及到一个或几个程序的执行。•进程有生命周期，有诞生有消亡，是短暂的；而程序是相对长久的;•程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的；•进程是系统分配调度的独立单位，能与其他进程并发执行;•从结构上看每个进程实体都含有程序段和相应的数据段两部分，这一特征与程序的含义相近。•进程具有创建其他进程的功能，而程序没有。2.2.2进程的基本状态及转换•1.进程的三种基本状态–就绪状态：进程已获得除CPU以外的所有必要资源。–执行状态：进程正在CPU上运行。–阻塞状态：正在执行的进程因某种事件而暂时无法继续执行。2.三种基本状态的转换运行就绪阻塞时间片用完/高优先级抢占进程调度等待I/O或其它事件I/O或其它事件完成•创建状态–已为进程分配了PCB，但所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。•终止状态–进程结束（自然结束或异常结束）时要进入终止状态。不可调用执行，但在操作系统中保留一份记录。3.创建状态和终止状态进程五态模型及其转换事件发生运行态就绪态等待态调度时间片到等待事件创建态终止态许可释放2.2.3.挂起操作和进程状态的转换•进程挂起的原因：1终端用户的请求2父进程的请求3负荷调节的需要4操作系统的需要具有挂起操作的进程状态转换图图2－5具有挂起状态的进程状态演变图具有创建、终止、挂起的进程状态图2.2.4.进程管理中的数据结构进程控制块（PCB）•1、进程控制块的作用系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。进程控制块的作用（续）(1)作为独立运行基本单位的标志。(2)能实现间断性运行方式。(3)提供进程管理所需要的信息。(4)提供进程调度所需要的信息。(5)实现与其它进程的同步与通信。2、进程控制块中的信息•1进程标识符–内部标识–外部标识•2处理机状态–通用寄存器–指令计数器–程序状态字–用户堆栈•3进程调度信息进程控制块中的信息（续）–进程的状态–进程优先级–调度算法–调度事件•4进程控制信息–程序和数据地址–进程同步和通信–资源清单–连接指针（加）5家族联系：用于说明本进程与其它家族成员间的关系。3、进程控制块的组织方式线性方式、链接方式组织PCB(队列)、索引方式。1）线性方式2）链接方式组织PCB3）索引方式2.3进程控制2.3.1操作系统内核进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。内核与原语•原语–是由若干条机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断.•内核的基本功能–支撑功能：中断处理、时钟管理、原语操作–资源管理功能：进程管理、存储器管理、设备管理进程控制创建、撤消以及完成进程各状态之间的转换。由具有特定功能的原语完成。进程创建原语：create进程撤消原语:exit/terminate阻塞原语:block唤醒原语:wakeup挂起原语:suspend激活原语:active2.3.2进程的创建1、进程的层次结构在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。2、进程图进程图是一棵有向树(如下图)，用于描述进程间的关系，结点代表进程。一棵树表示一个家族，根结点为该家族的祖先(Ancestor)。ˇˇˇˇˇˇˇ进程图3、引起创建进程的事件•1用户登录•2作业调度•3请求服务•4应用请求4、进程创建•使用进程创建原语创建一个具有指定标识符的进程，主要是创建进程控制块PCB。步骤如下：•申请空白PCB，并赋予一个统一进程标识符•分配资源：为进程映象分配空间•初始化进程控制块：初始化标识信息、CPU状态信息、进程状态信息等。•将进程插入就绪队列：设置相应的链接，把新进程加到就绪队列的链表中。创建原语的实现过程2.3.3进程的终止•当一个进程需要结束时，用进程终止原语撤消一个指定的进程，收回进程所占有的资源，撤消该进程的PCB。入口信息是被撤消的进程名。1、引起进程终止的事件（原因）•1正常结束•2异常结束（越界错、保护错、非法指令、特权指令错、运行超时、等待超时、算术错、I/O故障等）•3外界干预（操作员或操作系统干预、父进程请求、父进程终止）2、进程的终止过程•1找到要终止进程的PCB，读取进程的状态•2立即终止•3终止其所有子进程•4释放资源•5将PCB移出队列、等待其他进程来搜集信息。2.3.4进程阻塞与唤醒处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。1、引起进程阻塞和唤醒的事件(1)向系统请求共享资源失败。(2)等待某种操作的完成。(3)新数据尚未到达。(4)等待新任务的到达。2、进程阻塞过程•1进程停止执行、保存CPU现场•2改变状态•3插入相应阻塞队列•4调度进程重新调度进程的阻塞原语•阻塞原语的实现过程3、进程唤醒过程•1从阻塞队列中移出该进程•2改变状态•3插入到就绪队列2.3.5进程的挂起与激活•1、进程的挂起–挂起原语的功能•可将自身挂起、或挂起具有指定标识符的进程、或将其全部或部分“子孙”挂起。–进程挂起的过程•1查进程当前状态•2修改状态•3对换进程映像的非常驻部分到外存，将其PCB复制到指定内存区域。4若被挂起的进程正在执行，则调度程序重新调度•2、进程的激活–激活原语功能•激活指定进程或子进程，使处于静止状态的进程变为活动。–进程激活的过程•1将进程映像非常驻部分调入内存，并检查进程当前状态•2修改状态•3插入相应的队列•4若采用抢占调度策略，要检查是否需要重新调度。2.4进程的同步•问题的引入在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。•进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作。2.4.1进程同步的基本概念1.进程间的制约关系1）间接相互制约关系2）直接相互制约关系2.临界资源：在一段时间内只允许一个进程访问的资源（如：打印机、磁带机；共享变量、数据结构和缓冲区）3.临界区：访问临界资源的那段代码程序段1程序段2程序段n共享变量临界区1临界区2临界区n•售票系统（数据库中的票数x,另x=5）r=xr=r-1x=r•如果不加以控制，会导致错误。•对临界资源的访问要互斥•各进程互斥进入临界区访问临界资源4.同步机制应遵循的规则（使用临界区的原则）1)空闲让进2)忙则等待3)有限等待4)让权等待2.4.2硬件同步机制用特殊的硬件指令来实现对临界区的管理，将临界区的标志看做一个锁，初始锁是开的，进入临界区时，测试锁的状态，如果锁未开，则等待直到锁开；否则，如果锁开，立即将其立即锁上，防止其他进程进入临界区1.关中断在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。2.利用Test-and-Set指令实现互斥这是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实