操作系统 第二章 进程管理

中国民航大学冯霞在现代OS中，“进程”和“资源”是两个最重要的概念，进程是程序的一次执行。从进程的观点看，OS的一切活动都是围绕着进程服务而展开的，通过为进程服务而达到为用户服务的目的。CPU是最重要的系统资源，处理机管理的主要内容是处理机调度，而处理机分配和运行又是以进程为基本单位，故对处理机的管理可归结为对进程的管理，进程管理是OS中最重要、最复杂的管理。进程的基本概念进程控制进程同步经典进程的同步问题进程通信线程人类的擅长——逻辑程序（代码、数据）计算机的擅长——数字运算（指令、逻辑关系）OS负责将逻辑程序转换为CPU动作,进程是这一转换过程的中间结构使用者程序和数据进程结构指令流程序的顺序执行：仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。程序顺序执行时的特征◦顺序性◦封闭性◦可再现性前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图P={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)}程序的并发执行P1P2P3P4I1I2I3I4C1C2C3C4Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1在Pi-1和Ci以及Ii+1之间，可以并发执行多个程序同时在系统中运行，这些程序的执行在时间上是重叠的，即前一程序的执行尚未结束，后一程序的执行已经开始。程序的并发执行间断性◦相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。失去封闭性◦某程序执行时，必然受到参与并发执行的其它程序的影响不可再现性◦计算结果与并发程序执行速度有关。即同一程序，使用相同输入、在相同环境下运行，却可能获得完全不同的结果。不可再现性的例子：􀂾两个并发执行的程序A和B，如下所示：A：N:=N+1；B：print（N）；N:=0；分析：1）并发：A、B交替占用CPU执行；2）异步性导致：CPU交替执行A、B的语句时顺序可能不同！设某次循环前，N的值为8,CPU执行顺序打印结果N的值1)N:=N+1;print(N);N:=0;902)print(N);N:=0;N:=N+1;813)print(N);N:=N+1;N:=0;􀂾80多道程序环境下，程序的执行属于并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征因此，通常的程序不能参加并发执行为此，引入“进程”为什么要有进程？引入进程后引入进程进程是一个具有一定独立功能的程序关于某个数据集合的一次可以并发执行的运行活动。计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。多道程序环境下，如何能使程序并发执行？如何对并发执行的程序加以控制和描述？进程和程序的区别很微妙想象一位好厨艺的科学家正在为女儿烘制生日蛋糕。有食谱，有原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，食谱就是程序(即用适当形式描述的算法)，科学家就是处理机(CPU)，各种原料就是输入数据。进程就是厨师阅读食谱、取来各种原料、以及烘制蛋糕的一系列动作的总和。现在假设科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。科学家就记录下他照着食谱做到哪儿了(保存进程的当前状态)，然后拿出一本急救手册，按照其中的指示处理螫伤。这里，我们看到处理机从一个进程(做蛋糕)切换到另一个高优先级的进程(实施医疗救治)，每个(进程)拥有各自的程序(食谱和急救书)。当蜜蜂螫伤处理完之后，科学家又回来做蛋糕，从他离开时的那一步继续做下去。关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。进程基本概念主妇阅读菜谱准备原料烹制菜肴饭菜阅读洗衣机手册准备衣服、洗衣粉设定参数，洗衣服干净衣服程序输入运行输出程序输入运行输出分时切换洗衣进程做饭进程进程的核心思想进程是某个程序在某个数据集合上的运行过程，它有程序、输入、输出和状态。在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。进程是程序的执行，属于动态，程序是静态的进程的存在是暂时的，程序的存在是永久的进程＝程序＋数据＋PCB(进程控制块，processcontrolblock)，即进程是一个程序及其数据在处理机上顺序地执行时所发生的活动。一个程序可以对应多个进程一个进程可以包含多个程序一个程序对应两个进程一个进程包括多个程序结构特征◦程序段、相关数据段和PCB（进程控制块）——进程实体动态性◦由创建而产生，由调度而执行，由撤销而消亡并发性◦进程的重要特征，操作系统的重要特征独立性◦独立运行、独立分配资源、独立接受调度异步性◦按各自独立、不可预知的速度向前推进进程执行时的间断性，决定了进程可能具有多种状态。◦运行态：正在占用CPU运行程序◦阻塞态：等待外部事件发生，无法占用CPU◦就绪态：可运行，但其他进程正在占用CPU运行态阻塞态就绪态进程就绪，可以运行状态转换：进程等待外部事件，阻塞OS决定由哪个进程占用CPU，进程调度？运行态变为就绪态强制终止某进程的运行（系统原因）运行态变为阻塞态运行进程等待外部事件发生（自身原因）阻塞态变为就绪态外部事件已经发生，可准备运行就绪态变为运行态停止其他进程运行后，运行该进程占用CPU问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？答案：三种状态的变换体现了OS的资源管理作用进程的核心思想在于运行——CPU资源的分配新（New）状态：是一个进程刚刚建立，但还未将它送入就绪队列时的状态。终止（Terminated）状态：一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消时的状态。挂起状态（暂停执行或不接受调度）◦终端用户的请求◦父进程请求◦负荷调节的需要（实时系统）◦操作系统的需要是一个进程刚刚建立，但还未将它送入就绪队列时的状态一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起请在并发运行示意图中标识程序A、B的状态重要的术语–Cocurrency&Parallel&MultiProgramming–Program&Process&Thread–Running&Ready&Block&Suspend–Dispatch&Activate&Suspend&Wake重要的思想–程序与进程：静态和动态的思想–多道程序：并发与互斥的思想–进程管理：杂七杂八好烦哪？为描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块。PCB（ProcessControlBlock），是进程实体的一部分，记录了操作系统所需的、用于描述进程当前状况以及控制进程运行的全部信息。OS是根据PCB来对并发执行的进程进行控制和管理的。进程控制块是进程存在的惟一标志。当系统创建一个进程时，必须为它设置一个PCB，然后根据PCB的信息对进程实施控制管理，进程任务完成时，系统收回它的PCB，进程也随之消亡。进程标识信息：PID,PPID用于惟一地标识一个进程。一个进程通常有两种标识符：1）内部标识符，数字标识符；2）外部标识符，它由创建者提供，描述进程的家族关系。处理器状态信息：PC,PSW,堆栈指针、寄存器进程调度信息：与进程调度和进程对换有关的信息，包括：进程状态、进程优先级、进程调度所需的其它信息、事件进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针思考：PCB是进程存在的唯一标志为什么？因为PCB1、包含了进程的描述信息和控制信息，2、是进程的动态特征的集中反映，3、系统根据PCB而感知某一进程的存在，所以PCB是进程存在的唯一标志。(只有在多任务即多道批处理系统中，才可能建立PCB结构，该系统才具有进程活动)链接方式PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针…系统中可能拥有数十个、数百个乃至数千个PCB，如何组织？索引方式执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针进程的基本概念进程控制进程同步经典进程的同步问题进程通信线程进程控制是指：进程的创建、撤消，进程状态转换的控制进程控制由进程控制原语、系统调用实现的为了对进程控制，系统中必须设置一个机构，它具有创建撤消以及进程通讯和资源管理等功能，这样结构称为OS的内核(kernel)。内核本身并非一个进程，而是硬件的首次延伸，即它是加到硬件上的第一层软件。内核是通过执行各种原语操作来实现各种控制和管理功能的。原语是机器指令的延伸，是用若干条机器指令构成的，用以完成特定功能的一段程序。为保证操作的正确性，原语在执行期间是不可分割的。(1)创建进程原语(2)撤消进程原语(3)挂起进程原语(4)解挂进程原语(5)阻塞进程原语(6)唤醒进程原语(7)调度进程运行原语(8)改变优先级原语进程图(ProcessGraph)：描述一个进程家族关系的有向树。结点表示进程有向边表示进程之间的父子关系根表示进程家族的祖先子进程可以继承父进程所拥有的资源DEFGHBCIJKLMA引起创建进程的事件(1)用户登录（分时系统）(2)作业调度（批处理系统）(3)提供服务（打印进程）(4)应用请求系统内核创建进程应用程序创建进程进程的创建步骤(CreationofProcess)调用进程创建原语Create（）(1)申请空白PCB(2)为新进程分配资源（内存等）(3)初始化进程控制块(4)将新进程插入就绪队列程序中的第语句是调用查找进程名过程“GetInternalName”，参数为进程外部名n。该过程查找PCB集合，如已有此同样外部名进程则返回出错消息，否则返回一个空闲的PCB内部标识号i。第语句是把进程外部名n登记到第i个PCB的相应外部名表目中。语句是往PCB中登记优先数。语句登记现场状态初始值S0到相应的现场保留区中或Cpustate中。procedureCreate(n,S0,k0,M0,R0)begin/请求分配PCB空间i:=GetInternalName(n);/初始化PCBId(i):=n;Priority(i):=k0;Cpustate(i):=S0;MainStore(i):=M0;Resources(i):=R0;Status(i):=ReadysParent(i):=CALLER/插入就绪队列Insert(RL,i);end建立进程原语的工作大致描述为