实 时 数 据 库 的事 务 处 理

实 时 事 务 模 型

　

----1 ． 系 统 模 型与 传 统 数 据 库 系 统 相 类 似， 实 时 数 据 库 系 统 的 操 作 也 是 以 事 务 的 形 式 出 现。 事 务 就 是 包 含 在BEGIN/COMMIT/ABORT 之 间 的 操 作 序 列。 系 统 以 事 务 为 单 位 分 配CPU、 数 据 等 资 源， 进 行 优 先 级 的 分 配、 调 度 处 理 等。

---- 实 时 数 据 库 系 统 中 的 事 务 与 传 统 事 务 有 很 大 的 不 同， 其 事 务 可 以 有 定 时 限 制（ 典 型 地 为 截 止 期）， 系 统 追 求 的 目 标 不 是 系 统 的 吞 吐 量， 而 是 单 个 事 务 定 时 限 制 的 满 足， 以 使 满 足 定 时 限 制 的 事 务 比 率 最 大； 传 统 事 务 的 原 子 性、 一 致 性、 隔 离 性 及 永 久 性 在 实 时 环 境 下 变 得 太 严 格 或 不 可 能； 要 求 采 用" 识 时" 机 制 来 处 理 事 务 的 调 度 或 并 发 控 制， 而 不 是 传 统 的 先 来 先 服 务 方 式。

----2 ． 结 构 模 型

---- 传 统 数 据 库 中 事 务 就 是 一 个 平 坦 的 操 作 序 列， 事 务 的 执 行 要 么 顺 利 执 行 到 提 交， 要 么 夭 折 而 不 在 系 统 的 任 何 部 分 留 有 痕 迹。 在 实 时 应 用 环 境 下 则 不 同：

• 应 用 语 义 有 时 显 式 地 要 求 结 构 上 的 一 个 事 务 为 另 一 个 事 务 的 子 事 务。 例 如， 在CAD 工 程 中， 一 个 工 程 事 务 划 分 成 若 干 个 设 计 事 务， 而 每 一 设 计 事 务 又 可 分 成 若 干 个 子 任 务 而 分 配 给 各 设 计 者。
• 实 时 应 用 中 被 触 发 的 活 动 依 应 用 要 求 可 以 是 触 发 它 的 事 务 的 子 事 务。 在 过 程 控 制、 自 动 化 等 领 域 这 种 情 形 很 普 遍。
• 在 分 布 式 应 用 环 境 中， 一 个 事 务 可 能 要 分 出 若 干 在 不 同 节 点 上 执 行 的 代 理 事 务， 它 们 分 工 合 作 且 都 作 为 原 事 务 的 子 事 务。
• 在 工 程 应 用 中， 普 遍 存 在 长 寿 事 务 或 开 端 事 务。 这 种 事 务 会 造 成 系 统 资 源 需 求 的 瓶 颈。 为 此， 可 将 这 种 事 务 划 分 成 若 干 逻 辑 相 对 独 立 的 子 事 务， 以 便 当 其 结 束 时 能 提 前 释 放 占 用 的 资 源。

---- 所 以， 实 时 应 用 要 求 系 统 提 供 事 务 嵌 套 机 制。 包 含 其 他 事 务 的 事 务 称 为" 父 事 务"， 被 包 含 的 事 务 称 为 " 子 事 务"， 没 有 父 事 务 的 事 务 为" 根 事 务"。 事 务 之 间 可 以 形 成 嵌 套 关 系。

实 时 事 务 的 特 征

　

----1 ． 定 时 性

---- 实 时 应 用 中 事 务 的 定 时 性 来 源 于 两 方 面： 一 是 外 部 环 境 显 式 给 出 的 反 应 时 间 要 求， 如 截 止 期 等； 二 是 由 于 系 统 中 的 数 据 随 时 间 变 化 而 转 嫁 来 的。

---- 定 时 性 包 括 了 两 方 面 的 含 义：

---- 定 时 限 制 事 务 的 执 行 具 有 显 式 的 时 限， 如 期 限、 截 止 时 间 等。 这 是 由 于 控 制 系 统 要 随 时 紧 紧 地 跟 踪 被 控 系 统 而 引 起 的， 它 要 求RTDB 必 须 有 时 间 处 理 机 构。 时 限 还 可 有 软 硬 之 分。

---- 定 时 正 确 性 事 务 能 按 合 适 的 时 间 要 求 正 确 执 行。 这 是 由 于 要 求 数 据 对 于 控 制 系 统 的 各 种 决 策 活 动 随 时 有 效 而 引 起 的， 它 要 求 权 衡 定 时 限 制 与 数 据 一 致 性 等 多 方 面 因 素， 提 供 合 适 的 调 度 算 法。

