学位论文 > 优秀研究生学位论文题录展示
实时异构系统的集成动态调度模型与算法研究
作 者: 李建国
导 师: 陈松乔;王建新
学 校: 中南大学
专 业: 计算机应用技术
关键词: 实时异构系统 动态调度 任务分配 调度优化 实时调度算法
分类号: TP316.2
类 型: 博士论文
年 份: 2006年
下 载: 511次
引 用: 2次
阅 读: 论文下载
内容摘要
实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。在这些应用中,存在大量的硬、软实时任务共存的情况,对实时异构系统的集成动态调度模型与算法的研究具有重大理论和实际意义。本文对实时异构系统的集成动态调度问题进行了深入的研究,提出了一种实时异构系统的集成动态调度模型,基于这种模型,提出批优化的调度策略和批任务在处理器上运行的目标函数构造原则。在此基础上,提出了一种基于分批优化的实时异构系统的集成动态调度算法——GOIDSH算法。本文针对实时异构多任务调度的特点,采用集中式调度模型;提出软、硬实时任务形式化描述非精确计算的统一任务模型,清晰地描述实时任务的特点。系统任务描述简单,节省存储空间,为实现基于批优化的集成动态调度打下基础。论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础,主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分,采用统一形式完成了实时异构系统的集成动态调度。同时,在构造目标函数时,算法还引入软实时任务服务质量(Ouality of Service,Qos)降级策略来提高调度成功率。GOIDSH算法的核心思想是:在每次扩充当前局部调度时,首先按一定规则在待调度的任务集中选取一批任务组成任务子集,保证所选取的任务子集中某一任务对某个资源有访问需求时,子集中的其它任务不能对该资源有访问需求。然后,综合各种因素,对该批任务中的每项任务在每个处理器上的运行构造目标函数,将问题转化为非平衡指派问题,利用非平衡指派问题直接解法对任务进行优化分配,一次性为这些任务分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,增大未被调度任务的被成功调度的可行性。论文通过仿真和模拟,从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面,验证了GOIDSH算法的有效性及其调度性能。在仿真实验时,提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则:①任务的截止期越近,其价值越高;②任务需要访问的资源越多,其价值越高;③任务要需访问的资源中,互斥方式的访问越多,其价值越高;④任务的空闲时间越短,其价值越高;⑤相同情形下,硬实时任务的价值高于软实时任务的价值。仿真实验结果表明,基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题,而且还有效地提高了调度成功率,确保了软实时任务具有良好的服务质量,与其它相关算法,如传统的近视算法和节约算法相比较,具有明显优势。
|
全文目录
摘要 5-7 ABSTRACT 7-12 第1章 绪论 12-29 1.1 实时系统与实时调度基本概念 12-18 1.1.1 实时系统基本概念 12-13 1.1.2 实时调度基本概念 13-18 1.2 实时系统与实时调度研究进展 18-25 1.2.1 实时系统研究进展 18-19 1.2.2 实时调度研究进展 19-25 1.3 实时调度研究中存在的不足 25-27 1.4 研究目标和内容 27-28 1.5 论文的组织结构 28-29 第2章 实时异构系统的集成动态调度模型 29-39 2.1 实时异构系统的系统模型 29-31 2.2 调度器模型 31-33 2.3 实时异构系统的统一任务模型 33-37 2.3.1 非精确计算模型 33-34 2.3.2 统一任务模型的描述 34-37 2.4 本章小结 37-39 第3章 基于分批优化的实时异构系统的集成动态调度算法 39-65 3.1 相关定义 39-40 3.2 启发式搜索方法 40-46 3.3 任务分批规则 46-47 3.4 目标函数构造原则 47-50 3.6 基于批优化的任务调度策略 50-52 3.7 基于分批优化的实时异构系统的集成动态调度算法描述 52-55 3.8 对基于分批优化的实时异构系统集成动态调度算法的分析及讨论 55-57 3.9 非平衡指派问题直接解法 57-63 3.9.1 基本定理 58-59 3.9.2 直接解法 59-63 3.10 本章小结 63-65 第4章 仿真实验与分析 65-99 4.1 性能评估标准 65-66 4.2 仿真实验方法 66-68 4.2.1 仿真实验参数 66 4.2.2 仿真实验任务生成方法 66-68 4.3 仿真实验结果及其分析 68-90 4.3.1 处理器间的速度差异对调度成功率等的影响 70-72 4.3.2 软实时任务概率对调度成功率等的影响 72-74 4.3.3 最大回溯次数对调度成功率等的影响 74-75 4.3.4 分批窗口大小对调度成功率等的影响 75-77 4.3.5 任务的可延迟度对调度成功率等的影响 77-78 4.3.6 任务访问资源的概率的多少对调度成功率等的影响 78-82 4.3.7 任务对系统中资源数要求的多少对调度成功率等的影响 82-83 4.3.8 调度长度的大小对调度成功率等的影响 83-85 4.3.9 处理器数对调度成功率等的影响 85-90 4.4 算法的时间复杂度分析 90-96 4.5 仿真实验结论 96-98 4.6 本章小结 98-99 第5章 结束语和未来的工作展望 99-103 5.1 论文所做的主要工作和创新点 99-101 5.2 未来的工作展望 101-103 参考文献 103-118 致谢 118-119 攻读博士学位期间发表及录用的论文 119-120 攻读博士学位期间参加项目情况 120
|
相似论文
- 钢铁企业物料存取空间调度优化系统,F426.31
- 基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
- 基于博弈理论的货运列车编组调度模型与算法研究,O225
- 基于多Agent的河北冀通路桥公路施工智能决策支持系统研究,TP311.52
- 基于过程文档的产品设计开发过程管理系统研究与开发,TP311.52
- 柔性资源动态组合生产调度算法研究与实现,F426.8
- 多中心协同卫星任务规划平台关键技术研究,V448
- 自适应小生境混合遗传算法在车间调度问题中的研究,TP18
- 集装箱堆场场桥动态调度驾驶舱设计研究,U653.92
- 监控组态软件的设计与研究,TP273
- 面向单队单台动态调度问题的Hopfield神经网络改进算法的研究,F224
- 基于多Agent型号产品车间生产调度系统的研究,TH186
- 面向节能的流程工业系统动态调度建模及算法研究,TB497
- 文化进化算法在车间生产调度中的应用研究,F253.4
- 成品油配送调度优化问题的研究及应用,F426.22
- 基于ASIP的参数可选RISC结构汇编器以及VLIW结构汇编器设计,TP332
- 可扩展任务分配方式的工作流引擎的研究与实现,TP311.52
- 基于TR069协议的网管系统的研究,TP311.52
- 协同生产与商务平台任务分配方法的研究与实现,F273
- 面向第四方物流的供应链任务分配机制研究,F274
- 基于模块化的玻璃钢游艇工艺流程优化研究,F426.474
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 操作系统 > 实时操作系统
© 2012 www.xueweilunwen.com
|