RMS算法是最优算法的证明

1 证明 RMS 是最优算法 RMS 的由来是从硬实时环境的初始定义开始的 1 所有的任务都是周期性的 各个任务请求的 deadline 呈周期性 同 时具有恒定的时间间隔 2 所有任务都必须在下一次任务请求 即 deadline 到来之前完成 3 所有的任务都是独立的 每一次任务请求不依赖于其他任务的执 行或者初始化 4 每个任务都存在一个恒定且非时变的执行时间 即 CPU 不间断地 执行该任务的时间 5 任何非周期的任务属于特殊任务 它们属于初始化或者是恢复错 误的事件 仅当它们自身执行的时候才能取代周期性任务 同时非 周期性任务不存在有 deadline 假设使用表示 m 个周期任务 任务申请周期和运行时 1 2 间分别表示为和 1 2 1 2 定理 1 若所有进程在临界时刻启动的请求都能满足最后期限要求 则整个进程集可调度 即进程在临界时刻启动的请求响应时间最长 图 1 在执行之前的运行 1 1 证明 如图 1 所示 假定为优先级最低的任务 在时 1 2 1 刻任务发出了运行请求 显然在图 1 所示的时间间隔 1 到 1 之间请求运行的周期性占先任务会推迟完成时刻 除非在到 2 来之前完成它 当向方向移动的时候 任务完成的时刻要么 2 1 不变 要么被推迟 所以断定 在向 直至与重 2 1方向无线趋近 1 合的时候 能够做到完成任务的延时最长 根据定理 1 可以假定 有两个任务 对应的指定周期 1 和 2 假设的优先级更高 此时根据定理 1 可得 1 1 2 1 2 1 2 1 2 2 1 如果假设的优先级更高 此时显然有 2 1 2 1 2 因为有 2 1 1 2 1 2 2 1 1 2 换句话说 只要保证了 不论是的优先 2 式导出了1 式 1 换的优先级之后 不难发现结果的任务依然是可行的 由于其对 任意式子都成立 于是命题成立 因此 单调速率调度算法在静态优先级调度算法中属于最优算 法 所以该算法的 CPU 使用率必然大于等于其余的静态优先级调度 算法 2 证明 如果n 为任务的个数 则 RMS 调度方案一定 2 1 1 存在 基于单调速率调度的算法中 定义 U 为 Processor Utilization CPU 的使用率 由于为每一个任务 的 CPU 执行率 对系统 有 1 经推广到 n 个固定优先级的任务条件下 此时的最小上界为 2 1 1 由罗必塔法则 求得极限为 ln2 这就意味着 任何周期大小周期性 任务一旦使用 RMS 调度算法均能满足调度要求 即在 deadline 之前 完成 3 RMS 算法有哪些不足 如何改进 缺点 1 它的潜在 CPU 利用率小于动态优先级策略 在动态优先级的最 优算法 EDF Earliest Deadline First 中最坏情况下的可调度 CPU 使用 率为 1 000 2 执行频率最高的任务并非最重要的任务 且较长周期的任务相对 于较短周期的任务 更加容易错过 deadline 3 由于 RMS 算法的静态调度属性 它运行时灵活性较差 自适应 性弱 现今常用的实时性的操作任务 常常具有较灵活的使用率需 求 但同时具有严格 RMS 算法完全建立在硬实时的条件下 主张所 有被调度的周期性任务具有固定的优先级 这就显得强调在 deadline 之前的必须完成任务的思想超出了必要限度 具体而言 在特殊场 合 一些任务的 deadline 是可以被错过的 只要在 deadline 前完成 任务的要求能在一定百分率下得到满足 这种高灵活性使得 RMS 的 最小上界理论毫无提出之必要了 具体而言 在实时多媒体应用的 调度之中 特点经常是 a 单个应用的执行次数常常是不定的 b 错过 deadline 尽管是不愿意出现的情况 但它确实是非致命的错