操作系统课件第四版第二章剖析

《操作系统课件第四版第二章剖析》由会员分享，可在线阅读，更多相关《操作系统课件第四版第二章剖析（172页珍藏版）》请在金锄头文库上搜索。

1、第二章 进程管理,第二章 进程的描述与控制,2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题 2.6 管程机制 2.7 进程通信 2.8 线程的基本概念 2.9 线程的实现,前趋图(Directed Acyclic Graph)是一个有向无循环图，记为DAG 。 前趋图用来描述程序各部分间的依赖关系或一个大的计算各子部分间的因果关系。,2.1 前趋图和程序执行 一、前趋图,前趋图中的元素: 结点：表示一个语句、程序段或进程 有向边 ： 表示结点间的偏序关系（前趋关系） 若(Pi , Pj) ，可写成 Pi Pj，称 Pi是 Pj的直接

2、前趋，而 Pj是Pi的直接后继。,前趋图示例,2,3,1,6,7,4,5,7个结点的前趋图,前趋关系 P1 P2, P1 P3 P1 P4, P2 P5 P3 P5, P4 P6 P5 P7, P6 P7,1. 程序的顺序执行 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，仅当前一操作(程序段)执行完后，才能执行后继操作。这种程序执行的方式就称为程序的顺序执行。,二、程序顺序执行,程序顺序执行举例,程序顺序执行前趋图,语句的执行顺序 S1：a=x+y S2：b=a-5 S3：c=b+1,2. 程序顺序执行时的特征 程序执行的顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必

3、须在下一个操作开始之前结束。 程序执行的封闭性 独占资源，执行过程中不受外界影响 程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同,三、程序并发执行 1. 程序的并发执行,并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。,程序并发执行举例 (程序并发执行前趋图),I1,I2,I3,I4,C1,C2,C3,C4,P1,P2,P3,P4,对于具有下述四条语句的程序段， 可画出如图所示的前趋关系。 S1: a= x+2 S2: b= y+4 S3: c= a+b S4: d= c+b,图 2-4 四条语句

4、的前趋关系,可以看出：S1和S2可以并发执行。,2. 程序并发执行时的特征 （1）在并发环境下程序的执行是间断性的 执行暂停执行 （2）程序结果失去封闭性 系统中资源被多个进程使用，其状态由多个程序来改变 （3）程序结果的不可再现性 并发程序执行的结果与其执行的相对速度有关，是不确定的,例：观察者/报告者 观察者： 报告者： begin begin repeat repeat wait a car go through delay a time N=N+1 Print N Until N=0 ； end until end,初始N=n时不同执行序列：,N=N+1 ； Print N ； N=0

5、 ；,结果各不相同:,Print N ； N=0 ； N=N+1 ；,Print N ； N=N+1 ； N=0 ；,打印n+1，N=0；,打印n，N=1；,打印n，N=0；,2.2 进程的描述,一、进程的定义和特征 1. 进程的定义 为了管理和控制进程，系统为每个进程设立一个进程控制块（PCB），这样从结构上看，每个进程实体都由程序段、相关的数据段和PCB三部分组成，也称“进程映像”。,进程的定义,进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,2. 进程的特征 （1）动态性 进程是程序执行过程，动态性是基本特征。动态性还表现在进程有生命期，有创建、执行、暂停、消亡的过程

6、。 程序是静态的概念，在机内外都存在，而进程只存在于系统内部，引入进程的目的就是为了使程序能并发执行。 （2）并发性 指多个进程实体同时存在于内存中，能在一段时间内同时运行（并发）。 并发性是进程的重要特征，也是操作系统的重要特征。,（3）独立性 指进程是一个能独立运行单位、独立分配资源和独立接受调度的基本单位。 （4）异步性 由于进程共享资源和相互合作形成了相互制约的关系，造成进程执行的间断性，使进程以各自独立的、不可预知的速度向前推进。,程序与进程之间的区别： 进程更能真实地描述并发，而程序不能； 进程是由程序和数据两部分组成的； 程序是静态的，进程是动态的； 进程有生命周期，有诞生有消亡

7、，是短暂的；而程序是相对长久的； 一个进程可以涉及到一个或几个程序的执行；反之一个程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程 。 进程具有创建其他进程的功能，而程序没有。,二、进程的基本状态及转换,1. 进程的三种基本状态 进程在生命消亡前处于且仅处于三种基本状态之一。 1) 执行态（Running）： 进程占有CPU，并在CPU上运行 2）就绪态（Ready）： 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行） 3）阻塞态（Blocked）：有时也称为等待状态 指进程因等待某种事件的发生而暂时不能运行的状态 （即使

8、CPU空闲，该进程也不可运行）,执行,就绪,阻塞,进程的状态及其转换,2. 三种基本状态的转换 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换。, 就绪执行 调度程序选择一个新的进程运行 执行就绪 执行进程用完了时间片 执行阻塞 发生某事件 阻塞就绪 事件完成,【思考题】,1如果一个单处理机系统中有n个进程并发执行，在不考虑程序状态过渡的情况下，执行的进程最多几个？最少几个？就绪进程最多几个？最少几个？阻塞进程最多几个？最少几个？ 2. 某一时刻，处于执行状态的进程为0个，且当前处理机空闲，处于就绪状态的进程有几个？ 3. 有没有这样的状态转换

