操作系统第2章 进程管理

第二章进程管理2.1进程的基本概念2.2进程的控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程主要内容目的和要求通过本章的学习，使学生掌握并理解进程的概念，理解进程的基本状态及其转换的典型原因，掌握进程生命周期内的创建与撤消、阻塞与唤醒、挂起与激活等操作的执行过程，并理解和掌握进程的同步机制。重点和难点1、多道程序设计；2、进程和并发执行；3、进程的同步机制；4、线程的概念。2.1进程的基本概念2.1.1程序的顺序执行及其特征程序：一个在时间上按严格次序、顺序执行的操作序列程序的顺序执行：一个具有独立功能的程序独占处理机，直至得到最终结果的过程操作：数据处理的一种规则，一经启动就需要在有限时间内完成计算：若干操作严格顺序执行的集合1.程序的顺序执行一个具有独立功能的程序独占处理机，直至得到最终结果的过程；通常一个程序可分为若干程序段，它们必须按照一定的顺序执行，仅当前趋操作执行后才能执行后继操作；如果用前趋图描述各程序段的执行顺序，则呈线性结构。顺序性一个程序的各个部分的执行，严格地按照某种先后序执行封闭性程序在封闭的环境下运行，即程序运行时独占全部系统资源，资源的状态只有本程序改变。2.顺序执行的特征可再现性只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果3.性能评价优点：程序的顺序执行为程序的调试带来很大方便缺点：资源利用率不高2.1.2前趋图1.定义前趋图是有向无环图，记为DAG前趋图中的每个结点可以表示一条语句、一个程序段或一个进程结点间的有向边表示两个结点之间存在的偏序或前趋关系→＝{(Pi,Pj)|在Pj开始前Pi必须完成}如果（Pi，Pj）∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继2.说明前趋图中不能出现环路前趋图可用来表示语句、程序段或进程之间执行的先后顺序如果Pi→Pj，则Pi必须先于Pj执行如果PiPj，则Pi和Pj可以任意顺序执行2.1.3程序并发执行及其特征1.并发环境在一定时间内物理机器上有两个或两个以上的程序同处于开始运行、但尚未结束的状态，并且起始时间、推进速度、结束时间均是不可预知的2.程序的并发执行是指多个程序的执行在时间上是重叠的如果不同程序的若干程序段使用的资源不同且不存在合作关系，则允许同时执行如果用前趋图描述多个程序的各程序段的执行顺序，则呈网状结构并发执行举例例1输入、计算、打印三个程序对一批作业进行处理时，存在以下的前趋关系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1在Pi-1和Ci以及Ii+1之间，可以并发执行I1I2I3I4C1C2C3C4P1P2P3P4例2对于具有下述四条语句的程序段：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b3.并发执行的特征间断性程序并发执行时，由于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约失去封闭性程序并发执行时，多个程序共享系统资源，资源的状态由多个程序改变，运行环境失去封闭性。不可再现性由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性。例如：程序A和程序B共享变量NA：N=N+1;B：Print（N）；N=0；由于执行速度不同，导致执行结果各异４.性能评价优点：提高资源利用率和系统吞吐量缺点：容易出现与时间有关的错误不可再现性是不允许的！必须通过Berstein条件的限制，保证程序在异步环境下的执行结果是确定的。读集R(Pi)：为程序Pi在执行期间所需参考的所有变量的集合写集W(Pi)：为程序Pi在执行期间所要改变的所有变量的集合程序P1和P2能够并发执行，应满足Bernstein条件：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}Berstein条件2.1.4进程的特征与状态1.进程的定义与特征【进程的定义】进程是程序的一次执行进程是程序在数据集合上的一次运行过程进程是进行资源分配和调度执行的独立单位；进程由程序段、数据段和PCB三部分组成【进程的特征】思考：进程与程序的区别?结构特征为了控制和管理进程，系统为每个进程设置进程控制块—PCB，进程由PCB、程序段和数据段组成动态性进程的实质是程序的一次执行过程，因此，动态特征是进程最重要的特征并发性没有为之建立进程的程序是不能并发执行的，仅当为之建立一个进程后才能参加并发执行独立性进程是资源分配的基本单位，也是调度执行的独立单位异步性由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进作业是向计算机提交的任务实体，而进程是用户任务的执行实体一个作业可由多个进程组成，但必须至少由一个进程组成，反之不然作业的概念主要用在批处理系统中，而进程的概念用于所有的多道系统中*进程与作业的区别*2.进程的三种基本状态就绪状态当进程分配到除CPU以外所有必要的资源，只要再获得CPU即可运行的状态处于就绪状态的进程排成就绪队列等待进程调度执行状态已获得CPU且正在运行的状态单处理机系统只有一个处于运行状态的进程阻塞状态正在执行的进程因发生某事件而暂停执行的状态，也称等待或睡眠状态将处于阻塞状态的进程按阻塞原因排成不同的阻塞队列引起阻塞的事件消失后，进程不会立即恢复到执行状态，而转变为就绪状态等待重新调度执行就绪阻塞进程的状态及转换进程的状态及转换①就绪—执行：CPU空闲，引起进程调度②执行—就绪：当前进程的CPU被剥夺（2种）③执行—阻塞：当前进程因等待某个事件而无法执行，主动放弃CPU④阻塞—就绪：阻塞进程等待的事件出现，被唤醒到就绪队列，再次竞争CPU3.挂起状态引入挂起状态的原因终端用户的请求父进程的请求负荷调节的需要操作系统的需要——处于挂起状态的进程是静止的进程状态的转换——通过挂起原语将进程由活动状态变为静止状态：活动就绪→静止就绪：处于静止就绪状态的进程不再被调度执行；活动阻塞→静止阻塞：处于静止阻塞状态的进程在期待的事件出现后，从静止阻塞变为静止就绪；处于执行状态的进程被挂起后，变为静止就绪状态，不再参与调度。——通过激活原语将进程由静止状态变为活动状态：静止就绪→活动就绪：处于静止就绪状态的进程变为活动就绪状态，等待进程调度；静止阻塞→活动阻塞：静止阻塞状态的进程变为活动阻塞状态，等待期待的事件发生而进入就绪队列。具有挂起状态的进程状态图4.创建状态和终止状态创建状态已分配了PCB已填写了进程标识符等信息尚未送入就绪队列（比如内存不足）——增加管理的灵活性终止状态PCB从所在队列移出暂时由辅助程序保留以便收集数据尚未撤消PCB——进行记账信息的收集终止创建就绪阻塞执行许可释放等待事件进程的五种基本状态及其转换2.1.5进程控制块PCB1.PCB的作用系统为了管理进程设置的数据结构，存放了用于描述进程情况和控制进程运行所需的全部信息系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的２.PCB的内容描述信息内部标识符：系统赋予进程的数字序号外部标识符：创建者提供和使用的标识符家族关系：父进程、子进程标识符，以及用户标识符mainA1A2A3A21现场信息——运行时，保存在CPU中；中断时，保存在PCB中。通用寄存器：暂存中间结果等；指令计数器PC：下一条指令的内存地址；程序状态字PSW：条件码、中断允许位、中断屏蔽字等；用户栈指针：指向存放过程和系统调用的参数及断点地址的栈顶。调度信息进程状态进程优先级各种计时信息事件（阻塞原因）控制信息程序和数据起始地址进程同步和通信信息资源清单链接指针３.PCB的组织方式链接方式（队列）按进程状态分别组成执行队列、就绪队列、等待队列索引方式(表)按进程状态分别建立索引表，表明PCB在PCB表中的地址按链接方式组织PCBPCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......空PCB运行态就绪态等待1等待26751015按索引方式组织PCB队列管理队列数据结构：指向队首的表指针三个队列：运行队列、就绪队列、等待队列排队方式：排队首、排队尾、插队出队方式:队首出队、队中出队队列管理:中断之后，进程调度之前进程控制主要是对系统中所有进程，从创建到撤销的全过程实行的管理和控制进程控制一般由OS的内核通过执行各种原语操作实现2.2进程控制加在硬件上的第一层软件，通过执行各种原语操作实现控制和管理功能，具有进程管理、资源管理、中断处理等功能内核内核执行的特点由中断驱动的:中断→内核→退出内核执行是连续的内核使用特权指令是由若干条机器指令构成，用以完成特定功能的一段程序原语是原子操作，要么全做，要么全不做原子性通过关中断实现原语*进程上下文*进程执行活动全过程的静态描述包括各种寄存器和堆栈的值、正文段、数据集和PCB结构PCB各种控制表指针各种寄存器正文集数据集栈区2.2.1进程的创建1.进程图是描述进程的家族关系的有向树（PCB）一个结点代表一个进程，一条弧代表进程之间的父子关系根结点为该家族的祖先【引入进程图的目的】子进程继承父进程的资源子进程撤销时，向父进程归还资源父进程撤销时，同时撤销所有的子进程【进程图和前趋图】前趋图描述的是任务(或进程)之间的前趋关系,只有在前趋进程完成后，其后继进程才能运行进程图描述进程的创建者和被创建者之间的关系，它们可以并发执行，也可以父进程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要2.引起进程创建的事件用户登录：分时用户登录作业调度：批处理作业调度提供服务：用户请求系统服务(如打印)应用请求：父进程创建子进程3.进程的创建申请空白PCB，分配进程标识符；为新进程分配内存资源；初始化进程控制块初始化标识符信息（该进程、父进程）初始化处理机状态信息（PC、栈指针）初始化处理机控制信息（进程状态、优先级）将新进程插入就绪队列1.引起进程终止的事件正常结束批处理作业发出暂停（Halt）指令用户退出登录进程执行一终止服务请求2.2.2进程的终止异常结束越界错误；保护错；非法指令；特权指令错；运行超时；等待超时；算数运算错I/O故障。外界干预操作系统干预；父进程请求；父进程终止。2.进程的终止过程按标识符查找该进程，读取进程状态；若该进程处于执行状态,立即终止并置调度标志为真，引起新的进程调度；若该进程有子孙进程，则终止子孙进程运行；将该进程的所有资源，归还给父进程或系统；将该进程的PCB从所在队列移出，等待搜集信息，并撤销该进程的PCB。2.2.3进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件请求系统服务无法获得服务，进程主动阻塞；服务完成，由服务释放进程唤醒阻塞进程。启动某种操作进程主动阻塞，等待操作完成；操作完成，由中断处理程序唤醒阻塞进程。合作数据尚未到达合作进程的数据尚未到达，等待进程阻塞；新数据到达，由合作进程唤醒阻塞进程。无新工作可做系统进程无新工作可作，主动阻塞；新工作到达时，系统进程被唤醒。2.进程阻塞过程停止进程的执行，将进程状态由执行改为阻塞；按照阻塞原因将PCB插入相应的阻塞队列；引起新的进程调度并进行进程切换。（保存老现场，设置新现场）3.进程唤醒过程将唤醒进程的PCB从阻塞队列移出；将进程状态由阻塞改为就绪；将PCB插入就绪队列。例1父进程：创建子进程1和子进程2，并输出字母‘a’；子进程1：输出字母‘b’子进程2：输出字母‘c’系统调用fork()：创建子进程pid=fork（）；pid=-1：子进程创建失败pid=0：子进程创建成功，并运行子进程pid0：子进程创建成功，但运