第二讲进程管理

1、第二讲 进程管理中国科学技术大学计算机系中国科学技术大学计算机系 陈香兰陈香兰Fall 2013内容提要内容提要v多道程序技术和程序并发执行的条件v进程的定义v进程的状态v进程的描述v进程的控制内容提要内容提要v多道程序技术和程序并发执行的条件多道程序技术和程序并发执行的条件v进程的定义v进程的状态v进程的描述v进程的控制多道程序技术多道程序技术v从单道多道内存必须被多个“程序”共享CPU必须被多个“程序”复用操作系统必须具备4大基本功能：l处理器管理l内存管理lI/O管理l文件管理容易混淆的几个基本术语容易混淆的几个基本术语vProgram，程序；Tasks，任务Jobs，作业；Proces

2、ses，进程v本课程中关于上述几个术语的界定程序：静态的代码序列，通常以文件为存储介质。代码可以是高级语言的、汇编语言的、指令序列等等。任务：泛指。作业：批处理系统中，等待装入内存执行的用户程序和数据。进程：已经被装载到内存中运行的程序及其外延多道程序技术的难点多道程序技术的难点v与单道相比，在多道系统中，进程之间的运行随着调度的发生而具有无序性，那么如何保证正确的并发。v相关理论：程序并发执行的条件理论模型：前驱图基于前驱图的程序顺序执行分析基于前驱图的程序并发执行分析Precedence Graph 前驱图前驱图v目的：准确的描述语句、程序段、进程之间的执行次序v前驱图前驱图是一个有向无环

3、图DAG（Directed Acyclic Graph）结点：一个执行单元（如一条语句、一个程序段或进程） （有向）边：前驱关系“”，(Pi,Pj)|Pi必须在Pj开始执行前执行完若(Pi,Pj) ，可写成PiPj其中，称Pi是Pj的前驱，而Pj是Pi的后继v没有前驱的结点称为初始结点（initial node）没有后继的结点称为终止结点（final node）v结点上使用一个权值（weight）表示该结点所含的程序量或结点的执行时间v前驱图举例：123865749程序的顺序执行程序的顺序执行v 一个较大的程序通常包含若干个程序段。程序必须按照某种先后顺序逐个执行。例如 其中，I代表用户程序和

4、数据的输入；C代表计算；P代表输出结果v 在一个程序段中，多条语句也存在顺序执行的问题 S1：ax3 S2：by4 S3：cab S4：dacI1C1P1I2C2P2S1S2S3S4S1S2S3S4按照语句依赖关系按照语句依赖关系若按指令地址顺序执行若按指令地址顺序执行程序顺序执行时的特征程序顺序执行时的特征v顺序性v封闭性v可再现性程序的并发执行程序的并发执行I1C1P1I2C2P2I1C1P1I2C2P2I3C3P3I4C4P4程序并发执行时的特征程序并发执行时的特征v间断性间断性并发程序“执行暂停执行执行”v失去封闭性失去封闭性由于资源共享，程序之间可能出现相互影响的现象v不可再现性不可

5、再现性原因同上。举例：变量N的共享，设某时刻Nn，则若执行顺序为：lN:N1；print(N); N:=0; N的值依次为n1；n1；0lprint(N); N:=0; N:N1； N的值依次为n；0；1lprint(N); N:N1；N:=0; N的值依次为n；n1；0程序程序Arepeat N:=N+1;程序程序Brepeat print(N);N:=0;程序并发执行的条件程序并发执行的条件(Bernstein条件条件)v在上述3个特性中，必须防止“不可再现性”。v为使并发程序的执行保持“可再现性”，引入并发执行的条件。思路：分析程序或语句的输入信息和输出信息，考察它们之间的相关性符号和术

