操作系统第二章(1).ppt

1、1,第二章 进程管理,2,2.1 进程的基本概念,引入,操作系统的基本特性是什么？,并发和共享,并发和共享意味着什么？,在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源,并发和共享会引起哪些问题？,对资源的竞争、运行程序之间的通信、程序之间的合作与协同等等,要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。,3,2.1 进程的基本概念2.1.1 程序的顺序执行及其特征,1、程序的顺序的概念 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。 例如：,4,2.1 进

2、程的基本概念2.1.1 程序的顺序执行及其特征,2、程序顺序执行的特征 顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。 封闭性 程序一旦开始执行，其执行结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。 结果的可再现性 程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。,5,2.1 进程的基本概念2.1.2 前趋图（Precedence Graph）,1、概念： 前趋图：是一个有向无循环图，记为DAG（Directe

3、d Acyclic Graph), 用于描述进程之间执行的前后关系。 结点（Node）：描述一个程序段或进程，甚至一条语句。 初始结点（Initial Node）：没有前趋的结点。 终止结点（Final Node）：没有后继结点。 有向边（-）：表示两结点间的偏序（Partial Order）或前趋关系（Precedence Relation）。 重量（Weight）：表示结点所含有的程序量或结点的执行时间。也称为权值。,6,2.1 进程的基本概念2.1.2 前趋图（Precedence Graph）,2、描述： -=（Pi，Pj）| Pi must complete before Pj ma

4、y start Pi - Pj： Pi是Pj的直接前趋， Pj是Pi的直接后趋。,前趋关系： P1-P2，P1-P3，P1-P4，P2-P5，P3-P5，P4-P6，P5-P6 表示为: P=P1,P2,P3, P4,P5, P6 -=(P1,P2)，(P1,P3)，(P1,P4)，(P2,P5)，(P3,P5)，(P4,P6)，(P5,P6),7,2.1 进程的基本概念2.1.3程序的并发执行及其特征,1 . 程序的并发执行 例： 在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi (i=1,2,3,.,n)。 这些作业系统中执行时是对时间的偏序，有些操作

5、必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。,8,2.1 进程的基本概念 2.1.3 程序的并发执行及其特征,Ii、Ci、Pi的执行顺序如何？,Ii-Ci-Pi,P1与I2，C1与I2,I3与P1的执行顺序如何？,可以同时执行的。,9,2.1 进程的基本概念2.1.3程序的并发执行及其特征,1 . 程序的并发执行 定义: 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。,10,2.1 进程的基本概念2.1.3程序的并发执行及其特征,2 . 程序并发执行的描

6、述 cobegin S1;S2;S3;.;SN coend; Si(i=1,2,3,.,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrence的头两个字符。 这是Dijkstra提出的。,11,2.1 进程的基本概念2.1.3程序的并发执行及其特征,假设有一个程序由 S0Sn+1个语句， 其中 S1Sn语句是并发执行的,程序如下: S0; cobegin S1;S2;S3;.;SN; coend Sn+1;,12,2.1 进程的基本概念2.1.3程序的并发执行及其特征,算法： 输入：f 输出：g while (f 不

7、为结束符） input ; output ; ,3、并发执行的实行: 誊抄,一个循环程序顺序执行的誊抄,由这个程序完成誊抄工作会不会出错? NO,13,2.1 进程的基本概念2.1.3程序的并发执行及其特征,设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。缓冲区只存放一个字符.输出程序从缓冲区中取数据，送标准设备输出。,3、并发执行的实行: 誊抄,两个程序并发执行完成誊抄,14,2.1 进程的基本概念2.1.3程序的并发执行及其特征,算法： cobegin while (f不为结束符）/* 输入程序段 */ input; /

8、* 从标准输入设备读入一个数据 */ send; /* 将读入的数据送到bufferf */ while(buffer不为空） /* 输出程序段 */ receive; /* 从bufferf中取数据 */ output; /* 送打印机输出 */ coend ,15,2.1 进程的基本概念2.1.3程序的并发执行及其特征,这两个程序段并发执行时可能出现如下情况： 输出程序运行的速度比输入程序快时，有些输出会重复； 如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。 输入程序执行的速度比输出程序快时，有些数

9、据会丢失； 如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。,16,2.1 进程的基本概念2.1.3程序的并发执行及其特征,get程序负责从输入序列f中读取字符并送到缓冲区s中; copy程序把缓冲区s中的数据复制到缓冲区t中去; put程序从缓冲区t中取出数据打印。,3、并发执行的实行: 誊抄,三个并发执行程序的誊抄,17,2.1 进程的基本概念2.1.3 程序的并发执行及其特征,这个算法是正确与否? YES,算法: 输入:f 输出:g if (f不为结束符) get(s,f); while() t=s; co

10、begin put(t,g); get(s,f); coend ,假设有两个缓冲区，每个缓冲区只存放一个字符，get程序负责从输入序列f中读一个字符，然后，送到缓冲区s中，copy程序负责将s中的字符复制到t中，put负责从t中提取字符打印。,18,2.1 进程的基本概念2.1.3 程序并发执行的特征,间断(异步)性：走走停停，一个程序可能走到中途停下来，失去原有的时序关系； 失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：当处理机已被某个程序占有时，另一程序必须等待 不可再现性：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。,19,2.1 进程的

11、基本概念2.1.4 进程(process)的特征与状态,1、 进程的特征和定义 在多道程序设计的环境下，为了使程序能并发执行，并描述和控制并发执行的程序，必须引人新的概念进程。 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫作任务（task)。,20,2.1 进程的基本概念2.1.4 进程(process)的特征与状态,1、 进程的特征和定义 进程的特征 结构特征：程序段、数据段和进程控制块（PCB）(也称进程映像, 进程要素)构成进程实体；通常所说的创建/撤消进程实体，实质上是创建/撤消其PCB 动态性：进程的实质是进程实体的一

12、次执行过程，是动态的。 并发性：多个进程实体同时存在内存中，能在同一段时间内同时运行 独立性：各进程的地址空间相互独立，除非采用进程间通信手段； 异步性：进程按各自独立的、不可预知的速度（异步）向前推进,21,2.1 进程的基本概念2.1.4 进程(process)的特征与状态,B.进程的定义（枚举法） 行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。 进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan) 进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw) 进程是执行中的程序。（Ken

13、 Thompson and Dennis Ritchie ) 有的教材上给出的进程的定义： 进程，即是一个具有一定独立功能的程序关于某个数据集合的一次活动。,22,2.1 进程的基本概念2.1.4 进程(process)的特征与状态,C . 进程与程序的区别： 1)程序是指令的集合，是静态的概念。 进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。 2)进程是一个状态变化的过程,是有生命周期的;而程序则是永久的,可以长久保存。 3)进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）,而程序仅是代码的有序集合。 4）进

