基于任务级的设备动态调度机制的设计与实现
何可佳
（宁波工程学院 电子与信息工程学院，浙江 宁波 315016）
摘 要 传统动态电源管理（DPM）策略仅仅建立在对目标设备的工作负载进行观测的基础上。由于这些设备级的DPM策略只能隐式认为所有工作负载来自于同一个任务请求源，因而带有一些不可避免的缺陷。本文的主要工作是在DPM范畴内提出了一种基于任务级的动态功耗降低技术，通过对任务请求源进行划分以及系统级的准确建模，从而能够提供PM更多有关将来的工作负载请求信息。实验结果表明，本文所提出的EODSA策略及改进策略都具有稳定性，而且在满足相应假设和前提条件下都能够更为显著的降低外设乃至整个系统的平均功耗。
关键词 动态电源管理；低功耗；任务级；工作负载
1 引言
目前商用产品中的PM（Power Management，电源管理）大多数都基于Timeout超时策略，即当设备的空闲时段超过某个门限时将其关闭[1]；而大部分研究都以硬件为中心，它们通过对目标设备在过去一段时间内的任务请求情况进行观测来预测将来的使用情况。由于缺少区分任务请求源的相关信息，一些策略则使用随机模型[2]。
本文将这种以硬件为中心的方法称为DLPM（Device-Level PM）。DLPM具有两个主要的缺陷：第一，不同的任务可能具有本质上不同的请求形式，但是DLPM却不能做出任务具体形式的判断；第二，任务可被创建和终止[3]。
为了克服上述DLPM策略所固有的问题，本文从任务级的角度出发提出了一种新颖的在线设备调度策略EODSA及其改进策略IEODSA。
2 EODSA策略
2.1 EODSA介绍
EODSA策略的本质就是根据用户任务所提供的额外信息，能够在用户任务启动之前实现对设备的调度操作，避免传统DLPM策略在执行过程中所出现的诸如无谓等待过程或者预测错误等缺陷。所谓“调度”，就是对设备进行打开（让设备进入正常工作模式）和关闭（让设备进入睡眠状态）等操作。为了方便对EODSA以及IEODSA策略的阐述，本文选择了一种基于FIFO任务调度的系统进行了说明。
假设系统共有M个用户任务，记为Ti（1≤i≤M）；那么加上系统中的空闲任务（记为TM+1），整个系统共有（M+1）个可运行任务。本文将任务队列记为TQ，其最大长度为N（M<N）；并将TQ中的第一个任务记为TQ{0}，依此类推。如在图1所示的TQ中，处于就绪状态的任务分别是T2、T1、T4，系统将按照FIFO的规则对这些任务进行调度。
图1 任务队列表
在EODSA设备调度策略中，需要为每个任务Ti定义一个二维数据结构{Di，Ei}，其中Di表示任务Ti在整个执行过程中所使用到的IO设备集，Ei表示该任务的执行时间。这里预先假设，若di∈Dj，则Tj在整个过程中都会使用到di。EODSA基于这些额外的任务信息以及假设条件，就能够对外设进行调度操作。
2.2 EODSA策略算法
EODSA策略的主要原理为：在任务Ti开始运行之前，依次检测各个di在Ti或者di在Ti及其相连任务Tj中的使用情况，并做出相应的调度操作。对基于FIFO调度策略的系统来说，可以执行EODSA策略的任务只能是TQ{0}中的任务或者空闲任务这两种情况。另外，当TQ{0}中存有任务时，还要考虑TQ{1}是否为空，因此EODSA要针对三种系统任务情况进行讨论，即任务数目为0、1以及大于1的三种情形。EODSA的整个伪代码如下：
EODSA（任务数目）
前提条件：Ei>（TBE）max（1≤i≤M+1）
1. if（TQ中的任务数目大于1） //注释：TQ{0}、TQ{1}中都存在任务
2. if（设备di处于正常工作状态）
3. if（设备di不会被TQ{0}和TQ{1}使用）
4. 将di置为睡眠状态；
5. if（设备di不会被TQ{0}使用，但是会被TQ{1}使用）
6. 将di置为睡眠状态，并在TQ{0}任务结束之前提前打开di；
7. else（设备di处于关闭状态）
8. if（di将被TQ{1}使用）
9. 在TQ{0}任务结束之前提前打开di；
10. else if（TQ中的任务数目等于1） //注释：只有TQ{0}中存在任务
11. if（设备di处于正常工作状态且不会被TQ{0}使用）
12. 将di置为睡眠状态；
13. else //注释：任务队列中的任务数目等于0，TQ{0}为空
14. 进入Idle Task后关闭所有的di；
15. 退出Idle Task时打开所有T1将使用到的di
在EODSA伪代码中，引入了常量TBE。TBE是DPM理论中经常提到的一个概念，其本质含义是设备在空闲状态下进行工作状态转移时所对应的省电平衡时间点，每个外设di都存在一个（TBE），则（TBE）max=max（TBE）i，其中S代表设的总数。而EODSA策略所给出的前提条件，即所有任务的执行时间都大于（TBE）max，一方面是为了保证设备能够及时的对任务请求进行响应，另一方面也能够保证该设备的工作模式切换过程不会增加系统的额外功耗。
因此，当设备在所有任务中的使用特性都满足EODSA策略的假设条件时，EODSA策略的省电性能要优于DLPM策略。但在实际系统中，如果di∈Dj，并不能保证不在整个过程中都会使用到di；通常di只是在Tj的某一小段执行时间内被使用。那么在这种情况下，如果将di在Tj的整个运行过程中都处于正常工作状态，则会在很大程度上浪费能量。下面针对这种情况对EODSA进行了改进，在此基础上形成了IEODSA策略。
3 IEODSA策略
针对EODSA策略的不足之处，我们需要对每个任务作进一步划分，即将任务Tj划分成{STj，1，STj，2，...STj，n}等n个子任务。任务划分要满足下面的规则：（1）各个子任务的执行过程相互独立；（2）相连两个子任务所使用的外设至少有一个不相同；（3）若di被子任务STj，k使用，则STj，k将在整个过程中都会使用到di。
IEODSA策略的基本思想是：在对Tj进行设备调度的基础上，再在Tj运行过程中针对每相连的两个子任务STj，k，STj，k+1∈Tj进行设备调度。显然，可以直接采用EODSA策略对Tj进行先期的设备调度；因此IEODSA策略可以看成是EODSA策略和子任务设备调度过程两者的合成。本文将子任务设备调度过程记为STDSP（Sub-Task Device Schedulimg Process）。下面将侧重阐述STDSP的原理。
STDSP的前提条件是任何一个STj，k的执行时间都必须大于（TBE）max。由于EODSA策略已经保证任务Tj在执行之前将使用的外设都已处于正常工作状态，那么STDSP只需根据子任务的设备使用特征来对di∈Dj执行相关调度。其对设备的调度情况可以分为以下两种：（1）在运行STj，k之前，如果设备di（di∈Dj）处于正常工作状态，那么当STj，k与STj，k+1都不会使用di时则关闭之，当STj，k不使用di但是STj，k+1却使用时，则将di置为睡眠模式后需在STj，k运行完毕之前提前打开di；（2）在运行子任务STj，k之前，如果设备di处于睡眠状态，那么当STj，k不使用di但是STj，k+1却使用时，则需要在STj，k运行完毕之前提前打开di。
4 实验验证
4.1 实验环境
具体的实验环境设置如下：（1）系统任务组中共有四个可调度任务T1、T2、T3、T4，且Ti（i=1，2，3，4）服从随机分布。Ti对应子任务STi，k的执行时间及其所使用的外设如表1所示；（2）系统中的设备di（i=1，2，3，4）都具有两种电源状态，即高能耗的正常状态和低能耗的睡眠状态，这些状态的功耗以及状态切换时间则如表3所示；（3）若di被子任务STj，k使用，则STj，k将在整个过程中都会使用到di。从表2可以看出，STi，k的最小执行时间为6个时间单元；另外从表2可知，各个外设的TBE就是工作模式的切换间，则（TBE）max=4，因此这些设置都能够满足本文所提到的三种策略的前提条件。
表1 任务组特征
|
任务
|
T1
|
T2
|
T3
|
T4
|
|
子任务
|
ST1，1
|
ST1，2
|
ST1，3
|
ST2，1
|
ST2，2
|
ST3，1
|
ST4，1
|
ST4，2
|
ST4，3
|
|
外设
|
d1，d4
|
d1，d3
|
d1，d2
|
d3
|
d2
|
d2，d3
|
d1
|
d1，d4
|
d1，d3
|
|
执行时间
|
7
|
7
|
6
|
10
|
7
|
18
|
14
|
6
|
13
|
表2 外设电气特性
|
外设
|
正常功耗
|
睡眠功耗
|
切换功耗
|
切换时间
|
|
d1
|
10
|
1
|
5
|
4
|
|
d2
|
7
|
1
|
4
|
2
|
|
d3
|
12
|
2
|
4
|
2
|
|
d4
|
10
|
1
|
6
|
1
|
4.2 实验结果
为了对EODSA策略的省电效应以及QoS进行评估，本文基于多组任务进行了实验。
EODSA策略与Timeout、ALT策略之间的平均功耗比较结果：该组实验的目的是将任务级的设备调度策略EODSA与设备级的DPM策略Timeout、ALT进行省电性能的比较。Timeout的固定超时时限设为5个时间单元，即每个外设在经过5个单元的空闲时段后将进入到睡眠状态。ALT的基本思想是基于树型结构对空闲时间做出判断，在该实验中判断序列的长度设为4，即基于最近的4个历史空闲时段对将来的空闲时段值进行预测[4]。该组实验基于这三种策略分别针对外设d1、d2进行了平均功耗Pave的比较，实验结果如图2中的（a）、（b）所示，横轴代表实验的次数TestNum，纵轴代表Pave。
图2 EODSA与TimeOut、ALT策略之间的Pave比较
从图2可以看出，对外设di而言（图a），EODSA具有比Timeout、ALT等DLPM策略更好的节能效果；但对d2而言（图b），EODSA策略却不具有优势，在多次实验过程中其对应的Pave比Timeout、ALT还要高。导致该现象的原因在于EODSA策略有比较严格的假设条件。从表2可以看出，T1、T4在整个过程都在使用d1，而T2、T3不使用d1，该情况完全满足EODSA策略的假设条件；而对d2来说，只在T1、T2的部分运行时间内被使用，与EODSA策略的假设条件相差较大。这也说明了对任务进行子任务划分的必要性。
5 总结
本文从任务级的角度出发，针对基于FIFO的系统提出了一种新颖的在线设备调度策略EODSA及其改进策略IEODSA，从而克服了传统DLPM策略所固有的缺陷[5]。实验结果表明，本文所提出的三种策略都具有稳定性；而且和DLPM策略相比，EODSA、IEODSA在满足相应假设和前提条件下都能够更为显著的降低外设乃至整个系统的平均功耗[6]。
参考文献
[1] Rong P，Pedram M. An Analytical Model for Predicting the Remaining Battery Capacity of Lithium-ion Batteries[C]. Proc. 2003 Design，Automation and Test in Europe Conf. and Exposition IEEE CS Press. 2003：1148-1149
[2] Chiasserini C F，Rao R R.Improving Energy Saving in Wireless Systems by Using Dynamic Power Management[J]. IEEE Transactions on Wireless Communications. 2003，2（5）：1090-1100
[3] Jinwoo Suh，Dong-In Kang，Crago S P.Dynamic Power Management of Heterogeneous Systems. International Symposium on Parallel and Distributed Processing. 2003：125-132
[4] Qinru Qiu，Qing Wu，Massoud Pedram. Dynamic Power Management in a Mobile Multimedia System with Guaranteed Quality-of-Service[C]. DAC. 2002
[5] 张智，曹毅．基于嵌入式操作系统ARMLinux的图像传输研究[J]．微计算机信息，2008，10-3：312-314
[6] 李舒亮，刘有珠．基于ARM的嵌入式Web远程控制系统设计[J]．微计算机信息，2008，10-3：132-133
收稿日期：12月1日 修改日期：2009年1月9日
作者简介：何可佳（1978－），男，湖南省益阳人，讲师，本科，主要研究方向：计算机网络安全、Linux系统应用。
|
