操作系统课件第四版第二章.ppt

第二章第二章 进程管理进程管理第二章 进程的描述与控制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的直接前趋，而 Pj是Pi的直接后继前趋图示例23167457个结点的前趋图前趋关系 P1 → P2, P1 → P3 P1 → P4, P2 → P5 P3 → P5, P4 → P6 P5 → P7, P6 → P71. 程序的顺序执行一个程序由若干个程序段组成，而这些程序段 的执行必须是顺序的，仅当前一操作(程序段)执行完 后，才能执行后继操作。

这种程序执行的方式就称为 程序的顺序执行二、程序顺序执行程序顺序执行举例程序顺序执行前趋图 语句的执行顺序S1：a=x+yS2：b=a-5S3：c=b+1I1C1P1I2C2P2作业1作业22. 程序顺序执行时的特征• 程序执行的顺序性处理机严格按照程序所规定的顺序执行，即每个 操作必须在下一个操作开始之前结束• 程序执行的封闭性独占资源，执行过程中不受外界影响• 程序结果的可再现性程序运行结果与程序执行速度无关，只要初始状 态相同，结果应相同三、程序并发执行 1. 程序的并发执行并发环境：在一定时间内物理机器上有两个或两个以 上的程序同处于开始运行但尚未结束的状态，并 且次序不是事先确定的BAAB程序并发执行举例 (程序并发执行前趋图)I1I2I3I4C1C2C3C4P1P2P3P4存在前趋关系：Ii C i Ii Ii+1 C i Pi C i C i+1 Pi Pi+1但 Ii+1 和 C i 及 Pi－1 是重迭的对于具有下述四条语句的程序段， 可画出如图所示的前趋关系。

S1: a∶= x+2S2: b∶= y+4S3: c∶= a+bS4: d∶= c+b 图 2-4 四条语句的前趋关系可以看出：S1和S2可以并发执行2. 程序并发执行时的特征（1）在并发环境下程序的执行是间断性的执行——暂停——执行（2）程序结果失去封闭性系统中资源被多个进程使用，其状态由多个程序 来改变（3）程序结果的不可再现性并发程序执行的结果与其执行的相对速度有关， 是不确定的例：观察者/报告者 观察者： 报告者： begin beginrepeat repeatwait a car go through delay a timeN=N+1 Print NUntil N=0 ； end untilend初始N=n时不同执行序列：N=N+1 ；Print N ；N=0 ；结果各不相同: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）动态性进程是程序执行过程，动态性是基本特征动态性 还表现在进程有生命期，有创建、执行、暂停、消亡的 过程程序是静态的概念，在机内外都存在，而进程只存 在于系统内部，引入进程的目的就是为了使程序能并发 执行2）并发性指多个进程实体同时存在于内存中，能在一段时间 内同时运行（并发）并发性是进程的重要特征，也是操作系统的重要特 征3）独立性指进程是一个能独立运行单位、独立分配资源和独立接受调度的基本单位4）异步性由于进程共享资源和相互合作形成了相互制约的关系，造成进程执行的间断性，使进程以各自独立的、不可预知的速度向前推进程序与进程之间的区别：程序与进程之间的区别：Ë 进程更能真实地描述并发，而程序不能；Ë 进程是由程序和数据两部分组成的；Ë 程序是静态的，进程是动态的；Ë 进程有生命周期，有诞生有消亡，是短暂的；而程序是相对长久的； Ë 一个进程可以涉及到一个或几个程序的执行；反之 一个程序可以对应多个进程，即同一程序段可在不同 数据集合上运行，可构成不同的进程 。

Ë 进程具有创建其他进程的功能，而程序没有二、进程的基本状态及转换 1. 进程的三种基本状态 进程在生命消亡前处于且仅处于三种基本状态 之一 1) 执行态（Running）：进程占有CPU，并在CPU上运行 2）就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU 暂时不能运行的状态（当调度给其CPU时，立即可以 运行） 3）阻塞态（Blocked）：有时也称为等待状态指进程因等待某种事件的发生而暂时不能 运行的状态（即使CPU空闲，该进程也不可运行）执行就绪阻塞进程的状态及其转换时间片完时间片完I/OI/O完成完成进程进程 调度调度I/OI/O请求请求 2. 三种基本状态的转换在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换① 就绪—执行 调度程序选择一个新的进程运行② 执行—就绪 执行进程用完了时间片③ 执行—阻塞 发生某事件④ 阻塞—就绪 事件完成【思考题】1．如果一个单处理机系统中有n个进程并发执行，在 不考虑程序状态过渡的情况下，执行的进程最多几个 ？最少几个？就绪进程最多几个？最少几个？阻塞进 程最多几个？最少几个？2. 某一时刻，处于执行状态的进程为0个，且当前处 理机空闲，处于就绪状态的进程有几个？3. 有没有这样的状态转换，为什么？ 阻塞 —> 执行； 就绪 —> 阻塞4. 一个状态转换的发生，是否一定导致另一个转换发 生，列出所有的可能。

