《操作系统论文 处理机调度及算法》由会员分享，可在线阅读，更多相关《操作系统论文 处理机调度及算法（4页珍藏版）》请在金锄头文库上搜索。
1、处理机调度及算法摘要：在多道程序环境中，进程数往往多于处理机数，这必然引起多个程序对处理机的竞争问题，分配处理机的任务是由处理机调度程序完成的。处 理 机 调 度 是 操 作 系 统 核 心 的重 要 组 成 部 分 。 一 个 作 业 从 提 交 到 执 行 ， 要 经 过 三 级 调 度 。 处 理 机 常 用 的 调 度 算 法 有 先来 先 服 务 调 度 算 法 、 短 作 业 或 短 进 程 优 先 调 度 算 法 （ SJF/SPF） 、 时 间 片 论 转 调 度 算法 （ RR） 、 最 高 优 先 权 优 先 调 度 算 法 （ HPF） 、 最 高 响 应 比 优 先 调
2、 度 算 法 （ HRP） 多级 反 馈 队 列 调 度 算 法 。 在实时系统中存在若干实时任务，这些任务对时间有严格要求，并带有某种程度的紧迫性。关键词：处理机 调度算法 实时系统处理机调度即进程调度。在多道程序环境中，进程数往往多于处理机数，这必然引起多个程序对处理机的竞争问题，分配处理机的任务是由处理机调度程序完成的。如何提高处理机的利用率，在很大程度上取决于调度算法性能的好坏。处理机调度的目的是满足系统响应时间、吞吐量、处理机的效率等要求，一个作业被提交后，必须经处理机调度后，才能获得执行权力。一个作业从提交到执行，往往要经过三级调度。 一 般 情 况 下 ， 当 占 用 处 理 机
3、 的 进 程 因 为某 种 请 求 得 不 到 满 足 而 不 得 不 放 弃 CPU 进 入 等 待 状 态 时 ， 或 者 当 时 间 片 到 ，系 统 不 得 不 将 CPU 分 配 给 就 绪 队 列 中 另 一 进 程 的 时 候 ， 都 要 引 起 处 理 机 调 度 。除 此 之 外 ， 进 程 正 常 结 束 、 中 断 处 理 等 也 可 能 引 起 处 理 机 的 调 度 。处 理 机 调 度 是 操 作 系 统 核 心 的 重 要 组 成 部 分 。 要 记 住 进 程 的 状 态 ， 如 进程 名 称 、 指 令 计 数 器 、 程 序 状 态 寄 存 器 以 及 所
4、有 通 用 寄 存 器 等 现 场 信 息 ，将 这 些 信 息 记 录 在 相 应 的 进 程 控 制 块 中 。 然 后 根 据 一 定 的 算 法 ， 决 定 哪 个进 程 能 获 得 处 理 机 ， 以 及 占 用 多 长 时 间 。 最 后 收 回 处 理 机 ， 即 正 在 执 行 的 进程 因 为 时 间 片 用 完 或 因 为 某 种 原 因 不 能 再 执 行 的 时 候 ， 保 存 该 进 程 的 现 场 ，并 收 回 处 理 机 。 处 理 机 调 度 的 功 能 中 ， 很 重 要 的 一 项 就 是 根 据 一 定 算 法 ， 从就 绪 队 列 中 选 出 一 个 进
5、 程 占 用 CPU 运 行 。 可 见 ， 算 法 是 处 理 机 调 度 的 关 键 。一 个 作 业 从 提 交 到 执 行 ， 往 往 要 经 过 三 级 调 度 ， 即 高 级 调 度 、 低 级 调 度 和中 级 调 度 。 高 级 调 度 又 称 作 业 调 度 ， 用 于 决 定 把 外 存 中 处 于 后 备 队 列 中 的 哪些 作 业 调 入 内 存 。 当 作 业 调 入 内 存 后 ， 为 之 分 配 必 要 的 资 源 ， 创 建 进 程 ， 入就 绪 队 列 。 低 级 调 度 又 称 进 程 调 度 ， 用 于 决 定 就 绪 队 列 中 的 哪 个 程 序 获
6、 得 处理 机 ， 这 个 程 序 由 分 派 程 序 来 完 成 。 剥 夺 方 式 （ 抢 占 方 式 ） 允 许 进 程 调 度 程序 根 据 某 种 策 略 终 止 当 前 正 在 运 行 的 程 序 ， 将 其 转 入 就 绪 队 列 ， 并 根 据 某 种调 度 算 法 选 择 另 一 个 进 程 投 入 运 行 。 剥 夺 原 则 ： 1.优 先 权 原 则 ； 2.短 作 业（ 进 程 ） 优 先 原 则 ； 3.时 间 片 原 则 。 非 剥 夺 方 式 （ 非 抢 占 方 式 ） ： 在 这 种 进程 调 度 方 式 下 ， 一 旦 一 个 进 程 被 选 中 投 入 运
7、行 ， 它 就 一 直 运 行 下 去 ， 直 到 完成 工 作 或 自 愿 放 弃 CPU， 或 因 某 事 件 而 被 阻 塞 为 止 ， 才 把 CPU 让 给 其 他 进程 。 这 种 调 度 方 式 优 点 是 实 现 简 单 、 系 统 开 销 小 ， 适 于 大 多 是 批 系 统 处 理 环境 ， 但 它 难 以 满 足 紧 急 任 务 的 要 求 。 中 级 调 度 又 称 对 换 功 能 ， 用 于 把 那 些 暂时 不 能 运 行 的 进 程 调 到 外 存 去 等 待 （ 挂 起 状 态 ） ， 当 它 们 又 具 备 运 行 条 件 且内 存 空 闲 时 ， 决 定
8、将 外 存 那 些 重 新 又 具 备 运 行 条 件 的 就 绪 进 程 ， 重 新 又 调 入内 存 ， 并 修 改 其 状 态 为 就 绪 状 态 ， 入 就 绪 队 列 。 中 级 调 度 的 运 行 频 率 介 于 高级 调 度 与 低 级 调 度 之 间 。处 理 机 常 用 的 调 度 算 法 有 先 来 先 服 务 调 度 算 法 、 短 作 业 或 短 进 程 优 先 调 度算 法 （ SJF/SPF） 、 时 间 片 论 转 调 度 算 法 （ RR） 、 最 高 优 先 权 优 先 调 度 算 法（ HPF） 、 最 高 响 应 比 优 先 调 度 算 法 （ HRP）
9、多 级 反 馈 队 列 调 度 算 法 。 先来先服务调度算法基本思想是按作业（进程）到达时间先后顺序依次使用 CPU。适用于作业/进程调度。非抢占调度方式。优点是实现简单。缺点是未考虑进程的优先级或紧急性，不利于短作业（进程）的运行，利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。很少单独使用，常与其他 算法结合使用（辅助算法） 。所以这种算法容易实现，但效率低。短作业（进程）优先调度算法基本思想是选择就绪（后备）队列中估计运行时间最短的进程（作业）投入运行。适用于作业/进程调度。非抢占调度方式最短剩余时间优先算法或抢占调度方式。优点是有效缩短作业的平均周转时间，从而提高系统吞吐量。
10、缺点是不利于长作业和紧迫作业的运行（无法满足公平性，估计有主观性） 。所以这咱算法容易实现，且效率比较高，但未考虑作业的利益。高优先权优先调度算法基本思想是选择优先级最高的进程或作业投入运行。适用于作业/进程调度。非抢占调度方式批处理系统“等你打完我再打”抢占调度方式实时系统 “不等你打完电话，抢过话筒就打”优先级（优先权）即优先数，是由系统或用户按某种原则指定的，一般用整数表示。 （1）静态优先权“一定终身”是在创建进程/作业时确定的，且在整个运行期间保持不变。优先级的确定依据：用户要求、进程/作业类型、对资源的要求不同系统有不同的确定原则，及表求方法。优点是简单易行，系统开销小。缺点是不够
11、精确，可能出现某些低优先级的进程永不能被执行。动态优先权是在创建进程/作业时赋予的优先级，可随着进程的推进而改变。决定/动态改变因素：等待时间、已使用处理机的时间、其他资源的使用情况等。特点是可防止低优先级的进程/作业长时间得不到调度。高响应比优先调度算法实际上是一种动态优先权调度算法。响应比 R = 响应时间 / 要求服务时间=（等待时间 + 运行时间）/ 运行时间= 1 +（等待时间 / 运行时间） 基本思想是同时兼顾每个作业等待时间和运行时间两方面因素，选择响应比最高的作业/进程投入运行。优点是利于短作业，利于长作业。缺点：系统开销大。多级反馈队列调度算法是时间片轮转算法的发展，其出发点
12、是为照顾各种作业/进程。基本思想是系统中设置有多个不同优先级的就绪队列，且每个队列具有不同的时间片，使优先级愈高的队列时间片愈小。各个队列按照 FCFS调度算法，而最后一级则时间片轮转。一个新进程就绪后进入第一级队列。进程由于等待而放弃 CPU 后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列。当有一个优先级更高的进程就绪时，可以抢占 CPU，被抢占进程回到原来一级就绪队列末尾。当第一队列空时，就去调度第二级队列，依次类推。当时间片到后却还未完成的进程，则必须放弃 CPU，回到下一级队列。优点是有较好的性能，能满足各类型用户需要。在实时系统中存在若干实时任务，这些任务对时间有严格要求
13、，并带有某种程度的紧迫性。之前所描述的多种调度算法并不能很好的满足实时系统对调度的要求，为此，引入一种新的调度，即实时调度。实时系统的任务具有一定的时间约束（截止时间） 。根据截止时间，实时系统的实时性分为“硬实时”和“软实时” 。硬实时是指应用的时间需求能够得到完全满足，否则就造成重大安全事故，甚至造成重大的生命财产损失和生态破坏，如在航空航天、军事、核工业等一些关键领域中的应用。软实时是指某些应用虽然提出时间需求，但实时任务偶尔违反这种需求对系统运行及环境不会造成严重影响，如监控系统等和信息采集系统等。可预测性是指系统能够对实时任务的执行时间进行判断，确定是否能够满足任务的时限要求。由于实
14、时系统对时间约束要求的严格性，使可预测性称为实时系统的一项重要性能要求。除了要求硬件延迟的可预测性以外，还要求软件系统的可预测性，包括应用程序的响应时间是可预测的，即在有限的时间内完成必须的工作；以及操作系统的可预测性，即实时原语、调度函数等运行开销应是有界的，以保证应用程序执行时间的有界性。大多数实时系统要求有较高的可靠性。在一些重要的实时应用中，任何不可靠因素和计算机的一个微小故障，或某些特定强实时任务（又叫关键任务）超过时限，都可能引起难以预测的严重后果。为此，系统需要采用静态分析和保留资源的方法及冗余配置，使系统在最坏情况下都能正常工作或避免损失。可靠性已成为衡量实时系统性能不可缺少的
15、重要指标。实时系统通常运行在一定的环境下，外部环境是实时系统不可缺少的一个组成部分。计算机子系统一般是控制系统，它必须在规定的时间内对外部请求做出反应。外部物理环境往往是被控子系统，两者互相作用构成完整的实时系统。大多数控制子系统必须连续运转以保证子系统的正常工作或准备对任何异常行为采取行动。早期的实时系统功能简单，包括单板机、单片机，以及简单的嵌入式实时系统等，其调度过程相对简单。随着实时系统应用范围的不断扩大，系统复杂性不断提高，实时系统具有以下新特点：多任务类型，约束的复杂性具有短暂超载的特点。参考文献：计算机操作系统 滕艳萍 、 全国计算机考试用书 、百度文库齐齐哈尔大学操作系统课程综合实践题目：处理机调度及算法班级：计本 102姓名：郝然学号：2010021002指导教师：滕艳萍2012 年 11 月 11 日
