第二讲进程管理

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

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

＝{(Pi,Pj)|Pi必须在Pj开始执行前执行完}若(Pi,Pj)∈，可写成PiPj

其中，称Pi是Pj的前驱，而Pj是Pi的后继没有前驱的结点称为初始结点（initialnode）

没有后继的结点称为终止结点（finalnode）结点上使用一个权值（weight）表示该结点所含的程序量或结点的执行时间前驱图举例：123865749程序的顺序执行一个较大的程序通常包含若干个程序段。程序必须按照某种先后顺序逐个执行。例如其中，I代表用户程序和数据的输入；C代表计算；P代表输出结果在一个程序段中，多条语句也存在顺序执行的问题S1：a＝x＋3S2：b＝y＋4S3：c＝a＋bS4：d＝a＋cI1C1P1I2C2P2S1S2S3S4S1S2S3S4按照语句依赖关系若按指令地址顺序执行程序顺序执行时的特征顺序性封闭性可再现性程序的并发执行I1C1P1I2C2P2×I1C1P1I2C2P2I3C3P3I4C4P4程序并发执行时的特征间断性并发程序“执行－－暂停执行－－执行”失去封闭性由于资源共享，程序之间可能出现相互影响的现象不可再现性原因同上。举例：变量N的共享，设某时刻N＝n，则若执行顺序为：N:＝N＋1；print(N);N:=0;N的值依次为n＋1；n＋1；0print(N);N:=0;N:＝N＋1；N的值依次为n；0；1print(N);N:＝N＋1；N:=0; N的值依次为n；n＋1；0程序A

repeatN:=N+1;程序B

repeatprint(N);N:=0;程序并发执行的条件(Bernstein条件)在上述3个特性中，必须防止“不可再现性”。为使并发程序的执行保持“可再现性”，引入并发执行的条件。思路：分析程序或语句的输入信息和输出信息，考察它们之间的相关性符号和术语定义：读集R(pi)，表示程序pi在执行时需要参考的所有变量的集合写集W(pi)，表示程序pi在执行期间要改变的所有变量的集合1966，Bernstein：若两个程序p1和p2满足下列条件，则它们就能并发执行，且具有可再现性R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)＝{}内容提要多道程序技术和程序并发执行的条件进程的定义进程的状态进程的描述进程的控制进程进程需要使用某种方法加以描述，原因进程运行的间断性，要求在进程暂停运行时记录该程序的现场，以便下次能正确的继续运行资源的共享，要求能够记录进程对资源的共享情况为保证程序“正确”的并发执行，必须将进程看成某种对象，对其进行描述并加以控制引入进程控制块PCB进程的实体：程序段＋数据段＋PCB进程的定义汤子瀛，计算机操作系统，二版

是“可并发执行的程序在一个数据集合上的运行过程”

是进程实体的运行过程Silberschatz，OperatingSystemConcepts，7th

“Aprocessisaprograminexecution”进程的2大基本属性进程是可以独立运行的基本单位。有2大基本属性进程是一个可以拥有资源的独立单位进程是一个可以独立调度和分派的基本单位进程的5大特征vs.程序动态性：最基本的特性具有一定的生命期由创建而产生，由调度而执行；因得不到资源而阻塞；由撤消而消亡。程序只是一组有序指令的集合，存放在某种介质上，是静态的并发性：最重要的特征多道并发，不仅是进程也是OS的重要特征程序本身不能并发执行，必须“变成”进程后才能并发独立性是独立运行、调度、资源分配的基本单位；异步性进程按各自独立的、不可预知的速度向前推进进程之间是异步的对于“不可再现性”，需要采取某些措施来保证进程之间的协调运行结构特性具有结构性，由程序段、数据段及进程控制块三部分构成，称“进程映像”内容提要多道程序技术和程序并发执行的条件进程的定义进程的状态进程的描述进程的控制进程的状态根据进程的动态特性，进程在整个生命期中将会出于不同的状态。状态模型最基本的“三状态”模型引入“新”和“终止”态的“五状态”模型引入“挂起”状态的“七状态”模型“三状态”模型三种最基本的状态就绪状态“万事具备，只欠CPU”就绪队列执行状态阻塞（等待、睡眠）状态等待原因：

1）发出I/O指令之后，等待I/O操作的完成

2）等待某个事件发生

3）等待分配到资源

