面向非自监测系统的混合关键性实时调度算法研究

《面向非自监测系统的混合关键性实时调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文面向非自监测系统的混合关键性实时调度算法研究作者姓名：李龙久指导教师：邓庆绪教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机应用技术论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答辩委员会主席：书蓬华评阅人：确兹凇东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyResearchofReal-timeSchedulingAlgorithmforNon--monitoringMixed-·Critic

2、alitySystemsByLiLongjiuSupervisor：ProfessorDengQingxuNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：荟7彰众Et期：伽l牛‘、26学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使

3、用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年／学位论文作者签名：瓤么签字日期：勘l钦(Z名导师签名：及F袁彳荔签字日期：210lⅥ6。沈万方数据东北大学硕士学位论文摘要面向非自监测系统的混合关键’I生实时调度算法研究摘要随着信息技术产业的快速发展，实时嵌入式系统的应用日益广泛。由于受研发设备成本、体积、能耗、资源利用率等因素的多重约束，在同一个硬件平台上集成

4、多种不同关键性级别功能应用已经成为现代嵌入式系统的流行趋势。对不同关键性级别的功能应用，其验证方法和可靠性级别都有不同。对系统中不同重要程度的功能赋予不同的关键性级别的混合关键性系统为现代实时嵌入式系统的设计提供了有效的方案。随着混合关键性系统模型的的提出，混合关键性实时调度算法的研究与设计也成为实时嵌入式系统领域的热点问题。在混合关键性领域已有的调度算法中，OCBP(OwnCriticalityBasedPriority)算法具有很多优秀的性质并引起了混合关键性领域学者的广泛关注。但是OCBP算法只适用于有限数量作业的系统，为了解决这个问题，有学者提出了

5、LB算法，LB采用忙碌周期的技术将OCBP拓展到更为通用的混合关键性偶发性任务模型中。然而LB算法的运行时时间复杂度为伪多项式级别，这对嵌入式系统而言难以接受。后来的PLRS算法利用优先级计划表和运行时抽象数据结构将系统的时间复杂度降为平方级别，但对于嵌入式系统来说还是过高。最近提出的LPA(LazyPrioritiesAdjustment)算法在作业发生抢占时尽可能晚的调整优先级，从而大大降低了算法的时间复杂度。LPA等算法离线优先级分配都是基于OCBP算法，并且都是面向自监测系统的。自监测系统要求时刻监视着系统作业的执行时间，这就带来严重的运行时负载，

6、因此本文提出面向非自监测系统的混合关键性调度算法LPA丰。非自监测系统不要求时刻监视作业的执行时间，虽然可能导致某些作业执行过载，但极低的运实行调度开销使其更容易应用到实际系统中。本文提出了更为精确的离线作业固定优先级分配算法，提高系统资源利用率，并提出了性能良好的非自监测系统混合关键性实时调度算法LPA木。实验结果表明，采用本文的离线优先级分配算法，LPA水算法相对LPA算法有显著的资源利用率提升。特别地，LPA+在非自监测系统任务接受率性能下降不明显，甚至优于LPA、Vestal等算法在自监测系中的接受率。较高的资源利用率，和非自监测系统系统本身较低的

7、调度开销，使得LPA算法更容易应用到实际嵌入式系统当中。关键词：实时调度；混合关键性；非自监测系统；固定作业优先级万方数据东北大学硕士学位论文AbstractResearchofReal·-timeSchedulingAlgorithmforNon--monitoringMixed—-CriticalitySystemsAbstractWiththerapiddevelopmentofinformationtechnologyindustry,theapplicationofreal-timeembeddedsystemsisbecomingmoreand

8、morewidely．Duetothemultiplerestri