增加两种基本状态• 创建( 新new)状态–OS 已完成为创建一进程所必要的工作•已构造了进程标识符•已创建了管理进程所需的表格–但还没有允许执行该进程 (尚未同意)• 因为资源有限• 终止（退出exit)状态– 中止后进程移入该状态– 它不再有执行资格– 表格和其它信息暂时由辅助程序保留•例子: 为处理用户帐单而累计资源使用 情况的财务程序- 当数据不再需要后，进程(和它的表格)被删除• 挂起操作的引入（1）终端用户的请求（2）父进程请求（3）负载调节的需要（4）操作系统的需要三、挂起操作和进程状态的转换2. 引入挂起原语操作后进程状态的转换 • 活动阻塞 静止阻塞– 当所有进程都阻塞，OS会安排空间让一就绪进程进入 内存 • 静止阻塞 活动阻塞– 解除挂起命令 • 静止阻塞 静止就绪– 当等待的事件发生时 (状态信息已在OS中) • 静止就绪 活动就绪– 当内存中没有就绪进程时 • 活动就绪 静止就绪 (较少见)– 当没有被阻塞的进程，而为了性能上的考虑，必须释 放一些内存时 • 执行 静止就绪图 2-6 具有挂起状态的进程状态图 挂起命令可由进程自己或其他进程发出，而解除挂起命令只能由其他进程发出。

具有挂起状态的进程状态模型活动挂起事件 发生事件 发生等待 事件挂起调度超时释放活动挂起四、进程管理中的数据结构1. 操作系统中用于管理控制的数据结构在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针OS管理的这些数据结构一般分成以下四类：内存表设备表文件表进程表2. 进程控制块PCB的作用概念：系统为了管理进程设置的一个专门的数据结构 ，用它来记录进程的外部特征，描述进程的运动变化 过程系统利用PCB来控制和管理进程，所以PCB是系 统感知进程存在的唯一标志进程与PCB是一一对应的PCB在进程创建时建立，并伴随进程运行的全过 程，直到进程撤消而撤消 PCB就象我们的户口3. PCB中的信息1）进程标识符用于惟一地标识一个进程，一个进程通 常有两种标识符：（1）内部标识符 OS赋予每个进程一个惟一的数字标识符 2）外部标识符由创建者提供，由用户（进程）在访问 该进程时使用2）处理机状态信息 (在PCB中)• 处理器寄存器内容–通用寄存器 –指令计数器 –程序状态字 (PSW)–用户栈指针–例子: 在Pentium机中的EFLAGS寄存器3）进程调度信息 (在PCB中)（1）进程状态 (如: 运行，就绪，阻塞...)（2）进程优先级（3）进程调度所需的其它信息（4）事件 (若被阻塞) 4）进程控制信息 (在PCB中)• 程序和数据的地址• 进程同步和通信机制• 资源清单• 链接指针4. 进程控制块的组织方式1）线性方式2）链接方式不同状态进程分别组成队列，用其中的链接字 链接。

就绪队列、若干个阻塞队列、空白队列3）索引方式对具有相同状态的进程，分别设置各自的PCB索 引表，表明PCB在PCB表中的地址PCB链接队列示意图按索引方式组织PCB2.3 进程控制进程控制是进程管理中最基本的功能负责创 建、撤消进程以及完成进程各状态之间的转换由OS 的内核来实现• 原语： 进程控制在进行进程创建、进程撤消、进 程阻塞、进程唤醒这些操作时，都要对应地执行一个 特殊的程序段（操作系统核心程序），该程序段是由 若干条指令构成的“原子操作(atomic operation)” 过程，其作为一个整体而不可分割－－要么全都完成 ，要么全都不做这个程序段即为原语许多系统调 用都是原语通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些操作），都安排在紧靠硬件的软件层次中，将它们常驻内存，即通常被称为的OS内核这样安排的目的在于：一是便于对这些软件进行保护；二是可以提高OS的运行效率一、操作系统内核1. 1. 进程的层次结构进程的层次结构在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。

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