系统架构设计师教程：进程管理

系统架构设计师 系统架构设计师教程 进程管理 操作系统的主要功能是进行处理机与进程管理 存储管理 设备管理 文件管理和作 业管理 本节讨论操作系统是如何完成这些功能的 进程管理 处理机是计算机系统的核心资源 操作系统的功能之一就是处理机管理 随着计算机 的迅速发展 处理机管理显得更为重要 这主要由于 计算机的速度越来越快 处理机的 充分利用有利于系统效率的大大提高 处理机管理是整个操作系统的重心所在 其管理的 好坏直接影响到整个系统的运行效率 而且操作系统中并发活动的管理和控制是在处理机 管理下实现的 它集中了操作系统中最复杂的部分 它设计的好坏关系到整个系统的成败 进程 process 是处理机管理中最基本的 最重要的概念 进程是系统并发执行的 体现 由于在多道程序系统中 众多的计算机用户都以各种各样的任务 随时随地争夺使 用处理机 为了动态地看待操作系统 则以进程作为独立运行的基本单位 以进程作为分 配资源的基本单位 从进程的观点来研究操作系统 因此 处理机管理也被称为进程管理 处理机管理的功能就是组织和协调用户对处理机的争夺使用 把处理机分配给进程 对进 程进行管理和控制 以最大限度发挥处理机的作用 1 进程的概念 用静态的观点看 操作系统是一组程序和表格的集合 用动态的观点看 操作系统是 进程的动态和并发执行的 而进程的概念实际上是程序这一概念发展的产物 因此 可以 从分析程序的基本特征入手 引出 进程 的概念 顺序程序是指程序中若干操作必须按照某种先后次序来执行 并且每次操作前和操作 后的数据 状态之间都有一定的关系 在早期的程序设计中 程序一般都是顺序地执行的 系统架构设计师 在多道程序系统中 程序的运行环境发生了很大的变化 主要体现在 1 资源共享 为了提高资源的利用率 计算机系统中的资源不再由一道程序专用 而是由多道程序共同使用 2 程序的并发执行或并行执行 逻辑上讲 允许多道不同用户的程序并行运行 允许一个用户程序内部完成不同操作的程序段之间并行运行 允许操作系统内部不同的程 序之间并行运行 物理上讲 内存储器中保存多个程序 I O 设备被多个程序交替地共享 使用 多处理机系统的情形下 表现为多个程序在各自的处理机上运行 执行时间是重叠 的 单处理机系统时 程序的执行表现为多道程序交替地在处理机上相互空插运行 实际上 在多道程序系统中 程序的并行执行和资源共享之间是相辅相成的 一方面 只有允许程序并行执行 才可能存在资源共享的问题 另一方面 只有有效地实现资源共 享 才可能使得程序并行执行 这样 可增强计算机系统的处理能力和提高机器的利用率 并发操作实际上是这样的 事实 大多数程序段只要求操作在时间上是有序的 也就是有些操作必须在其他操作之前 这是有序的 但其中有些操作却可以同时进行 2 进程的定义与分类 由于多道程序系统环境下并行程序执行的特征 并发性 动态性 开放性和相互制约 这样 使用程序的概念就不能如实地反映程序活动的这些特征 必须引入新的概念 进程 操作系统内在最本质的特征是动态性和并发性 而进程正反映了动态性和并发性等特征 程序的并行执行具有如下特征 1 并发性 即并发程序的若干个程序段同时在系统中运行 这些程序段的执行在 时间上是重迭的 一个程序段的执行尚未结束 另一个程序段的执行已经开始 即使这种 系统架构设计师 重迭是很小的一部分 也称这几个程序段是并发执行的 2 动态性 指程序与其执行活动不再一一对应 并发程序中的并发活动是动态产 生 动态消亡的 如 几道并发执行的 C 语言程序共享 C 编译系统 在这种情况下 个 编译程序能同时为多道程序服务 每个程序调用 次就是执行一次 即这个编译程序对应多 个执行活动 3 开放性 指系统中并发执行的程序共享使用的资源 程序的执行与外部因素 如执行速度 相关 不再具有封闭性 4 相互制约性 指程序的动态活动相互依赖 相互制约 其制约关系可分为间接 制约关系和直接制约关系两种 间接制约关系是指相互无逻辑关系的用户程序之间竞争使 用资源所发生的制约关系 直接制约关系是指存在逻辑关系的程序之间相互等待而发生的 制约关系 通过程序活动的这种相互制约关系 才能保证程序的正确运行 系统中同时存在许多进程 它们依性质不同可分为各种不同的类别 1 系统进程和用户进程 一般来讲 在管态下执行的进程称为系统进程 在目态 下执行的进程称为用户进程 系统进程起着资源管理和控制的作用 用户进程是为用户任 务而建立的进程 2 父进程和子进程 系统或用户首先创建的进程称为父进程 在父进程下面的进 程称为子进程 父子进程间存在着某些控制结构和控制关系 因此可以定义一个进程图 进程图是一棵有向的 包含一个根节点的树 节点表示进程 记为 Pi 从节点 Pi 到节点 Pj 的一条边表示进程 Pj 是由进程 Pi 创建的 其中 称 Pi 是 Pj 的父进程 而 Pj 则是 Pi 的子 进程 如图 1 2 所示 系统架构设计师 进程图 图 1 2 进程图 进程图反映了进程间的父 子关系 创建与被创建关系 控制与被控制关系 反映了 进程间的层次关系 同一个进程下属的所有进程称为一个进程族 即协调完成同一任务的 进程集合同属于一个进程族 父 子进程间的关系主要如下 1 进程控制 任何一个进程只能由其直接的父进程创建 进程也只能被其父进程 删除 而且当删除某一中间进程 即非叶子节点 时 同时隐含地删除其所属的所有各级 子进程 父进程能对其下属的各级子孙进程实施控制 如挂起某个子孙进程 而子进程无 权对其父进程实施控制 2 运行方式 父进程一旦创建了进程后 可以选择父 子进程同时运行的方式 父进程也可以等待子进程的运行 直至全部子进程结束后 才开始重新运行 3 资源共享 可以选择两种不同的资源共享方式 一是子进程可共享父进程所拥 有的全部资源 二是子进程仅能共享父进程的部分资源 3 进程的状态转换 由进程运行的间断性 决定了进程至少具有下述三种状态 1 就绪状态 当进程已分配了除 CPU 以外的所有必要的资源后 只要能再获得处 理机 便能立即执行 把进程这时的状态称为就绪状态 在一个系统中 可以有多个进程 系统架构设计师 同时处于就绪状态 通常把它们排成一个队列 称为就绪队列 2 执行状态指进程已获得处理机 其程序正在执行 在单处理机系统中 只能有 一个进程处于执行状态 3 阻塞状态进程因发生某事件 如请求 I O 申请缓冲空间等 而暂停执行时的状 态 亦即进程的执行受到阻塞 故称这种暂停状态为阻塞状态 有时也称为 等待 状态 或 睡眠 状态 通常将处于阻塞状态的进程排成一个队列 称为阻塞队列 进程的状态随着自身的推进和外界的变化而变化 例如 就绪状态的进程被进程调度 程序选中进入执行状态 执行状态的进程因等待某一事件的发生转入等待状态 等待状态 的进程所等待事件来到便进入就绪状态 进程的状态可以动态地相互转换 但阻塞状态的 进程不能直接进入执行状态 就绪状态的进程不能直接进入阻塞状态 在任何时刻 任何 进程都处于且只能处于某一状态 进程状态的变化情况如下 1 运行态 等待态 一个进程运行中启动了外围设备 它就变成等待外围设备传 输信息的状态 进程在运行中申请资源 主存储空间及外围设备因得不到满足 时 变成 等待资源状态 进程在运行中出现了故障 程序出错或主存储器读写错等 变成等待干 预状态 2 等待态 就绪态 外围设备工作结束后等待外围设备传输信息的进程结束等待 等待的资源能得到满足时 另一个进程归还了资源 则等待资源者就结束等待 故障排 队后让等待干预的进程结束等待 任何一个结束等待的进程必须先变成就绪状态 待分配 到处理器后才能运行 3 运行态 就绪态 进程用完了一个使用处理器的时间后强迫该进桂暂时让出处 理器 当有更优先权的进程要运行时也迫使正在运行的进程让出处理器 由于自身或外界 原因成为等待状态的进程让出处理器时 它的状态就变成就绪状态 系统架构设计师 4 就绪态 运行态 等待分配处理器的进程 系统按一种选定的策略从处于就绪 状态的进程中选择一个进程 让它占用处理器 那个被选中的进程就变成了运行态 图 1 3 表示了进程的三种基本状态及各状态之间的转换 图 1 3 进程三态模型及其状态转换 3 关于挂起状态 在不少系统中 进程只有图 1 3 所示的三种状态 但在另一些系统中 又增加了一些 新状态 其中最重要的是挂起状态 引入挂起状态的原因有 1 对换的需要 为了缓和内存紧张的情况 而将内存中处于阻塞状态的进程换至 外存上 使进程又处于一种有别于阻塞状态的新状态 因为即使该进程所期待的事件发生 该进程仍不具备执行条件而不能进入就绪队列 称这种状态为挂起状态 2 终端用户的请求 当终端用户在自己的程序运行期间 发现有可疑问题时 往 往希望使自己的进程暂停下来 也就是说 使正在执行的进程暂停执行 若是就绪进程 则不接受调度以便研究其执行情况或对程序进行修改 把这种静止状态也称为挂起状态 3 父进程请求 父进程常希望挂起自己的子进程 以便考查和修改子进程 或者 协调各子进程间的活动 4 负荷调节的需要 当实时系统中的工作负荷较重 有可能影响到对实时任务的 控制时 可由系统把一些不重要的进程挂起 以保证系统能正常运行 5 操作系统的需要 操作系统希望挂起某些进程 以便检查运行中资源的使用情 系统架构设计师 况及进行记账 由上所述 不难了解挂起状态具有下述三个属性 1 被挂起的进程 原来可能处于就绪状态 此时进程 被挂起 的状态称为挂起 就绪 若被挂起的进程原来可能处于阻塞状态 此时的状态称为挂起阻塞 不论哪种状态 该进程都是不可能被调度而执行的 2 处于挂起阻塞状态的进程 其阻塞条件与挂起条件无关 当进程所期待的事件 出现后 进程虽不再被阻塞 但仍不能运行 这时 应将该进程从静止阻塞转换为挂起就 绪 3 进程可以由其自身挂起 也可由用户或操作系统等将之挂起 其目的都在于阻 止进程继续运行 被挂起的进程是只能被用显式方式来激活 以便从挂起状态中解脱出来 图 1 4 示出了具有挂起操作的进程状态演变情况 图 1 4 进程状态转换 4 进程互斥与同步 进程互斥定义为 一组并发进程中一个或多个程序段 因共享某一共有资源而导致必 系统架构设计师 须以一个不允许交叉执行的单位执行 也就是说互斥是要保证临界资源在某一时刻只被一 个进程访问 进程同步定义为 把异步环境下的一组并发进程因直接制约而互相发送消息而进行互 相合作 互相等待 使得各进程按一定的速度执行的过程称为进程同步 也就是说进程之 间是异步执行的 同步即是使各进程按一定的制约顺序和速度执行 系统中有些资源可以供多个进程同时使用 有些资源则一次仅允许一个进程使用 将 一次仅允许一个进程使用的资源称为临界资源 Critical Resourse 很多物理设备如打 印机 磁带机等都属于临界资源 某些软件的变量 数据 表格也不允许两个进程同时使 用 所以也是临界资源 进程在并发执行中可以共享系统中的资源 但是临界资源的访问则必须互斥进行 即 各进程对临界资源进行操作的那段程序的执行也须是互斥的 只有这样才能保证对临界资 源的互斥访问 把一个进程访问临界资源的那段程序代码称为临界区 Critical section 有了临界区的概念 进程间的互斥就可以描述为 禁止两个及以上的进程同时进入访问同 一临界资源的临界区 为此 必须有专门的同步机构来协调它们 协调准则如下 1 空闲让进 无进程处于临界区时 若有进程要求进入临界区则立即允许其进入 2 忙则等待 当已有进程进入其临界区时 其他试图进入各自临界区的进程必须 等待 以保证诸进程互斥地进入临界区 3 有限等待 有若干进程要求进入临界区时 应在有限时间内使一进程进入临界 区 即它们不应相互等待而谁也不进入临界区 4 让权等待 对于等待进入临界区的进程必须释放其占有的 CPU 信号量可以有效地实现进程的同步和互斥 在操作系统中 信号量是一个整数 当信 系统架构设计师 号量大于等于零时 代表可供并发进程使用的资源实体数 当信号量小于零时则表示正在 等待使用临界区的进程数 建立一个信号量必须说明所建信号量所代表的意义和设置初值 以及建立相应的数据结构 以便指向那些等待使用该临界区的进程 对信号量只能施加特殊的操作 P 操作和 V 操作 P 操作和 V 操作都是不可分割的原 子操作 也称为原语 因此 P 原语和 V 原语执行期间不允许中断发生 P sem 操作的作用是将信号量 sem 值减 l 若 sem 的值成负数 则调用 P 操作的进 程暂停执行 直到另一个进程对同一信号量做 V 操作 V sem 操作的作用是将信号量 sem 值加 1 若 sem 的值小于等于 0 从相应队列 与 sem 有关的队列 中选一个进程 唤 醒它 一般 P 操作与 V 操作的定义如下所述 P 操作 P sem sem sem 1 if sem 0 进程进入等待状态 else 继续进行 V 操作 V sem sem sem 1 if sem 0 唤醒队列中的一个等待进程 else 继续进行 为了保护共享资源 如公共变量等 使它们不被多个进程同时访问 就要阻止这些 进程同时执行访问这些资源 临界资源 的代码段 临界区 进程互斥不允许两个以上 系统架构设计师 共享临界资源的并发进程同时进入临界区 利用 P V 原语和信号量可以方便地解决并发 进程对临界区的进程互斥问题 设信号量 mutex 是用于互斥的信号量 初值为 1 表示没有并发进程使用该临界区 于是各并发进程的临界区可改写成下列形式的代码段 P mutex 临界区 V mutex 要用 P V 操作实现进程同步 需要引进私用信号量 私用信号量只与制约进程和被制 约进程有关 而不是与整组并发进程相关 与此相对 进程互斥使用的信号量为公用信号 量 首先为各并发进程设置私用信号量 然后为私用信号量赋初值 最后利用 P V 原语和 私用信号量规定各进程的执行顺序 经典同步问题的例子是生产者 消费者问题 这要求存后再取 取后再存 即有两个制 约关系 为此 需要两个信号量 表示缓冲区中的空单元数和非空单元数 记为 Bufempty 和 Buffull 它们的初值分别是 1 和 0 相应的程序段形式是 生产者 loop 生产一产品 next P Bufempty next 产品存缓冲区 V Buffull endloop 消费者 系统架构设计师 loop P Buffulll V Bufempty 从缓冲区中取产品 使用产品 endloop 5 前趋图 前趋图是一个由结点和有向边构成的有向无循环图 该图通常用于表现事务之间先后 顺序的制约关系 图中的每个结点可以表示一个语句 一个程序段或是一个进程 结点间 的有向边表示两个结点之间存在的前趋关系 例 在计算机中 经常采用流水线方式执行指令 若每一条指令都可以分解为取指 分析和执行三步 取指操作为 取指操作为 Ai 分析操作为 Bi 和执行操作为 Ci i 1 2 3 图 1 5 为三个任务各程序段并发执行的前驱图 图中 A1 没有前趋结点 称为开始结点 它不受任何制约 可以直接执行 而 B1 与 A2 只能在 A1 执行完成之后才能开始 而 B2 必须在 B1 与 A2 完成之后才能开始 C3 没 有后继结点 称为终止结点 图 1 5 前趋图 在前趋图中 执行优后顺序的制约关系可分为两种 直接制约和间接制约 系统架构设计师 直接制约通常是指一个操作中 多个步骤之间的制约关系 也可以说是 同步的进程之 间的制约关系 例如图 1 5 中 A1 B1 C1 是一条指令的取指 分析 执行三个步骤 所以他们之间的关系是直接制约 间接制约通常是指多个操作之间相同步骤的制约关系 也可以说是 互斥的进程之间的 制约关系 例如图 1 5 中 A1 A2 A3 之间就存在间接制约的关系 前趋图的应用广泛 在项目开发中 可用前趋图来分析哪些活动可以并行完成 同时 项目管理工具 Pert 图 单 双 代号网络图等都融入了前趋图的思想 6 进程调度与死锁 进程调度即处理器调度 又称上下文转换 它的主要功能是确定在什么时候分配处 理器 并确定分给哪一个进程 即让正在执行的进程改变状态并转入就绪队列的队尾 再 由调度原语将就绪队列的队首进程取出 投入执行 引起进程调度的原因有以下几类 1 正在执行的进程执行完毕 2 执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态 3 执行中的进程调用了 P 原语操作 从而因资源不足而阻塞 或调用 V 原语操作 激活了等待资源的进程队列 4 在分时系统中 当一进程用完一个时间片 5 就绪队列中某进程的优先级变得高于当前执行进程的优先级 也将引起进程调 度 进程调度的方式有两类 剥夺方式与非剥夺方式 所谓非剥夺方式是指 一旦某个作 业或进程占有了处理器 别的进程就不能把处理器从这个进程手中夺走 直到该进程自己 因调用原语操作而进入阻塞状态 或时间片用完而让出处理机 剥夺方式是指 当就绪队 系统架构设计师 列中一旦有进程的优先级高于当前执行进程的优先级时 便立即发生进程调度 转让处理 机 进程调度的算法是服务于系统目标的策略 对于不同的系统与系统目标 常采用不同 的调度算法 1 先来先服务 FirstComeandFirstServerd FCFS 调度算法 又称先进先出 FirstInandFirstOut FIFO 就绪队列按先来后到原则排队 2 优先数调度 优先数反映了进程优先级 就绪队列按优先数排队 有两种确定 优先级的方法 即静态优先级和动态优先级 静态优先级是指进程的优先级在进程开始执 行前确定 执行过程中不变 而动态优先级则可以在进程执行过程中改变 3 轮转法 RoundRobin 就绪队列按 FCFS 方式排队 每个进程执行一次占有 处理器时间都不超过规定的时间单位 时间片 若超过 则自行释放自己所占有的 CPU 而排到就绪队列的末尾 等待下一次调度 同时 进程调度程序又去调度当前就绪队列中 的第一个进程 进程管理是操作系统的核心 在进程管理的实现中 如果设计不当 会出现一种尴尬 的局面 死锁 当若干个进程互相竞争对方已占有的资源 无限期地等待 不能向前推进时会造成 死 锁 例如 P1 进程占有资源 R1 P2 进程占有资源 R2 这时 P1 又需要资源 R2 P2 也需要 资源 R1 它们在等待对方占有的资源时 又不会释放自己占有的资源 因而