基于区间划分的实时系统节能调度

发布时间：2017-05-18 18:02

  本文关键词：基于区间划分的实时系统节能调度，，由笔耕文化传播整理发布。

【摘要】：大部分嵌入式设备由于设备体积和使用环境等原因,使得为设备充电变得异常困难,甚至在一些应用场景中,嵌入式设备的电能使用时间也即设备的生命周期。嵌入式设备的能耗管理近些年已经发展成为嵌入式系统相关研究中最重要的研究方向之一。在过去十年里,学术界在低能耗系统设计相关领域取得了巨大的成就。工业界将高级配置与能耗接口(ACPI)标准植入了操作系统,并增加了能耗管理模块,通过提供系统调用将一些系统设备转换为低能耗状态,从而达到节能的目的。许多在嵌入式设备上运行的应用也存在严格的时间限制,这些应用必须在截止期前完成,例如嵌入式控制器。嵌入式实时系统中,在满足任务在截止期前完成(实时性)要求的前提下,尽可能的降低整个嵌入式系统的能耗,是一个需要迫切解决的问题。 将系统中小的空闲时间片段合并,增加空闲时间片段的平均长度,是解决嵌入式实时系统能耗问题的一个行之有效的策略。基于这种策略,提出了一种区间划分的能耗管理策略,由于划分的区间在形状上类似于垛的形状,因此将其称为Crenel-Interval (CI)。划分CI需要满足两个条件：1.将一个CI中所有的空闲时间片段合并后,CI中最多只能出现一个空闲时间片段：2.在满足1的条件下,CI的长度尽可能的长。在每个CI中,任务实例只能在CI的两端执行,而CI中所有的空闲时间片段都集中在CI的中间,因此在每个CI中最多只会存在一个CI。通过分析CI与任务实例之间的关系,CI中的任务实例被分为强制任务实例和可选任务实例,其中强制实例必须在当前的CI中完成,且在CI的前端执行,可选任务实例的部分工作量可以被推迟到后续的CI中执行,且在当前CI中执行的部分工作量需要在CI的后端执行。由于在每个CI中都形成了一个连续且较长的空闲时间片段,CI能够辅助一些调度算法降低系统能耗。 DPM (Dynamic Power Management)技术可以将系统中的空闲设备转换为低能耗状态,从而达到节能的目的。利用DPM技术,基于不同的设备模型,提出了两种采用EDF (Earliest Deadline First)优先级分配策略的动态优先级节能调度算法。在单设备模型中,系统中只有一个设备,所有的任务都使用这个设备,基于此模型提出了CI-EDF调度算法。针对按照CI规则划分的可选任务实例的推迟问题,在保证任务集(任务集利用率U满足U≤1)可被CI-EDF调度的条件下,给出了每个可选任务实例在CI中的执行时间以及所有可选任务实例可被开始调度执行的时间点。CI-EDF的算法复杂度为O(n2)(n是系统中任务的个数)。在多设备模型中存在多个设备,一个任务可以使用多个设备,一个设备可以被多个任务使用,基于此模型提出了CI-EDFm算法。CI-EDFm为每个设备提供了一个CI (DCI), DCI是根据访问该设备的所有任务的周期计算而来。考虑到一个任务实例可能会访问多个设备,设计了一个基于权重因子的策略来判断任务实例是否应该被推迟,这个策略综合考虑了任务实例访问的所有设备的DCI以及这些DCI对能耗的影响,同时给出了计算任务实例可被推迟的最长时问的方法。CI-EDFm的时间复杂度为O(nm)(m是系统中设备的个数)。为了进一步的降低系统的能耗,提出了将DVFS技术集成到CI-EDF和CI-EDFm中的方法。考虑到任务在实际执行的过程中需要执行的时间要小于最坏情况的执行时间,对CI-EDF和CI-EDFm进行了修订,使得它们能够通过回收动态空闲时间来进一步节省系统能耗。 现代处理器中,晶体管的尺寸变的越来越小,晶体管需要的阈值电压也在降低。由于亚阈值漏电流(Subthreshold Leakage.处理器漏电流的主要来源)随着阈值电压的降低而呈指数级增长,导致更多的电流消耗在晶体管的基底中。晶体管阈值电压的降低也使得处理器在较低的供应电压下也能获得较高的频率,导致处理器的动态功耗的减少。这说明在很多现代处理器中,能够用DVFS (Dynamic Voltage and Frequency Scaling)技术降低的动态能耗在减少,处理器的漏电流功耗(静态功耗)却在增加,漏电流功耗在处理器的功耗中占有的比例呈增大趋势。为了降低处理器的漏电流功耗,提出了基于CI的CI-RM算法。CI-RM算法为每个任务设置了一个阈值参数,这个参数和任务的周期以及任务集的利用率有关。如果任务实例的周期区间和CI的重叠区域的长度大于该任务的阈值参数,那么这个任务实例必须在当前的CI中完成其所有的工作量,反之,这个任务实例必须被推迟到下一个CI中执行。为了保证任务集在CI-RM算法下的可调度性,给出了可调度性证明以及CI-RM算法适用的任务集的利用率范围。CI-RM的时间复杂度为O)(n)。实验结果表明,和现有的基于区间划分的漏电流功耗管理算法相比,CI-RM能够适用利用率范围更广的任务集,CI-RM生成的空闲时间的平均长度是现有算法的两倍多,而且CI-RM能够节省更多的能耗(最高12%)。
【关键词】：功耗/能耗 嵌入式实时系统 垛区间 动态能耗管理 漏电流功耗
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP332
【目录】：