等等阻塞（等待）队列，通常按照原因，有多个“五状态”模型在三种基本状态中，引入新状态：进程刚创建，但还没有进入就绪队列需要进程初始化，分配一些预设资源等等终止状态：进程已经（正常/异常）结束，已经从就绪队列中移出，但尚未撤销需要将进程暂时留在系统中，以便其他进程去收集该进程的相关信息状态转换图Readyqueuewaitqueues六种转换关系“七状态”模型进程因自身内部的一些原因，无法继续运行时，暂时进入“等待”状态，当等待的原因消除后，就可以返回就绪状态；但有时候会因为进程外部的一些原因，使得进程暂时不能继续运行。外部原因主要有终端用户的需要父进程的需求操作系统的需要对换的需要负载调节的需要引入“挂起”状态“挂起”状态不是一种状态，而是一类状态挂起后处于静止状态：静止就绪，静止阻塞非挂起的活动状态：活动就绪，活动阻塞，还包括执行态在状态转换中，增加了从活动状态与静止状态之间，以及静止状态内部之间的状态转换状态转换图执行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起释放释放挂起请求I/O新增6种状态转换调度中断另外一个视图对换引入的中期调度作业调度：长期调度对换：引起中期调度多道数过高，引起内存不足进程调度：短期调度Mid-termschedulerSelectwhichprocesstoswapin&outSwapping

Removeprocessesfrommemory,&

reintroduceprocessesintomemoryReducethedegreeofmultiprogramming,WHY?内容提要多道程序技术和程序并发执行的条件进程的定义进程的状态进程的描述进程的控制进程控制块PCB进程控制块是操作系统中的一种关键数据结构由操作系统进程管理模块维护常驻内存操作系统根据PCB来控制和管理并发执行的进程PCB是进程存在的唯一标志进程控制块中的4大类信息进程标识符信息：外部标识vs内部标识处理机的状态信息，即硬件上下文

CPUregisters:Architecture-specificPC:Addressofthenextinstruction通用寄存器程序状态字用户堆栈指针PointerProcessstateProcessnumberProgramcounterRegistersMemorylimitsListofopenfiles...调度信息Processstate，Priority,queuepointers,…进程控制信息Memory-managementinformationBase&limit,page/segmenttables,…AccountinginformationTimeused/limits,accountnumbers,processNO,…I/OstatusinformationAllocateddevices,openfiles,…同步和通信信息进程控制块的组织方式在内存中的位置：操作系统数据区，位于内核中常用的2种组织方式：链接方式索引方式根据组织在一起的进程控制块的状态以及对应进程的状态的不同就绪队列阻塞队列空闲队列等执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB918……PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针链接方式索引方式进程在不同队列中的迁移DispatchSelectaprocesstoexecuteWhilerunning,events:IssueanI/OrequestCreateanewsub-process&waitforitsterminationInterruptoccurredProcessmigratesbetweenqueues调度引起的上下文切换Savingthestateoftheoldprocess,&

loadingthesavedstateforthenewoneContext(上下文)ofaprocessisrepresentedinitsPCBContext-switchtimeOverhead(系统开销)NousefulTimeorspeedarchitecture-specific(1~1000ms),&Dependsonothercomponents(E.X.:memorymanagement)Occursonlyinkernelmode进程切换引起的时空感觉上的混乱用户在宏观上：并发；间断CPU在微观上：串行；连续；空间变化程序在功能上：完整，连续；空间不变操作系统在进程管理上：时空交错内容提要多道程序技术和程序并发执行的条件进程的定义进程的描述进程的状态进程的控制进程控制进程控制是操作系统进程管理功能的一部分，由操作系统内核实现操作系统内核运行在内核态，用户程序运行在用户态内核态，系统态具有较高的特权，能执行一切指令，能访问所有寄存器和存储区用户态，具有较低特权，只能执行规定的指令，访问指定的寄存器和存储区用户程序不能执行OS特权指令，不能直接访问OS区域进程控制原语进程的创建和进程的终止进程的阻塞和唤醒进程的挂起与激活进程关系图：用于描述进程家族关系的有向树结点：进程若进程1创建了进程2，则1是2的父进程，2是1的子进程使用从1到2的有向边表示进程的“父子关系”父进程的父进程：祖父进程树的根结点为进程家族的祖先进程树示意图P1P2P3P4P5P6P7P8P9P10P11P12UNIX中的经典进程树父子之间的关系资源共享关系ParentandchildrenshareallresourcesChildrensharesubsetofparent’sresourcesParentandchildsharenoresources并发执行关系ParentandchildrenexecuteconcurrentlyParentwaitsuntilchildrenterminate地址空间关系Childduplicateofparent.Childhasaprogramloadedintoit.UNIXexamplesForksystemcallcreatesnewprocessExecvesystemcallusedafteraforktoreplaceth