---- 实 时 事 务 有 不 同 的 定 时 限 制， 其 中 最 重 要 的 有：

---- 截 止 时 间 实 时 事 务 完 成 的 最 后 期 限。 它 可 以 有 硬、 软 之 分， 具 有 硬 截 止 时 间 的 事 务（ 称 为 硬 实 时 事 务）， 必 须 在 其 截 止 时 间 以 前 完 成， 否 则 将 带 来 灾 难 性 的 后 果， 故 到 达 其 截 止 时 间 还 不 能 完 成 的 硬 实 时 事 务 必 须 夭 折。 具 有 软 截 止 时 间 的 事 务（ 称 为 软 实 时 事 务）， 应 该 在 其 截 止 期 完 成， 但 超 过 其 截 止 时 间 也 还 有 一 定 意 义（ 尽 管 不 断 下 降）， 故 软 实 时 事 务 到 达 其 截 止 时 间 后 不 必 立 即 夭 折 它。

---- 到 达 时 间 事 务 在 系 统 中 生 成 的 时 间。 它 可 以 是 可 预 报 的， 也 可 以 是 不 可 预 报 的。 可 预 报 的 到 达 时 间 可 显 式 地 给 出 或 者 作 为 一 个 导 出 函 数， 如 周 期 事 务 的 到 达 时 间 是 可 预 报 的。 不 可 预 报 的 到 达 时 间 是 指 当 相 应 事 务 到 达 系 统 时 才 能 知 道， 非 周 期 事 务 的 到 达 时 间 就 是 不 可 预 报 的。

---- 期 望 执 行 时 间 估 算 的 最 坏 情 况 执 行 时 间。 由 于 各 种 不 可 预 报 性 因 素， 它 很 难 做 到 准 确， 估 算 的 最 坏 情 况 执 行 时 间 可 能 与 实 际 情 况 相 差 很 大。 然 而， 为 了 合 理 地 得 到 事 务 的 截 止 时 间 及 适 当 地 调 度 以 使 其 满 足， 又 必 须 事 先 较 准 确 地 估 算 其 执 行 时 间。

----2 ． 语 义 相 关 性

---- 实 时 数 据 库 事 务 之 间 存 在 着 各 种 关 系， 包 括 结 构 关 系、 数 据 与 通 信 关 系、 时 间 关 系 等， 这 些 关 系 带 来 了 事 务 间 的 各 种 相 关 性。

----(1) 结 构 相 关

---- 它 来 自 于 复 杂 事 务 模 型 的 结 构 特 征， 用 来 建 模 复 杂 事 务 内 部 并 发 事 务 行 为 的 一 种 约 束。 不 同 的 复 杂 事 务 模 型 有 不 同 的 结 构 相 关 性， 但 它 们 可 以 通 过 事 务 间 的" 执 行 依 赖 性" 来 定 义， 实 时 嵌 套 事 务 中 基 本 的 事 务 依 赖 有：

