资源描述
嵌 入 式 系 统 原 理 与 开 发 第 18讲南 京 大 学 计 算 机 系 俞 建 新 主 讲2008年 春 季 2008年6月24日南京大学计算机系2 第 9章 嵌 入 式 操 作 系 统 概 论l 本 章 主 要 介 绍 以 下 内 容 :l 实 时 系 统l 嵌 入 式 操 作 系 统 的 特 点 与 分 类l RTOS常 用 调 度 算 法l 启 动 代 码 Bootloaderl 嵌 入 式 操 作 系 统 uCOS-II 2008年6月24日南京大学计算机系3 9.1 实 时 系 统l 什 么 是 实 时 系 统l 一 般 而 言 具 有 实 时 性 能 的 控 制 系 统 是 实 时 系 统 。l 实 时 表 示 一 个 非 常 短 的 时 间 间 隔 “ time gap”( 也 可以 认 为 表 示 时 间 框 架 “ time frame”或 者 时 间 窗 口“ time window”) , 具 有 “ 立 即 ” 之 含 义 。l 当 计 算 机 进 行 实 时 处 理 时 , 要 求 在 接 收 到 数 据 的 同时 执 行 操 作 并 输 出 计 算 结 果 , 不 能 超 出 计 算 机 系 统所 能 容 忍 的 时 限 。 2008年6月24日南京大学计算机系4 实 时 系 统 的 定 义l IEEE( 美 国 电 气 电 子 工 程 师 协 会 ) 给 出 的 实 时系 统 定 义 是 “ 那 些 正 确 性 不 仅 取 决 于 计 算 的 逻辑 结 果 , 也 取 决 于 产 生 结 果 所 花 费 的 时 间 的 系统 ” 。 这 就 是 说 , 实 时 系 统 运 算 能 力 具 有 及 时与 正 确 的 双 重 特 征 。l 本 教 程 给 出 的 实 时 系 统 ( Real-Time System)定 义 是 : 对 外 来 事 件 能 在 限 定 的 响 应 时 间 内 做出 预 定 质 量 处 理 的 计 算 机 系 统 。 2008年6月24日南京大学计算机系5 实 时 系 统 的 主 要 特 点l 及 时 响 应 外 部 发 生 的 随 机 任 务 请 求l 在 规 定 的 时 间 内 完 成 任 务l 任 务 执 行 的 时 间 限 制 类 型 和 类 型 间 关 系l 截 止 时 间 (finish time)l 任 务 执 行 预 设 时 间 (budget time)l 一 个 任 务 的 截 止 时 间 通 常 大 于 任 务 执 行 预 设 时 间 2008年6月24日南京大学计算机系6 实 时 系 统 的 关 键 因 素l 计 算 机 系 统 的 实 时 性 能 主 要 由 操 作 系 统 和 运 行在 操 作 系 统 上 的 应 用 软 件 决 定 , 对 于 无 操 作 系统 的 计 算 机 则 由 控 制 程 序 决 定 。l 具 有 实 时 性 能 的 操 作 系 统 称 为 实 时 操 作 系 统(Real-Time Operating System, RTOS) 2008年6月24日南京大学计算机系7 实 时 系 统 与 非 实 时 系 统 的 例 子l 实 时 系 统 典 型 例 子l 民 用 飞 机 的 导 航 系 统l 汽 车 的 防 刹 车 抱 死 系 统 (ABS)l 非 实 时 系 统 典 型 例 子l 银 行 数 据 查 询 处 理 系 统l 视 频 播 放 系 统l 图 像 扫 描 l 文 字 识 别 系 统 2008年6月24日南京大学计算机系8 提 高 实 时 性 能 的 因 素l 以 下 几 种 途 径 常 常 用 来 提 高 应 用 系 统 实 时 性 能l 尽 量 采 用 硬 件 处 理l 优 化 微 处 理 器 的 中 断 机 制l 采 用 简 单 的 单 线 程 循 环 程 序l 采 用 基 于 实 时 操 作 系 统 的 复 杂 多 线 程 操 作 2008年6月24日南京大学计算机系9 实 时 系 统 的 属 性 和 指 标l 实 时 系 统 的 两 个 基 本 属 性l 可 预 测 性 和 可 靠 性l 实 时 系 统 的 实 时 性 能 主 要 根 据 其 RTOS的 三 个主 要 指 标 来 衡 量 l 响 应 时 间 (response time)l 吞 吐 量 (throughput)l 生 存 时 间 (survival time) 2008年6月24日南京大学计算机系10 响 应 时 间l 计 算 机 从 识 别 一 个 外 部 事 件 到 做 出 响 应 的 时 间 l RTOS响 应 时 间 的 具 体 指 标 是 :l 中 断 延 迟 时 间 ( Interrupt Latency)l 任 务 切 换 时 间 ( Task Switching Latency) 2008年6月24日南京大学计算机系11 响 应 时 间 (续 )l 两 个 时 间 指 标 的 计 算 公 式 是 :l 中 断 延 迟 时 间 = TCloseINT + TDoISR + TSaveReg + TStartServiceTCloseINT : 关 中 断 的 最 长 时 间TDoISR : 开 始 执 行 中 断 服 务 子 程 序 的 第 一 条 指 令 的 时 间TSaveReg : 保 存 CPU内 部 寄 存 器 的 时 间TStartService : 内 核 进 入 中 断 服 务 函 数 的 执 行 时 间l 任 务 切 换 时 间 : T to Do B Task Time T to Pause A Task TimeT to Do B Task Time : 开 始 执 行 B任 务 的 时 刻T to Pause A Task : 暂 停 执 行 A任 务 的 时 刻 2008年6月24日南京大学计算机系12 响 应 时 间 (续 )l 任 务 的 切 换 时 间 就 是 CPU从 停 止 一 个 任 务 的 执 行 切 换到 另 一 个 任 务 所 需 时 间l VxWorks是 实 时 嵌 入 式 系 统 , 内 核 为 Wind。l 下 表 给 出 了 eCos操 作 系 统 内 核 实 时 响 应 时 间 参 考 数 据硬 件 测 试 环 境 中 断 延 迟 时 间 任 务 切 换 时 间ARM7TDMI( 20MHz) 22.10 ms 49.14 msStrongARM( 221.2MHz) 3.25 ms 1.85 msIntel Xcale( 600MHz) 1.87 ms 0.87 ms 2008年6月24日南京大学计算机系13 实 时 系 统 的 分 类l 根 据 响 应 性 能 分l 硬 实 时 系 统系 统 未 能 在 时 限 内 就 某 一 事 件 做 出 响 应 而 失 败 , 并且 该 失 败 被 认 为 是 一 种 全 面 的 系 统 失 败 , 则 可 以 认为 该 系 统 是 一 个 硬 实 时 ( hard real-time) 系 统 。 l 软 实 时 系 统非 硬 实 时 的 实 时 系 统 可 以 归 类 为 软 实 时 系 统 。 在 一个 软 实 时 ( soft real-time) 系 统 中 , 存 在 时 限 指 标 ,但 是 如 果 输 出 响 应 超 过 时 限 , 一 般 不 会 造 成 严 重 后果 。 2008年6月24日南京大学计算机系14 硬 实 时 系 统 和 软 实 时 系 统 时 限 效 益l 下 面 是 两 种 实 时 系 统 的 时 限 效 益 图 2008年6月24日南京大学计算机系15 实 时 系 统 的 分 类 (续 )l 按 照 响 应 时 间 的 快 慢 分 类 :l 强 实 时 系 统 :l 其 响 应 时 间 在 毫 秒 级 或 微 秒 级l 普 通 实 时 系 统 :l 其 响 应 时 间 一 般 几 秒l 弱 实 时 系 统 :l 其 响 应 时 间 一 般 在 数 十 秒 2008年6月24日南京大学计算机系16 9.2 嵌 入 式 操 作 系 统 的 特 点 和 分 类l 操 作 系 统 可 以 最 粗 略 地 分 为 内 核 ( kernel) 、设 备 驱 动 与 外 壳 ( shell) 三 大 部 分 。 通 俗 地 讲 ,内 核 是 操 作 系 统 的 核 心 模 块 , 管 理 CPU的 运 行 ;而 外 壳 是 内 核 的 外 围 模 块 , 对 用 户 发 出 的 命 令进 行 解 释 和 处 理 。 2008年6月24日南京大学计算机系17 嵌 入 式 系 统 内 核l 广 义 解 释l 指 装 入 到 存 储 器 的 嵌 入 式 软 件 中 的 操 作 系 统 部 分 ,在 这 种 情 况 下 , 除 了 操 作 系 统 内 核 之 外 , 嵌 入 式 软件 还 包 括 板 级 支 持 包 , 驱 动 程 序 和 应 用 软 件 l 狭 义 解 释l 指 嵌 入 式 操 作 系 统 中 负 责 多 任 务 管 理 及 任 务 之 间 进行 通 信 的 多 任 务 处 理 部 分 。 它 进 行 任 务 管 理 ( 进 程管 理 ) , 时 钟 管 理 , 内 存 管 理 等 2008年6月24日南京大学计算机系18 嵌 入 式 操 作 系 统 的 特 点l 可 移 植 性l 强 调 实 时 性 能l 内 核 精 简 , 所 占 空 间 小l 抢 占 式 内 核l 使 用 可 重 入 函 数l 可 配 置l 可 裁 剪l 高 可 靠 性 2008年6月24日南京大学计算机系19 可 移 植 性l 硬 件 平 台 的 多 样 性 以 及 提 高 代 码 可 重 用 性 的 双重 条 件 , 导 致 嵌 入 式 操 作 系 统 研 发 机 构 力 求 做到 嵌 入 式 系 统 具 有 良 好 的 可 移 植 性 。l 考 虑 到 移 植 性 , 嵌 入 式 系 统 通 常 分 为 两 部 分l 硬 件 相 关 部 分包 括 班 级 支 持 包 (BSP)或 硬 件 抽 象 层 (HAL)l 硬 件 无 关 部 分包 括 内 核 、 中 间 件 和 API 2008年6月24日南京大学计算机系20 强 调 实 时 性 能l 传 统 观 点l 嵌 入 式 操 作 系 统 应 该 具 有 强 实 时 性 能 l 现 代l 由 于 手 机 和 媒 体 播 放 器 之 类 的 软 实 时 嵌 入 式 产 品 日益 普 及 , 导 致 一 些 嵌 入 式 操 作 系 统 降 低 了 实 时 性 能 l 实 时 性 能 仍 然 被 认 为 是 评 价 嵌 入 式 操 作 系 统 的 最 重要 技 术 指 标 2008年6月24日南京大学计算机系21 内 核 精 简 : 所 占 空 间 小l 内 核 是 操 作 系 统 中 靠 近 硬 件 并 且 享 有 最 高 特 权的 一 层 。 为 了 适 应 嵌 入 式 计 算 机 存 储 空 间 小 的限 制 , 嵌 入 式 操 作 系 统 的 内 核 都 尽 量 小 型 化 。 2008年6月24日南京大学计算机系22 典 型 的 操 作 系 统 内 核 空 间 尺 寸 VxWorks操 作 系 统 内 核 最 小 可 裁 减 到 8KB Nucleus Plus内 核 在 典 型 的 CISC体 系 结 构 上 占据 大 约 20KB空 间 , 而 在 典 型 的 RISC体 系 结 构上 占 据 空 间 为 40KB左 右 , 其 内 核 数 据 结 构 占据 1.5KB空 间 QNX的 内 核 大 约 占 12KB 国 产 Hopen操 作 系 统 的 内 核 大 约 占 10KB WinCE操 作 系 统 的 内 核 大 约 占 25KB 2008年6月24日南京大学计算机系23 抢 占 式 内 核l 从 内 核 调 度 基 本 特 点 分 类 , 嵌 入 式 操 作 系 统 内核 分 为 抢 占 式 内 核 (preemptive kernel)和 不 可 抢占 式 内 核 (non-preemptive kernel)l 抢 占 式 内 核 的 最 大 特 点 是 最 高 优 先 级 任 务 能 够立 即 得 到 执 行 , 从 而 能 够 保 证 系 统 具 有 高 度 实时 性 能 。 2008年6月24日南京大学计算机系24 抢 占 式 内 核 ( 续 1)l 不 可 抢 占 式 内 核l 不 可 抢 占 式 内 核 称 为 合 作 型 多 任 务 ( 进 程 ) 处理 , 要 求 每 个 任 务 在 程 序 代 码 执 行 完 毕 后 自 我放 弃 CPU的 所 有 权 l 不 可 抢 占 式 内 核 的 最 大 缺 陷 在 于 响 应 时 间 。 高优 先 级 的 任 务 已 经 进 入 就 绪 态 , 但 还 不 能 运 行 ,直 到 当 前 运 行 的 任 务 释 放 CPU为 止 。 2008年6月24日南京大学计算机系25 抢 占 式 内 核 ( 续 2)l 抢 占 式 内 核 的 工 作 原 理l 最 高 优 先 级 的 任 务 就 绪 必 然 得 到 CPU的 控 制 权 。 当一 个 运 行 着 的 任 务 使 另 一 个 比 它 优 先 级 高 的 任 务 进入 了 就 绪 态 , 则 当 前 任 务 的 CPU控 制 权 就 会 被 抢 占 ,那 个 高 优 先 级 的 任 务 立 刻 获 得 CPU的 控 制 权 。 l 通 常 把 最 高 优 先 级 指 派 给 实 时 要 求 最 高 的 任 务 。 且绝 大 多 数 嵌 入 式 操 作 系 统 的 内 核 采 用 抢 占 式 调 度 策略 2008年6月24日南京大学计算机系26 使 用 可 重 入 函 数l 实 时 操 作 系 统 要 求 使 用 可 重 入 函 数 l 什 么 是 可 重 入 函 数 ?l 如 果 一 个 函 数 的 代 码 能 够 同 时 被 多 个 任 务 并 发 地 调用 ( 分 享 ) , 并 且 在 调 用 该 函 数 时 这 些 任 务 之 间 不会 产 生 数 据 干 扰 错 误 , 那 么 这 个 函 数 就 是 可 重 入(reentrant)函 数 。 2008年6月24日南京大学计算机系27 意 义 和 准 则l 可 重 入 函 数 的 重 要 价 值 在 于 : 任 意 时 刻 被 中 断后 再 继 续 运 行 不 会 丢 失 数 据 l 可 重 入 函 数 中 使 用 变 量 有 两 个 准 则l 尽 量 使 用 局 部 变 量 , 即 把 变 量 保 存 在 CPU寄 存 器 中或 者 栈 区 中l 如 果 使 用 全 局 变 量 , 则 要 对 全 局 变 量 进 行 保 护 2008年6月24日南京大学计算机系28 使 用 可 重 入 函 数 ( 续 1)l 不 可 重 入 函 数 的 特 征 有l 函 数 体 内 使 用 了 静 态 的 数 据 结 构l 函 数 体 内 调 用 了 malloc()或 者 free()函 数l 函 数 体 内 调 用 了 标 准 I/O函 数l 抢 占 式 内 核 的 函 数 必 须 是 可 重 入 的 。 在 抢 占 式 内核 控 制 之 下 , 如 果 有 两 个 以 上 任 务 需 要 调 用 同 一个 不 可 可 重 入 函 数 , 则 必 须 使 之 满 足 互 斥 条 件 。 2008年6月24日南京大学计算机系29 使 用 可 重 入 函 数 ( 续 2)l 为 了 保 证 编 写 的 函 数 具 有 可 重 入 性 , 其 关 键 之处 是 应 当 做 到 以 下 几 点 :l 使 用 本 地 数 据 。l 不 返 回 指 向 静 态 数 据 的 指 针 , 所 有 数 据 都 由 函 数 的调 用 者 提 供 。 l 不 为 连 续 的 调 用 持 有 静 态 数 据 。l 通 过 制 作 全 局 数 据 的 本 地 拷 贝 来 保 护 全 局 数 据 。 l 不 调 用 任 何 不 可 重 入 函 数 。 2008年6月24日南京大学计算机系30 可 配 置l 嵌 入 式 操 作 系 统 必 须 具 有 良 好 的 可 配 置 功 能 ,这 也 是 嵌 入 式 操 作 系 统 区 别 于 通 用 操 作 系 统 的一 个 重 要 方 面 l 最 典 型 的 可 配 置 型 嵌 入 式 操 作 系 统 是 eCos, 在内 部 设 计 了 大 量 可 以 调 节 操 作 系 统 特 性 和 性 能的 参 数 , 并 为 配 置 这 些 参 数 设 计 了 专 门 的 配 置工 具 2008年6月24日南京大学计算机系31 可 裁 剪l 指 编 译 之 前 对 嵌 入 式 操 作 系 统 功 能 部 件 进 行 增加 和 删 除 , 可 定 制 是 可 裁 减 的 另 外 一 种 表 达 方式 l 可 以 根 据 产 品 的 资 源 限 制 和 功 能 /性 能 需 求 对嵌 入 式 操 作 系 统 的 功 能 部 件 进 行 增 删 , 将 所 有不 必 要 的 部 件 去 除 , 同 时 把 增 强 功 能 和 提 高 性能 的 部 件 添 加 进 去 , 最 终 编 译 成 一 个 满 足 特 定设 计 要 求 的 最 小 尺 寸 的 操 作 系 统 目 标 程 序 2008年6月24日南京大学计算机系32 高 可 靠 性l 嵌 入 式 系 统 往 往 在 无 人 操 作 和 值 守 的 环 境 下 运行 , 有 的 嵌 入 式 系 统 运 行 时 间 长 甚 至 是 常 年 运行 , 因 此 对 可 靠 性 的 要 求 就 成 为 嵌 入 式 操 作 系统 的 一 个 重 要 特 点 l VxWorks、 C/OS-II等 , 都 已 经 经 过 了 多 年 应用 的 考 验 , 一 般 来 说 这 些 操 作 系 统 都 是 稳 定和 安 全 的 , 具 有 公 认 的 高 可 靠 性 2008年6月24日南京大学计算机系33 嵌 入 式 操 作 系 统 分 类l 按 源 代 码 分 类l 商 用 型 和 开 源 型l 按 实 时 性 能 分 类l 强 实 时 型 和 普 通 实 时 型l 按 内 核 结 构 分 类l 单 内 核 型 和 微 内 核 型 2008年6月24日南京大学计算机系34 单 内 核l 单 内 核 ( monolithic kernel) 是 传 统 型 操 作 系 统内 核 , 有 时 也 被 称 为 宏 内 核 ( macro kernel)l 单 内 核 内 部 包 含 I/O管 理 和 设 备 管 理 、 进 程 管理 、 调 度 器 、 内 存 管 理 、 文 件 管 理 和 时 间 管 理等 模 块l 各 模 块 之 间 的 耦 合 度 很 紧 , 模 块 之 间 的 通 信 通过 直 接 函 数 调 用 实 现 , 而 不 是 消 息 传 递 2008年6月24日南京大学计算机系35 单 内 核 ( 续 )l 缺 点l 占 内 存 空 间 大 , 缺 乏 可 扩 展 性 , 维 护 困 难 , 排 除 故障 和 增 加 新 功 能 需 要 重 编 译 l 优 点l 系 统 花 在 内 核 功 能 切 换 的 开 销 非 常 小 , 对 外 来 事 件反 应 速 度 快 2008年6月24日南京大学计算机系36 单 内 核 /微 内 核 的 内 部 结 构 图 解单 内 核 与 微 内 核 操 作 系 统 模 块 框 架 2008年6月24日南京大学计算机系37 微 内 核l 基 本 思 想 是 在 内 核 模 式 中 执 行 基 本 的 核 心 操 作系 统 功 能 , 非 基 本 的 服 务 和 应 用 构 筑 在 微 内 核之 上 l 微 内 核 用 水 平 架 构 代 替 了 传 统 的 垂 直 分 层 架 构 l 设 备 驱 动 程 序 、 文 件 系 统 、 虚 拟 内 存 管 理 程 序和 窗 口 系 统 等 以 服 务 器 进 程 方 式 工 作 。 它 们 之间 的 相 互 作 用 变 成 了 对 等 地 通 过 微 内 核 传 递 消息 2008年6月24日南京大学计算机系38 微 内 核 ( 续 )l 突 出 特 点l 内 核 小 巧 , 通 常 微 内 核 只 有 任 务 管 理 、 虚 存 管 理 和 进 程 间 通信 3个 部 分l 接 口 一 致 , 所 有 进 程 请 求 使 用 统 一 接 口 , 进 程 不 需 要 区 分 内核 模 式 和 用 户 模 式 服 务l 各 个 功 能 模 块 之 间 松 散 耦 合 , 只 完 成 服 务 功 能 , 系 统 管 理 功能 交 给 一 个 或 多 个 特 权 服 务 程 序l 基 于 客 户 /服 务 器 体 系 结 构 , 在 微 内 核 结 构 的 操 作 系 统 中 , 任务 间 通 信 机 制 消 息 机 制 是 系 统 的 基 础 l 微 内 核 功 能 扩 充 方 便 , 但 是 各 个 功 能 之 间 的 切 换 而 引 起 的 开销 非 常 大 。 2008年6月24日南京大学计算机系39 9.3 RTO S常 用 的 调 度 算 法l 本 节 内 容l 基 于 优 先 级 的 调 度 算 法l 时 钟 驱 动 调 度 算 法l 基 于 比 例 共 享 的 调 度 算 法l 非 周 期 任 务 的 调 度l 优 先 级 反 转 和 对 策 2008年6月24日南京大学计算机系40 基 于 优 先 级 的 调 度 算 法l 大 多 数 实 时 系 统 采 用 该 算 法l 该 算 法 给 每 个 任 务 分 配 一 个 优 先 级 , 在 每 次 任 务 调度 时 , 总 是 执 行 最 高 优 先 级 的 任 务 。l 优 先 级 驱 动 算 法 是 事 件 驱 动 算 法l 在 基 于 该 算 法 调 度 的 内 核 中 , 保 存 就 绪 任 务 队 列 的数 据 结 构 有 几 种 , 可 以 是 位 图 , 也 可 以 是 表 格l 根 据 不 同 的 优 先 级 指 派 方 法 , 该 调 度 算 法 可 以 分 为静 态 实 时 调 度 和 动 态 实 时 调 度 两 种 类 型 2008年6月24日南京大学计算机系41 静 态 实 时 调 度l 在 系 统 编 译 的 时 候 就 做 出 决 定 从 就 绪 任 务 队 列中 选 择 哪 个 任 务 来 运 行 l 假 设 系 统 中 实 时 任 务 特 性 是 事 先 知 道l 可 以 完 全 脱 机 的 进 行 可 调 度 性 分 析 l 两 种 静 态 实 时 调 度 算 法l RMS算 法 和 DMS 算 法 2008年6月24日南京大学计算机系42 RMS算 法l 全 称 速 率 单 调 调 度 (Rate Monotonic Scheduling),它 是 由 Liu和 Layand在 1973年 提 出 来 的 静 态 多任 务 调 度 算 法 , 适 用 于 那 些 响 应 和 处 理 周 期 性事 件 的 实 时 任 务 l 基 本 原 理 是 任 务 的 速 率 与 其 周 期 成 反 比 2008年6月24日南京大学计算机系43 RMS算 法 ( 续 )l RMS算 法 基 于 嵌 入 式 系 统 做 出 了 如 下 5个 模 型 假 设l 所 有 的 任 务 请 求 都 是 周 期 性 的 , 必 须 在 限 定 的 时 限 内 完 成 ;l 任 务 之 间 都 是 独 立 的 , 每 个 任 务 的 请 求 不 依 赖 于 其 他 任 务 请求 的 开 始 或 完 成 ; l 每 个 任 务 的 运 行 时 间 是 不 变 的 ( 不 考 虑 中 断 情 况 ) ;l 所 有 的 非 周 期 性 任 务 都 在 特 殊 的 情 况 下 运 行l 抢 占 式 调 度 , 单 处 理 器 , 任 务 切 换 的 时 间 忽 略 不 计 。 2008年6月24日南京大学计算机系44 RMS算 法 ( 续 1)l RMS模 型l 设 S=S1, S2, S3, . Sn为 一 个 含 有 n个 周 期 性 任 务的 集 合 , S集 合 中 的 任 务 用 Si=Ti, Ci, Di, Pi, Ui( i=1,2,3,.n) 来 表 示 。 其 中 : Ti表 示 任 务 的 发 生周 期 , Ci表 示 任 务 的 最 长 执 行 时 间 , Di表 示 任 务 的相 对 截 止 时 间 , Pi表 示 任 务 在 S中 的 优 先 级 ( 优 先级 数 值 越 小 , 优 先 权 越 高 ) , Ui表 示 任 务 的 CPU利用 率 l 整 个 任 务 集 S的 CPU利 用 率 为 :Un= ini i TC /1 2008年6月24日南京大学计算机系45 RMS算 法 ( 续 2)RMS算 法 的 任 务 优 先 级 2008年6月24日南京大学计算机系46 DMS算 法l 全 称 是 截 止 时 间 单 调 调 度 ( Deadline Monotonic Scheduling)l DMS是 在 速 率 单 调 调 度 的 基 础 上 发 展 起 来 的 。不 同 的 是 任 务 Si的 优 先 级 按 相 对 截 止 时 间 Di来分 配 。l 相 对 截 止 时 间 短 的 任 务 优 先 级 高 , 相 对 截 止 时间 长 的 任 务 优 先 级 低 2008年6月24日南京大学计算机系47 动 态 实 时 调 度l 指 调 度 器 在 运 行 期 间 才 决 定 选 择 哪 个 就 绪 任 务来 运 行 l 主 要 算 法l 最 早 截 止 时 间 优 先 ( EDF, Earliest Deadline First) l 最 小 空 闲 时 间 优 先 ( LSF, Least Slack Time First) 等 2008年6月24日南京大学计算机系48 最 早 截 止 时 间 优 先 算 法l 1973年 由 Liu和 Layland首 先 提 出 来 的 l 是 一 个 动 态 优 先 级 驱 动 的 调 度 算 法 , 其 中 分 配给 每 个 任 务 的 优 先 级 根 据 它 们 当 前 对 截 止 时 限的 要 求 而 定 l 离 截 止 时 限 最 短 时 间 的 就 绪 任 务 分 配 最 高 的 优先 级 , 而 离 截 止 时 限 最 长 时 间 的 任 务 被 分 配 最低 优 先 级 。 2008年6月24日南京大学计算机系49 最 早 截 止 时 间 优 先 ( 续 )l 抢 占 式 EDF调 度 算 法 基 于 如 下 的 假 设 l 所 有 实 时 任 务 的 启 动 时 间 为 零 ;l 所 有 的 任 务 都 是 无 关 的 , 不 存 在 先 后 次 序 的 约 束 ;l 任 何 任 务 不 存 在 不 可 抢 占 的 代 码 段 , 且 抢 占 的 代 价可 以 忽 略 ;l 只 有 处 理 器 请 求 是 有 意 义 的 , 内 存 、 I/O和 其 它 资源 请 求 可 以 忽 略 ;l 任 务 的 相 对 最 终 完 成 时 限 与 它 的 周 期 相 等 2008年6月24日南京大学计算机系50 最 小 空 闲 时 间 优 先 l 是 对 经 典 的 动 态 优 先 级 算 法 EDF的 改 进l 提 出 了 空 闲 时 间 ( 也 就 是 时 间 裕 度 ) 的 概 念 ,进 程 的 优 先 级 由 空 闲 时 间 大 小 决 定 l LSF算 法 的 缺 点 : 由 于 等 待 任 务 的 空 闲 时 间 是递 减 的 , 其 等 待 执 行 的 缓 急 程 度 也 随 时 间 逝 去越 来 越 紧 迫 , 因 此 在 系 统 执 行 过 程 中 , 等 待 任务 随 时 可 能 会 抢 占 当 前 执 行 的 任 务 2008年6月24日南京大学计算机系51 静 态 的 与 动 态 的 基 于 优 先 级 调 度 算法 比 较 l 静 态 调 度 算 法 适 合 于 任 务 时 间 要 素 比 较 明 确 场合 l 静 态 调 度 算 法 不 适 合 用 于 任 务 时 限 未 明 确 场 合l 动 态 调 度 算 法 需 要 不 断 地 调 整 任 务 的 优 先 级 别 ,以 适 应 任 务 时 限 变 化 的 执 行 环 境 l 一 般 而 言 , 动 态 优 先 级 调 度 算 法 对 资 源 的 利 用率 高 于 静 态 优 先 级 调 度 算 法 2008年6月24日南京大学计算机系52 时 钟 驱 动 调 度 算 法l 该 算 法 是 系 统 调 度 程 序 通 过 时 钟 驱 动 , 在 事 先确 定 的 某 些 时 刻 做 出 调 度 决 策l 作 业 的 调 度 表 可 以 脱 机 计 算 并 保 存 下 来 l 运 行 时 的 调 度 开 销 可 被 最 小 化 l 调 度 时 刻 通 常 由 一 个 硬 件 定 时 器 的 时 钟 中 断 产生 l 采 用 该 算 法 的 嵌 入 式 操 作 系 统 可 以 是 实 时 的 ,也 可 以 是 分 时 的 2008年6月24日南京大学计算机系53 基 于 比 例 共 享 的 调 度 算 法l 基 本 思 想 就 是 按 照 一 定 的 权 重 ( 比 例 ) 对 一 组需 要 调 度 的 任 务 进 行 调 度 , 让 它 们 的 执 行 时 间与 它 们 的 权 重 完 全 成 正 比 l 通 过 两 种 方 法 来 实 现 比 例 共 享 调 度 算 l 第 一 种 方 法 是 调 节 各 个 就 绪 进 程 出 现 在 调 度 队 列 队首 的 频 率 , 并 调 度 队 首 的 进 程 执 行 l 第 二 种 做 法 就 是 逐 次 调 度 就 绪 队 列 中 的 各 个 进 程 投入 运 行 , 但 根 据 分 配 的 权 重 调 节 分 配 给 每 个 进 程 的运 行 时 间 片 2008年6月24日南京大学计算机系54 非 周 期 任 务 的 调 度l 非 周 期 任 务 被 实 时 系 统 用 来 响 应 外 部 触 发 事 件 ,非 周 期 任 务 完 成 的 时 间 越 快 , 系 统 的 响 应 性 能越 好 l 实 时 系 统 设 计 重 要 目 标 之 一 是 提 高 混 合 任 务 集的 响 应 性 能 , 也 就 是 说 除 了 保 证 周 期 任 务 得 到正 确 执 行 外 , 还 应 该 减 小 非 周 期 任 务 的 响 应 时间 l 非 周 期 任 务 的 调 度 三 种 方 法 : 后 台 处 理 、 中 断驱 动 执 行 和 周 期 查 询 执 行 。 2008年6月24日南京大学计算机系55 临 界 资 源 和 代 码 临 界 区l 临 界 资 源 指 在 一 段 时 间 只 允 许 一 个 进 程 访 问 的资 源 。l 硬 件 临 界 资 源 和 软 件 临 界 资 源 之 分l 代 码 临 界 区 指 处 理 时 不 可 分 割 的 代 码l 进 入 临 界 区 时 必 须 关 中 断l 执 行 完 临 界 区 代 码 之 后 要 立 即 开 中 断 2008年6月24日南京大学计算机系56 优 先 级 反 转 和 对 策l 优 先 级 翻 转 现 象l 由 于 多 进 程 共 享 资 源 , 具 有 最 高 优 先 权 的 进 程 被低 优 先 级 进 程 阻 塞 , 反 而 使 具 有 中 优 先 级 的 进 程先 于 高 优 先 级 的 进 程 执 行 , 导 致 系 统 的 崩 溃 。l 解 决 该 问 题 的 方 法l 优 先 级 封 顶 协 议l 优 先 级 继 承 协 议 2008年6月24日南京大学计算机系57 9.4 启 动 程 序 Bootloaderl 本 节 讲 授 以 下 内 容l 嵌 入 式 系 统 的 启 动 方 式l Bootloader的 程 序 结 构 与 调 试l Bootloader人 机 交 互 接 口 设 计l 常 用 Bootloader介 绍 2008年6月24日南京大学计算机系58 启 动 程 序 Bootloaderl 属 于 嵌 入 式 软 件 最 底 层 的 部 分 。l 从 软 件 角 度 ( 分 两 部 分 )l 固 件 ( fireware) 中 的 引 导 代 码 ( 可 选 )l Bootloader 2008年6月24日南京大学计算机系59 嵌 入 式 系 统 的 启 动 方 式l 整 个 系 统 的 加 载 启 动 任 务 就 完 全 由 Bootloader完 成 。l 是 嵌 入 式 系 统 加 电 后 运 行 的 第 一 段 软 件 代 码 ,先 于 内 核 以 及 用 户 应 用 程 序 运 行 。l Bootloader初 始 化 硬 件 设 备 、 建 立 内 存 空 间 的映 射 图 , 从 而 将 系 统 的 软 硬 件 环 境 设 定 在 一 个正 确 的 状 态 , 以 便 接 下 来 加 载 操 作 系 统 内 核 、运 行 用 户 应 用 程 序 。 2008年6月24日南京大学计算机系60 Bootloader系 统 架 构 用 例 分 析 参数设置(from Use Case View)内存管理 (from Use Case View) TFTP下载(from Use Case View) Flash烧写 (from Use Case View) 下载模式(from Use Case View) 开发者 硬件初始化(from Use Case View)参数配置 (from Use Case View) 用户 正常启动加载(from Use Case View) RARP/TFTP启动加载(from Use Case View) BOOTP/TFTP启动加载(from Use Case View) 启动加载模式(from Use Case View) 2008年6月24日南京大学计算机系61 Bootloader的 安 装l 对 于 每 一 个 嵌 入 式 硬 件 电 路 板 , 需 要 开 发 人 员 单 独 编写 该 电 路 板 所 使 用 的 Bootloader代 码 l 安 装l 统 加 电 或 复 位 后 , 所 有 的 微 处 理 器 通 常 都 从 某 个 由 CPU制 造商 预 先 安 排 的 地 址 上 取 指 令 。 通 常 基 于 微 处 理 器 构 建 的 嵌 入式 系 统 都 有 某 种 类 型 的 固 态 存 储 设 备 被 映 射 到 这 个 预 先 安 排的 地 址 上 。 而 Bootloader则 从 这 个 地 址 开 始 固 化 到 固 态 存 储设 备 中 l 例 如 , 基 于 ARM7TDMI核 的 微 处 理 器 在 复 位 时 都 从 地 址0 x00000000取 得 它 的 第 一 条 指 令 。 2008年6月24日南京大学计算机系62 Bootloader的 操 作 方 式l 两 种 操 作 模 式l 启 动 加 载 模 式 和 下 载 模 式l 启 动 加 载 模 式 ( boot loading)l 也 称 自 主 ( Autonomous) 模 式 , 是 指 Bootloader从目 标 机 上 的 某 个 固 态 存 储 设 备 上 将 操 作 系 统 加 载 到RAM中 运 行 , 整 个 过 程 并 没 有 用 户 的 介 入l 是 Bootloader的 正 常 工 作 模 式 , 在 嵌 入 式 产 品 完 工交 付 时 或 者 实 际 使 用 时 , 必 须 使 得 Bootloader工 作在 这 种 模 式 下 2008年6月24日南京大学计算机系63 Bootloader的 操 作 方 式 ( 续 1)l 下 载 模 式 ( downloading)l 目 标 板 上 的 Bootloader将 先 通 过 串 口 连 接 或 网 络 连接 等 通 信 手 段 从 主 机 下 载 文 件 l Bootloader 的 这 种 模 式 通 常 在 开 发 过 程 中 以 及 第 一次 安 装 内 核 与 根 文 件 系 统 时 被 使 用 , 此 外 , 以 后 的系 统 更 新 也 会 用 到 Bootloader的 这 种 工 作 模 式 l 这 种 模 式 下 的 Bootloader通 常 都 会 向 它 的 终 端 用 户提 供 一 个 简 单 的 命 令 行 接 口 2008年6月24日南京大学计算机系64 Bootloader通 信 接 口 及 协 议l 两 种 通 信 方 式l 串 口 通 信常 用 的 串 口 协 议 : XMODEM, YMODEM和ZMODEMl 以 太 网 通 信常 用 协 议 : TFTP 2008年6月24日南京大学计算机系65 Bootloader的 程 序 结 构 与 调 试l Bootloader的 实 现 依 赖 于 CPU的 体 系 结 构 , 故大 多 数 Bootloader都 分 为 stage1和 stage2两 大 部分 l stage1的 主 要 操 作 l 基 本 的 硬 件 初 始 化 l 为 加 载 stage2准 备 RAM空 间l 拷 贝 stage2的 执 行 代 码 到 RAM中 l 设 置 栈 区 指 针 SPl 跳 转 到 stage2的 入 口 点 2008年6月24日南京大学计算机系66 Bootloader的 程 序 结 构 与 调 试 ( 续 )l stage2的 主 要 操 作l 初 始 化 本 阶 段 要 使 用 的 硬 件 设 备l 检 测 系 统 的 内 存 映 射l Bootloader的 调 试l 交 叉 调 试 技 术l 可 分 为 硬 件 调 试 和 源 码 软 件 调 试 2008年6月24日南京大学计算机系67 Bootloader人 机 交 互 接 口 设 计l 通 过 串 口 实 现 。 用 户 使 用 超 级 终 端 或 minicom与 目 标 板 通 信l U-Boot是 目 前 广 泛 使 用 的 一 个 通 用 引 导 加 载 程序 2008年6月24日南京大学计算机系68 常 用 Booloader介 绍l U-Bootl U-Boot全 称 Universal Bootloader, 是 德 国 DENX软件 公 司 开 发 的 , 用 于 多 种 嵌 入 式 CPU的 Bootloader程 序 l U-Boot不 仅 支 持 嵌 入 式 Linux系 统 的 引 导 , 还 能 支持 NetBSD、 VxWorks、 QNX、 RTEMS、 ARTOS、LynxO、 Windows CE、 QNX等 嵌 入 式 操 作 系 统 的 引导 2008年6月24日南京大学计算机系69 常 用 Booloader介 绍 ( 续 1)l Redbootl RedBoot, 是 基 于 eCos实 时 操 作 系 统 硬 件 抽 象 层 实现 的 一 个 嵌 入 式 系 统 的 引 导 程 序 l 支 持 的 处 理 器 也 很 多 , 包 括 PowerPC、 MIPS、 x86、ARM等 , 支 持 的 操 作 系 统 主 要 有 eCos和 Linux l RedBoot支 持 串 口 和 网 口 下 载 嵌 入 式 应 用 程 序 , 包括 嵌 入 式 Linux和 eCos的 应 用 2008年6月24日南京大学计算机系70 常 用 Booloader介 绍 ( 续 2)l ARMbootl ARMboot是 针 对 ARM处 理 器 编 写 的 开 源 固 件 套 件l ARMboot支 持 的 处 理 器 构 架 有 StrongARM,ARM720T, PXA250等 l ARMboot是 GPL下 的 ARM固 件 项 目 中 为 数 不 多 的 多种 功 能 嵌 入 式 操 作 系 统 引 导 加 载 程 序 。 它 能 够 支 持闪 存 , BOOTP、 DHCP、 TFTP网 络 下 载 ,PCMCLA的 CF卡 引 导 等 2008年6月24日南京大学计算机系71 第 18讲 重 点l 实 时 系 统 的 定 义 、 特 点 和 分 类l 嵌 入 式 操 作 系 统 特 点 和 分 类l 术 语 内 核 的 内 涵 与 外 延l 抢 占 式 内 核l 微 内 核l RTOS常 用 调 度 算 法l RMS算 法l DMS算 法l 启 动 程 序 Bootloader l 两 种 Bootloader类 型l Bootloader程 序 结 构l 常 用 的 Bootloader介 绍 2008年6月24日南京大学计算机系72 第 18讲 复 习 题 思 考 题l 请 列 举 出 在 你 周 围 的 典 型 实 时 系 统 , 并 说 明 它 们 的 系 统 结构 和 特 点 。l 试 分 析 教 材 第 315页 图 9-2的 非 抢 占 式 内 核 和 抢 占 式 内 核 的操 作 时 序 区 别 。l 中 断 服 务 子 程 序 的 执 行 对 抢 占 式 内 核 的 任 务 调 度 有 何 影 响 ?l 如 何 理 解 嵌 入 式 操 作 系 统 的 可 配 置 性 和 可 裁 减 性 ? 它 们 是同 一 个 术 语 吗 ? 试 比 较 它 们 的 共 同 点 和 不 同 点 。l 考 察 一 些 知 名 的 嵌 入 式 操 作 系 统 , 试 说 明 它 们 是 属 于 单 内核 还 是 微 内 核 , 判 断 的 依 据 又 是 什 么 ? l 如 果 在 嵌 入 式 开 发 过 程 中 遇 到 优 先 级 反 转 问 题 , 你 认 为 应该 如 何 处 理 2008年6月24日南京大学计算机系73 第 18讲 复 习 题 思 考 题 ( 续 )l 试 阅 读 S3C44B0X实 验 平 台 上 不 含 操 作 系 统 的 Bootloader源代 码 , 在 理 解 的 基 础 上 绘 制 该 启 动 代 码 的 流 程 图 。 试 阅 读S3C44B0X实 验 平 台 上 基 于 C/OS-II操 作 系 统 的 Bootloader源 代 码 , 在 理 解 的 基 础 上 绘 制 该 启 动 代 码 的 流 程 图 。 比 较这 两 种 Bootloader的 不 同 之 处 。l 试 列 出 你 所 知 道 的 常 用 的 Bootloader, 并 且 比 较 它 们 的 特点 和 适 用 范 围 。l 针 对 图 9-10的 火 星 探 路 者 优 先 级 反 转 案 例 , 试 编 写 一 个 基于 C/OS-II操 作 系 统 的 实 验 程 序 , 该 实 验 程 序 能 够 反 映 这种 优 先 级 反 转 的 时 序 特 点 , 而 后 考 虑 如 何 采 取 措 施 避 免 发生 这 种 错 误 操 作 。 2008年6月24日南京大学计算机系74 第 19讲 结 束l 谢 谢 大 家 !l 欢 迎 各 位 读 者 提 出 宝 贵 的 意 见 和 建 议 !
展开阅读全文