基于智能电能表微内核动态优先级任务调度方法

侯慧娟,李梦溪,郭思维

(国网河南省电力公司营销服务中心,郑州 450052)

0 引 言

随着IR46智能电能表、智能物联电能表(新一代智能电能表)的快速发展[1],软件迭代更新、系统功能管理、维护等需求也随之受到了研发人员的广泛关注,其中运行可靠性和实时性成为了新一代智能电能表软件开发的重点[2-4]。嵌入式操作系统作为一种用途广泛的系统软件,提供任务调度和管理、内存管理、任务间同步与通信、时间管理等功能,具有执行效率高、实时性能优良和扩展性强等特点。因此,将其部署到智能物联电能表软件系统中,是新一代智能电能表迈向高性能、高稳定性、可扩展性和高可靠性的关键技术。

目前,实时嵌入式操作系统的种类繁多,但由于智能电能表RAM等资源的限制,使得所移植的嵌入式操作系统必须满足轻量级、可裁剪、可移植和高可靠性等特性。微内核作为嵌入式操作系统内核的精简版本,具有占用内存小、移植性强等特点[5],为智能物联电能表嵌入式系统开发提供了可能,并将为其优异的性能发挥强大的潜力。

在嵌入式操作系统中,任务调度是其中最为核心的功能[6]。根据任务调度方式的不同,通常可将嵌入式操作系统内核分为非抢占式和抢占式两种,因此对于任务调度而言,抢占式任务调度更加能够体现任务响应的实时性。例如μC/OS操作系统采用最高优先级作为任务调度方法,任务优先级越高,当处于就绪态时,其切换至运行态的可能性越大[7-8]。然而,针对任务集中优先级较低的任务,因其时常被高优先级抢占而得不到执行,文献[9]提出了一种任务补偿调度机制,使得在设定的时间内对较低优先级任务进行补偿调度。文献[10]首先将任务划分为实时任务、分时任务和后台任务,实时任务采用优先级最高执行调度,而分时任务采用时间片调度算法,后台任务则以中断响应为主,实现整个操作系统任务的调度。在上述嵌入式系统中,任务优先级通常属于静态,不具有动态变化特性,从而限制了任务调度的灵活性以及系统的进一步扩展。

针对任务优先级动态设置问题,国内外研究者分别提出了多种经典的任务调度算法,其中最早截止时间优先调度(eearliest deadline first,EDF)可以根据任务的截止时间排序执行任务调度[11-12],从而大幅提升处理器的利用率。然而当系统任务过载时,容易引发任务错失截止时间而影响后续其他任务的执行,为此文献[13]综合考虑任务截止时间、执行价值和消耗能耗三种因素确定任务优先级,并通过希尔排序算法对任务进行选择,从而降低任务错失率。文献[14]在EDF算法基础上,综合截止期和关键度两种特征参数,提出一种动态截止期-关键度调度算法,通过构建判断函数执行任务调度,从而降低任务错失率和保障重要任务的调度成功率。文献[15]针对混合任务调度问题,提出了一种静态周期性可抢占式混合任务调度策略,该策略问题同时支持中断级与任务级的任务切换,并采用EDF算法对被抢占的时间触发任务进行恢复,提高系统资源利用率,并最大限度保证任务实时性。然而,动态优先级调度方法只针对任务的时间特性,并没有考虑任务的重要程度,容易引起资源的竞争,引发优先级反转、死锁等隐患,一定程度上增加了任务调度算法设计的难度。此外,针对不同的应用,如何综合多种因素实现稳定可靠的任务调度,也成为了任务调度算法研究的热点[16-20]。

文中针对智能物联电能表实际应用,在其RAM等资源受限等情况下,通过引入微内核架构设计软件及相应任务,提出一种微内核动态优先级任务调度方法。首先,根据智能物联电能表功能需求,采用功能模块任务化设计,划分为周期性任务和事件触发任务,并引入最高优先级、最早截止时间调度以及补偿调度等方法,通过构建动态优先级分配方法,确保任务调度的实时性和可靠性。最后,通过仿真分析验证文中方法的有效性。

1 智能电能表任务设计

1.1 驱动层实现

