◆88· 北京科技大学学报 2003年第1期 i=1,2,…,n 线调度政策下，在时间周期[0，]内，n个实时传 定理1在抢先静线调度政策下，n个实时传 输连接(D,0,T,P),=1,2,,n,通过一个协议处理 输连接(D,,T,p,)i=1,2,,n通过一个协议处理 器是能够调度的，而且系统在时刻6是空着的 器调度能力的充分必要条件是： 在时刻以后，新的报文将到达该系统，于是下 1s0到P1-Dpzt 一个循环周期[，2]将开始，并将如此进行下去. 其中，(x)是一个阶跃函数， 22统计性保证的调度性问题 {0x≤0 传统性的抢先的静线调度目的在于保证报 x)1 x20 文静线，因此它经常用于QoS的确定性保证.对 符号[]是高斯小数求整数符号，后面的「1符号 于QoS的统计保证，建议用拥有中断点抢先静线 是小数求上限整数值符号 调度，其描述如下： 定理2抢先静线调度政策下，通过协议处理 调度政策企图去保证，非实时传输连接在其 器对n个实时传输连接(Dn0,T,P),1,2,,n调 生存期间，会失去大于它们的最大报文损失的报 度能力的一个必要条件是2≤1 文.首先定义一些在调度中会用到的变量，用于 证明：很明显，p/T,是第i个连接所要求的处 并解释中断点的概念. 理器处理时间的最大分数值，并且三号也是协 令a,=已经处理过的报文总量，或者是迄今 为止错过其静线的报文总量；b=迄今为止由于 议处理器的最大利用率.显然，如果处理器利用 错过其静线而丢失的报文总量 率号>1，则协议处理器无法调度个实时传输 很显然，有a>b.如果a=0,定义b/a,=0.对 连接.定理2证毕 于每一个实时传输连接，为了实现其调度的目 定理3在抢先静线调度政策下，若号≤1， 的，协议处理调度器将保持这些量有两种不同的 1e0a,'2-D)ns是通过协议处 变化.同样，(b+1)(a+1)>b/a和b/a,是流动报文 的损失率 理器的n个实时传输连接(D,0T,p以，i=l,2,,n 这里，对于第i个实时传输连接而言，中断点 调度的充分必要条件.这里=(TC方C,是一个 只是一个时间瞬间1，在该瞬间协议处理器必须 自然数，T,C:成为最小可能自然数. 处理第i个实时传输连接中处于等待队列的第一 证明：该定理隐含着定理1.由号≤1，得 条信息.在处理阶段，协议处理器不能中断.在一 气p+会P…+p.s假设该系统的开始时间 to 定条件下，中断点可以重新建立或清除.如果处 为4：注意到兰-(C)i(C以C为一自然 于第i个实时传输连接的等待队伍的第一条报文 完全被处理以后，对该报文而言，中断点（若此处 数，并且是在时间周期[0，期间，在第个实时传 有一个，已安排好时)将被自动清除，或者，如果 输连接处，到达主机的最大报文量.很显然，在时 第i个实传输连接的中断点正好错过另一个中断 间周期[0，)内，通过所有的实时传输连接到达主 点处理过程，它也会被自动清除掉 机的所有报文能够在6之前被完全处理完，而不 拥有中断点的静线调度政策描述如下： 用考虑报文的延迟范围.因为，在时间周期[0，]， (I)如果(b,*0)和(b+1)/(a+1>g,假设在第i 通过所有的实时传输连接到达主机的所有报文 个实时传输连接第一个等待处理的报文静线是 所需要的处理时间总值是不大于的 d,,则中断点建立在d一p 假设vre0a到2-D)n≤t是满 (2)如果第i个与实时传输连接的第一个等 足的.这意味着在时间周期[0，期间，所有静线 待队列的报文已被完全处理完，则报文的中断点 d,≤的到达主机的报文可以完全被处理完而不 将被自动地清除，或者第i个实时传输连接的中 侵犯其的静线 断点正好错过另一个中断点处理过程，它也会被 综上所述，可以推断出，在时间周期[0，]内， 自动地清除掉 通过所有实时传输连接，到达主机的所有报文， (3)在条件(1)及(2)的情况下执行抢先静线 不管其静线是小于、大于或等于，完全能够被 调度 处理完毕，而不侵犯其静线.换句话说，在抢先静 定理4在具有中断点的抢先静线调度政策北 京 科 技 大 学 学 报 年 第 一期 ， ， … ， 定 理 在抢先静线调 度政策下 ， 个实时传 输连接， ，拼 ， 兀 〕 ， ， ， … ， 通 过一个协议处理 器调 度能力 的充分必 要 条件是 ‘ ， 艺 毕 。 卜。 ， ，二， 、 才 产 其中 ， 占 是一 个 阶跃 函数 ， 占工 亏 七 符号 【 是 高斯 小 数求整 数符号 ， 后 面 的【 符号 是小 数求上 限整数值符号 定理 抢 先静线调 度政策下 ， 通 过协议处 理 器 对 。 个 实 时 传输 连 接 ‘， ， 兀川 ， ， ， … ， 调 度能力 的一 个 必 要 条件是 全县引 曰 ， 证 明 很 明显 ， 川不 是第 个连接所要 求的处 理 器处 理 时 间 的最 大分数值 ， 并且 鑫登也 是 协 议 处 理器 的最 大利用率 显 然 ， 如果 处 理 器 利用 率 全今 ， 则 协议处理器无法 调 度 。 个实 时传输 一 高 不 一 ’ 乃 囚 “ “ “ ’一 ， ， ” ’ 『’ ‘ ’ 、 ’ 川 连 接 定 理 证 毕 定 理 ， 在抢先静线调 度政 策下 ， 若 登 ‘ ， ‘。 。 ， ， 艺 兰撰 三 。 卜。 〕 ，“ ，是 通 过 协 议 处 尸 、 苦 理 器 的 个 实 时 传输 连 接 ， 兀川 ， ， ， … ， 调 度 的充分必要 条件 · 这 里“ 一 县忱 是一个 自然 数 ， 不 成为最 小可 能 自然 数 证 明 该定理 隐含着 定理 ， · 由鑫会引 ， 得 知资 二 资 。 二 假设该 系统 的开 始 时 间 为 注 意 到粤才 忱 忱 ， 为 一 自然 数 ， 并且 是 在 时 间周期 〔 ， 期 间 ， 在第 个实 时传 输连接处 ， 到达 主机 的最 大报文量 很显 然 ， 在 时 间周期 【 ， 内 ， 通 过所有的实时传输连 接到达 主 机 的所 有报文 能够在 ‘ 之前被完全处 理完 ， 而不 用考 虑报文 的延迟 范围 因为 ， 在 时 间周期 仁 ， ， 通 过 所 有 的实 时传输连 接 到 达 主 机 的所有 报 文 所需 要 的处 理 时 间 总值是 不 大 于 的 ，， 、 。 、 ， ， 二 「一 、 。 ， 、 。 假 设 任 ， 〕 ， 艺 生带 三 占 一 ， 队 “ 是 满 认 ” ” ，列 ， 胃 不 」 ’ ‘ 厂 、 ’ 一 ‘ 产 尸 一 ’ ’ ’ 足 的 这 意 味着在时 间周期〔 ， 司期间 ， 所 有静线 试夕 ， 的到 达 主机 的报文 可 以完全被处 理完 而 不 侵犯 其的静线 综上 所 述 ， 可 以推断 出 ， 在时 间周期【 ， 内 ， 通 过 所 有实时传输 连接 ， 到 达 主机 的所 有 报 文 ， 不 管其静线 是小 于 、 大于或等于 ， 完全能够被 处理完毕 ， 而不侵犯其静线 换句话说 ， 在抢先静 线调 度 政 策下 ， 在 时 间周期 ， 内 ， 个实 时传 输连接 ， ， 兀户 ， ’ ， ， … ， ， 通 过 一 个协议处 理 器是 能够调 度 的 ， 而且 系统在 时 刻 是 空 着 的 在 时刻 以后 ， 新 的报 文将到达该 系统 ， 于 是下 一 个循 环周期 〔 ， 将开 始 ， 并将如此进行 下 去 统 计 性保 证 的调 度 性 问题 传统 性 的抢 先 的 静 线 调 度 目的 在 于 保证 报 文静线 ， 因此 它经 常用 于 的确 定性 保证 对 于 的统计保证 ， 建议用拥 有 中断点 抢 先静线 调 度 ， 其描述 如下 调 度政策企 图去保证 ， 非 实 时传输 连 接在 其 生存期 间 ， 会失 去 大于 它们 的最大报 文损 失 的报 文 首先定义 一 些 在 调 度 中会用 到 的变 量 ， 用 于 并 解 释 中断点 的概 念 令 万 已经处 理过 的报 文 总量 ， 或 者是 迄 今 为 止 错过 其静线 的报 文 总量 产 迄 今 为 止 由于 错 过 其静线而 丢 失 的报 文 总量 很 显 然 ， 有 玄 如 果 产 ， 定 义 ，“ 对 于 每一 个 实 时传输 连 接 ， 为 了实 现其调 度 的 目 的 ， 协议处 理调 度器将保持这些 量 有两 种不 同的 变化 同样 ， 汁 瓜 和 ， 是 流 动报 文 的损 失 率 这 里 ， 对 于第 个 实时传输连 接而 言 ， 中断点 只是 一 个 时 间 瞬 间 ， 在该 瞬 间协议处 理 器必 须 处 理第 个 实 时传输连接 中处 于等待队列 的第一 条信息 在处 理 阶段 ， 协议处 理器不 能 中断 在一 定条 件下 ， 中断点可 以重新 建立 或清 除 如果 处 于第 个实时传输连接 的等待 队伍的第一 条报 文 完全被处理 以后 ， 对该报文 而 言 ， 中断点 若此处 有 一 个 ， 已 安 排好 时 将被 自动清 除 ， 或 者 ， 如果 第 个实传输连 接的 中断点正好错过 另一个 中断 点处 理 过程 ， 它 也会被 自动 清除掉 拥 有 中断点 的静线 调 度政 策描述 如下 如果 ‘ 羊 和 冲 冲 假设 在 第 个 实 时 传输 连 接第 一 个 等 待 处 理 的报 文 静 线 是 试 ， 则 中断点建 立 在 试， 卜 如果 第 个 与实 时传输 连 接 的第一 个 等 待 队列 的报文 已被完全处理完 ， 则报 文 的 中断点 将被 自动地 清 除 ， 或者第 个 实时传输 连 接 的 中 断点正好错过另 一个 中断点处理过程 ， 它也会被 自动 地清 除掉 在条件 及 的情 况 下 执行抢先静线 调 度 定 理 在具有 中断点 的抢先静线调 度 政 策