6、语定义：l读集R(pi)，表示程序pi在执行时需要参考的所有变量的集合l写集W(pi)，表示程序pi在执行期间要改变的所有变量的集合1966， Bernstein：若两个程序p1和p2满足下列条件，则它们就能并发执行，且具有可再现性R(p1) W(p2) R(p2) W(p1) W(p1) W(p2) 内容提要内容提要v多道程序技术和程序并发执行的条件v进程的定义进程的定义v进程的状态v进程的描述v进程的控制进程进程v进程需要使用某种方法加以描述，原因进程运行的间断性，要求在进程暂停运行时记录该程序的现场，以便下次能正确的继续运行资源的共享，要求能够记录进程对资源的共享情况为保证程序“正确”的

7、并发执行，必须将进程看成某种对象，对其进行描述并加以控制v引入进程控制块PCB进程的实体：程序段数据段PCB进程的定义进程的定义v汤子瀛，计算机操作系统，二版是“可并发执行的程序在一个数据集合上的运行过程”是进程实体的运行过程vSilberschatz，Operating System Concepts，7th“A process is a program in execution”进程的进程的2大基本属性大基本属性v进程是可以独立独立运行的基本单位。v有2大基本属性进程是一个可以拥有资源的独立单位进程是一个可以独立调度和分派的基本单位进程的进程的5大特征大特征 vs. 程序程序v动态性：最基

8、本的特性动态性：最基本的特性具有一定的生命期由创建而产生，由调度而执行；因得不到资源而阻塞；由撤消而消亡。程序只是一组有序指令的集合，存放在某种介质上，是静态的v并发性：最重要的特征并发性：最重要的特征多道并发，不仅是进程也是OS的重要特征程序本身不能并发执行，必须“变成”进程后才能并发v独立性独立性是独立运行、调度、资源分配的基本单位；v异步性进程按各自独立的、不可预知的速度向前推进进程之间是异步的对于“不可再现性”，需要采取某些措施来保证进程之间的协调运行v结构特性具有结构性，由程序段、数据段及进程控制块三部分构成，称“进程映像”内容提要内容提要v多道程序技术和程序并发执行的条件v进程的定

9、义v进程的状态进程的状态v进程的描述v进程的控制进程的状态进程的状态v根据进程的动态特性，进程在整个生命期中将会出于不同的状态。v状态模型最基本的“三状态”模型引入“新”和“终止”态的“五状态”模型引入“挂起”状态的“七状态”模型“三状态三状态”模型模型v三种最基本的状态就绪状态 “万事具备，只欠CPU” 就绪队列执行状态阻塞（等待、睡眠）状态l等待原因：1）发出I/O指令之后，等待I/O操作的完成2）等待某个事件发生3）等待分配到资源等等l阻塞（等待）队列，通常按照原因，有多个“五状态五状态”模型模型v在三种基本状态中，引入新状态：进程刚创建，但还没有进入就绪队列l需要进程初始化，分配一些预

10、设资源等等终止状态：进程已经（正常/异常）结束，已经从就绪队列中移出，但尚未撤销l需要将进程暂时留在系统中，以便其他进程去收集该进程的相关信息状态转换图状态转换图Ready queuewait queues六种转换关系六种转换关系“七状态七状态”模型模型v进程因自身内部的一些原因，无法继续运行时，暂时进入“等待”状态，当等待的原因消除后，就可以返回就绪状态；v但有时候会因为进程外部的一些原因，使得进程暂时不能继续运行。外部原因主要有终端用户的需要父进程的需求操作系统的需要对换的需要负载调节的需要v引入“挂起”状态v“挂起”状态不是一种状态，而是一类状态挂起后处于静止状态：静止就绪，静止阻塞非挂

11、起的活动状态：活动就绪，活动阻塞，还包括执行态v在状态转换中，增加了从活动状态与静止状态之间，以及静止状态内部之间的状态转换状态转换图状态转换图执行执行活动活动就绪就绪静止静止就绪就绪活动活动阻塞阻塞静止静止阻塞阻塞激活激活挂起挂起激活激活挂起挂起释放释放释放释放挂起挂起请求请求I/O新增新增6种状态转换种状态转换调度调度 中断中断另外一个视图另外一个视图对换引入的中期调度对换引入的中期调度v作业调度：长期调度v对换：引起中期调度多道数过高，引起内存不足v进程调度：短期调度Mid-term schedulerv Select which process to swap in & out