14、程与程序之间不是一一对应的。通过多次运行，同一程序可以对应多个进程；通过调用关系，一个进程可以包含多个程序,23,2.1 进程的基本概念2.1.4 进程(process)的特征与状态,C . 进程与程序的区别与联系（续）： 例子：光盘（CD、VCD） 光盘（程序） 放光盘的活动（进程）,24,2.1 进程的基本概念2.1.4 进程(process)的特征与状态,2.进程的三种基本状态 进程的基本状态 进程在系统中的活动规律是： 执行 - 暂停 - 执行 进程的三种基本状态： 就绪状态 执行状态 阻塞状态（又称等待状态）,25,1 2.进程的基本概念2.1.4 进程(process)的特征与状态

15、,2.进程的三种基本状态(续) 1) 就绪状态（Ready) 存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所处的状态为就绪状态。（有多个进程处于此状态） 2) 执行状态(Running） 当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，总只有一个进程处于此状态） 3) 阻塞状态（Wait) 若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。,26,1 2.进程的基本概念2.1.4 进程(process)的特征

16、与状态,2.进程的三种基本状态（续） 进程状态变迁图 进程的状态不是固定不变的，而是在不断变换。,27,2.1 进程基本概念2.1.4 进程(process)的特征与状态,2.进程的三种基本状态（续） 进程状态变迁图说明: 运行 - 等待 等待某事件的发生（如等待I/O完成） 等待 - 就绪 事件已经发生（如I/O完成） 运行 - 就绪 时间片到（例如，两节课时间到，下课） 新建进程-就绪 新创建的进程进入就绪状态 就绪 - 运行 当处理机空闭时，由调度（分派）程序从就绪进程队列中选择一个进程占用CPU。,28,3其他状态： 创建状态终止状态挂起状态,2.1 进程基本概念2.1.4 进程(pr

17、ocess)的特征与状态,创建( 新new)状态 OS 已完成为创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未同意) 因为资源有限,29,终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而累计资源使用情况的财务程序 当数据不再需要后，进程(和它的表格)被删除,2.1 进程基本概念2.1.4 进程(process)的特征与状态,30,五状态进程模型,2.1 进程基本概念2.1.4 进程(process)的特征与状态,31,. 挂起状态（Suspend） a 挂起状态的

18、含义 把正在执行的或没有执行的进程挂起,使其处于静止状态 b引起挂起(静止)状态的原因: 终端用户请求 父进程请求 负荷调节需要 操作系统需要,2.1 进程基本概念2.1.4 进程(process)的特征与状态,32,2.1 进程基本概念2.1.4 进程(process)的特征与状态,c. 状态转换: 活动就绪(Readya)-静止就绪(Readys) (较少见) (就绪-就绪挂起 )用Suspend挂起 处于Readys状态的进程不再被调度执行 活动阻塞(Blockeda) -静止阻塞(Blockeds) (阻塞 -阻塞挂起)用Suspend挂起 静止就绪(Readys) -活动就绪(Rea

19、dya) (就绪挂起-就绪)用Active激活 静止阻塞(Blockeds) -活动阻塞(Blockeda) 用Active激活 静止阻塞(Blockeds) -静止就绪(Readys) 当等待的事件发生时 (状态信息已在OS中),33,2.1 进程基本概念2.1.4 进程(process)的特征与状态,七状态进程模型,34,2.1 进程基本概念2.1.5 进程控制块（PCB Process Control Block）,1.进程控制块的作用 A.概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 B.作用： 系统利用PCB来控制和管理进程，所以

20、PCB是系统感知进程存在的唯一标志 C.进程与PCB是一一对应的,35,2.1 进程基本概念2.1.5 进程控制块（Process Control Block）,2.进程控制块中的信息 A. 进程映像(进程要素) 用户程序 用户数据 栈 用于过程调用和参数传递 进程控制块PCB (执行上下文) 控制进程所需的数据(进程属性) ，包括: 进程标识符信息 处理器状态信息 进程调度信息 进程控制信息,36,2.1 进程基本概念2.1.5 进程控制块（Process Control Block）,B. PCB的内容： 调度信息： 调度和状态信息 进程状态 (如: 运行，就绪，阻塞.) 进程优先级 该进程在等待的事件 (若被阻塞) 其他信息 现场信息： 记录了重要的寄存器；(虚)时钟等内容,37,2.1 进程基本概念2.1.5 进程控制块（Process Control Block）,C. PCB中的信息 进程标识符:用于唯一标识一个进程 内部标识符:系统使用 外部标识符:用户访问进程使用 用户标识:与某个作业对应的用户,38,2.1 进程基本概念2.1.5 进