随着新一代智能电能表中多芯的引入,微内核作为小型嵌入式操作系统的核心,已经成为了嵌入式系统开发的一个重要方向。图1给出了目前智能物联电能表硬件架构图,其包含了自身的电量计量模组,同时增加了扩展模组、管理模组等。此外,MCU、计量芯以及扩展模组等多芯的使用,使得智能电能表管理芯面临代码执行效率优化以及各模块运行的实时性跟进等问题。

图1 智能物联电能表框图

目前,整个电能表管理芯的功能框架主要包含了10种功能的开发,例如LCD显示、按键控制、继电器、存储器、通信以及计量等,具体如表1所示。显然,在底层软件开发过程中,不仅需要满足表计法制计量功能的要求,而且面对下行扩展功能模块的通信与交互同样要求具备实时响应特性。为此,微内核的引入,并将各个功能模块任务化,一方面可大大降低其编程的复杂度,同时也可利用任务调度算法提高各个功能模块的实时响应能力。

表1 智能电能表硬件驱动

1.2 应用层任务设计

由表1以及图1可知,整个智能物联电能表需要实现的功能主要包括:电能量计量、数据冻结、事件记录、显示、通信(蓝牙、串口交互)等功能。为了使得各功能模块具有并发处理能力,文中将各个功能模块与任务建立对应关系,具体如表2所示。

表2 智能物联电能表任务的构建

同时,利用嵌入式操作系统任务调度执行整个智能电能表软件系统,具体设计如下:

1)任务类型的设计。

根据表2可知,任务可划分为周期性任务和事件触发任务,其中任务1～任务6属于周期性任务;任务7～任务11为事件触发任务。考虑到在周期性任务中存在事件触发,文中将其事件触发修改为判断全局变量值来保证任务只执行周期性任务。例如任务6,在按钮中断响应中改变全局变量的值,而在该任务周期执行中,加入对这个全局变量的判断执行相应的功能;

2)任务调度算法的设计。

为了确保整个操作系统稳定、可靠的运行,在上述任务中,针对周期性任务,可采用最高优先级的方式进行调度;而通信部分采用的是事件触发机制,即可在通信接收中断函数中发放信号量等,使得等待信号量的各个通信接收处理任务能够获得CPU而执行。因此,相对于周期性任务而言,其要求任务调度具有一定的实时性。为了满足这个特性,可采用EDF等动态优先级任务调度算法;

3)任务之间的同步与通信的设计。

在嵌入式操作系统内核管理中,各个任务间不允许相互调用,需通过同步与通信机制来进行协调。例如在数据通信中,通常采用串口中断的方式实现数据的接收。因此,在中断函数中接收到一帧数据后,通过发放信号量的方式触发相应的任务,使得等待该信号量的任务能够执行,例如任务7和任务9。

为了清晰描述各个任务以及与中断之间关联特性,图2给出了整体软件系统框架。整个嵌入式系统的处理主要分为三大部分:周期性任务处理、中断响应处理以及事件触发任务处理,其中在中断响应中,负责协调周期性任务和事件触发任务。

图2 软件系统框架

2 任务调度算法

为了确保周期性任务和事件触发任务的实时性,文中采用抢占式嵌入式操作系统设计,并引入最高优先级调度以及最早截止时间优先调度算法。

2.1 最高优先级调度

最高优先级优先是一种高效的调度算法,它可以通过查表法快速查找优先级,具体如图3所示,定义一个OSEventGrp字节变量,其中从低位开始第i位表示数组OSEventTbl[i]中对应的那一行是否存在就绪任务;然后再根据OSEventTbl[i],从最低位开始查看每一位是否存在相对应的就绪任务。

图3 μC/OS II 最高优先级查找法

为了能够快速查找最高优先级任务,通常采用OSUnMapTbl[256]数组[7],记录一个字节变量所对应从低位到高位第一次出现为1的位置,此时最高优先级通过以下三步即可找到:

y=OSUnMapTbl[OSEventGrp]

(1)

x=OSUnMapTbl[OSEventTbl[y]]

(2)

prio=(y<<3)+x

(3)

当需要寻找次优先级时,可以将OSEventTbl[y]中最高优先级所在位赋0,继续寻找更低一级优先级,从而遍历所有就绪任务。

2.2 最早截止时间优先调度算法

