关于自适应实时调度中若干问题的研究

论文摘要

随着应用的推动,实时系统变得越来越复杂和灵活,比如像普适计算,自适应控制,视频会议等应用都具有高度的动态性与时变性。因此,实时系统的研究重点也从静态调度过渡到动态调度、从可预测环境过渡到不可预测环境、从周期性任务过渡到非周期性任务。本文着重研究动态系统的实时调度问题,具体内容如下:首先简要回顾了动态系统实时调度的研究现状,重点对反馈控制实时调度和实时排队论进行了介绍。然后介绍了一种静态的资源管理方法。在任务集具有速率约束时,该方法能以线性时间复杂度生成任务的可调度性上下界,并确定任务集的一个可行解。在此基础上,设计了一种简单的随机启发式算法来获得一个可行解,该可行解可以作为其他算法(如遗传算法、模拟退火算法、人工神经网络等)的初始点来进一步获得更精确的解。也可用其他的方法来获得可行解。接着讨论了如何把反馈控制用于实时调度中。首先把反馈理论中的自平衡概念引入到动态实时系统中,并在此基础上提出了针对单处理器非周期任务集的自平衡模型,该模型从实时计算系统本身出发,采用一种模型化实时系统的新方法,把许可控制和QoS降级相结合,运用反馈控制技术来确保系统的性能和提高系统的吞吐率。然后针对端到端结构的分布式实时系统提出了一种线性二次最优控制模型,该模型通过两个控制环来确保系统的实时性和性能。再接着讨论了基于排队论的实时调度。任务到达和执行时间均是随机的非周期软实时系统可以看作是一个随机服务系统。首先给出了先来先服务调度策略的一些结果;然后在此基础上构造了针对DM调度算法的最优控制模型,此时非周期软实时系统是一个多优先级的单服务台排队系统。该模型能在统计意义上保障系统的实时性,同时兼顾系统的服务质量和提高系统吞吐率。最后分析了缓冲阈值对系统性能的影响,并设计了相应的控制模型。最后对一个应用实例进行了研究,即无线局域网作为有线网络的扩展时的压缩视频实时传输问题。也就是一边是有线网,一边是无线局域网时,如何确保传输的实时性和接收端播放的连续性。在TMN8测试模型的基础上,讨论了一种适用于无线局域环境的速率自适应转码算法。该算法采用了随机控制技术来适应无线信道带宽的随机变化。我们进行了较详细的性能分析,最后的仿真试验结果说明该算法能够兼顾视频传输的实时性和播放质量要求。和TMN8的比较也说明我们的算法更能适应带宽的变化和充分利用信道资源。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 课题研究背景
• 1.2 研究意义
• 1.3 国内外研究现状
• 1.3.1 动态系统的实时调度
• 1.3.2 反馈控制实时调度
• 1.3.3 实时排队论
• 1.4 本文主要研究内容及主要贡献
• 1.4.1 主要研究内容
• 1.4.2 主要贡献
• 1.5 本文章节安排
• 第二章 载荷管理的动态随机启发式算法
• 2.1 简介
• 2.2 任务模型
• 2.3 最优性
• 2.4 弹簧调度算法
• 2.5 启发式算法
• 2.5.1 可行解域
• 2.5.2 随机启发式算法
• 2.5.3 算法分析
• 2.6 实验
• 2.7 本章小结
• 第三章 基于反馈控制的实时调度算法
• 3.1 简介
• 3.2 结构化非周期任务模型及DM算法简介
• 3.3 执行器
• 3.4 自平衡的概念
• 3.5 单处理器的反馈控制实时调度
• 3.5.1 计算系统及干扰
• 3.5.2 DRSSR系统模型
• 3.5.3 性能分析及参数设定
• 3.6 端到端多处理器的反馈控制实时调度
• 3.6.1 端到端任务模型
• 3.6.2 LQSOCM的结构
• 3.6.3 端到端控制系统的设计
• 3.7 试验
• 3.8 本章小结
• 第四章 基于排队论的软实时调度算法
• 4.1 简介
• 4.2 任务模型
• 4.3 FCFS的动态最优控制
• 4.4 DM算法的动态最优控制
• 4.5 缓冲阈值的设计及控制
• 4.5.1 缓冲阈值H对系统性能的影响
• 4.5.2 缓冲阈值H的设计
• 4.5.3 有缓冲阈值限制的控制模型
• 4.6 试验及性能分析
• 4.6.1 采用DM调度算法时的性能比较
• 4.6.2 缓冲对系统性能的影响分析
• 4.6.3 缓冲阈值限制时的控制实验
• 4.7 本章小结
• 第五章 压缩视频实时传输中的自适应码率控制
• 5.1 简介
• 5.2 码率控制研究现状
• 5.3 无线视频通信系统
• 5.4 自适应码率控制算法
• 5.4.1 系统结构
• 5.4.2 TMN8测试模型介绍
• 5.4.3 帧一级的码率控制算法
• 5.4.4 参数a，b的确定
• 5.4.5 宏块一级的码率控制算法
• 5.5 性能分析
• 5.5.1 瞬态性能
• 5.5.2 稳态性能
• 5.5.3 算法复杂度
• 5.6 试验
• 5.6.1 测试目标帧的比特数变化情况
• 5.6.2 缓冲填充度的变化情况
• 5.6.3 系统的阶跃响应
• 5.6.4 缓冲为空的概率
• 5.6.5 跳帧的概率
• 5.6.6 和TMN8进行比较
• 5.7 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 展望
• 致谢
• 参考文献
• 博士期间发表论文