针对电力监控系统的改进页面交换算法*

虢 韬，杨 洋，杨 恒，沈 平

(1.中国南方电网 贵州电网有限责任公司，贵阳 550005；2.贵州电力设计研究院 地理信息中心，贵阳 550005)

电力监控系统是集成计算机技术、嵌入式技术、远程通讯传输技术以及变配电信号采集和自动分析技术于一体的电力管理系统[1-3].尤其是微嵌入式技术的广泛使用，使得用于变配电终端监测的节点传感器、电能传输过程中检测装置以及各个中端通讯节点均成为了可以与主机系统进行通讯的智能设备.便捷实时的多层监测信息交互虽提高了系统整体的自动化水平，但却增加了系统的内存信息交换负担，高效稳定的虚拟内存信息读取和交换技术直接影响了电力监控系统的整体性能.

虚拟内存一般依靠2级以上页面映射单位，实现不同调入页面的信息交互管理.访问页面的频率、顺序以及数量是控制和设计的主要参数[4-5].与一般的计算机虚拟内存不同，适用于电力监控各个终端的虚拟内存所占的资源更少，可以调用的访问内存资源存在竞争关系，访问未映射内存的缺页中断，可能使得页面更新的错误率增高，操作耗时.适用于嵌入式电力管理系统的高效页面置换算法对于降低缺页率，提升系统整体稳定性至关重要.经典的页面交换算法包括：最佳页面置换算法(OPT)、最久未使用算法(LRU)、先入先出算法(FIFO)等[6-8].其中，计算代价最大的是最佳页面置换算法，其能够得到最低的缺页率，但算法的时间和空间复杂度均较高，对于实时小内存的嵌入式系统而言并不适用.先入先出算法的计算复杂度最低，实现也最为简单，但缺页率最高，且先入先出的页面交换方式对于每个页面的使用情况均假定为相同，这显然与实际应用，尤其是电力系统的节点监测特点存在差异[9-11].

相比而言，最久未使用算法成为一种更理想且能够有效平衡算法复杂度与计算可靠性的选择.本文在LRU算法的基础上，结合电力监测实际场景和电力系统微内存嵌入式系统的实际情况，提出了一种软硬件结合的改进最久未使用算法(advanced least recently used，ALRU)，实现现场电力监控数据、通信模块数据和系统上位组态模块实时监测数据的实时调入监控.

1 电力监测系统及页面交互特点

电力监控系统结合整体架构而言，可以分为系统管理层、网络通讯层及最底层等现场监控层[12-15].一般而言，现场监控层具有最多的智能监测终端，包括电能质量分析仪、多功能电力仪表以及交流电表等；网络通信层用于建立现场监控终端和系统管理层之间的联系，其主要是由一组或多组通讯服务器构成；从通讯层传递的信息，最后经过交换机进入监控主机.各功能组件参考示意图如图1所示.

图1 电力监控系统示意图

多层架构为页面交互和信息交互增加了难度.实时性与有效性均要求在进行信息调用虚拟内存资源时，一方面要提高速度，另一方面要降低错误率，以保障系统整体的运行稳定.这需要虚拟内存查询和分配必须同时考虑每个监测终端页面使用的基本频率以及实际进行页面交替时出现错误的容错能力.在实际改进LRU算法时，针对电力监控系统，需要将每个监测单元的页面使用频率作为一种先验信息引入到算法模型中.

2 最久未使用算法及改进

LRU算法是依据页面调入内存的实际使用情况来进行置换决策的，该算法的基本想法是选择当前一段时间内最久没有被使用过的页面，予以进行新页面的交换.算法本身在实现上并不复杂，可以采用给每个调入内存的页面进行计时，即增加时间标记位来实现；或者进行计数，即增加累计值标记位来实现.对于计时算法，固有页面的访问带来计时清零操作，需要进行替换的页面是内存所有页面中时间数值最大的.计数实现算法的操作原理和计时方法相同，只是因计数方法操作的是累加器，而无需获取时间.在计算上不是浮点模式，因而对于淘汰缓存以及改善算法性能更优.本文采用的是基于计数法实现的LRU算法，对于一个设定为具有4个物理存储空间的调用分配页面置换示意图如图2所示.其中，调用的页面访问次序标记调整为对应的电能质量监测装置A～G，仅作为示意.一个实际监测得到的页面序列为：A，B，C，D，B，A，E，F，B，A，B，C，G，F，C，B，A，B，C，F.

图2 电力监测页面置换示意图

统计需要访问页面不在内存中的次数占总访问次数的比例，便能得到其缺页率，图2中的缺页率为50%.从上述分析可以看出，实际出现的页面频率以及次序均直接影响了缺页率.而在系统物理可用存储不变的情况下，提高效能的关键就在于对所出现页面的频率有更加准确的先验知识，即能够分析出该页面是否是常用页面.若其属于常用页面，便让其被更换的可能性再降低.换言之，对于LRU算法的改进，在于不是让其简单计数，而是能够使其了解当前时刻何种页面的存在时间更久，还包括引入学习历史数据，增加一个先验知识，结合概率来重新确定该页面是否需要被置换.

