面向混合关键性系统与drt模型的实时调度问题研究

《面向混合关键性系统与drt模型的实时调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、博士学位论文ＤＯＣＴＯＲＡＬＤＩＳＳＥＲＴＡＴＩＯＮ论文题面向混合关键性系统与ＤＲＴ模型的目实时调度问题研究作者谷传不东北大学信息科学与工程学院学＿专业计算机软件与理论指导教师邓庆绪教授备注二〇一五年十月曰分类号级密ＵＤＣ学位论文面向混合关键性系统与ＤＲＴ模型的实时调度问题研究作者姓名：谷传才指导教师：邓庆绪教授东北大学物联网工程研宄所申请学位级别：博士学科类别：工学学科专业名称：计算机软件与理论论文提交日期：２０１５年７月论文答辩日期：２０１５年１０月

2、：学位授予日期答辩委员会主席：、评阅人：东北大学２０１５年７月ＡＤｉｓｓｅｒｔａｔｉｏｎｉｎＣｏｍｐｕｔｅｒＳｏｆｔｗａｒｅａｎｄＴｈｅｏｒｙ－ＴＲｅｓｅａｒｃｈｏｎＲｅａｌｉｍｅＳｃｈｅｄｕｌｉｎｇ－ｄｏｆＭｉｘｅｄＣｒｉｔｉｃａｌｉｔｙＳｙｓｔｅｍｓａｎＤＲＴＭｏｄｅｌｂｙＧｕＣｈｕａｎｃａｉＳｕｐｅｒｖｉｓｏｒ：Ｐｒｏｆ．ＤｅｎｇｉｎｕＱｇｘＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙＪｕｌ２０１５ｙ，独创性声明。本人声明，所呈交的学位论文是在导师的指导

3、下完成的论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研宄成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研宄所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者：斯日期：以学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印。件和磁盘，允许论文被查阅和借阅本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的

4、时间为作者获得学位后：一年一半年□□年半□两年学位论文作者签名：导师签名：签字ｎ期：签字ｎ期：ｘ么、－－Ｉ东北大学博士学位论文摘要面向混合关键性系统与ＤＲＴ模型的实时调度问题研究摘要现代实时嵌入式系统不断发展的一个重要趋势是在同一硬件平台中集成多种不同关键性级别的应用。与此同时，嵌入式系统硬件也在经历从单核平台向多核平台的变革之中，未来还将发展至众核平台。但是这种混合关键性系统的调度问题即便是对于单核平台也是极具挑战性的，大多。目前数复杂的嵌入式系统很难被传统基于周期的简单模型所精确描述，可以用于

5、。实时任务有向图（ＤＲＴ）模型具备很强的描述能力没有循环时间行为的复杂实时系统的建模。但是针对该模型的精确时间分析在时间复杂度上通常是不可接受的（指数级复杂度）。本文研究了基于混合关键性系统和ＤＲＴ模型的实时调度算法的设计与分析等问一。在混合关键性系统研究方面，提出了种高效的单核处理器运行时调度算法题，和两种多核、多处理器划分调度算法。在ＤＲＴ模型研宂方面，提出了两种有效的近似响一应时间分析方法，并通过计算加速比进行了量化评价，还提出了种有效的有向图整形算法来提升系统的可调度性。本文的主要贡献点可以被总结如下：（ＢＰ策略的固

6、定作业优先１）提出了基于ＯＣ级单处理器混合关键性实时调度算法ＬＰＡ。与其它ＯＣＢＰ族的算法相比，ＬＰＡ算法显著提升了系统的运行时时间效率（线性时间复杂度）、空间效率和可调度性。ＬＰＡ算法的核心思想是尽可能晚的调整作业的运行时优先级，从而避免了与实际调度决策不相关的冗余优先级调整工作。本文还提出了更精确的混合关键性系统忙碌周期上界的计算方法。使用随机生成任务集合的实验结果表明本文提出算法显著提升了运行时时间效率、空间效率和可调度性。（２）提出了新型混合关键性划分调度算法ＭＰＶＤ，将单处理器上可调度性能最佳的算法ＥＹ－ＶＤ扩展至多处

7、理器平台。ＭＰＶＤ算法的核心思想是将不同关键性级别的任务尽可能均匀地分配到各个处理器中，以更好地利用不同关键性级别任务间的差异性，从而提升系统的可调度性，。本文还分析了ＭＰＶＤ的不足并提出了两个优化技术一来进步提升算法的性能。使用随机生成任务集合的实验结果表明本文提出算法的可调度性显著高于己有算法。（３）提Ｐ－出了新型混合关键性多处理器划分调度策略ＯＣＯ。本文首先结合ＥＹＶＤ算法和传统划分调度策略提出丫混合关键性系统划分调度算法ＭＣ－ＰＥＤＦ。该算法的－ＴＩ－东北大学博士学位论文摘要性能显著高于其它己有划分调度算法，

8、但本文研究发现传统的划分策略不能很好的利用任务在不同关键性级别