实时系统可变工作量建模及计算方法

发布时间：2019-10-24 00:51

【摘要】：传统实时系统性能分析以最差情况下执行时间(worst-case execution time,WCET)作为主要输入,导致分析过于保守.针对实时系统设计时预留冗余过大的问题,建立了以到达事件类型、数量和分布为决策变量,包括工作量曲线(workload curves)、逆工作量曲线(inverse workload curves)、工作量比率曲线(workload ratio curves)在内的实时系统可变工作量模型,给出了相关计算方法.基于可变工作量模型分析了其在混合调度中的应用,结果表明:采用可变工作量模型和算法可显著减少任务所需的执行工作量,降低了实时系统的资源需求.
【图文】：

算法,事件序列,计算方法,事件

亩ㄒ逋评恚釓獐?γl－1(e)的定义，可得γl(k1)=γl(γl－1(e))=γl(mink1∈Z≥0{k1:γl(k1)≥e})≥e;根据γu－1(e)的定义，可得γu(k2)=γu(γu－1(e))=γl(maxk2∈Z≥0{k2:γu(k2)≤e})≤e;所以γl(k1)≥γu(k2)．至此可见由逆工作量曲线定义得出的结论与反证法最初假设推出的结论矛盾，因此性质7得证．2工作量曲线与逆工作量曲线的算法2.1算法1———工作量曲线计算方法算法1的流程图如图1所示．图1工作量曲线算法Fig.1Workloadcurvesalgorithm算法1基于定义1、定义3、定理1、定理2得出．算法1的时间复杂度为O(k×(n－k+1))，若k郙n，则算法时间复杂度退化成O(n)．2.2算法2———逆工作量曲线计算方法算法2的流程图如图2所示．图2逆工作量曲线算法Fig.2Inverseworkloadcurvesalgorithm算法的时间复杂度为O(n×k×(n－k+1))，若k郙n，则退化成O(n2)．算法2是在算法1的基础上基于定义5及其性质得出．算法1和算法2中事件到达模型一般有两种确定方法，一种是根据实际系统的经验数据，另一种是根据系统严格的形式化说明［7－8］．2.3仿真计算针对上述建模及计算方法，给出仿真计算示例．图3给出一个长度为10的三种类型事件到达序列，以及各类型事件的WCET和BCET．图3具有不同类型的事件序列Fig.3Eventsequencewithdifferenttypesofevents针对图3所示的事件序列，采用算法1和算法2分别计算相应的工作量曲线和逆工作量曲线，如图4所示．可以看出:由于γl(10)=14，，所以当工作量e≥15时，不存在最小工作量曲线的逆，算法返回值为－1;由于γu(10)=37，所以当工作量e≥37时，?

算法,事件序列,计算方法,事件

l(maxk2∈Z≥0{k2:γu(k2)≤e})≤e;所以γl(k1)≥γu(k2)．至此可见由逆工作量曲线定义得出的结论与反证法最初假设推出的结论矛盾，因此性质7得证．2工作量曲线与逆工作量曲线的算法2.1算法1———工作量曲线计算方法算法1的流程图如图1所示．图1工作量曲线算法Fig.1Workloadcurvesalgorithm算法1基于定义1、定义3、定理1、定理2得出．算法1的时间复杂度为O(k×(n－k+1))，若k郙n，则算法时间复杂度退化成O(n)．2.2算法2———逆工作量曲线计算方法算法2的流程图如图2所示．图2逆工作量曲线算法Fig.2Inverseworkloadcurvesalgorithm算法的时间复杂度为O(n×k×(n－k+1))，若k郙n，则退化成O(n2)．算法2是在算法1的基础上基于定义5及其性质得出．算法1和算法2中事件到达模型一般有两种确定方法，一种是根据实际系统的经验数据，另一种是根据系统严格的形式化说明［7－8］．2.3仿真计算针对上述建模及计算方法，给出仿真计算示例．图3给出一个长度为10的三种类型事件到达序列，以及各类型事件的WCET和BCET．图3具有不同类型的事件序列Fig.3Eventsequencewithdifferenttypesofevents针对图3所示的事件序列，采用算法1和算法2分别计算相应的工作量曲线和逆工作量曲线，如图4所示．可以看出:由于γl(10)=14，所以当工作量e≥15时，不存在最小工作量曲线的逆，算法返回值为－1;由于γu(10)=37，所以当工作量e≥37时，最大工作量曲线的逆等于10．192东北大学学报(自然科学版)第38卷
【作者单位】：东北大学信息科学与工程学院;
【基金】：国家自然科学基金资助项目(61472072) 国家重点基础研究发展计划项目(2014CB360509)
【分类号】：TP301.6;TP332

【相似文献】