事实上，每个需要进行页面交换的智能终端i是否需要进行页面交换均可以看作是一个事件，其发生的频率具有先验的分布p(θ)，每个加载进入的新页面Xi均是修正整个页面分布的观测结果，从而得到实际的后验概率分布p(Xi|θ).将得到的后验概率分布p(Xi|θ)作为一个参数引入，来决定是否需要进行页面置换.当计算结果大于设定的阈值时，调用置换算法，交换当前的页面，实现的数学模型为

式中：p0为计算得到的每个引入新页面的后验概率；q0为用LRU算法计算得到的是否进行置换的累计标记位，数值为1或0；T为用于算法调整的阈值标记位.

本算法的改进方式是通过对历史得到的页面交换数据进行概率统计，在算法具体执行过程中，需要将系统运行过程前期得到的交互页面进行计数和统计，得到不同页面使用的概率分布模型.这是一个统计学习的过程，统计得到的概率分析作为一个先验知识，即前文的先验分布p(θ).

在后续进行页面交换算法时，LRU需要将先验概率分布和累计标记位结合来确定是否进行交换，其交换的判定需要比较阈值，阈值可以由实际测试得到.电力系统从加载到稳定运行的过程中，加载阶段由于需要调用不同的控制单元以及监测终端，系统的页面种类多，统计分布一般采用均匀概率密度函数作为先验分布函数，其阈值采用页面种类个数的倒数；随着系统逐步趋于稳定，采用正态分布函数进行调整替换.

3 结果与分析讨论

改进的LRU算法可以缩短访问数据的更新处理过程，减少跨页访问更新数据的同时改善了硬件操作频度，避免了访问计数器溢出的问题.统计概率更新和判断可以通过简单的比较和赋值完成，计算复杂度与原本的LRU算法基本相同.

本文使用改进的LRU算法与实际常用的改进型Clock算法进行实测对比.实际搭建一个小型电力监控系统来采集电能质量信号图像以及无功补偿异常指示页面.文中设计了4个日常使用场景作为测试对比点，具体包括：

1)系统加载阶段.从各个具体实际监测节点上电到完成系统整体初始化，这一阶段的页面交互最为频繁，需要顺次接入所有的待测试节点.

2)加载完成阶段.系统启动进入主界面，此时系统的整体运行负荷最低，实际上各个监测节点均没有进行数据的返回，页面置换次数最少.

3)监测运行阶段.挑选部分或全部的监测节点进行实时数据监查，可以是大范围顺序执行，也可以是由触发报警引起的临时调用查看，页面交换没有明显的规律，受工作量的影响较大.

4)监测平稳阶段.系统已经正常运行一段时间，各种常见的故障以及问题也均发生和统计了.系统依据前期累计的各种时间概率分布进行页面交换的参数控制，页面交换次数稳定.

表1为改进LRU算法和改进Clock算法的测试页面交换次数对比，每个场景测量了6次.本文对比的是改进效能，默认页面交换一般并不存在错误，不考虑因为系统故障或者偶然噪声产生的页面加载错误问题.

表1 页面交换次数对比

相比于改进Clock算法，本文提出的改进LRU算法对于降低平均页面交换时间有较大改进，具体对比如表2所示.表2中的效能提升比较来自同一场景，结果为改进LRU算法相较改进Clock算法页面交互次数均值降低的百分比.采用改进LRU算法的整体缺页率比改进Clock算法降低了约20%，能够实现电力系统中多个终端间的快速信息交换.

表2 算法效能对比

图3给出了测试系统进入监测平稳期的页面交换性能.随着连续运行时间的增加，系统整体进行页面交换的时间曲线逐步缩短，并趋于平缓，系统整体运行性能得到改善.由表1、2可以看出改进算法性能的提升，但系统稳定运行的对比需要建立在以小时为单位的运行测试环境中，所以操作时需要具体考虑改进Clock算法进行验证的测试成本.

从上述分析可以看出，通过概率分布修正的页面置换算法在电力监控系统场景中使用时，其优势主要集中体现在监测系统平稳运行的过程中.这主要是因为当采集了一段时间的各类样本后，系统对于每个页面的发生和出现均有了比较准确的后验概率分布信息，将该信息融合进入LRU算法的决策中时，可以有效减少发生页面交换的频率，提高系统的稳定性.

图3 平稳运行期性能

4 结 论

本文提出了一种用于电力监测系统的页面置换算法，其通过改进LRU算法、引入后验事件的概率分布并结合阈值判断实现对系统监测信息的快速稳定交换.算法主要改进在于提升整体的运行性能，若可以采用多位寄存器作为辅助硬件结构，便能将整体算法的实现转变为O(1)复杂度的计算模式，从而使整体监测系统的响应速度与实现性能再次提升.