第二章_处理机管理1_2

第2章处理机管理 2 1概述2 2进程及其状态 多用户 程序 程序的执行有两种方式 顺序执行和并发执行 顺序执行是单道批处理系统的执行方式 也用于简单的单片机系统 现在的操作系统多为并发执行 具有许多新的特征 引入并发执行的目的是为了提高资源利用率 图2 1程序的顺序执行 这是最自然 也是最初的设计 仅当前一操作 程序段 执行完后 才能执行后继操作 例如 在进行计算时 总须先输入用户的程序和数据 然后进行计算 最后才能打印计算结果 S1 a x y S2 b a 5 S3 c b 1 程序的顺序执行 程序顺序执行时的特征 1 顺序性 处理机的操作严格按照程序所规定的顺序执行 只有当上一个操作完成后 下一个操作才能执行 2 封闭性 程序运行在一个封闭的环境中 即程序运行时独占系统的全部资源 这些资源的状态只能因程序的执行而改变 不受任何外界因素的影响 3 可再现性 由于程序顺序执行的封闭性 只要程序顺序执行的初始条件和环境相同 则不论何时执行 也不论程序执行期间是否存在停顿 程序所得的结果也相同 结论 正由于程序顺序执行的特点 程序员可以方便地检测和重现程序的错误 可以方便地调试和校正程序 程序的并发执行及其特征 1 程序的并发执行 并发程序执行图 并发程序 对比于顺序程序 程序并发执行时的特征 间断性程序在并发执行时 由于共享资源 或者需要相互合作 致使相互间产生了制约关系 呈 走走停停 的间断执行特征 失去封闭性程序并发执行时的系统环境 主要指各程序所共享的系统资源的状态 是由多个程序来改变的 因而失去了封闭性 难以再现性程序在并发执行时的中间结果与其执行速度等有关 具有不确定性 例如 有两个程序A和B 它们共享一个变量N 初始值为x A N N 1B Print N N 0 程序A和B并发执行 以不可预知的速度运行 可出现以下三种情况 1 N N 1在Print N 和N 0之前 此时得到的N值分别为x 1 x 1 0 2 N N 1在Print N 和N 0之后 此时得到的N值分别为x 0 1 3 N N 1在Print N 和N 0之间 此时得到的N值分别为x x 1 0 补充 并发执行失去封闭性的原因是共享资源的影响 去掉这种影响就行了 1966年 由Bernstein 波恩斯坦 给出并发执行的条件 若两个程序P1和P2满足下述条件 便能并发执行且有可再现性 R P1 W P2 R P2 W P1 W P1 W P2 解释 运算的读集R Pi 是指在运算执行期间参考的所有变量的集合 运算的写集W Pi 是指在运算执行期间要改变的所有变量的集合 存在的问题是这个条件不好检查 例 S1 a x yR S1 x y W S1 a S2 b z 1R S2 z W S2 b S3 c a bR S3 a b W S3 c S4 d c 1R S4 c W S4 d 可见 语句S1和S2可以并发执行吗 语句S1和S3可以并发执行吗 语句S2和S3可以并发执行吗 语句S3和S4可以并发执行吗 语句S2和S4可以并发执行吗 R S1 W S2 R S2 W S1 W S1 W S2 可以 不可以 因为 R S3 W S1 a 不可以 因为 R S3 W S2 b 不可以 因为 R S4 W S3 c 可以 程序任意并发执行具有一些新的特征 间断性 无封闭性 难以再现性 旧的程序的概念已不足以刻画这种并发执行的程序及其执行所产生的新特征 为使程序能并发执行 且为了能对并发执行的程序加以描述和控制而引入进程 简言之 为了实现程序的并发执行 进程的引入 2 2进程及其状态 1 进程及进程实体的概念进程是对正在运行的程序的抽象 是OS最核心的概念 计算机上所有可运行的软件 包括OS 都被组织成若干进程 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动 是系统进行资源分配和调度的一个独立单位 生活例子 一人按菜谱做菜 进程实体由程序段 相关数据段和进程控制块构成 进程实体由三部分构成 1 程序 段 进程要进行的操作 2 数据段 包括操作的数据和程序自己的变量 3 进程控制块PCB ProcessControlBlock 存放进程标识符 进程运行的当前状态 程序和数据的地址 程序运行时的CPU环境等 进程的本质 进程的存在必然需要程序的存在进程是系统中独立存在的实体进程的并发特征通过对资源的竞争来体现 进程的动态特性通过状态来描述进程和数据相关 但它不是数据 在它的存在过程中要对数据进行处理 进程的特征 动态性 进程是一个动态的概念 实质上是程序的一次执行过程 进程具有生命期 它因 创建 而产生 因 调度 而执行 执行时还走走停停 因 撤消 而灭亡 并发性 多个进程实体同存于内存中 且能在一段时间内同时运行 共享系统资源 引入进程实体的目的就是并发执行 独立性 进程是一个能独立运行的基本单位 也是系统进行资源分配和调度的基本单位 异步性 各进程按各自独立的 不可预知的速度向前推进 结构特征 程序段 数据段和PCB 程序文件中通常也划分了代码段和数据段 进程的创建与撤消就是PCB的创建与撤消 进程与程序的区别 进程是动态的 程序是静态的 程序是有序代码的集合 它可以复制 进程是程序在数据集上的一次执行 进程是暂时的 程序是永久的 进程是一个状态变化的过程 有它的撤销 程序可长久保存 进程具有结构特征 由程序段 数据段和进程控制块三者组成 而程序仅是指令的有序集合 是进程的组成部分之一 进程与程序的对应关系 通过多次执行 一个程序可对应多个进程 进程的三种基本状态 1 就绪 Ready 状态进程已获得除处理机外的所需资源 等待分配处理机资源 只要分配CPU就可执行 一个系统中多个处于就绪状态的进程排成就绪队列 2 运行 Running 状态处于就绪状态的进程一旦获得了处理机 就可以运行 进程状态也就处于执行状态 处于此状态的进程的数目小于等于CPU的数目 3 等待 Waiting 状态 阻塞 或 睡眠 由于进程等待某种事件 如I O操作或进程同步 在事件发生之前无法继续执行 该事件发生前即使把处理机分配给该进程 也无法运行 如 请求I O操作 申请缓冲空间等通常阻塞进程也排成若干队列 运行状态 等待状态 就绪状态 进程调度 等待条件 I O请求 时间片完毕 条件满足 I O完成 就绪状态 Ready 运行状态 Running 和等待状态 Waiting 其转换方向和常见的转换原因如下图所示 4 进程的三种基本状态及其转换图 进程的其它两种状态 新状态当一个新进程刚刚建立 还未将其放入就绪队列时的状态 称为新状态 终止状态当一个进程已经正常结束或异常结束 操作系统已将其从系统队列中移出 但尚未撤消 这时称为终止状态 图进程的五种基本状态及其转换 进程的五种基本状态及其转换 说明 在实际的OS中 进程的状态会更多 比如UNIXSV中有9种 Linux中有6种 Windows2000中有7种 进程控制块 PCB 系统中用于存放进程的描述和控制信息的数据结构 它是进程存在于系统的唯一标志 它描述了一个进程和其他进程以及系统资源的关系 记录了进程在各个不同时期所处的状态 描述参数 区分信息 动态信息 资源信息等 进程控制块 ProcessControlBlock PCB 进程控制块PCB 1 进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序 含数据 成为一个能独立运行的基本单位 一个能与其它进程并发执行的进程 或者说 OS是根据PCB来对并发执行的进程进行控制和管理的 记录了操作系统所需的 用于描述进程情况及控制进程运行所需的全部信息 PCB是进程存在的唯一标志 2 进程控制块中的信息 进程标识符 进程标识符用于惟一地标识一个进程 一个进程通常有两种标识符 1 内部标识符 在所有的操作系统中 都为每一个进程赋予一个惟一的数字标识符 它通常是一个进程的序号 设置内部标识符主要是为了方便系统使用 2 外部标识符 它由创建者提供 通常是由字母 数字组成 往往是由用户 进程 在访问该进程时使用 为了描述进程的家族关系 还应设置父进程标识及子进程标识 此外 还可设置用户标识 以指示拥有该进程的用户 进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息 包括 进程状态 指明进程的当前状态 作为进程调度和对换时的依据 进程优先级 用于描述进程使用处理机的优先级别的一个整数 优先级高的进程应优先获得处理机 进程调度所需的其它信息 它们与所采用的进程调度算法有关 比如 进程已等待CPU的时间总和 进程已执行的时间总和等 事件 是指进程由执行状态转变为阻塞状态所等待发生的事件 即阻塞原因 进程控制信息 进程控制信息包括 程序和数据的地址 是指进程的程序和数据所在的内存或外存地 首 址 以便再调度到该进程执行时 能从PCB中找到其程序和数据 进程同步和通信机制 指实现进程同步和进程通信时必需的机制 如消息队列指针 信号量等 它们可能全部或部分地放在PCB中 资源清单 是一张列出了除CPU以外的 进程所需的全部资源及已经分配到该进程的资源的清单 链接指针 它给出了本进程 PCB 所在队列中的下一个进程的PCB的首地址 PCB通常包含的内容 进程实体 构成进程的基本部分称为进程实体 进程实体由三部分构成 进程控制块 PCB 程序段 数据段程序段 进程需要运行的纯代码段 PCB 数据 程序 PCB 数据 PCB 程序 进程实体 PCB的组织方式 PCB表 图2 7PCB链接队列示意图 PCB的组织方式 1 链接方式把具有同一状态的PCB用其中的链接字链接成一个队列 可以形成就绪队列 若干个阻塞队列和空闲队列 2 图2 8按索引方式组织PCB PCB的组织方式 1 2 索引方式系统根据所有进程