12、 Swapping Remove processes from memory, & reintroduce processes into memory Reduce the degree of multiprogramming, WHY?内容提要内容提要v多道程序技术和程序并发执行的条件v进程的定义v进程的状态v进程的描述进程的描述v进程的控制进程控制块进程控制块PCBv进程控制块是操作系统中的一种关键数据结构由操作系统进程管理模块维护常驻内存v操作系统根据PCB来控制和管理并发执行的进程vPCB是进程存在的唯一标志进程控制块中的进程控制块中的4大类信息大类信息v 进程标识符信息： 外

13、部标识 vs 内部标识v 处理机的状态信息，即硬件上下文CPU registers: Architecture-specific PC: Address of the next instruction 通用寄存器 程序状态字 用户堆栈指针PointerProcess stateProcess numberProgram counterRegistersMemory limitsList of open files.v调度信息 Process state，Priority, queue pointers, v进程控制信息Memory-management information lBase &a

14、mp; limit, page/segment tables, Accounting information lTime used/limits, account numbers, process NO, I/O status informationlAllocated devices, open files, 同步和通信信息进程控制块的组织方式进程控制块的组织方式v在内存中的位置：操作系统数据区，位于内核中v常用的2种组织方式：链接方式索引方式v根据组织在一起的进程控制块的状态以及对应进程的状态的不同就绪队列阻塞队列空闲队列等执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针空

15、闲队列指针空闲队列指针执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针链接方式链接方式索引方式索引方式进程在不同队列中的迁移进程在不同队列中的迁移v Dispatch Select a process to executev While running, events: Issue an I/O request Create a new sub-process & wait for its termination Interrupt occurredv Process migrates between queues调度引起的上下文切换调度引起的上下文切换vSaving

16、the state of the old process, &loading the saved state for the new oneContext (上下文) of a process is represented in its PCBContext-switch timelOverhead (系统开销)lNo usefullTime or speed architecture-specific (11000ms), & Depends on other components (E.X.: memory management)Occurs only in kernel

17、mode进程切换引起的时空感觉上的混乱进程切换引起的时空感觉上的混乱v用户在宏观上：并发；间断vCPU在微观上：串行；连续；空间变化v程序在功能上：完整，连续；空间不变v操作系统在进程管理上：时空交错内容提要内容提要v多道程序技术和程序并发执行的条件v进程的定义v进程的描述v进程的状态v进程的控制进程的控制进程控制进程控制v进程控制是操作系统进程管理功能的一部分，由操作系统内核实现v操作系统内核运行在内核态，用户程序运行在用户态内核态，系统态l具有较高的特权，能执行一切指令，能访问所有寄存器和存储区用户态，l具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区v用户程序不能执行OS特权指

18、令，不能直接访问OS区域进程控制原语进程控制原语v进程的创建和进程的终止v进程的阻塞和唤醒v进程的挂起与激活v进程关系图：用于描述进程家族关系的有向树结点：进程若进程1创建了进程2，则1是2的父进程，2是1的子进程l使用从1到2的有向边表示进程的“父子关系”l父进程的父进程：祖父进程l树的根结点为进程家族的祖先进程树示意图进程树示意图P1P2P3P4P5P6P7P8P9P10P11P12UNIX中的经典进程树中的经典进程树父子之间的关系父子之间的关系v 资源共享关系 Parent and children share all resources Children share subset of parents resources Parent and child share no resourcesv 并发执行关系 Parent and children execute concurrently Parent waits until children terminatev 地址空间关系 Child duplicate of parent. Child has a program loaded into it.v UNIX examples Fork system call creates new proc