实时系统调度优化理论及方法研究
文献类型：学位论文
| 作者 | 刘军祥 |
| 学位类别 | 博士 |
| 答辩日期 | 2006-06-07 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 中国科学院软件研究所 |
| 导师 | 王永吉 |
| 关键词 | 实时系统 速率单调 可调度性判定 利用率上界 逻辑“或” 最优化设计 非线性规划 进程调度 调度空间 过载 能耗管理 |
| 其他题名 | Scheduling Optimization Theory and Methods for Real-Time Systems |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 随着多媒体技术、嵌入式系统、移动计算、普适计算等计算机科学与技术的发展，实时计算与实时系统正日益深入人们的日常生活。与非实时系统相比，实时系统最显著的特点是系统的正确性不仅取决于计算逻辑结果的正确性，而且必须同时保证每个实时任务在其截止期之前完成。一方面，实时系统越来越复杂，应用的领域越来越广泛，由于系统的特殊性，它要求我们能对实时系统进行快速的分析，这需要好的理论和方法来支持。另一方面，硬件技术日新月异，产品周期日益缩短，实时系统的设计者既要考虑系统硬件成本及系统向后的扩充能力，也要考虑系统的性能指标，如能耗、CPU利用率等。 传统的实时系统调度理论旨在找到高效的方法来验证系统的可调度性，但是它既没有回答如果系统不可调度，如何调整任务的时间参数使得系统的实时性能被满足，也没有回答在系统可调度的同时，有多大的自由度来调整参数使得系统的性能指标最优，解决这两个新问题需要新的学科领域知识。本文结合运筹学基本优化理论，针对被实时计算标准和商业操作系统广泛支持的速率单调(Rate monotonic，RM)调度算法，以可调度性判定理论为主线，把实时系统研究的多个方面，如实时系统设计、嵌入式系统能耗管理、系统过载处理等有机融合在一起，对实时系统的基本理论和方法进行了研究。全文主要贡献如下： 1.实时系统分析，即使是离线的，也需要一个高效的算法，不同的方法具有不同的特点，应根据具体的应用，选择最适合的方法。本文系统而深入地总结了现有实时系统研究文献提出的各种CPU利用率上界，并对各种确切性判定方法从理论和实践两个方面进行综合深入地时间及空间性能分析。同时，对任务之间的可调度相关性进行研究，探讨了特殊任务集的调度复杂性。研究结果表明，如果任务的周期在一定的范围内选择, 那么利用可调度性判定的充要条件进行分析是多项式时间复杂的，特别是当Tn≤2T1时，可调度判定的时间复杂度为 。 2.在实时系统理论研究方法上,第一次把优化理论应用到实时系统可调度判定充要条件上,利用数学变换消去充要条件中的逻辑“或”关系，并用一个不等式描述了任务的可调度性判定充要条件，提出了一个新的判定条件——P-bound。P-bound所描述的可调度区域与充要条件所描述的一致，克服了传统CPU利用率上界的“悲观性”。 3.基于P-bound，首次把实时系统设计问题描述为标准非线性优化问题来求解，使得我们可以直接利用最优化领域中经典的优化理论和数值分析方法，对实时系统进行高效分析和设计。具体地，从C-空间中任意一点到可调度性边界的三种距离被求出：(1)使得任务i继续保持可调度或可调度时任意任务执行时间Ck能够增加或减少的量；(2)使得任务集变为可调度或继续保持可调度时各任务子功能模块的最小拆分量；(3)使得任务集变为可调度或继续保持可调度时所有任务执行时间能够增加或减少的量；(4)使得系统可调度时的最小处理器速度。与基于CPU利用率上界进行系统设计相比资源利用率高，与其它依赖可调度性判定充要条件逐一计算每个判定不等式的方法相比，任何系统的性能指标都可以成为系统的设计目标。 5.总结了目前实时嵌入式系统能耗研究的各种模型、电压调节策略以及所要解决的问题，提出了一种新的嵌入式系统动态电压调节(DVS)技术，主要解决了当前研究的三个问题：(1)使得单一任务可调度或继续保持可调度时CPU 能够调高或降低的比例因子；(2)使得任务集可调度或继续保持可调度时对每个任务而言CPU 能够调高或降低的比例因子；(3)使得任务集可调度或继续保持可调度时处理器的最小电压。 6.从控制系统的基本原理出发，探讨了实时数字控制系统控制任务周期的来源及其可变性，提出了一种集成的柔性负载管理调度框架，该框架提供了各种过载处理方法的统一的视角，并分析了周期再配置时机的选择，一种改进的周期再配置方法被用于避免周期变更时产生的瞬时过载。我们在实时内核RTAI上进行了实现，实验结果验证了其有效性。 |
| 公开日期 | 2011-03-17 |
| 源URL | [http://124.16.136.157/handle/311060/6358]  |
| 专题 | 软件研究所_互联网软件技术实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 刘军祥. 实时系统调度优化理论及方法研究[D]. 中国科学院软件研究所. 中国科学院研究生院. 2006. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。