9、，为什么？ 阻塞 执行； 就绪 阻塞 4. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能。,增加两种基本状态,创建( 新new)状态 OS 已完成为创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未同意) 因为资源有限,终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而累计资源使用情况的财务程序 - 当数据不再需要后，进程(和它的表格)被删除,挂起操作的引入 （1）终端用户的请求 （2）父进程请求 （3）负载调节的需要 （4）操作系统的需要,三、挂起操

10、作和进程状态的转换,2. 引入挂起原语操作后进程状态的转换,活动阻塞 静止阻塞 当所有进程都阻塞，OS会安排空间让一就绪进程进入内存 静止阻塞 活动阻塞 解除挂起命令 静止阻塞 静止就绪 当等待的事件发生时 (状态信息已在OS中) 静止就绪 活动就绪 当内存中没有就绪进程时 活动就绪 静止就绪 (较少见) 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时 执行 静止就绪,图 2-6 具有挂起状态的进程状态图,挂起命令可由进程自己或其他进程发出，而解除挂起命令只能由其他进程发出。,具有挂起状态的进程状态模型,四、进程管理中的数据结构,1. 操作系统中用于管理控制的数据结构 在计算机系统

11、中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。 OS管理的这些数据结构一般分成以下四类： 内存表 设备表 文件表 进程表,2. 进程控制块PCB的作用 概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的 PCB在进程创建时建立，并伴随进程运行的全过程，直到进程撤消而撤消。 PCB就象我们的户口。,3. PCB中的信息 1）进程标识符 用于惟一

12、地标识一个进程，一个进程通常有两种标识符： （1）内部标识符 OS赋予每个进程一个惟一的数字标识符。 （2）外部标识符 由创建者提供，由用户（进程）在访问该进程时使用。,2）处理机状态信息 (在PCB中),处理器寄存器内容 通用寄存器 指令计数器 程序状态字 (PSW) 用户栈指针 例子: 在Pentium机中的EFLAGS寄存器,3）进程调度信息 (在PCB中),（1）进程状态 (如: 运行，就绪，阻塞.) （2）进程优先级 （3）进程调度所需的其它信息 （4）事件 (若被阻塞),4）进程控制信息 (在PCB中),程序和数据的地址 进程同步和通信机制 资源清单 链接指针,4. 进程控制块的组

13、织方式,1）线性方式 2）链接方式 不同状态进程分别组成队列，用其中的链接字链接。 就绪队列、若干个阻塞队列、空白队列 3）索引方式 对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址。,PCB链接队列示意图,按索引方式组织PCB,2.3 进程控制,进程控制是进程管理中最基本的功能。负责创建、撤消进程以及完成进程各状态之间的转换。由OS的内核来实现。,原语： 进程控制在进行进程创建、进程撤消、进程阻塞、进程唤醒这些操作时，都要对应地执行一个特殊的程序段（操作系统核心程序），该程序段是由若干条指令构成的“原子操作(atomic operation)”过程，其作为一个整

14、体而不可分割要么全都完成，要么全都不做。这个程序段即为原语。许多系统调用都是原语。,通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些操作），都安排在紧靠硬件的软件层次中，将它们常驻内存，即通常被称为的OS内核。 这样安排的目的在于：一是便于对这些软件进行保护；二是可以提高OS的运行效率。,一、操作系统内核,1. 进程的层次结构 在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。子进程可继续创建更多的孙进程，由此便形成了一个进程的层次结构。 值得注意的是：在

15、Windows中不存在任何进程层次结构的概念，所有进程都具有相同的地位。,二、进程的创建,进程家族示例,2. 进程图 用于描述一个进程的家族关系的有向树。 （在PCB表中都设置了家庭关系表项，以标明自己的父进程及所有的子进程）,3. 引起创建进程的事件,用户登录 作业调度 提供服务 由OS创建，用以向一用户提供服务( 如：打印文件) 应用请求 由已存在的一进程创建(一个用户程序可创建成多个进程),4. 进程的创建,一个进程可调用进程创建原语(Create)创建一个新进程，该新进程是它的子进程。 申请空白PCB，赋予一个统一进程标识符 为新进程分配资源 初始化进程控制块 许多默认值 (如: 状态

16、为 New，无I/O设备或文件.) 将新进程插入就绪队列 如: 把新进程加到就绪队列的链表中,三、进程的终止 1.引起进程终止的事件,正常结束（如给定时限到） 异常结束 - 越界错误 - 保护性出错（例子: 写只读文件） - 非法指令 - 特权指令错误 - 超出时间（进程运行或等待超过对某事件的最大值） - 算术运算错 外界干预 - 操作员或操作系统干预（如当死锁发生时） - 父进程请求终止某一子进程 - 父进程终止，所以子进程也终止,由操作员、操作系统或父进程发出进程终止原语（Termination）终止它的一个子进程及该子进程所有的子孙进程。 检索出该进程的PCB 终止执行，置调度指针为真 终