动态电源管理经典算法总结
written by： zengyi 2008-12-4
操作系统级动态电源管理的提出者是Mark Weiser，在其1994年发表的一篇名为《Scheduling for Reduced CPU Energy》的文章中首次提出节能和操作系统级的电源管理思想。在其后的一些年中Kinshuk Govil在操作系统级电源管理方面也做出了比较大的贡献，在其发表的名为《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》一文中对Mark Weiser提出的算法进行了改进，创造出了一些自己的方法。
在国内，对操作系统级动态电源管理的研究开始地比较迟；从阅读文章来看：科学院、中科大、国防大学、复旦大学等在这方面有着比较前沿的研究。相对于国外的研究来说，中国的研究似乎更注重于用繁杂成型算法来优化功耗：如采用隐马模型、蚁群算法等。
一、动态电压调节算法：
1、OPT(unbounded-delay perfect-future)：提出者mark weiser，文献《scheduling for reduced cpu energy》，主要思想：是使用整个踪迹数据(意思也就是说要知道将来的所有时间里cpu使用情况)，将运行时间延伸以填补所有的空闲时间周期。该算法能达到的最大可能节省通常被最小速率所限制。这个算法既不实际也不合乎逻辑。不实际是因为它需要任务在将来周期内的一些完美数据，同时它也假设空闲能被运行时间所填补。不合乎逻辑是因为在各个进程运行的过程中产生了大量的延迟，而没有很好地管理好实时进程和交互进程的响应时间，如用户击键或网络包来临了都可能会无限制地等待下去。
2、FUTUR(Ebounded-delay limited-future)：提出者mark weiser，文献《scheduling for reduced cpu energy》，主要思想：是OPT算法的一个改进，只不过它所指的将来缩短为了一个小的时间窗口，在那个时间窗口内优化能耗，这样的话将不会拖延任务的响应时间；同样，它也假设下一间隔的所有空闲时间可以被消除，除非达到了cpu的最小工作频率。而且当时间窗口达到400秒的时候，该算法跟OPT几乎是一样的效果。该算法也是不实际的，原因也是因为它使用了将来的信息；但它却是合理的，因为没有一个实时响应的延迟会超过一个时间窗口。(意思是说只要时间窗口定义恰当，还是可以满足一些实时响应的要求，至少不会出现无限制地延迟)。
3、PAST(bounded-delay limited-past)：提出者mark weiser，文献《scheduling for reduced cpu energy》, 是一个能实现的FUTURE版本。与FUTURE算法往前看一个固定窗口相反，该算法是往后看一个固定大小的时间窗口，同时假设下一时间窗口的工作量跟上一窗口是相像的。主要思想是根据前一个时间片上遗留的工作和处理器使用率来设置下一个时间片上处理器的频率和电压。将时间划分为固定长度的时间片，在每个时间片开始的时候，计算前一个时间片上处理器使用率，预测在下一个时间片上处理器会同样忙。算法使用处理器使用率的两个门限值来决定在下一个时间片上是增加、减少、还是保持当前的处理器频率。如果预测的使用率低于下门限值，就降低处理器频率，高于上门限值就增加处理器频率，否则保持处理器的频率不变。具体调节多少频率一般是与使用的处理器相关，处理器可用的频率并不是连续变化的，而是几个分离的频率点，通常的调节是每次增加或减少一挡频率。
4、AVGn：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想是与Past 算法类似，只是在预测下一个时间片上的处理器的使用率时有所不同。采用了指数平均数的方法，预测下一个时间片上的使用率是以前所有时间片上的使用率的加权平均，每个时间片上的权随着时间的向前推移而几何减小。即令n是指数平均的衰退因子， Ut 是时间片 t 上的实际的使用率，Wt 是该区间上预测的使用率，则AVGn 算法预测时间片 t 上的使用率为。衰退因子n 权衡了负载响应的及时性与稳定性，当n 越小时，系统响应负载的变化越快，但系统的频率/电压变化波动越大；n 越大，系统响应负载的变化就越慢。跟我自己看的有些出入。不知道是不是另一算法。
5、LongShort：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，该算法更注重于预测方面，它试图在本地行为以及一个相当长时期里的平均值之间寻找到一个黄金平均值。它有一个非负的实参，本地行为的权重将随着该参数的增加而增加。通过给本地行为指定一个最优可能权值，来发现该算法的一个最优预测值。按预测设置模型来说就是：
一、查找最近12个运行百分比，最近的三个构成短期预测数，余下的9个构成长期预测数。对接下来的运行百分比预测为一个加权平均值，在这个加权平均值中短期数据需乘以一个权重，也即是前面所提及的参数；
二、设置一个尽可能快的速率来完成预测工作。例如：假设权重值为4，最近12次的运行百分比是0、0.3、0.
5、
1、
1、
1、0.8、0.
5、0.3、0.
1、0、0；于是我们可以设置速率为：(0+0.3+0.5+1+1+1+0.8+0.5+0.3+4*(0.1+0+0))/(9+4*3)=0.276
6、Flat：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，该算法在预测方面比较薄弱，它只是简单地将速率平滑到全局的平均使用率上。该算法需要一个输入参数，而且必须是0-1之间的常数。算法分为两步：
一、预测一个常数级的运行百分比；
二、设置一个速率使其能足够快完成预测出的新的及遗留的任务。该思想希望将运行百分比保持的尽量平滑，不至于出现突变。由于速率总是设置成足够快来完成预测的新任务和遗留任务，所以所有任务的延迟都不会超过一个时间间隔。这一思想也被应用到其他算法中。
7、AGED_AVERAGES：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，与LONG_SHORT方法不一样，该算法采用了一种指数级的平滑方式，试图通过加了权重的平均值来预测下一个时间间隔的运行百分比。例如：假设间隔长度为0.01秒，权重值为2/3，先前的运行百分比是P(t),P(t-1)，P(t-2)，...，预测的新运行百分比是1/3*P(t)+2/9*P(t-1)+4/27*P(t-2)+...。注：权重值定义的注意点是应与间隔长度基本保持独立。
8、CYCLE：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，应该说以前的一些算法都比较的久经世故。然而在对运行百分比图的观察中，我们发现这些运行百分比似乎都是周期性出现的，这一规律是否可以被我们所利用呢？我们是否能找到一个这样的x，使得在x开始处的长度上与2x开始处的一个x长度上两者图形几乎一样呢？为此我们定义了一个变量error-measure，该变量的计算是这样的，对于两个一样长的跟踪数据，对应位相减后取绝对值再相加的平均值。看起来有点拗口，让我们来举一个例子：假设最近的8个数据是0-0.4-0.8-0.1-0.3-0.5-0.7-0.x取为4，于是我们可以将这八个数据分成两组，0-0.4-0.8-0.1和0.3-0.5-0.7-0，最后error-measure计算如下：(|0-0.3|+|0.4-0.5|+|0.8-0.7|+|0.1-0|)/4=0.15。由此我们可以很容易看出，error-measure的值越小，两者的相似度越高。于是我们可以通过具有最小error-measure值的区间预测下一个周期内的运行百分比。但如果算出来的error-measure都大于0.2，则将运行百分比预测为一个常数。(在有些地方，该算法也叫着自相似性，应该说有着一定的道理，不过由于用户的参与，使得随机性很大，有时根本就没什么规律)
9、PATTERN：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想是将先前的运行百分比转变成一种样式，例如我们可以定义字母表中A代表0~0.25的运行百分比，B代表0.25~0.5，C代表0.5~0.75，D代表0.75~1；于是假设我们有这样一个跟踪序列0-0.13-0.28-0.33-0.52-0.79，那么我们可以转变成这样的一个样式AABBCD。往后查看如果发现跟在该样式后面的是一个A的话，那么我们可以猜测下一间隔的运行百分比为0.125(A的中间值)。
10、Peak：提出者Kinshuk Govil，文献《Comparing Algorithms for Dynamic Speed Setting of a Low Power CPU》，主要思想算法预测当前的负载将伴随一个窄峰值，即预测一个上升的运行百分比将对称地下降，而下降的运行百分比将继续下降。当运行百分比为100%时，它将下降;当它为0%时，将保持不变。假设Pt-1和Pt分别为最近两个间隔的运行百分比，Pt+1为下一间隔的运行百分比。 该算法预测Pt+1的原则如下: (1) If Pt > Pt-1
then Pt+1 = max(P t-1，0.1)； (2) If Pt
then Pt+1=min{Pt, 0.1}； (3) If Pt = Pt-1
then if Pt = 1, Pt+1 = 0.4； otherwise, pt+1 = pt；