最早截止时间优先(EDF)算法是一种经典的实时调度算法。在每一个新的就绪状态到来时,调度器都将从那些已就绪或者当前没有完全处理完毕的任务中根据最早截止时间排出新的执行次序,并且按照新任务的截止时间的先后决定是否调度该新任务。为了便于清晰说明,图4给出了最早截止时间优先调度的一个示例。

图4 最早截止时间优先调度

式中任务P1的周期为t=25,任务P2周期t=35。整个执行过程如下:

1)任务P1和P2处于就绪态。由于P1的截止时间最早,即t=50,因此它的初始化优先级要比任务P2高而开始执行,直至任务P1执行完成一个周期 (t=25),此时P2开始执行;

2)当P2执行完一个周期,此时任务P1就绪,并给定截止时间t=100,优先于其给定的任务2的截止时间,P1开始执行,直至任务P1结束(t=85),此时,任务P2开始运行;

3)在时刻t=100处,任务P1处于就绪态,由于其截止时间(t=150)要比任务P2的截止时间(t=160)要早,因此任务P2被任务P1抢占,当其完成后任务切换,任务P2恢复执行,直至任务P2完成。

3 改进的任务调度算法

通常,在嵌入式操作系统中,最高优先级调度属于固定优先级调度算法,而EDF算法则属于动态优先级调度算法,为了能够提高任务调度的实时性和可靠性,文中融合了最高优先级调度和最早时间截止调度方法。针对周期性任务,采用最高优先级调度,而对于事件触发任务,采用了最早截止时间调度机制,并通过优先级的换算,集中采用最高优先级查找,执行最高优先级任务。此外,为了避免出现因任务低优先级而得不到执行等问题,文中引入了任务补偿调度方法,使得整个系统能够稳定、可靠地运行。

3.1 动态优先级分配

在事件触发任务中,引入一个衡量优先级的度量值Pi,其包括任务价值Vi和截止时间Ci两个重要度参数,其计算如下:

Pi=ceil(kvVi+kcCi-0.5)

(4)

式中kv、kc分别表示任务价值和运行时间的权重,满足kv+kc=1;ceil(·)表示向上取整。

式(4)中,将任务价值Vi设置为用户初始化任务时设置的静态优先级,表示当任务优先级值越小,任务价值越大。而截止时间Ci与当前运行时刻t和任务截止运行时间有关。同样地,截止时间越短,则任务优先级越高。为了描述其优先级动态变化特性,Ci直接采用距离截止时间远近来度量,即:

Ci=Pmax×(Ti-t)/Ti

(5)

式中Ti表示任务i的截止时刻;Pmax为静态优先级最大值。当t接近Ti时,Ci值越小,式(4)计算得到的Pi越小,表示优先级越高。当t超过Ti时,此时引入补偿调度机制,确保当前任务能够获得执行。

进一步地,kv、kc这两个静态参数决定了任务的优先级。由于Vi在设计中采用静态优先级值,因此,式(4)中优先级值的变化主要由Ci决定,而系数kc则将控制优先级调节范围。显然,当kc=0时,此时得到的优先级即为用户设置的静态优先级;而当kc逐渐增大,任务优先级则逐步由最早截止时间优先级决定。因此,该权重参数需要根据实际应用具体设置。另外,需要注意的是,当计算得到的任务优先级存在相同情况,采用时间片轮转的方式进行调度。

3.2 补偿调度机制

随着系统中任务的执行,当高优先级任务处于就绪队列时其总能够得到执行,而低优先级任务则有可能因此得不到调度。为此,文中引入任务补偿调度方法。其基本思想是在任务中设置截止运行时间作为一个补偿调度周期,即任务在进入就绪态后就开始启动补偿计时,如果在设定的截止运行时间前任务被执行了,则重新补偿计时;如果在截止运行时间之后还未执行,则进入补偿队列,并启动任务补偿调度,以确保低优先级任务响应的实时性。

图5为整个补偿调度机制的流程图。当任务进入就绪队列后,通过与其内在的截止运行时间进行比较,当超过了截止运行时间,则修改该任务的截止时间为最先,并启动补偿调度时间计数器。在补偿调度过程中如果出现补偿调度时间片已经用完,但补偿调度任务还未执行完成时,中止该任务,并将其任务恢复初始截止运行时间并转入就绪态;如果任务在补偿调度时间内执行完成时,任务恢复初始截止运行时间并进入下一轮调度。

图5 补偿算法执行流程