• 摘要4-7
• Abstract7-12
• 1 绪论12-22
• 1.1 研究背景与意义12-15
• 1.2 国内外研究现状15-20
• 1.3 论文的组织结构20-22
• 2 基于Crenel-Interval的区间划分22-31
• 2.1 任务模型22
• 2.2 Crenel-Interval的定义22-23
• 2.3 计算Crenel-Interval的长度23-26
• 2.4 Crenel-Interval中任务实例的分类26-30
• 2.5 本章小结30-31
• 3 基于Crenel-Interval的动态优先级调度算法31-64
• 3.1 任务与能耗模型31-33
• 3.2 算法动机33-35
• 3.3 单设备模型下的CI-EDF算法35-43
• 3.4 多设备模型下的CI-EDFm算法43-52
• 3.5 进一步降低能耗的策略52-54
• 3.6 实验与分析54-63
• 3.7 本章小结63-64
• 4 基于Crenel-Interval的处理器静态能耗管理算法64-82
• 4.1 任务与能耗模型64-65
• 4.2 算法动机65-67
• 4.3 CI-RM算法67-76
• 4.4 CI-RM算法和RMS以及ERHS的比较76
• 4.5 实验与分析76-81
• 4.6 本章小结81-82
• 5 总结与展望82-86
• 5.1 主要工作总结82-84
• 5.2 研究展望84-86
• 致谢86-88
• 参考文献88-94
• 附录1 攻读学位期间发表论文目录94-95
• 附录2 攻读博士学位期间参加课题目录95

【相似文献】

中国期刊全文数据库 前10条

1 杨羽,鄢伶俊;多机异构相关任务集的调度优化研究[J];计算机学报;1993年09期

2 孟新;杨震;;空间科学探测任务集同论证平台[J];科研信息化技术与应用;2011年03期

3 尹翔;蒋建国;夏娜;常传文;;多任务多联盟并行生成:模型与求解[J];系统工程理论与实践;2008年04期

4 陈庭贵;肖人彬;;基于内部迭代的耦合任务集求解方法[J];计算机集成制造系统;2008年12期

5 徐敏,王行仁，冯勤;同构型分布式计算机系统的启发式任务分配算法[J];计算机学报;1994年02期

6 陈宇;熊光泽;杨春;;非精确任务集的容错单调比率调度[J];计算机科学;2002年01期

7 王涛;刘大昕;;单调速率任务分配算法利用率的界限分析[J];计算机应用;2006年09期

8 钱光明;;平滑而快速地插入新任务[J];湖南文理学院学报(自然科学版);2008年02期

9 李婷;王海瑞;张继燕;;混合任务集的层次调度方案[J];电脑知识与技术;2008年35期

10 赵韩;武照云;宋晖;邰丽君;;一种求解产品开发耦合任务依赖度的方法[J];中国机械工程;2009年07期

中国博士学位论文全文数据库 前1条

1 张易;基于区间划分的实时系统节能调度[D];华中科技大学;2015年

中国硕士学位论文全文数据库 前8条

1 姜辉;基于EDF算法的任务最早插入时间研究[D];湖南师范大学;2012年

2 陈湘华;一种基于EDF的运行时模型研究[D];湖南师范大学;2012年

3 肖柱;多任务飞行控制系统中调度算法与可靠性控制研究[D];电子科技大学;2012年

4 钱杰;DVS节能技术与EDF调度结合的节能算法[D];浙江大学;2007年

5 李学辉;异构多核系统中面向细粒度任务集的调度算法研究[D];湖南大学;2011年

6 问翠梅;多Agent系统中联盟形成问题的研究[D];兰州大学;2009年

7 刘莉;基于实时Linux的调度方法研究[D];沈阳工业大学;2006年

8 马炳周;考虑缓存替换影响的最坏响应时间分析研究[D];湖南大学;2013年

  本文关键词：基于区间划分的实时系统节能调度，由笔耕文化传播整理发布。

本文编号：376727