公开/公告号CN103810043A
专利类型发明专利
公开/公告日2014-05-21
原文格式PDF
申请/专利权人 中国科学院沈阳计算技术研究所有限公司;
申请/专利号CN201210445655.0
申请日2012-11-09
分类号G06F9/50;G06F1/32;
代理机构沈阳科苑专利商标代理有限公司;
代理人许宗富
地址 110168 辽宁省沈阳市东陵区南屏东路16号
入库时间 2024-02-20 00:07:10
法律状态公告日
法律状态信息
法律状态
2016-09-07
授权
授权
2014-06-18
实质审查的生效 IPC(主分类):G06F9/50 申请日:20121109
实质审查的生效
2014-05-21
公开
公开
技术领域
本发明涉及实时系统领域任务的实时调度,具体的说是一种适用于数控系统周期任务的节能调度方法。
背景技术
实时系统在数控技术领域和嵌入式产品的应用越来越广泛,尤其在功能复杂、系统庞大的应用中显得愈来愈重要。这就要求实时系统能够提供更为高效的计算能力,以满足无线通信、多媒体应用的要求,然而高性能的代价就是高能耗。同时,随着制造工艺的日益精密,集成电路规模的飞速发展,导致了系统功耗的急剧上升,高功耗带来的高温会导致系统发生故障的可能性增加,降低整个系统的可靠性;因此,能耗已成为实时系统设计的瓶颈。
动态电压调节(DVS)技术是一种有效的低功耗和能耗优化技术。其主要思想是针对不同的系统负载,在满足系统实时性的前提下,降低CPU的工作电压和时钟频率。
现有的低功耗调度算法采用DVS技术,在满足系统实时性的前提下,通过回收系统的空闲时间,利用空闲时间降低处理器的运行电压和时钟频率,以降低系统能耗;但其假设处理器提供连续的频率和电压,而实际的商用处理器只提供离散的频率和电压,为了确保任务不错过截止期限,其选择的实际运行速度比连续频率情况下计算出的理想速度大,这样会造成系统资源的浪费。
发明内容
针对现有低功耗调度算法的不足之处,本发明提出了一种适用于数控系统周期任务的节能调度方法,该算法能够有效地利用系统的空闲时间,降低系统的能耗。
为实现上述算法,本发明采用以下的技术方案:
一种适用于数控系统周期任务的节能调度方法,其特征在于:包括如下步骤:
任务集调度之前,计算数控系统中任务Ti在离线状态下的最佳运行速度
再计算任务Ti在最佳运行速度下的执行时间,根据最早截止期限优先原则对任务集进行排序;
当某个任务完成时,回收该任务空闲时间Slack_Time,利用该空闲时间Slack_Time计算出该任务的在处理器规定连续电压下的运行速度S;
根据运行速度S,来确定每个任务前部分的运行速度SL和后部分的运行 速度SH,最后计算出任务在前部分的运行速度SL下,任务的执行时间ex.L和在后部分的运行速度SH任务的执行时间ex.H,最后以所求的实际的执行时间ex.L、ex.H来调度执行任务。
最早截止期限优先原则:截止期限越短,优先级越高,当任务Ti的截止期限相同时,早到达的任务Ti优先级高;当任务Ti的截止期限和到达时间均相同时,任务Ti系列的下标i小的有更高的优先级。
计算各任务Ti在离线状态下的最佳运行速度其计算步骤如下:
利用执行时间Ci与周期Pi比值之和公式计算出系统的利用率Utot,再将利用率Utot与处理器的最小速度Smin进行比较,较大者为离线状态下的最佳运行速度
当某个任务完成时,回收该任务空闲时间Slack_Time,利用该空闲时间Slack_Time计算出该任务的在处理器提供连续电压下的运行速度S,其运行速度S处理步骤如下:
建立一个数据结构α队列来记录提前完成的任务,α队列为在离线状态最佳运行速度下的就绪队列,记录任务的到达时间、截止期限和剩余执行时间;
回收该任务空闲时间Slack_Time,找出α队列中提前完成的任务,利用每个提前完成任务的剩余执行时间,计算出每个提前完成任务的空闲时间Slack_Time,利用总的空闲时间Slack_Time计算出运行速度S。
根据运行速度S,来确定每个任务前部分的运行速度SL和后部分的运行速度SH,其处理步骤如下:
根据运行速度S的值与处理器规定的两个相邻速度SLow和SHigh进行比较,当运行速度S大于SLow并S小于等于SHigh(SLow<S≤SHigh)时,来确定认为任务前部分的运行速度SL即为处理器规定的速度SLow,任务后部分的运行速度SH即为处理器规定的速度SHigh。
本发明具有以下有益效果及优点:
(1)采用本发明方法,由于充分利用系统的空闲时间Slack_Time,降低处理器的运行速度,从而比现有的低功耗调度算法节约30.69%的能耗。
(2)由于高功耗带来的高温会导致系统发生故障的可能性增加,会降低整个系统的可靠性,而本发明充分利用系统的空闲时间Slack_Time,降低系统能耗,因此提高了系统的可靠性。
(3)降低系统封装和冷却的成本。功耗增加会显著提高系统的发热量,为了使产品能正常地散热,厂家必定会增加对于新的封装和冷却技术研究的投资,因此用于封装和冷却设备的成本会提高。
附图说明
图1为本发明方法处理步骤流程图;
图2为本发明的仿真实验结果图。
具体实施方式
下面结合附图和实施例对本发明方案作进一步详细描述。
参见附图1、图2,是一种适用于数控系统周期任务的节能调度方法,其特征在于:包括如下步骤:
任务集调度之前,计算数控系统中任务Ti在离线状态下的最佳运行速度
再计算任务Ti在最佳运行速度下的执行时间,根据最早截止期限优先原则对任务集进行排序;
当某个任务完成时,回收该任务空闲时间Slack_Time,利用该空闲时间计算出该任务的在处理器提供连续电压下的运行速度S;
根据运行速度S,来确定每个任务前部分的运行速度SL和后部分的运行速度SH,最后计算出任务在前部分的运行速度SL下的执行时间ex.L和在后部分的运行速度SH下的执行时间ex.H,最后以所求的实际的执行时间ex.L、ex.H来调度执行任务。
对本发明方法进一步说明:
计算出任务Ti在离线状态任务的最佳运行速度
由公式(1)计算出系统的利用率Utot
式中,Ci、Pi、i分别为周期任务Ti最坏情况下的执行时间、周期、任务的标识符;n为任务的个数。
由公式(2)计算出任务Ti在离线状态任务的最佳运行速度
其中Smin是处理器规定的最小速度。
当有新任务到达时,根据最早截止期限优先原则将新任务插入到α队列中的相应位置中。
最早截止期限优先原则:截止期限越短,优先级越高,当任务Ti的截止期限相同时,早到达的任务Ti优先级高;当任务Ti的截止期限和到达时间均相同时,任务Ti系列的下标i小的有更高的优先级。
当某个任务完成时,回收该任务空闲Slack_Time时间,利用该空闲时间Slack_Time计算出该任务的在处理器提供连续电压下的运行速度S,其运行速度S处理步骤如下:
建立一个数据结构α队列来记录提前完成的任务,α队列为在离线状态 最佳运行速度下的就绪队列,记录任务的到达时间、截止期限和剩余执行时间;
回收该任务空闲时间Slack_Time,找出α队列中提前完成的任务,利用每个提前完成任务的剩余执行时间,计算出每个提前完成任务的空闲时间Slack_Time,利用总的空闲时间Slack_Time计算出运行速度S。
由公式(3)计算出每个提前完成任务的空闲时间Slack_Time:
式中i为任务的标志符,di、dx分别为任务Ti、Tx的截止期限;remi(t)为任务Ti在时刻t的剩余执行时间,任务的剩余执行时间随着任务的执行逐渐减少;当任务完成时,任务的剩余时间为0。为任务Tx在时刻t以速度Sx运行的最坏情况下的剩余执行时间.由公式(3)可以看出空闲时间Slack_Time是通过提前完成任务的剩余执行时间的总和与最坏情况下的剩余执行时间之差计算得出。
利用空闲时间Slack_Time计算出任务的运行速度S:
由公式(4)算出任务的运行速度S
式中,remx(t)为任务Tx在时刻t的剩余执行时间,Slack_Time为任务的空闲时间。当任务的运行速度S比处理器规定的最小速度Smin值小时,运行速度S等于处理器规定的最小速度Smin。
根据运行速度S,来确定每个任务前部分的运行速度SL和后部分的运行速度SH,最后计算出任务在前部分的运行速度SL下的执行时间ex.L和在后部分的运行速度SH的执行时间ex.H,其处理步骤如下:
根据运行速度S的值与处理器规定的两个相邻速度SLow和SHigh进行比较,当运行速度S大于SLow并S小于等于SHigh(SLow<S≤SHigh)时,来确定认为任务前部分的运行速度SL即为处理器规定的速度SLow,任务后部分的运行速度SH即为处理器规定的速度SHigh。
在前部分的运行速度SL下,任务Tx的执行时间为执行时间ex.L;在后部分的运行速度SH下,任务Tx的执行时间为执行时间ex.H。
任务Tx的执行时间满足(5)式:
ex=ex.L+ex.H (5)
任务Tx刚到达时的执行时间满足(6)式:
S·ex=SL·ex.L+SH·ex.H (6)
由公式(5)得知执行时间ex,将执行时间ex代入公式(6)计算出在前部分的运行速度SL下,任务Tx的执行时间ex.L:
由公式(7)得知执行时间ex.L,将执行时间ex.L代入公式(5)计算出在后部分的运行速度的SH下,任务Tx的执行时间ex.H,最后以所求的实际的执行时间ex.L、ex.H来调度执行任务。
机译: 单核处理器上具有概率计算的实时任务的节能调度方法
机译: 单核处理器上具有概率计算的实时任务的节能调度方法
机译: 一种在分布式实时系统中的周期性任务之间及时传递数据的方法