Cache(高速缓存)与主存一致性初探 毕业论文.doc

本 科 生 毕 业 论 文 (设 计 ) cache(高 速 缓 存 )与 主 存 一 致 性 初 探 院 系 名 称 信 息 工 程 系 姓 名 姓 名 学 号 2008341142 专 业 计 算 机 科 学 与 技 术 专 业 指 导 教 师 导 师 教 授 2012 年 3 月 25 日 ii 摘 要 存 储 器 是 具 有 “记 忆 ”功 能 的 部 件 ， 它 在 计 算 机 系 统 中 占 有 十 分 重 要 的 地 位 。 存 储 器 的 基 本 功 能 是 存 放 以 二 进 制 形 式 表 示 的 程 序 与 数 据 。 如 何 设 计 容 量 大 、 速 度 快 且 造 价 低 的 存 储 器 ， 一 直 是 计 算 机 发 展 中 的 关 键 问 题 ， 目 前 还 没 有 哪 一 种 存 储 器 功 能 完 全 满 足 计 算 机 系 统 对 存 储 器 的 需 求 。 因 此 ， 计 算 机 系 统 通 常 配 备 分 层 结 构 的 存 储 系 统 ， 以 满 足 容 量 、 速 度 和 造 价 等 方 面 的 要 求 。 衡 量 存 储 器 有 三 个 指 标 ： 容 量 、 速 度 和 价 格 /位 。 一 般 地 说 ， 速 度 高 的 存 储 器 ， 每 位 价 格 也 高 ， 因 此 容 量 不 能 太 大 。 所 以 存 储 器 设 计 的 约 束 有 容 量 、 速 度 和 价 格 。 容 量 似 乎 没 有 限 制 ， 不 管 容 量 多 大 ， 总 要 开 发 出 应 用 程 序 来 使 用 。 为 了 获 得 更 好 的 性 能 ， 存 储 器 的 速 度 必 须 能 够 跟 上 cpu， 即 当 cpu 执 行 指 令 时 ， 不 想 让 他 停 下 来 等 待 指 令 或 操 作 数 。 价 格 问 题 也 必 须 考 虑 ， 对 于 实 用 的 系 统 ， 存 储 器 的 价 格 必 须 相 对 于 其 他 部 件 是 合 理 的 。 因 此 三 个 指 标 之 间 需 要 进 行 权 衡 。 高 速 缓 存 系 统 中 能 否 确 保 高 速 缓 冲 存 储 器 和 主 存 内 容 一 致 性 ， 这 个 问 题 直 接 关 系 到 整 个 计 算 机 系 统 的 性 能 。 这 两 部 分 的 数 据 一 致 性 问 题 产 生 的 原 因 有 二 ： 其 一 ， 由 于 cpu 对 高 速 缓 冲 存 储 器 的 写 入 导 致 它 的 内 容 更 新 而 主 存 内 容 陈 旧 ； 其 二 ， 由 于 i/o 处 理 机 或 多 处 理 机 系 统 中 某 一 处 理 机 修 改 了 主 存 内 容 导 致 高 速 缓 冲 存 储 器 内 容 陈 旧 。 针 对 不 同 原 因 ， 分 析 了 写 策 略 中 七 种 解 决 方 案 ， 并 就 高 速 缓 存 系 统 采 用 的 第 二 级 脱 片 高 速 缓 冲 存 储 器 ， 以 及 第 三 级 脱 片 高 速 缓 冲 存 储 器 结 构 数 据 一 致 性 问 题 进 行 初 步 探 讨 。 本 文 通 过 对 存 储 器 系 统 cache（ 高 速 缓 存 ） 与 主 存 的 概 念 进 行 描 述 和 目 前 两 者 之 间 一 致 性 存 在 的 一 些 问 题 进 行 研 究 。 并 分 析 在 多 处 理 机 系 统 中 ， 主 存 与 各 处 理 机 私 有 cache 之 间 及 各 私 有 cache 之 间 存 在 的 数 据 不 一 致 性 。 对 解 决 不 一 致 性 的 方 法 ： 监 听 总 线 协 议 、 基 于 目 录 的 cache 一 致 性 协 议 、 软 件 控 制 方 法 等 进 行 详 细 的 定 性 分 析 ， 并 指 出 各 种 方 法 的 优 缺 点 ， 供 设 计 者 参 考 ； 同 时 提 出 软 件 和 硬 件 相 结 合 的 方 法 ， 能 有 效 解 决 cache 的 一 致 性 问 题 。 关 键 词 ： 存 储 器 ； 主 存 ； 缓 存 ； 一 致 性 iii abstract memory is a “ memory “ function components , it in a computer system occupies a very important position . the basic function of memory is stored in binary form of said programs and data . how to design capacity , speed is quick and low cost of memory , is always the key problems in the development of the computer , there is no memory function fully meet the needs of the memory of a computer system. therefore, the computer system usually equipped with a layered structure of storage system, to satisfy the capacity, speed and cost requirements. measure memory has three index : capacity , speed and price/a. generally speaking , the high speed of memory, every price is high , therefore capacity can not be too big . so memory design constraints capacity , speed and price . there seems to be no limit capacity , no matter how much capacity , the total to develop applications to use . in order to obtain the better performance, the speed of the memory must be able to keep up with the cpu,and that is when the cpu executing instructions , dont want him to stop and wait for instructions or operand. the question of price must also consider, for practical system, memory prices relative to other parts must be is reasonable. so the three indexes to weigh between. cache system can ensure cache memory and main memory contents consistency , the directly related to the entire computer system performance . the two parts of the data consistency issues of two reasons : first , because of the cpu cache memory write led to its contents to update the memory and out-of-date contents ; second , because of i/o processor or multi-processor systems of a processor modified the main memory contents lead to cache content obsolete . according to different reasons , analyzes the strategy of written seven kinds of solutions, and the cache system uses 2 to take off the piece of cache, and the third class to take off the piece of cache structure data consistency problem for a preliminary discussion. this article through to the memory system cache ( cache ) and the concept of main storage describe between consistency and at present there are some problems. and analysis in multiprocessor system , main memory with the processor cache between the private and private cache of inconsistency between data. to solve the inconsistency method: surveillance bus agreement, the cache directory based on consistency agreement, software control method of detailed qualitative analysis , and points out the advantages and disadvantages of each method for designers ; some software and hardware the method of combining the cache can effectively resolve the consistency of the problem. key words: memory , the main memory , cache , the consistency iv 目 录 1 引 言 .1 2 研 究 的 背 景 和 意 义 .2 2.1 研 究 的 背 景 .2 2.1.1 主 -辅 存 存 储 层 次 2 2.1.2 cache-主 存 存 储 层 次 .3 2.1.3 存 储 器 分 层 结 构 .3 2.2 研 究 的 意 义 .5 3 数 据 一 致 性 问 题 的 提 出 .7 4 基 于 不 同 原 因 的 写 策 略 解 决 方 案 .9 4.1 基 于 原 因 1 的 解 决 办 法 .9 4.1.1 写 直 达 .9 4.1.2 写 回 发 .9 4.2 基 于 原 因 2 的 解 决 办 法 .9 4.2.1 总 线 监 视 法 .9 4.2.2 硬 件 监 视 法 10 4.2.3 划 出 不 可 高 速 缓 存 存 储 区 法 10 4.2.4 cache 清 除 法 .10 4.3 基 于 原 因 3 的 解 决 办 法 10 4.4 基 于 目 录 的 cache 一 致 性 协 议 10 5 数 据 一 致 性 问 题 的 发 展 与 展 望 13 6 结 束 语 15 参 考 文 献 16 致 谢 18 1 1 引 言 高 速 缓 冲 存 储 器 是 存 在 于 主 存 与 cpu 之 间 的 一 级 存 储 器 ， 由 静 态 存 储 芯 片 (sram)组 成 ， 容 量 比 较 小 但 速 度 比 主 存 高 得 多 ， 接 近 于 cpu 的 速 度 。 在 计 算 机 存 储 系 统 的 层 次 结 构 中 ， 是 介 于 中 央 处 理 器 和 主 存 储 器 之 间 的 高 速 小 容 量 存 储 器 。 它 和 主 存 储 器 一 起 构 成 一 级 的 存 储 器 。 高 速 缓 冲 存 储 器 和 主 存 储 器 之 间 信 息 的 调 度 和 传 送 是 由 硬 件 自 动 进 行 的 。 高 速 缓 冲 存 储 器 的 容 量 一 般 只 有 主 存 储 器 的 几 百 分 之 一 ， 但 它 的 存 取 速 度 能 与 中 央 处 理 器 相 匹 配 。 根 据 程 序 局 部 性 原 理 ， 正 在 使 用 的 主 存 储 器 某 一 单 元 邻 近 的 那 些 单 元 将 被 用 到 的 可 能 性 很 大 。 因 而 ， 当 中 央 处 理 器 存 取 主 存 储 器 某 一 单 元 时 ， 计 算 机 硬 件 就 自 动 地 将 包 括 该 单 元 在 内 的 那 一 组 单 元 内 容 调 入 高 速 缓 冲 存 储 器 ， 中 央 处 理 器 即 将 存 取 的 主 存 储 器 单 元 很 可 能 就 在 刚 刚 调 入 到 高 速 缓 冲 存 储 器 的 那 一 组 单 元 内 。 于 是 ， 中 央 处 理 器 就 可 以 直 接 对 高 速 缓 冲 存 储 器 进 行 存 取 。 在 整 个 处 理 过 程 中 ， 如 果 中 央 处 理 器 绝 大 多 数 存 取 主 存 储 器 的 操 作 能 为 存 取 高 速 缓 冲 存 储 器 所 代 替 ， 计 算 机 系 统 处 理 速 度 就 能 显 著 提 高 。 当 然 ， 计 算 机 存 储 系 统 中 ， 高 速 缓 冲 存 储 器 系 统 的 引 入 虽 然 为 计 算 机 系 统 处 理 数 据 的 速 度 带 来 了 显 著 地 提 高 ， 但 是 随 之 而 来 的 cache（ 高 速 缓 存 ） 与 主 存 间 数 据 一 致 性 问 题 也 是 日 益 凸 显 出 来 。 存 储 器 中 的 一 致 性 问 题 ， 是 伴 随 着 存 储 器 结 构 的 概 念 而 提 出 的 ， 又 一 直 是 困 扰 着 计 算 机 设 计 者 的 一 个 重 要 问 题 ， 也 是 很 多 从 事 计 算 机 体 系 结 构 研 究 的 人 们 所 共 同 面 对 的 一 个 热 门 研 究 课 题 。 特 别 是 近 年 来 出 现 的 多 处 理 系 统 ， 超 并 行 机 系 统 ， 超 大 规 模 计 算 机 系 统 等 采 用 dsm（ distributed shared memory） -分 布 式 共 享 存 储 器 技 术 的 大 型 系 统 中 ， 都 采 用 了 多 级 cache 的 存 储 器 层 次 结 构 。 在 cache 的 数 据 一 致 性 问 题 上 ， 就 更 显 突 出 了 。 如 在 dsm 多 处 理 机 系 统 结 构 中 ， 相 邻 层 之 间 和 同 一 层 之 内 可 能 会 出 现 数 据 不 一 致 性 。 通 过 存 储 器 的 共 享 数 据 ， 进 程 在 同 一 算 法 下 并 行 工 作 。 为 了 减 少 内 存 访 问 延 时 和 内 存 总 线 的 拥 塞 ， 要 求 cache 与 每 个 处 理 器 相 关 。 这 样 同 一 数 据 在 不 同 的 cache 中 有 多 个 副 本 。 当 处 理 机 对 共 享 存 储 器 某 个 单 元 在 其 本 地 cache 中 的 拷 贝 要 进 行 维 护 时 ， 只 要 对 该 单 元 的 本 地 拷 贝 进 行 修 改 ， 这 就 有 可 能 引 起 存 储 器 的 全 局 不 一 致 性 等 等 。 所 以 如 何 在 维 护 一 致 性 情 况 下 又 保 证 处 理 机 代 价 最 小 是 这 本 论 文 讨 论 的 主 要 问 题 。 本 文 将 在 对 计 算 机 存 储 系 统 存 储 进 行 介 绍 的 前 提 下 ， 对 高 速 缓 存 系 统 中 cache（ 高 速 缓 存 ） 与 主 存 这 两 部 分 的 数 据 一 致 性 问 题 产 生 的 各 种 原 因 进 行 充 分 的 分 析 和 研 究 ， 并 针 对 不 同 的 原 因 ， 给 予 适 当 各 种 维 护 策 略 下 的 保 证 一 致 性 的 可 行 方 案 。 2 2 研 究 的 背 景 和 意 义 2.1 研 究 的 背 景 存 储 器 是 具 有 “记 忆 ”功 能 的 部 件 ， 它 在 计 算 机 系 统 中 占 有 十 分 重 要 的 地 位 。 存 储 器 的 基 本 功 能 是 存 放 以 二 进 制 形 式 表 示 的 程 序 与 数 据 。 如 何 设 计 容 量 大 、 速 度 快 且 造 价 低 的 存 储 器 ， 一 直 是 计 算 机 发 展 中 的 关 键 问 题 ， 目 前 还 没 有 哪 一 种 存 储 器 功 能 完 全 满 足 计 算 机 系 统 对 存 储 器 的 需 求 。 因 此 ， 计 算 机 系 统 通 常 配 备 分 层 结 构 的 存 储 系 统 ， 以 满 足 容 量 、 速 度 和 造 价 等 方 面 的 要 求 。 衡 量 存 储 器 有 三 个 指 标 ： 容 量 、 速 度 和 价 格 /位 。 一 般 地 说 ， 速 度 高 的 存 储 器 ， 每 位 价 格 也 高 ， 因 此 容 量 不 能 太 大 。 所 以 存 储 器 设 计 的 约 束 有 容 量 、 速 度 和 价 格 。 容 量 似 乎 没 有 限 制 ， 不 管 容 量 多 大 ， 总 要 开 发 出 应 用 程 序 来 使 用 。 为 了 获 得 更 好 的 性 能 ， 存 储 器 的 速 度 必 须 能 够 跟 上 cpu， 即 当 cpu 执 行 指 令 时 ， 不 想 让 他 停 下 来 等 待 指 令 或 操 作 数 。 价 格 问 题 也 必 须 考 虑 ， 对 于 实 用 的 系 统 ， 存 储 器 的 价 格 必 须 相 对 于 其 他 部 件 是 合 理 的 。 因 此 三 个 指 标 之 间 需 要 进 行 权 衡 。 2.1.1 主-辅存存储层次 由 于 计 算 机 主 存 容 量 相 对 于 程 序 员 所 需 要 的 容 量 来 说 总 是 太 小 ， 程 序 与 数 据 从 辅 存 调 入 主 存 是 由 程 序 员 自 己 安 排 的 ， 程 序 员 必 须 花 费 很 大 精 力 和 时 间 把 大 程 序 预 先 分 成 块 ， 确 定 好 这 些 程 序 块 在 辅 存 中 的 位 置 和 装 入 主 存 的 地 址 ， 而 且 还 要 预 先 安 排 好 程 序 运 行 时 各 块 如 何 和 何 时 调 入 调 出 ， 因 此 存 在 存 储 空 间 的 分 配 问 题 。 操 作 系 统 的 形 成 和 发 展 使 得 程 序 员 尽 可 能 摆 脱 主 、 辅 存 之 间 的 地 址 定 位 ， 同 时 形 成 了 支 持 这 些 功 能 的 “辅 助 硬 件 ”， 通 过 软 件 、 硬 件 的 结 合 ， 把 主 存 和 辅 存 统 一 成 了 一 个 整 体 ， 如 图 2-1 所 示 。 这 时 ， 由 主 存 、 辅 存 形 成 了 一 个 存 储 层 次 ， 即 存 储 系 统 。 从 整 体 看 ， 其 速 度 接 近 于 主 存 的 速 度 ， 其 容 量 则 接 近 于 辅 存 的 容 量 ， 而 每 位 的 平 均 价 格 也 接 近 于 廉 价 的 慢 速 的 辅 存 平 均 价 格 。 这 种 系 统 不 断 发 展 和 完 善 ， 就 逐 步 形 成 了 现 在 广 泛 使 用 的 虚 拟 存 储 系 统 。 在 系 统 中 ， 应 用 程 序 员 可 用 机 器 指 令 地 址 码 对 整 个 程 序 统 一 编 址 ， 如 同 程 序 员 具 有 对 应 这 个 地 址 码 宽 度 的 全 部 虚 存 空 间 一 样 。 该 空 间 可 以 比 主 存 实 际 空 间 大 得 多 ， 以 致 可 以 存 得 下 整 个 程 序 。 这 种 指 令 地 址 码 称 为 虚 地 址 （ 虚 存 地 址 、 虚 拟 地 址 ） 或 逻 辑 地 址 ， 其 对 应 的 存 储 容 量 称 为 虚 存 容 量 或 虚 存 空 间 ； 而 把 实 际 主 存 的 地 址 称 为 物 理 地 址 、 实 （ 存 ） 地 址 ， 其 对 应 的 存 储 容 量 称 为 主 存 容 量 、 实 存 容 量 或 实 （ 主 ） 存 空 间 。 3 图 2-1 主 -辅 存 存 储 层 次 2.1.2 cache-主存存储层次 当 用 虚 地 址 访 问 主 存 时 ， 机 器 自 动 地 把 它 经 辅 助 软 件 、 硬 件 变 换 成 主 存 实 地 址 。 察 看 这 个 地 址 所 对 应 的 单 元 内 容 是 否 已 经 装 入 主 存 ， 如 果 在 主 存 就 进 行 访 问 ， 如 果 不 在 主 存 内 就 经 辅 助 软 件 、 硬 件 把 它 所 在 的 那 块 程 序 和 数 据 由 辅 存 调 入 主 存 ， 而 后 进 行 访 问 。 这 些 操 作 都 不 必 由 程 序 员 来 安 排 ， 也 就 是 说 ， 对 应 用 程 员 员 是 透 明 的 。 主 -辅 存 层 次 解 决 了 存 储 器 大 容 量 要 求 和 低 成 本 之 间 的 矛 盾 。 在 速 度 方 面 ， 计 算 机 的 主 存 和 cpu 直 保 持 了 大 约 一 个 数 量 级 的 差 距 。 显 然 这 个 差 距 限 制 了 cpu 速 度 潜 力 的 发 挥 。 为 了 弥 合 这 个 差 距 ， 仅 采 用 一 种 工 艺 的 单 一 存 储 器 是 行 不 通 的 ， 必 须 进 一 步 从 计 算 机 系 统 结 构 和 组 织 上 去 研 究 。 设 置 高 速 缓 冲 存 储 器 （ cache） 是 解 决 存 取 速 度 的 重 要 方 法 。 在 cpu 和 主 存 中 间 设 置 高 速 缓 冲 存 储 器 ， 构 成 高 速 缓 存 （ cache） -主 存 层 次 ， 要 求 cache 在 速 度 上 能 跟 得 上 cpu 的 要 求 。 cache-主 存 间 的 地 址 映 象 和 调 度 吸 取 了 比 它 较 早 出 现 的 主 -辅 存 存 储 层 次 的 技 术 ， 不 同 的 是 因 其 速 度 要 求 高 ， 不 是 由 软 、 硬 件 结 合 而 完 全 由 硬 件 来 实 现 ， 如 图 2-2 所 示 。 图 2-2 cache-主 存 存 储 层 次 2.1.3 存储器分层结构 从 cpu 的 角 度 看 ， cache-主 存 层 次 的 速 度 接 近 于 cache， 容 量 与 每 位 价 格 接 近 于 主 存 ， 因 此 ， 解 决 了 速 度 与 成 本 之 间 的 矛 盾 。 4 综 上 所 述 ， 计 算 机 的 存 储 系 统 是 采 用 了 存 储 器 的 分 层 结 构 ， 而 不 只 是 依 赖 单 一 的 存 储 部 件 或 技 术 。 图 2-3 给 出 了 一 个 通 用 分 层 结 构 ， 图 中 从 上 到 下 出 现 情 况 如 下 ： 1每 位 的 价 格 降 低 ； 2容 量 增 大 ； 3存 取 时 间 增 大 ； 4cpu 存 取 存 储 器 的 频 度 降 低 。 图 2-3 存 储 器 分 层 结 构 因 此 ， 较 小 、 较 贵 、 较 快 的 存 储 器 可 作 为 较 大 、 较 便 宜 、 较 慢 的 存 储 器 的 补 充 。 这 个 结 构 成 功 的 关 键 是 最 后 一 项 ， 即 存 取 频 度 降 低 。 如 果 能 够 根 据 以 上 的 1到 3项 来 组 织 存 储 器 ， 而 且 数 据 和 指 令 能 够 根 据 4分 布 在 存 储 器 中 ， 很 显 然 ， 这 个 方 案 在 保 证 给 定 的 性 能 水 平 的 情 况 下 能 降 低 总 体 价 格 。 下 面 用 一 个 简 单 的 例 子 来 说 明 这 一 点 。 假 设 cpu 能 够 存 取 二 级 的 存 储 器 ， 第 1 级 包 含 1000 个 字 并 有 1 微 秒 的 存 取 时 间 ， 第 2 级 包 含 1000000 个 字 并 有 10 微 秒 的 存 取 时 间 。 假 设 要 存 取 的 一 个 字 在 第 1 级 ， 那 么 cpu 能 直 接 存 取 它 ； 假 设 它 在 第 2 级 ， 则 这 个 字 首 先 传 到 第 1 级 ， 然 后 再 由 cpu 存 取 它 。 为 了 简 化 ， 不 考 虑 cpu 确 定 这 个 字 在 第 1 级 还 是 在 第 2 级 所 需 的 时 间 。 图 2-4 表 示 了 平 均 总 存 取 时 间 和 在 第 1 级 中 存 取 字 所 需 的 时 间 占 总 的 百 分 比 的 函 数 关 系 。 可 见 ， 第 1 级 存 取 百 分 比 高 时 ， 平 均 总 的 存 取 时 间 接 近 于 第 1 级 的 存 取 时 间 。 此 例 说 明 了 这 种 策 略 工 作 的 原 理 。 如 果 条 件 1到 4都 满 足 ， 则 它 能 工 作 。 5 图 2-4 简 单 的 两 级 存 储 性 能 条 件 4有 效 的 基 础 是 访 问 局 部 性 原 理 。 在 程 序 执 行 过 程 中 ， 处 理 器 访 问 存 储 器 中 的 指 令 和 数 据 倾 向 于 成 块 进 行 。 程 序 通 常 包 含 许 多 迭 代 循 环 的 子 程 序 ， 一 旦 进 入 了 一 个 循 环 或 子 程 序 ， 则 需 重 复 访 问 一 小 组 指 令 。 同 样 ， 对 于 表 和 数 组 的 操 作 ， 包 含 存 取 一 块 块 的 数 据 字 。 在 一 长 段 时 间 内 ， 使 用 的 块 是 变 化 的 ， 而 在 一 小 段 时 间 内 ， 处 理 器 主 要 访 问 存 储 器 中 的 固 定 块 。 因 此 ， 通 过 分 层 结 构 组 织 数 据 ， 有 可 能 使 存 取 较 低 层 的 存 取 时 间 百 分 比 低 于 存 取 高 层 的 百 分 比 。 根 据 上 面 给 出 的 二 级 例 子 ， 让 第 2 级 的 存 储 器 包 含 所 有 程 序 的 指 令 和 数 据 ， 当 前 的 块 临 时 放 在 第 1 级 ， 第 1 级 某 些 块 回 不 时 地 交 换 回 第 2 级 。 然 而 ， 多 数 是 对 第 1 级 中 的 指 令 和 数 据 的 访 问 。 这 个 原 理 可 以 应 用 到 两 级 以 上 的 存 储 器 。 考 虑 如 图 2-3 所 示 的 分 层 结 构 ， 最 快 、 最 小 和 最 贵 的 存 储 器 是 处 理 器 的 内 部 存 储 器 。 通 常 一 个 处 理 器 包 含 几 十 个 寄 存 器 ， 虽 然 有 些 机 器 包 含 几 百 个 寄 存 器 。 向 下 跳 二 层 是 主 存 储 器 。 主 存 储 器 通 常 用 一 个 速 度 更 快 、 容 量 更 小 的 高 速 缓 存 来 扩 充 。 高 速 缓 存 是 透 明 的 ， 它 在 主 存 和 处 理 器 寄 存 器 之 间 传 送 数 据 以 提 高 性 能 。 2.2 研 究 的 意 义 高 速 缓 冲 存 储 器 是 存 在 于 主 存 与 cpu 之 间 的 一 级 存 储 器 ， 由 静 态 存 储 芯 片 (sram)组 成 ， 容 量 比 较 小 但 速 度 比 主 存 高 得 多 ， 接 近 于 cpu 的 速 度 。 在 计 算 机 存 储 系 统 的 层 次 结 构 中 ， 介 于 中 央 处 理 器 和 主 存 储 器 之 间 的 高 速 小 容 量 存 储 器 。 它 和 主 存 储 器 一 起 构 成 一 级 的 存 储 器 。 高 速 缓 冲 存 储 器 和 主 存 储 器 之 间 信 息 的 调 度 和 传 送 是 由 硬 件 自 动 进 行 的 。 6 高 速 缓 冲 存 储 器 的 容 量 一 般 只 有 主 存 储 器 的 几 百 分 之 一 ， 但 它 的 存 取 速 度 能 与 中 央 处 理 器 相 匹 配 。 根 据 程 序 局 部 性 原 理 ， 正 在 使 用 的 主 存 储 器 某 一 单 元 邻 近 的 那 些 单 元 将 被 用 到 的 可 能 性 很 大 。 因 而 ， 当 中 央 处 理 器 存 取 主 存 储 器 某 一 单 元 时 ， 计 算 机 硬 件 就 自 动 地 将 包 括 该 单 元 在 内 的 那 一 组 单 元 内 容 调 入 高 速 缓 冲 存 储 器 ， 中 央 处 理 器 即 将 存 取 的 主 存 储 器 单 元 很 可 能 就 在 刚 刚 调 入 到 高 速 缓 冲 存 储 器 的 那 一 组 单 元 内 。 于 是 ， 中 央 处 理 器 就 可 以 直 接 对 高 速 缓 冲 存 储 器 进 行 存 取 。 在 整 个 处 理 过 程 中 ， 如 果 中 央 处 理 器 绝 大 多 数 存 取 主 存 储 器 的 操 作 能 为 存 取 高 速 缓 冲 存 储 器 所 代 替 ， 计 算 机 系 统 处 理 速 度 就 能 显 著 提 高 。 在 由 主 存 和 高 速 缓 存 组 成 的 存 储 器 层 次 结 构 中 ， 主 存 是 多 处 理 机 共 享 ， 而 高 速 缓 存 是 每 个 处 理 机 私 有 的 。 主 存 和 高 速 缓 存 都 以 块 为 单 位 进 行 划 分 ， 以 映 射 的 方 式 来 检 索 。 映 射 的 方 法 有 直 接 映 射 、 组 关 联 映 射 、 区 段 关 联 映 射 和 全 相 联 映 射 。 在 主 存 和 高 速 缓 存 之 间 ， 是 以 块 为 单 位 进 行 搬 送 。 主 存 中 保 存 有 各 高 速 缓 存 的 副 本 ， 高 速 缓 存 的 目 录 中 ， 存 放 相 应 主 存 的 块 号 及 一 些 标 志 。 通 过 对 目 录 的 检 索 来 寻 找 高 速 缓 存 中 的 数 据 。 当 处 理 机 发 出 一 个 访 问 主 存 地 址 时 ， 如 果 包 含 这 个 地 址 在 内 的 模 块 在 高 速 缓 存 中 ， 则 称 之 为 命 中 ， 该 高 速 缓 存 可 以 使 用 。 如 果 不 在 高 速 缓 存 中 ， 则 称 之 为 未 命 中 （ 或 cache 失 效 ） ， 这 时 ， 必 须 把 这 个 模 块 从 主 存 搬 到 高 速 缓 存 中 ， 叫 做 块 搬 送 。 如 果 高 速 缓 存 已 满 ， 则 必 须 按 一 定 的 置 换 算 法 挑 出 一 个 模 块 搬 出 高 速 缓 存 到 主 存 ， 这 叫 置 换 。 置 换 算 法 有 fifo 算 法 ， url 算 法 等 。 计 算 机 高 速 缓 存 系 统 的 发 展 为 计 算 机 设 计 者 提 出 了 一 个 重 要 课 题 ： 数 据 在 cache（ 高 速 缓 冲 存 储 器 ） 和 主 存 之 间 交 换 时 必 须 满 足 数 据 一 致 的 要 求 ， 随 着 多 任 务 系 统 的 采 用 ， 数 据 一 致 性 问 题 越 来 越 突 出 ， 以 往 关 于 这 方 面 的 著 述 具 有 了 很 大 的 局 限 性 ， 例 如 ， 对 于 486 以 上 机 种 出 现 的 第 二 级 托 片 cache、 第 三 级 托 片 cache 如 何 保 存 数 据 一 致 的 问 题 尚 未 见 于 专 门 的 论 述 。 为 了 探 索 更 适 合 于 当 前 计 算 机 发 展 的 趋 势 ， 必 须 适 时 追 溯 数 据 一 致 性 问 题 出 现 和 发 展 的 历 史 轨 迹 ， 步 入 多 任 务 系 统 的 解 决 方 案 。 因 此 高 速 缓 存 系 统 中 能 否 确 保 高 速 缓 冲 存 储 器 和 主 存 内 容 一 致 性 ， 这 个 问 题 直 接 关 系 到 整 个 计 算 机 系 统 的 性 能 。 对 于 计 算 机 整 体 性 能 的 提 升 有 十 分 重 要 的 意 义 。 7 3 数 据 一 致 性 问 题 的 提 出 高 速 缓 存 是 旨 在 改 善 存 储 器 平 均 响 应 时 间 的 小 型 快 速 存 储 器 ， 它 在 系 统 中 位 于 微 处 理 器 和 主 存 之 间 ， 使 得 系 统 从 cpu 看 具 有 cache 的 速 度 ， 主 存 的 容 量 。 图 3-1 为 一 高 速 缓 冲 存 储 器 系 统 框 图 ， 它 将 微 处 理 器 频 繁 向 主 存 请 求 的 代 码 和 数 据 予 以 拷 贝 。 图 3-1 高 速 缓 存 框 图 cachc 的 操 作 与 存 储 器 一 样 具 有 读 /写 两 种 模 式 ， 其 中 读 操 作 主 要 局 限 在 不 命 中 时 更 新 cache 内 容 ， 只 影 响 存 储 系 统 工 作 速 度 。 写 操 作 不 仅 工 作 时 间 比 读 操 作 长 ， 而 且 更 新 主 存 内 容 ， 直 接 影 响 机 器 性 能 ， 据 李 学 干 、 苏 东 庄 在 计 算 机 系 统 结 构 一 书 中 借 典 型 程 序 的 统 计 可 知 ， 所 有 访 存 中 约 有 10%34%甚 至 更 多 的 是 写 操 作 。 写 操 作 是 直 接 导 致 数 据 一 致 性 问 题 产 生 的 原 因 。 在 一 个 系 统 中 ， 同 一 个 数 据 的 多 个 拷 贝 可 以 同 时 存 在 ， 如 果 一 个 拷 贝 改 变 了 而 其 它 的 没 变 ， 那 么 两 组 不 同 的 数 据 便 与 主 存 的 同 一 地 址 有 关 。 cache 必 须 包 含 一 个 更 新 系 统 以 防 止 老 数 据 (陈 旧 数 据 )被 使 用 ， 即 解 决 一 致 性 问 题 。 分 析 产 生 数 据 一 致 性 问 题 的 原 因 主 要 有 三 个 ： 1 同 样 一 个 数 据 可 能 既 存 于 cache 中 ， 也 存 于 主 存 中 ， 这 样 可 能 前 者 己 更 新 ， 后 者 未 更 新 ， 造 成 数 据 丢 失 。 2 在 有 dma 系 统 或 多 处 理 器 系 统 中 ， 有 多 个 部 件 可 以 访 问 主 存 ， 这 时 可 能 其 中 有 些 部 件 是 直 接 访 问 主 存 ， 也 可 能 每 个 dma 部 件 和 每 个 处 理 器 配 一 个 cache， 这 样 主 存 的 一 块 区 域 可 能 对 应 于 多 个 cache 中 的 各 1 个 块 区 ， 产 生 主 存 中 的 数 据 被 某 个 总 线 主 控 部 件 更 新 过 ， 而 某 个 cache 中 的 内 容 未 更 新 ， 造 成 cache 中 数 据 过 时 。 3 当 主 存 中 同 时 有 多 道 程 序 运 行 时 ， cache 中 均 有 相 应 的 数 据 副 本 与 每 道 程 序 相 对 应 ； 对 于 共 享 数 据 ， 每 道 程 序 都 有 各 自 的 cache 数 据 与 主 存 数 据 相 一 致 。 当 某 道 更 新 8 了 其 相 应 的 cache 数 据 和 主 存 数 据 ， 而 其 它 程 序 的 cache 数 据 也 有 此 页 内 容 .则 其 内 容 不 会 改 变 (例 如 写 直 达 法 约 束 )。 这 道 程 序 再 次 读 到 的 内 容 就 会 因 是 原 先 的 内 容 而 出 错 。 写 策 略 是 cache 使 用 的 保 证 数 据 一 致 性 的 方 法 ， 保 持 系 统 主 存 更 新 ， 处 理 陈 旧 数 据 。 高 速 缓 存 一 致 性 是 指 要 求 同 一 个 信 息 项 与 后 继 存 储 器 层 次 上 的 副 本 是 一 致 的 。 如 果 在 高 速 缓 存 中 的 一 个 字 被 修 改 过 ， 那 么 在 所 有 更 高 层 上 该 字 的 副 本 也 必 须 立 即 或 最 后 加 以 修 改 。 对 于 多 处 理 机 系 统 的 存 储 器 层 次 结 构 ， 相 邻 层 之 间 和 同 层 之 间 可 能 会 出 现 数 据 不 一 致 性 。 比 如 某 个 处 理 机 修 改 了 该 处 理 机 的 cache 的 某 个 数 据 ， 则 该 数 据 块 可 能 在 别 的 处 理 机 上 有 相 同 的 拷 贝 ， 由 于 该 数 据 块 得 到 了 最 新 的 修 改 ， 所 以 如 果 其 它 相 同 的 拷 贝 不 及 时 得 到 修 改 的 话 ， 被 其 它 处 理 机 访 问 以 后 ， 可 能 出 现 错 误 。 这 也 就 是 所 谓 的 cache 不 一 致 性 。 我 们 用 图 3-2 一 致 性 定 义 图 来 直 观 的 表 示 ： 图 3-2 一 致 性 定 义 图 但 是 这 种 只 对 本 地 拷 贝 进 行 修 改 的 方 法 就 可 能 导 致 存 储 器 的 全 局 不 一 致 性 ， 也 就 是 这 些 拷 贝 并 不 一 致 。 如 何 能 够 让 处 理 器 访 问 不 会 出 错 ， 并 且 维 护 一 致 性 的 代 价 最 小 是 研 究 高 速 缓 存 一 致 性 和 同 步 机 制 的 主 要 研 究 课 题 。 9 4 基 于 不 同 原 因 的 写 策 略 解 决 方 案 4.1 基 于 原 因 1 的 解 决 办 法 原 因 1 导 致 的 数 据 一 致 性 问 题 是 建 立 在 cache 内 容 与 主 存 内 容 一 一 对 应 基 础 上 ， 不 能 相 关 更 新 造 成 的 数 据 丢 失 ， 解 决 方 法 首 先 解 决 cache 与 主 存 的 相 关 动 作 。 4.1.1 写直达 它 利 用 cache-主 存 贮 层 次 在 处 理 机 和 主 存 之 间 的 直 接 通 路 ， 每 当 处 理 机 写 入 cache 的 同 时 ， 也 通 过 此 通 路 直 接 写 入 主 存 。 从 而 主 存 随 时 跟 踪 cache 的 最 新 版 本 ， 也 就 不 会 有 主 存 将 数 据 丢 失 的 问 题 但 缺 点 也 显 而 易 见 ， 它 把 开 销 花 费 在 每 次 写 cache 时 就 有 对 主 存 的 写 入 ， 造 成 总 线 活 动 繁 忙 。 4.1.2 写回发 这 种 方 法 是 在 cpu 执 行 写 操 作 时 ， 信 息 只 写 入 cache， 仅 当 需 要 被 替 换 时 ， 才 将 已 被 写 入 过 的 cache 块 先 送 回 主 存 ， 然 后 再 调 入 新 块 。 cache-主 存 的 地 址 映 象 表 中 需 对 cache 中 每 个 块 设 置 一 个 “修 改 位 ”， 作 为 该 块 装 入 cache 后 是 否 被 修 改 过 的 标 志 ， 只 要 修 改 过 ， 就 使 该 标 志 位 置 成 “1”。 它 的 开 销 花 在 每 次 需 要 替 换 时 ， 增 加 了 cache 的 复 杂 性 。 以 上 两 种 解 决 方 法 的 采 用 没 有 严 格 约 束 ， 从 可 靠 性 讲 写 直 达 法 优 于 写 回 法 ， cache 出 错 时 可 由 主 存 来 纠 错 。 而 写 回 法 因 有 效 块 只 在 cache 中 ， 故 需 在 cache 中 采 用 纠 错 码 ， 增 力 了 冗 余 信 息 ； 从 成 本 上 讲 ， 写 回 法 低 于 写 直 达 法 ， 写 直 达 法 要 花 费 大 量 缓 冲 器 和 其 它 辅 助 逻 辑 。 所 以 方 法 的 采 用 主 要 山 应 用 场 合 决 定 ， 单 处 理 机 系 统 以 节 省 成 本 为 主 ， 多 采 用 写 直 达 法 。 对 共 享 主 存 的 多 处 理 系 统 ， 以 可 靠 性 为 主 ， 多 采 用 写 直 达 法 。 4.2 基 于 原 因 2 的 解 决 办 法 原 因 2 是 由 于 主 存 区 块 更 新 而 cache 未 更 新 产 生 的 数 据 过 时 错 误 ， 解 决 方 法 应 首 重 主 存 内 容 的 约 束 。 4.2.1 总线监视法 在 这 种 方 法 中 ， 由 cache 控 制 器 随 时 监 视 系 统 的 地 址 总 线 ， 如 其 它 部 件 将 数 据 写 到 主 存 ， 并 且 写 入 的 主 存 区 块 正 好 是 cache 中 的 区 块 对 应 的 位 置 ， 那 么 cache 控 制 器 会 自 动 将 cache 中 的 区 块 标 为 “无 效 ”。 10 4.2.2 硬件监视法 如 果 把 主 存 映 象 到 cache 的 区 块 称 为 已 映 象 区 块 ， 硬 件 监 视 法 就 是 通 过 外 加 硬 件 电 路 ， 使 cache 本 身 能 观 察 到 主 存 中 已 映 象 区 块 的 所 有 存 取 操 作 。 解 决 办 法 是 所 有 部 件 对 主 存 的 存 取 都 通 过 同 一 个 cache 完 成 或 每 个 部 件 配 备 各 自 的 cache， 当 一 个 cache 有 写 操 作 时 ， 新 数 据 既 拷 贝 到 主 存 ， 也 拷 贝 到 其 它 cache(播 写 法 )。 4.2.3 划出不可高速缓存存储区法 这 种 方 法 是 控 制 某 些 共 享 信 息 (如 信 号 灯 或 作 业 队 等