另外,在任务补偿调度过程中,补偿调度时间的设置对于被中断的当前任务的正常运行是存在一定影响。通常设置补偿调度时间短,执行完一次任务可能需要被执行多次补偿调度,而任务补偿调度时间较长,可能会影响当前被中断的任务的实时响应。因此,这个补偿时间通常相对比较短,在实际应用中,需要用户根据实际需要来设置。

4 实验结果与分析

为了验证文中的任务调度方法,文中针对表2中的任务集,并根据智能物联电能表实际应用开发,给出了具体任务集及其参数,如表3所示。其中设置优先级最大值Pmax=15,周期性任务和事件触发任务优先级权重kv,kc均设置为0.5。为了不频繁发生调度,更改动态优先级的步长t设置为50 ms。此外,设置任务补偿调度时间为50 ms,对于相同优先级任务,时间片轮转设置为50 ms,且忽略在任务切换中MCU的消耗。

表3 智能物联电能表任务集及其参数

图6给出了周期性任务t1～t6按最高优先级调度的执行时序图,不难发现,在没有事件触发任务情况下,这些任务都能够得到有效执行。然而,当执行完这些周期任务时,在周期1 s内空闲时间为90 ms,这对于后续执行事件触发的任务而言,会影响任务调度的实时性,如图7所示,在事件触发下,任务t5和t6需要在下一个周期内获得MCU。

图6 任务执行过程时序图

图7 事件触发任务执行时序图

图7给出了文中方法在事件触发任务t7发生下任务运行的时序图,其中t=300 ms时刻任务t7就绪。由式(4)计算可得,当前任务动态优先级为10,因当前执行的任务t4优先级为8,高于任务t7优先级,故t4继续执行;当t=450 ms时,t4执行完成,此时t7优先级为8,高于任务t3优先级而开始执行;当执行到500 ms时,因任务t5和任务t6截止时间到,尽管当前任务1已经就绪,但是任务t5和任务t6会进入补偿调度队列,进而执行补偿调度。执行完成后,任务1因优先级高而开始执行。由于任务t7属于事件触发任务,因此其优先级是每隔50 ms动态变化的,当执行到t=650 ms时,此时任务t7的优先级为3,高于任务t1的优先级4,此时任务t7抢占任务t1而执行。相比于图7所示的任务调度效果,文中方法(见图8)在事件触发任务触发下,各个任务都能够在1 000 ms周期内都能获得运行。

图8 文中方法任务执行序图

为了能够更好地验证文中方法的先进性,采用了与最高优先级方法和最早截止事件算法进行了对比,其结果如图9和图10所示。从图中可以看出,在最高优先级调度过程中,由于事件任务触发,使得低优先级的任务5和任务6在其第一个周期内并没有得到调度运行。最早截止时间调度方法,由于任务集中截止时间存在相同,为此采用50 ms时间片轮转方法进行调度。从测试结果中可以看出,尽管最早截止时间能提升处理器的利用率,但是最早截止时间方法并没有将任务的紧急程度体现到优先级中,使得显示、指示灯等任务执行优先于比其重要度高的优先级。另外,由于截止时间设置的不合理,存在任务切换频繁问题,这在一定程度上会耗费MCU资源,影响执行效率。而文中在任务的优先级分配上,针对事件触发型任务,采用动态优先级和静态优先级相结合的方法,为事件任务响应的实时性提供了可行。其次,对低优先级任务调度,任务时间补偿机制也为任务的实时响应奠定了基础。

图9 最高优先级任务执行序图

图10 最早时间截止任务执行序图

5 结束语

文中针对智能物联电能表嵌入式操作系统开发,提出了一种微内核动态优先级任务调度方法。该方法根据电能表任务类别的不同,构建了一种基于周期性任务最高优先级和事件任务动态优先级调度策略以及动态优先级分配方法。同时,为了避免低优先级在截止运行时间范围内未获得调度,采用一种时间补偿任务调度方法,提升任务的实时响应能力。最后,通过案例仿真分析验证了文中方法的有效性。在下一步工作中,将针对新一代智能电能表的实际应用场景,进一步优化设计任务调度,尽可能降低任务调度的频繁性。同时,对于任务补偿调度时间进行测试,使得整个智能物联电能表能够具有高响应能力、高稳定性的任务调度性能,进而为新一代智能电能表实时任务处理应用奠定基础。