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

嵌入式实时操作系统在目前的嵌入式应用中用得越来越广泛，尤其在功能复杂、系统庞大的应用中显得愈来愈重要。人们要求实时嵌入式产品能够提供更为强劲的计算能力，以满足无线通信、多媒体应用的要求，然而高性能的代价就是高能耗，因此延长实时嵌入式系统电池使用时间已经成为实时嵌入式系统设计普遍关注的问题。在实时嵌入式系统中，核心处理器的能耗占据整个能耗的相当大一部分。动态电压调节被看作是降低处理器能耗的关键技术，其原理是在系统运行时态通过动态改变处理器的电压和频率，降低系统中的无用能耗，从而提高能量的有效利用率[1]。

当前，基于任务的动态电压调节算法主要集中在对周期性任务集合的研究，其中只有很少一部分是对周期性任务和非周期性任务的混合任务集进行研究。另外，基于工作负荷的DVS算法尽管能从系统级上解决无用能耗问题，但却很少考虑到系统的实时性。

1 动态电压调节算法理论背景

1.1 动态电压调节算法的必要性

由于CMOS电路的能量消耗E与电路电压V的平方成正比，因此降低电压是降低线路能耗的最有效的方法之一。DVS算法的基本原理： 系统在运行时间内根据性能的不同要求而相应地执行降低或者提高电压和工作频率的操作，从而降低能耗。

传统的电源管理技术只是在空闲时间内降低功耗十分有效，而在运行时间内却无能为力。目前，一些操作系统内核对动态电压管理（DPM）的支持还是局限于不能调整核心电压，主要是通过调整CPU频率和支持开关外围设备的供电来实现。但是近年来，随着半导体技术的发展，在运行时态动态改变处理器的工作电压和/或时钟频率已经变成了现实。很多商用嵌入式处理支持动态电压调节DVS这一技术，比如TI公司的OMAP系列处理器、Intel公司的StrongARM处理器、Transmeta公司的Crusoe处理器，还有IBM公司的PowerPC 405LP处理器等。

1.2 实时操作系统与任务调度

在实时系统软件中，最基本的软件是实时操作系统。它是实时系统软件的基础，所有的实时应用软件都是在实时操作系统的支撑下运行的。与通用操作系统相比，实时操作系统有其特有的一些重要特征，包括规模较小、中断时间很短、进程切换很快、中断被屏蔽时间很短、能管理ms级或μs级的多个定时器。因此它能适应各种实时应用的需求，从快速的实时响应到慢速的实时响应，都能应付自如。

实时系统的实时性通过周期（period）和时限（deadline）来体现。周期是均匀重复性任务每两次调用开始的时间间隔。任务必须在某个时刻前完成操作，启动时刻与该时刻的时间间隔被称为“时限”。均匀重复性任务又称为“周期性任务（periodic task）”。周期性任务在一个周期内的一次调用可以看作是一个作业。通常，周期性任务的作业周期和时限是相等的。

实时操作系统的核心就是任务调度。它提供给系统一个决策机制，决定在某个瞬间时刻下，系统作业池中哪一个作业占用处理器。基于线程的任务间DVS算法就是以实时系统的任务调度为主要理论基础。

1.3 服务器

然而，现实的情况是实时系统中并非所有的任务都是非周期性的。对于两种任务的混合调度情况，在基于优先级的方案中，简单地使非周期性任务的优先级低于周期性的任务[2]。这样，非周期性任务作为后台活动运行；而在抢占式系统中，它就不能掠夺周期性任务的资源。尽管这是一个安全的方案，但是考虑到非周期性任务的时限，如果让它们只作为后台运行，往往会错过它们的时限。为了改善非周期性任务的这种状况，可利用服务器（server）来解决。在RM策略下，最广泛研究的是可延期服务器（Deferred Server，DS）和偶发服务器[3]（Sporadic Server，SS）。

在DS中，引进一个新的最高优先级任务，这个任务也就是服务器。它有一个周期Ts和一个容量（Budget）Es。在运行时态，当一个非周期性任务达到时，如果服务器有可用容量，就立即开始执行，直到任务完成或服务器容量耗尽;如果服务器没有可用容量，那么非周期进程会被挂起（或转换为后台优先级）。在DS模型中，服务器容量每Ts个单位被补充一次。

SS的操作不同于DS在于它的容量补充策略。在SS中，如果一个任务在t时刻到达，并要求使用容量e,那么服务器在时间t后的Ts个时间单位补充容量e。通常，SS能提供比DS更高的容量，但同时也增加了实现的开销。

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算法的情况。

4 结论

本文提出的针对静态空闲间隔的静态减慢因子算法属于脱机（offline）的DVS算法。该算法同时把占系统很大部分的非周期性任务一起进行分析，把非周期性任务的服务器当作周期性任务进行动态电压调节，从而解决了非周期性任务的功耗问题，具有很大的实际意义。在保证性能的同时，降低了系统中的无用能耗，提高了能量的有效利用率。随着研究的深入，还将深入到对联机（online）情况进行动态电压调节。

参考文献

[1] Pering T, Burd T, Brodersen R. Dynamic voltage scaling and the design of a lowpower microprocessor system[C]. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, 2001:251259.
[2] Hakan Aydin, Qi Yang. EnergyResponsiveness Tradeoffs for RealTime Systems with Mixed Workload[C].IEEE RealTime and Embedde Technology and Applications Symposium，7483，2004.
[3] Dongkun Shin, Jihong Kim. Dynamic voltage scaling of periodic and aperiodic tasks in prioritydriven systems[C]. Proceedings of the 2004 Conference on Asia South Pacific Design Automation: Electronic Design and Solution Fair 2004, 2004:653658.