• 子 事 务 对 父 事 务 的 开 始 依 赖（BD）： 子 事 务 开 始 前 父 事 务 已 经 开 始；
• 父 事 务 对 子 事 务 的 提 交 依 赖(CD）： 父 事 务 提 交 前 子 事 务 已 经 结 束（ 提 交 或 夭 折）；
• 子 事 务 对 父 事 务 的 夭 折 依 赖（AD）： 父 事 务 夭 折 则 子 事 务 一 定 夭 折。

----(2) 数 据 相 关

---- 数 据 相 关 就 是 不 同 事 务 间 的 共 享 数 据 联 系， 但 此" 共 享" 概 念 比 传 统 的 具 有 更 广 的 意 义： 实 时 嵌 套 事 务 中 的 子 事 务 共 享 父 事 务 数 据， 子 事 务 提 交 时 其 对 数 据 库 的 更 改 委 托 给 父 事 务， 只 有 父 事 务 提 交 时 才 能 真 正 地 写 入 数 据 库。

----(3) 功 能 替 代/ 结 果 补 偿

---- 一 个 实 时 应 用 常 常 由 若 干 任 务 组 成， 而 一 个 任 务 有 时 可 以 通 过 不 同 途 径 来 实 现。 一 个 应 用 建 模 为 一 个 事 务， 一 个 任 务 则 建 模 为 一 组 功 能 等 价 的 子 事 务， 称 为 该 任 务 的 替 代 集。 若 一 个 任 务 的 替 代 集 中 的 子 事 务 之 一 能 成 功 执 行， 则 该 任 务 是 可 完 成 的。 若 对 应 一 个 事 务 的 所 有 任 务 可 完 成， 则 该 事 务 是 成 功 的（ 可 提 交）。 功 能 替 代 导 致 了 事 务 执 行 路 径 的 不 确 定 性， 即 一 个 事 务 成 功 执 行 的 路 径 依 赖 于 执 行 过 程 中（ 子 事 务） 失 败 的 发 生， 且 即 使 某 些 子 事 务 失 败 了， 事 务 仍 可 能 顺 利 提 交。 这 还 体 现 了 实 时 事 务 的 健 壮 性， 即 有 的 事 务（ 任 务） 不 能 失 败。

---- 由 于 前 面 所 述 的 事 务 的 结 构 复 杂 性 和 功 能 替 代 性， 因 此， 事 务 的 执 行 经 历 不 确 定， 一 个 子 事 务 的 执 行 直 到 提 交 时 还 不 能 确 定 它 是 否 需 要。 若 一 个（ 子） 事 务 提 交 后， 发 现 它 是 不 需 要 的， 该 怎 么 办 ？ 另 一 方 面， 一 个 实 时 事 务 可 以 物 理 改 变 现 实 世 界 的 状 态， 换 句 话 说， 事 务 可 以 启 动 各 种 活 动， 这 些 活 动 在 它 提 交 前 就 已 经 影 响 了 现 实 世 界， 因 而 当 这 种 事 务 夭 折 时， 不 能 进 行 传 统 意 义 下 的" 还 原"（Undo）。 于 是 需 要 一 种" 补 偿" 活 动 来 抵 消 它 所 有 的 影 响， 这 种 补 偿 活 动 也 是 事 务。 对 于 一 个（ 子） 事 务， 若 存 在 能 抵 消 它 提 交 后 所 产 生 的 所 有 影 响 的（ 子） 事 务， 则 称 其 为 是 可 补 偿 的， 否 则 是 不 可 补 偿 的。 当 然， 不 是 每 一 个（ 子） 事 务 都 是 可 补 偿 的， 不 可 补 偿 的（ 子） 事 务 在 知 道 它 确 实 是 需 要 的 以 前， 一 定 不 能 提 交。

实 时 事 务 分 类

　

---- 实 时 事 务 可 以 从 不 同 的 侧 面 进 行 分 类。

----1 ． 按 关 键 性 分 类

---- 也 就 是 按 事 务 时 限（ 截 止 期） 的 性 质， 即 事 务 超 截 止 期 对 系 统 带 来 的 影 响 分 类。 而 这 种 时 限 的 性 质 可 以 很 好 地 用 价 值 函 数 来 建 模， 于 是 我 们 有：

---- 硬（ 截 止 期/ 实 时） 事 务 超 截 止 期 会 导 致 恶 果（ 价 值 函 数 取 大 且 可 能 不 断 增 加 的 负 值）。 它 对 应 于 安 全 危 急 性 活 动。

---- 软（ 截 止 期/ 实 时） 事 务 超 截 止 期 仍 有 一 定 的 价 值， 且 价 值 不 断 下 降， 直 到 某 一 时 刻（ 称 为 最 终 有 效 时 间） 降 到 零， 此 后 保 持 为 零（ 不 会 为 负）。

---- 固（ 截 止 期/ 实 时） 事 务 一 旦 到 达 截 止 时 间， 其 价 值 立 即 降 为 零， 此 后 固 定 为 零（ 也 不 会 为 负）。 显 然， 它 是 软 实 时 事 务 在 最 终 有 效 时 间 与 截 止 时 间 重 合 情 况 的 特 例。

----2 ． 按 功 能 分 类

---- 一 个 实 时 数 据 库 系 统 以 两 种 方 式 直 接 与 现 实 世 界 交 互 作 用， 一 是 关 于 现 实 世 界 状 态 或 事 件 的 信 息 被 记 录 到 数 据 库 中， 二 是 事 务 可 以 启 动 各 种 影 响 现 实 世 界 的 活 动。 这 就 给 予 我 们 一 种 如 下 事 务 分 类：

---- 数 据 接 收 事 务 记 录 现 实 世 界 的 状 态 或 发 生 的 事 件 到 数 据 库 中。 它 是 简 单 的 只 写 事 务； 为 了 保 持 数 据 库 的" 外 部 一 致" 和 跟 踪 记 录， 它 应 是 短 的、 周 期 的， 且 应 是 被 立 即 执 行（ 不 能 等 待 和 阻 塞） 的 硬 实 时 事 务。 为 了 保 证 其 定 时 限 制 的 满 足， 它 可 能 会 引 起 对 数 据 库 一 致 性 的 破 坏。

---- 数 据 处 理 事 务 类 似 传 统 数 据 库 的 事 务。 它 用 来 恢 复 已 违 反 了 一 致 性（ 可 能 由 于 数 据 接 收 事 务 的 结 果） 的 数 据 库 的 状 态。 这 种 事 务 可 看 作 维 护 正 常 运 行 的 监 控 器， 它 可 能 是" 长 寿" 的。

---- 控 制 事 务 引 起 现 实 世 界 中 有 关 活 动 的 执 行。 像 数 据 接 收 事 务 一 样， 这 种 事 务 是 很 短 的， 尽 管 所 引 起 的 现 实 活 动 可 能 要 执 行 很 长 时 间。 它 通 常 也 是 硬 实 时 的。 这 种 事 务 还 可 以 作 为 数 据 处 理 事 务 的 子 事 务 而 被 调 用， 而 它 本 身 也 可 以 触 发 子 事 务， 比 如 以 一 子 事 务 来 检 测 所 引 起 的 现 实 活 动。

实 时 事 务 的 正 确 性

　

----1 ． 正 确 性 概 念 及 内 涵 实 时 事 务 与 传 统 事 务 的 本 质 区 别 就 在 于 其 有 定 时 限 制， 因 此， 事 务 处 理 必 须 同 时 满 足 一 致 性 要 求 和 定 时 限 制。 虽 然 实 时 事 务 的 正 确 性 与 传 统 事 务 一 样， 也 包 括 数 据 库 状 态 正 确 性 和 事 务 执 行 正 确 性 两 个 方 面， 但 其 含 义 与 内 容 有 很 大 的 不 同。 数 据 库 状 态 正 确 性 包 含 内 部 一 致 和 时 间 一 致， 事 务 执 行 正 确 性 则 包 含 其 结 果 正 确 性、 行 为 正 确 性、 结 构 正 确 性 和 时 间 正 确 性。

----2 ． 正 确 性 标 准

---- 传 统 数 据 库 中 的 原 子 性 和 可 串 行 化 包 含 了 事 务 正 确 性 的 所 有 概 念。 而 实 时 嵌 套 事 务 正 确 性 的 内 容 更 为 丰 富， 实 现 的 手 段 也 就 更 为 复 杂。 传 统 可 串 行 化 标 准 在 实 时 环 境 下 太 严 格 或 不 适 合， 限 制 了 系 统 中 事 务 执 行 的 并 发 度， 对 于 满 足 事 务 定 时 限 制 是 不 利 的。 我 们 开 发 了 一 种 新 颖 的 准 一 致 性 可 串 行 化 并 发 控 制 策 略， 事 务 执 行 给 系 统 带 来 的 不 一 致 被 限 定 在 一 定 的 范 围 内， 并 在 一 定 的 时 机 恢 复 数 据 库 到 一 致 状 态。 而 实 时 事 务 的 时 间 正 确 性 需 要" 识 时" 协 议 实 现， 结 构 正 确 性 需 要 事 务 管 理 检 查 事 务 间 的 结 构 相 关 性 来 实 现。

实 时 事 务 处 理

　

----1 ． 实 时 事 务 优 先 级 分 配

---- 实 时 事 务 的 调 度 和 并 发 控 制 都 是 基 于 事 务 的 优 先 级 进 行 的， 因 此， 如 何 分 配 事 务 的 优 先 级 是 一 个 重 要 的 问 题。

---- 常 见 的 事 务 优 先 级 分 配 算 法 有 以 下 几 种：

---- 最 早 放 行 最 优 先（Earliest Release First） 该 策 略 将 最 高 优 先 级 指 派 给 具 有 最 早" 放 行"（Release） 时 间 的 事 务。 所 谓 放 行 时 间 就 是 事 务 可 以 开 始 执 行 的 最 早 时 间， 与 此 相 联 的 有 事 务 到 达（Arrive） 时 间、 事 务 接 纳（Admission） 时 间。

---- 截 止 期 最 早 最 优 先（Earliest Deadline First） 即 具 有 最 早 截 止 期 者 优 先 级 最 高。

---- 可 达 截 止 期 最 早 最 优 先（Earliest Feasible Deadline First） 具 有 最 早 的 可 达 截 止 期 者 优 先 级 最 高。 所 谓 一 个 事 务t 的 截 止 期 是 当 前 时 间" 可 达 到" 的， 乃 指 τ ＋（E －P） ≤d。 这 里 τ 为 当 前 时 间，E、P 分 别 为 事 务T 的 执 行 时 间 估 算 和 已 执 行 时 间， d 为 其 截 止 期。

---- 空 余 时 间 最 短 最 优 先（Least Slack First） 事 务t 的 空 余 时 间S=d －（ τ ＋E －P）， 即 推 迟T 的 执 行 而 仍 然 满 足 其 截 止 期 的 可 推 迟 时 间 量 估 算。

---- 价 值 最 高 最 优 先（Highest Value First） 每 一 事 务 都 有 一 价 值 函 数， 其 值 最 大 者 最 优 先。 问 题 是 如 何 合 理 地 构 造 价 值 函 数， 一 个 例 子 是：

---- V（t）=c（w₁（ τ － τ_S） －w₂d ＋w₃P －w₄S）

---- 其 中 τ、d、P、S 的 意 义 同 上，c、 τs 分 别 为 t 的 危 急 度、 开 始 时 间，wi 为 加 权 因 子。

---- 价 值 密 度 最 大 最 优 先（Greatest Value Density First） 价 值 密 度 函 数 为：

---- 即 事 务 完 成 时 的 期 望 价 值 与 实 现 该 价 值 所 需 计 算 量 的 比 最 大 者 优 先 级 最 高。 显 然， 对 于 期 望 价 值 一 样 的 事 务， 该 策 略 偏 向 较 短 者， 因 为 它 每 单 位 消 耗 时 间 所 获 得 的 价 值 更 大。 与 上 面 的HVF 策 略 一 样， 这 里 也 有 如 何 设 计 价 值 函 数 的 问 题。

----2 ． 实 时 事 务 并 发 控 制 和 调 度

---- 在 实 时 应 用 环 境 中， 如 果 处 理 不 当， 可 能 造 成" 优 先 级 颠 倒"， 即 优 先 级 高 的 事 务 等 待 优 先 级 低 的 事 务， 这 对 实 现 事 务 的 定 时 限 制 是 不 利 的。 为 此， 我 们 提 出 了 以 下 几 种 改 进 方 案：

----(1) 优 先 级 继 承

---- 优 先 级 继 承 的 基 本 思 想 是： 当 发 生 优 先 级 颠 倒 时， 将 占 有 者tH 的 优 先 级 提 高 到 与tR 的 一 样（ 即 继 承tR 的 优 先 级），tH 继 续 执 行 直 到 结 束（ 提 交 或 夭 折）。 在tH 因 某 种 原 因（ 如 成 为 死 锁 的 牺 牲 者） 而 重 启 动 时， 它 恢 复 原 来 的 优 先 级。 让tH 继 承 tR 优 先 级 是 为 了 让 它 尽 快 完 成， 因 为tH 的 进 展 也 意 味 着tR 的 进 展。 这 种 策 略 称 为 优 先 继 承（PI）。

----(2) 高 优 先 级 夭 折

---- 这 种 策 略 的 思 想 是， 当 发 生 优 先 级 颠 倒 时， 夭 折 低 优 先 级 的tH 而 让 高 优 先 级 的tR 执 行。 该 策 略 称" 高 优 先" 法（HP）。

---- 这 种 策 略 可 以 消 除 死 锁， 但 它 的 问 题 是：

• 对 那 些 已 执 行 时 间 很 长 而 还 需 执 行 的 时 间 已 很 短 的tH， 夭 折 的 代 价 很 大。 尤 其 是 当dH（ 截 止 时 间） －ct（ 当 前 时 间） 与tH 的" 剩 余 执 行 时 间 估 算"el(tH) 相 差 不 大 时， 重 启 动 必 然 导 致 其 超 截 止 时 间， 而 且 浪 费 大 量 系 统 资 源， 使 整 个 系 统 性 能 下 降。
• 若 采 用 像LSF 这 样 的 动 态 优 先 级 分 配 策 略， 则 被 夭 折 而 重 启 动 的tH 可 能 马 上 会 有 比tR 更 高 的 优 先 级。 为 此， 当 重 启 动 的tH 再 次 与 tR 冲 突 时，tR 可 能 又 被tH 夭 折， 这 样 就 导 致 循 环 夭 折。

---- 为 了 解 决 上 述 两 个 问 题， 人 们 提 出 了 不 同 的 改 进 策 略， 在 此 限 于 篇 幅 不 再 详 细 叙 述。

不错，很好