实时系统中混合任务集的动态电压调节算法

2 基于混合任务集的减慢因子DVS算法
　　在实时系统中可调度性是保证系统可靠的重要参数，对任务集进行可调度性分析是减慢因子算法的必要部分。在进行可调度性分析的过程中，本文把非周期性任务的服务器看作固定优先级的周期性任务，将服务器的周期Ts作为任务周期和周期性任务一起分析。假设在系统S中存在着n个周期性任务t1、t2、t3、K、tn和个非周期性任务a1、a2、a3、K、an，所有的非周期性任务受可延期服务器DS的调度。如果系统S运行于固定速度处理器上，混合任务集在单调速率可抢占的调度方案下调度，那么可以用周期性任务集的单调速率可抢占调度方案的响应时间分析方法对这个混合任务集进行可调度分析。
　　减慢因子即任务的运行频率和最高频率之间的比值。在系统运行期间，即使所有任务按照最坏情况执行时间（WCET）运行，大多数情况下处理器的利用率也远低于100%，任务集在某个任务时限前，系统处于空闲调度循环中。因此，对处理器的电压和工作频率进行减慢因子计算，使空闲时间间隔大大缩短甚至消失，这样就达到了降低能耗的目的。
　　在下面的减慢DVS算法中，当任何新的周期性任务或者服务器进入系统并且在调度器中登记后，将会执行Compute_Slowdown_Factors过程，进行整个系统的可调度性分析，并且为每一个任务计算出最低的工作频率，从而保证所有任务在其工作频率下运行仍旧是可调度的，不会影响整个系统的实时性需求。
　　下面给出计算静态减慢因子αs算法的伪代码(其中0<αs≤1)：
//Algorithm Compute_Slowdown_Factors
Inputs:
　　S//将要进行减慢因子计算的任务集，包括周期性任务和非周期性任务的服务器
Outputs:
　　Slowdown_Factors[]//任务集的静态减慢因子
{
　　Sm//计算出减慢因子后，将要超过时限的任务集，初始化为空集
　　Current_Scaling _Factor=1;
　　For S中的每一个任务i
　　　　Slowdown_Factor[i]=1;
　　While （S不为空集）{
　　　　F=Scale_WCET(S，Slowdown_Factor[]);//计算减慢因子F
　　　　重新设置Sm;
　　　　Current_Scaling_Facotr *=F;
　　　　For S中的每一个任务i {
　　　　　　If任务i!=服务器
　　　　　　　　Slowdown_Factor[i]=F;
　　　　}
　　　　重新设置集合S，让集合S中所有任务的优先级小于Sm中最低优先级任务的优先级;
　　}
}
　　上面的程序通过Scale_WCET过程计算一个减慢因子，使得给定任务集中存在的一个或者多个任务的最差响应时间刚好等于它们的时限（此时该任务集刚好可调度），这样的任务称为"临界任务"。Compute_Slowdown_Factors过程首先调用Scale_WCET过程计算初始任务集的同一减慢因子F；然后让优先级低于临界任务的任务集继续调用Scale_WCET过程计算出新的减慢因子。这是因为如果继续让作用于优先级高于临界任务的减慢因子F变小，则必然会导致至少有一个临界任务超过时限，破坏了系统的实时性；而让作用优先级低于临界任务的减慢因子F变小，则不会影响整个任务集的可调度性。这个过程将会反复执行，直到初始任务集中的最低优先级任务变成临界任务。总之，这个迭代过程为每一个任务计算出减慢因子，同时保证整个任务集是可以调度的。需要说明的是，对于服务器将不会应用静态减慢因子，因为如果增加了服务器的运行时间，则必然会造成受服务器调度的非周期性任务的平均响应时间的增加。

3 算法验证和仿真
　　本算法通过T1 OMAP1612的TCSCDMA无线终端平台来验证，对实时嵌入式操作系统Nucleus微内核进行功能上的扩充，主要是实现了可延期服务器(DS)和偶发服务器（SS）来对非周期性任务进行调度。同时，又整合了基于本算法的DVS模块和CPU功率检测模块。
　　本实验通过3种情况（没有采用DVS算法,以及基于混合任务集的减慢因子DVS算法在DS和SS中的分别应用）分别在服务器利用率为25%、35%、45%的情况下进行了时间为60 s的实验，得出各情况下能耗在不同服务器利用率下的关系，如图1所示。

图1 各种算法的能耗对比

　　图1结果表明，采用基于混合任务集的减慢因子DVS算法与没有采用DVS算法相比，能耗降低了大概19.3％~32%；同时也看到，服务器利用率越高，能耗越接近于没有采用DVS算法所产生的能耗。这是因为为了保证非周期性任务有很短的响应时间，基于混合任务集的减慢因子DVS算法在服务器上运行时，总是以最高频率运行，同时高服务器利用率意味着服务器会占用很大一部分CPU周期。因此，在这样的环境下，CPU很大的一部分时间都运行在最高频率上，导致服务器利用率越高， 越接近没有采用DVS算法的情况。