中科大操作系统原理与实现课件3_Processes0.pdf

.操作系统原理与设计第3章 Processes（进程）1陈香兰中国科学技术大学计算机学院2009年09月01日.提纲多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.多道程序技术I从单道多道I内存必须被多个“程序”共享ICPU必须被多个“程序”复用I操作系统必须具备4大基本功能：I处理器管理I内存管理II/O管理I文件管理.容易混淆的几个基本术语IProgram，程序；Tasks，任务Jobs，作业；Processes，进程I本课程中关于上述几个术语的界定I程序：静态的代码序列，通常以文件为存储介质。代码可以是高级语言的、汇编语言的、指令序列等等。I任务：泛指。I作业：批处理系统中，等待装入内存执行的用户程序和数据。I进程：已经被装载到内存中运行的程序及其外延.多道程序技术的难点I与单道相比，在多道系统中，进程之间的运行随着调度的发生而具有无序性，那么I如何保证正确的并发?I相关理论：I程序并发执行的条件I理论模型：前趋图I基于前趋图的程序顺序执行分析I基于前趋图的程序并发执行分析.Precedence Graph 前驱图 II目的：准确的描述语句、程序段、进程之间的执行次序Definition前趋图是一个有向无环图DAG（Directed Acyclic Graph）I结点：一个执行单元（如一条语句、一个程序段或进程）I（有向）边：前驱关系“”，=(Pi,Pj)|Pi必须在Pj开始执行前执行完I若(Pi,Pj)，可写成Pi Pj其中，称Pi是Pj的前驱，而Pj是Pi的后继.Precedence Graph 前驱图 III没有前趋的结点称为初始结点（initial node）I没有后继的结点称为终止结点（final node）I结点上使用一个权值（weight）表示该结点所含的程序量或结点的执行时间I前趋图举例：.Precedence Graph 前驱图 III.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.程序的顺序执行 II一个较大的程序通常包含若干个程序段。程序在执行时，必须按照某种先后顺序逐个执行，仅当前一个程序段执行完，后一个程序段才能执行。例如I其中II代表用户程序和数据的输入；IC代表计算；IP代表输出结果I在一个程序段中，多条语句也存在执行顺序的问题。在下面的例子中，S1和S2必须在S3执行前执行完。类似的，S4必须在S3执行完才能执行。IS1：ax3.程序的顺序执行 IIIS2：by4IS3：cabIS4：dac.程序顺序执行时的特征I顺序性I封闭性I可再现性.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.程序的并发执行IPi与Ii+1之间不存在内在的前趋关系I程序并发执行时的前趋图.程序并发执行时的特征I间断性I并发程序“执行暂停执行执行”I失去封闭性I由于资源共享，程序之间可能出现相互影响的现象I不可再现性I原因同上。I举例：变量N的共享，设某时刻Nn，则若执行顺序为：1.N:N1；print(N);N:=0;N的值依次为n1；n1；02.print(N);N:=0;N:N1；N的值依次为n；0；13.print(N);N:N1；N:=0;N的值依次为n；n1；0.程序并发执行的条件(Bernstein条件)I在上述3个特性中，必须防止“不可再现性”。I为使并发程序的执行保持“可再现性”，引入并发执行的条件。I思路：分析程序或语句的输入信息和输出信息，考察它们的相关性I符号和术语定义：I读集R(pi)，表示程序pi在执行时需要参考的所有变量的集合I写集W(pi)，表示程序pi在执行期间要改变的所有变量的集合I1966，Bernstein：若两个程序p1和p2满足下列条件，则它们就能并发执行，且具有可再现性R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.I进程需要使用某种方法加以描述，原因I进程运行的间断性，要求在进程暂停运行时记录该程序的现场，以便下次能正确的继续运行I资源的共享，要求能够记录进程对资源的共享情况I为保证程序“正确”的并发执行，必须将进程看成某种对象，对其进行描述并加以控制.Process Concept IIAn OS executes a variety of programs:IBatch system jobsITime-shared systems user programs or tasksIProcessIa program in execution;Iprocess execution must progress in sequential fashionA process includes:Itext sectionIprogram counter+other registersIstack?Idata section?Iheap?.Process Concept IICOMPARE:Program vs.Process?I静态的 vs 活动的IProcess in Memory.Process Concept III.进程的五大特征 I1.动态性“它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤销而消亡”I具有生命期I最基本的特性2.并发性I多道I即是进程也是OS的重要特征3.独立性I进程是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位。4.异步性I进程按各自独立的、不可预知的速度向前推进。I导致“不可再现性”.进程的五大特征 IIIOS必须采取某种措施来保证各程序之间能协调运行。5.结构特征.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.Process StateI根据进程的动态特性，进程在整个生命期中将会处于不同的状态。状态模型I最基本的“三状态”模型I引入“新”和“终止”态的“五状态”模型I引入“挂起”状态的“七状态”模型.“三状态”模型.I三种最基本的状态I就绪状态（ready）I“万事具备，只欠CPU”I就绪队列I执行状态（running）I阻塞（等待、睡眠）（waiting）状态。等待原因：1.发出I/O指令之后，等待I/O操作的完成2.等待某个事件发生3.等待分配到资源等等I阻塞（等待）队列，通常按照原因，有多个.“五状态”模型I在三种基本状态中，引入I新状态（new）：进程刚创建，但还没有进入就绪队列I需要进程初始化，分配一些预设资源等等I终止状态（terminated）：进程已经（正常/异常）结束，已经从就绪队列中移出，但尚未撤销I需要将进程暂时留在系统中，以便其他进程去收集该进程的相关信息.Diagram of Process StateI进程的状态转换图I6种转换关系.“七状态”模型 II进程因自身内部的一些原因，无法继续运行时，暂时进入“等待”状态，当等待的原因消除后，就可以返回就绪状态；I但有时候会因为进程外部的一些原因，使得进程暂时不能继续运行。外部原因主要有I终端用户的需要I父进程的需求I操作系统的需要I对换的需要I负载调节的需要I引入“挂起”状态I“挂起”状态不是一种状态，而是一类状态I挂起后处于静止状态：静止就绪，静止阻塞I非挂起的活动状态：活动就绪，活动阻塞，还包括执行态.“七状态”模型 III在状态转换中，增加了从活动状态与静止状态之间，以及静止状态内部之间的状态转换.“七状态”模型 III.Outline多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.Process Control Block(PCB)II进程控制块（Process Control Block，PCB）是操作系统中的一种关键数据结构I由操作系统进程管理模块维护I常驻内存I操作系统根据PCB来控制和管理并发执行的进程PCB是进程存在的唯一标志.IInformation associated witheach processIProcess state(.)IProgram counterICPU registersICPU scheduling informationIMemory-managementinformationIAccounting informationII/O status information.CPU Switch From Process to Process.ExamplesI观察：I数据结构I状态Istruct task struct in Linux0.11&Linux 2.6.26Istruct OS TCB in C/OS-II.小结多道程序技术和程序并发执行的条件多道程序技术的难点程序的顺序执行程序的并发执行Process Conceptthe ProcessProcess StateProcess Control Block(PCB)小结和作业.作业I程序的顺序执行和并发执行有什么异同之处？I什么是Bernstein条件？I对于下面的语句：S1：a=5 x;S2：b=a x;S3：c=4 x;S4：d=b+c;S5：e=d+31.画出前趋图2.证明S2和S3是可以并发执行的，而S3和S4是不能并发执行的。I阅读至少2本操作系统相关书籍，给出这些书中关于进程的定义，要列出出处。I阅读linux-0.11的内核代码，找到其进程数据结构加以分析。说明linux-0.11中进程的状态及其转换关系。.谢谢！