【摘要】：随着多核处理器的飞速发展,越来越多的嵌入式实时系统设计者选择多核处理器作为硬件平台,以满足各类应用不断增长的高性能与低功耗的需求。更高精确度和更高效率的多核处理器实时调度技术已成为这一发展趋势的迫切需要。在过去的四十年中,面向单核处理器的实时调度技术已经发展得比较成熟。相比之下,面向多核并行体系结构的实时调度,无论从理论方面还是系统实现方面依然面临着巨大挑战。 基于这一背景,本文研究面向多核体系结构的实时调度技术,旨在突破多处理机模型调度中的重要基本理论难题,并解决在多核平台上构建实时系统的实际挑战。多处理机调度主要分为全局调度和划分(及半划分)调度。本文分别针对这两类调度算法中的关键理论问题给出了新的理论结果(包括全局调度的关键时刻、全局调度的有限响应时间条件、半划分调度中的资源利用率界限),并提出了一系列调度技术来提高多处理机系统的平均实时性能(包括不可抢占全局调度技术、任务实例级别优先级分配技术、半划分调度中基于响应时间的划分技术、半划分调度中参数化的资源利用率界限)。主要贡献点概括如下： (1)建立了多处理机全局调度近似关键时刻的概念,在此基础上提出了一种针对可抢占全局固定优先级调度的响应时间分析新技术,在不牺牲分析效率的前提下大幅度提高了分析的精确度。在这一理论基础之上,建立了可抢占全局固定优先级调度下任务具有有限响应时间的一般性条件。 (2)提出了一种新的针对不可抢占全局固定优先级调度的可调度性分析技术,并结合大量的模拟实验,推翻了从单处理机实时调度中衍生出来并被普遍接受的关于“可抢占调度的实时性能总是好于不可抢占调度”的错误观念,并对这种现象进行了深入分析,系统分析了如何利用不可抢占调度来提高系统的实时性能。 (3)提出了一种固定实例优先级的全局调度算法及相应的分析技术。该算法结合了固定任务优先级分配与最早截止期优先(EDF)两类算法的优点,通过发掘任务实例之间的优先级顺序来大幅度提高系统的可调度性。该算法在设计阶段仅对有限个具体的任务实例进行优先级分配,以构建运行时系统的负载抽象表达；在运行时,通过复用上述优先级分配方案实现高效的在线调度。 (4)将单处理机调度中著名的LiuLayland资源利用率界限推广到多处理机调度模型,解决了实时调度领域一个近四十年悬而未决的重要理论问题。提出一种具有LiuLayland资源利用率界限的半划分调度算法,使用与装箱问题中的“最坏适用递减”启发式算法类似的任务划分顺序,来使任务切割只发生在高优先级任务中,并利用高优先级任务具有较大松弛时间的特性,来抵消任务切割所带来的负载增长效应。 (5)将单处理调度中大部分的参数化资源利用率界限扩展到了多处理机调度。提出一种具有参数化资源利用率的半划分调度算法,该算法在大部分情况下满足单处理机RMS调度中任意已知的参数化资源利用率界限。此外,该算法由于使用响应时间分析来决定一个处理器上可以接纳的最大负载,因此获得了比现有算法更好的平均实时性能。 此外,本文还研究了面向共享缓存的多核实时调度技术。多核处理器的一个全新特性是存在大量的片上共享硬件资源(如共享缓存等),对共享资源的并行访问使得一个任务的执行时间依赖于其它同时执行的任务,因此动摇了传统实时调度中“已知任务的最坏情况执行时间”这一基本假设,为多核实时调度及可调度性分析带来了前所未有的挑战。本文提出了一种全新的共享缓存敏感的多核实时调度及可调度性分析技术。该方法首先通过划分共享缓存来减少任务间干涉从而提高了系统的时间可预测性,在此基础上,从“处理机”和“缓存”两个维度上解决资源分配与调度的问题,并相应的给出了两种可调度性判定的方法。 综上,本文研究了面向多核处理器的实时调度问题,内容涵盖了多个调度算法种类(全局与划分,可抢占与不可抢占,固定任务优先级与固定实例优先级)。本文的研究成果为面向多核处理器的实时系统的设计与分析提供了重要的理论依据,并对解决在多核系统上部署实时系统的实际问题具有很好的参考价值。
[Abstract]:......
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP332
【共引文献】
相关期刊论文 前10条
1 夏继强;薛利强;满庆丰;;时间触发CAN总线实时性分析及评估方法[J];北京航空航天大学学报;2012年02期
2 赵海;周峰;罗玎玎;;WebitOS中动态优先级调度机制及EDF算法的实现[J];东北大学学报(自然科学版);2008年11期
3 周本海;乔建忠;林树宽;;多核平台的并行实时调度与内存分配算法[J];东北大学学报(自然科学版);2012年03期
4 廖勇;熊光泽;陈旭东;桑楠;朱清新;;分布式实时嵌入式系统端到端性能确保[J];电子科技大学学报;2007年03期
5 陈旭东;朱清新;廖勇;匡平;熊光泽;;一种非周期软实时系统的缓冲设计方法[J];电子科技大学学报;2007年03期
6 廖勇;陈旭东;桑楠;胡林辉;熊光泽;朱清新;;分布式实时系统的自适应资源管理中间件[J];电子科技大学学报;2008年01期
7 宋振超;;基于多处理器嵌入式系统调度算法的研究[J];电脑知识与技术(学术交流);2007年21期
8 余科军;卢建斌;;基于平均分配原则的任务调度算法[J];电脑知识与技术;2008年01期
9 陶军;吴清亮;吴强;;基于非合作竞价博弈的网络资源分配算法的应用研究[J];电子学报;2006年02期
10 郭锐锋;刘娴;丁万夫;;基于优先级降低策略的回卷恢复容错实时调度算法研究[J];电子与信息学报;2012年02期
相关会议论文 前4条
1 王文伟;鲁植雄;袁越阳;;基于CAN总线的拖拉机虚拟仪表系统设计[A];纪念中国农业工程学会成立30周年暨中国农业工程学会2009年学术年会（CSAE 2009）论文集[C];2009年
2 淡图南;朱立平;颜纪迅;;一种基于时间触发的安全关键操作系统混合调度策略[A];全面建成小康社会与中国航空发展——2013首届中国航空科学技术大会论文集[C];2013年
3 时小虎;;实时并行处理技术在指控系统中的应用[A];2014第二届中国指挥控制大会论文集（上）[C];2014年
4 梁心雄;吴兆雄;罗胜平;;实现资源信息自助服务的智慧气象共享数据中心研究论述[A];第31届中国气象学会年会S13 气象通信与信息技术应用实践与新技术探索[C];2014年
相关博士学位论文 前10条
1 殷进勇;可重构系统中实时任务调度算法研究[D];哈尔滨工程大学;2010年
2 郭秀岩;面向多核的多层次实时网络数据流调度技术研究[D];中国科学技术大学;2011年
3 陈曦;CAN总线实时性和可靠性若干问题的研究[D];天津大学;2010年
4 盛伟;考虑缓存预热时间的多核实时调度算法和分析[D];中国科学技术大学;2011年
5 李婵娟;安全关键实时通信协议研究[D];兰州大学;2011年
6 桂盛霖;安全关键嵌入式实时软件的关键非功能属性分析研究[D];电子科技大学;2011年
7 吕鸣松;实时系统最坏情况执行时间分析技术的研究[D];东北大学;2010年
8 乔颖;实时异构系统的集成动态调度算法研究[D];中国科学院软件研究所;2001年
9 王X;基于异构系统的实时数据处理[D];中国科学院研究生院（软件研究所）;2002年
10 阳春华;工业实时系统多任务容错调度技术及应用研究[D];中南大学;2002年
，
本文编号：
2443142
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2443142.html
