虢 韜，楊 洋，楊 恒，沈 平

(1.中國南方電網(wǎng) 貴州電網(wǎng)有限責任公司，貴陽 550005；2.貴州電力設計研究院 地理信息中心，貴陽 550005)

電力監(jiān)控系統(tǒng)是集成計算機技術、嵌入式技術、遠程通訊傳輸技術以及變配電信號采集和自動分析技術于一體的電力管理系統(tǒng)[1-3].尤其是微嵌入式技術的廣泛使用，使得用于變配電終端監(jiān)測的節(jié)點傳感器、電能傳輸過程中檢測裝置以及各個中端通訊節(jié)點均成為了可以與主機系統(tǒng)進行通訊的智能設備.便捷實時的多層監(jiān)測信息交互雖提高了系統(tǒng)整體的自動化水平，但卻增加了系統(tǒng)的內存信息交換負擔，高效穩(wěn)定的虛擬內存信息讀取和交換技術直接影響了電力監(jiān)控系統(tǒng)的整體性能.

虛擬內存一般依靠2級以上頁面映射單位，實現(xiàn)不同調入頁面的信息交互管理.訪問頁面的頻率、順序以及數(shù)量是控制和設計的主要參數(shù)[4-5].與一般的計算機虛擬內存不同，適用于電力監(jiān)控各個終端的虛擬內存所占的資源更少，可以調用的訪問內存資源存在競爭關系，訪問未映射內存的缺頁中斷，可能使得頁面更新的錯誤率增高，操作耗時.適用于嵌入式電力管理系統(tǒng)的高效頁面置換算法對于降低缺頁率，提升系統(tǒng)整體穩(wěn)定性至關重要.經(jīng)典的頁面交換算法包括：最佳頁面置換算法(OPT)、最久未使用算法(LRU)、先入先出算法(FIFO)等[6-8].其中，計算代價最大的是最佳頁面置換算法，其能夠得到最低的缺頁率，但算法的時間和空間復雜度均較高，對于實時小內存的嵌入式系統(tǒng)而言并不適用.先入先出算法的計算復雜度最低，實現(xiàn)也最為簡單，但缺頁率最高，且先入先出的頁面交換方式對于每個頁面的使用情況均假定為相同，這顯然與實際應用，尤其是電力系統(tǒng)的節(jié)點監(jiān)測特點存在差異[9-11].

相比而言，最久未使用算法成為一種更理想且能夠有效平衡算法復雜度與計算可靠性的選擇.本文在LRU算法的基礎上，結合電力監(jiān)測實際場景和電力系統(tǒng)微內存嵌入式系統(tǒng)的實際情況，提出了一種軟硬件結合的改進最久未使用算法(advanced least recently used，ALRU)，實現(xiàn)現(xiàn)場電力監(jiān)控數(shù)據(jù)、通信模塊數(shù)據(jù)和系統(tǒng)上位組態(tài)模塊實時監(jiān)測數(shù)據(jù)的實時調入監(jiān)控.

1 電力監(jiān)測系統(tǒng)及頁面交互特點

電力監(jiān)控系統(tǒng)結合整體架構而言，可以分為系統(tǒng)管理層、網(wǎng)絡通訊層及最底層等現(xiàn)場監(jiān)控層[12-15].一般而言，現(xiàn)場監(jiān)控層具有最多的智能監(jiān)測終端，包括電能質量分析儀、多功能電力儀表以及交流電表等；網(wǎng)絡通信層用于建立現(xiàn)場監(jiān)控終端和系統(tǒng)管理層之間的聯(lián)系，其主要是由一組或多組通訊服務器構成；從通訊層傳遞的信息，最后經(jīng)過交換機進入監(jiān)控主機.各功能組件參考示意圖如圖1所示.

圖1 電力監(jiān)控系統(tǒng)示意圖

多層架構為頁面交互和信息交互增加了難度.實時性與有效性均要求在進行信息調用虛擬內存資源時，一方面要提高速度，另一方面要降低錯誤率，以保障系統(tǒng)整體的運行穩(wěn)定.這需要虛擬內存查詢和分配必須同時考慮每個監(jiān)測終端頁面使用的基本頻率以及實際進行頁面交替時出現(xiàn)錯誤的容錯能力.在實際改進LRU算法時，針對電力監(jiān)控系統(tǒng)，需要將每個監(jiān)測單元的頁面使用頻率作為一種先驗信息引入到算法模型中.

2 最久未使用算法及改進

LRU算法是依據(jù)頁面調入內存的實際使用情況來進行置換決策的，該算法的基本想法是選擇當前一段時間內最久沒有被使用過的頁面，予以進行新頁面的交換.算法本身在實現(xiàn)上并不復雜，可以采用給每個調入內存的頁面進行計時，即增加時間標記位來實現(xiàn)；或者進行計數(shù)，即增加累計值標記位來實現(xiàn).對于計時算法，固有頁面的訪問帶來計時清零操作，需要進行替換的頁面是內存所有頁面中時間數(shù)值最大的.計數(shù)實現(xiàn)算法的操作原理和計時方法相同，只是因計數(shù)方法操作的是累加器，而無需獲取時間.在計算上不是浮點模式，因而對于淘汰緩存以及改善算法性能更優(yōu).本文采用的是基于計數(shù)法實現(xiàn)的LRU算法，對于一個設定為具有4個物理存儲空間的調用分配頁面置換示意圖如圖2所示.其中，調用的頁面訪問次序標記調整為對應的電能質量監(jiān)測裝置A～G，僅作為示意.一個實際監(jiān)測得到的頁面序列為：A，B，C，D，B，A，E，F(xiàn)，B，A，B，C，G，F(xiàn)，C，B，A，B，C，F(xiàn).

圖2 電力監(jiān)測頁面置換示意圖

統(tǒng)計需要訪問頁面不在內存中的次數(shù)占總訪問次數(shù)的比例，便能得到其缺頁率，圖2中的缺頁率為50%.從上述分析可以看出，實際出現(xiàn)的頁面頻率以及次序均直接影響了缺頁率.而在系統(tǒng)物理可用存儲不變的情況下，提高效能的關鍵就在于對所出現(xiàn)頁面的頻率有更加準確的先驗知識，即能夠分析出該頁面是否是常用頁面.若其屬于常用頁面，便讓其被更換的可能性再降低.換言之，對于LRU算法的改進，在于不是讓其簡單計數(shù)，而是能夠使其了解當前時刻何種頁面的存在時間更久，還包括引入學習歷史數(shù)據(jù)，增加一個先驗知識，結合概率來重新確定該頁面是否需要被置換.

事實上，每個需要進行頁面交換的智能終端i是否需要進行頁面交換均可以看作是一個事件，其發(fā)生的頻率具有先驗的分布p(θ)，每個加載進入的新頁面Xi均是修正整個頁面分布的觀測結果，從而得到實際的后驗概率分布p(Xi|θ).將得到的后驗概率分布p(Xi|θ)作為一個參數(shù)引入，來決定是否需要進行頁面置換.當計算結果大于設定的閾值時，調用置換算法，交換當前的頁面，實現(xiàn)的數(shù)學模型為

式中：p0為計算得到的每個引入新頁面的后驗概率；q0為用LRU算法計算得到的是否進行置換的累計標記位，數(shù)值為1或0；T為用于算法調整的閾值標記位.

本算法的改進方式是通過對歷史得到的頁面交換數(shù)據(jù)進行概率統(tǒng)計，在算法具體執(zhí)行過程中，需要將系統(tǒng)運行過程前期得到的交互頁面進行計數(shù)和統(tǒng)計，得到不同頁面使用的概率分布模型.這是一個統(tǒng)計學習的過程，統(tǒng)計得到的概率分析作為一個先驗知識，即前文的先驗分布p(θ).

在后續(xù)進行頁面交換算法時，LRU需要將先驗概率分布和累計標記位結合來確定是否進行交換，其交換的判定需要比較閾值，閾值可以由實際測試得到.電力系統(tǒng)從加載到穩(wěn)定運行的過程中，加載階段由于需要調用不同的控制單元以及監(jiān)測終端，系統(tǒng)的頁面種類多，統(tǒng)計分布一般采用均勻概率密度函數(shù)作為先驗分布函數(shù)，其閾值采用頁面種類個數(shù)的倒數(shù)；隨著系統(tǒng)逐步趨于穩(wěn)定，采用正態(tài)分布函數(shù)進行調整替換.

3 結果與分析討論

改進的LRU算法可以縮短訪問數(shù)據(jù)的更新處理過程，減少跨頁訪問更新數(shù)據(jù)的同時改善了硬件操作頻度，避免了訪問計數(shù)器溢出的問題.統(tǒng)計概率更新和判斷可以通過簡單的比較和賦值完成，計算復雜度與原本的LRU算法基本相同.

本文使用改進的LRU算法與實際常用的改進型Clock算法進行實測對比.實際搭建一個小型電力監(jiān)控系統(tǒng)來采集電能質量信號圖像以及無功補償異常指示頁面.文中設計了4個日常使用場景作為測試對比點，具體包括：

1)系統(tǒng)加載階段.從各個具體實際監(jiān)測節(jié)點上電到完成系統(tǒng)整體初始化，這一階段的頁面交互最為頻繁，需要順次接入所有的待測試節(jié)點.

2)加載完成階段.系統(tǒng)啟動進入主界面，此時系統(tǒng)的整體運行負荷最低，實際上各個監(jiān)測節(jié)點均沒有進行數(shù)據(jù)的返回，頁面置換次數(shù)最少.

3)監(jiān)測運行階段.挑選部分或全部的監(jiān)測節(jié)點進行實時數(shù)據(jù)監(jiān)查，可以是大范圍順序執(zhí)行，也可以是由觸發(fā)報警引起的臨時調用查看，頁面交換沒有明顯的規(guī)律，受工作量的影響較大.

4)監(jiān)測平穩(wěn)階段.系統(tǒng)已經(jīng)正常運行一段時間，各種常見的故障以及問題也均發(fā)生和統(tǒng)計了.系統(tǒng)依據(jù)前期累計的各種時間概率分布進行頁面交換的參數(shù)控制，頁面交換次數(shù)穩(wěn)定.

表1為改進LRU算法和改進Clock算法的測試頁面交換次數(shù)對比，每個場景測量了6次.本文對比的是改進效能，默認頁面交換一般并不存在錯誤，不考慮因為系統(tǒng)故障或者偶然噪聲產(chǎn)生的頁面加載錯誤問題.

表1 頁面交換次數(shù)對比

相比于改進Clock算法，本文提出的改進LRU算法對于降低平均頁面交換時間有較大改進，具體對比如表2所示.表2中的效能提升比較來自同一場景，結果為改進LRU算法相較改進Clock算法頁面交互次數(shù)均值降低的百分比.采用改進LRU算法的整體缺頁率比改進Clock算法降低了約20%，能夠實現(xiàn)電力系統(tǒng)中多個終端間的快速信息交換.

表2 算法效能對比

圖3給出了測試系統(tǒng)進入監(jiān)測平穩(wěn)期的頁面交換性能.隨著連續(xù)運行時間的增加，系統(tǒng)整體進行頁面交換的時間曲線逐步縮短，并趨于平緩，系統(tǒng)整體運行性能得到改善.由表1、2可以看出改進算法性能的提升，但系統(tǒng)穩(wěn)定運行的對比需要建立在以小時為單位的運行測試環(huán)境中，所以操作時需要具體考慮改進Clock算法進行驗證的測試成本.

從上述分析可以看出，通過概率分布修正的頁面置換算法在電力監(jiān)控系統(tǒng)場景中使用時，其優(yōu)勢主要集中體現(xiàn)在監(jiān)測系統(tǒng)平穩(wěn)運行的過程中.這主要是因為當采集了一段時間的各類樣本后，系統(tǒng)對于每個頁面的發(fā)生和出現(xiàn)均有了比較準確的后驗概率分布信息，將該信息融合進入LRU算法的決策中時，可以有效減少發(fā)生頁面交換的頻率，提高系統(tǒng)的穩(wěn)定性.

圖3 平穩(wěn)運行期性能

4 結 論

本文提出了一種用于電力監(jiān)測系統(tǒng)的頁面置換算法，其通過改進LRU算法、引入后驗事件的概率分布并結合閾值判斷實現(xiàn)對系統(tǒng)監(jiān)測信息的快速穩(wěn)定交換.算法主要改進在于提升整體的運行性能，若可以采用多位寄存器作為輔助硬件結構，便能將整體算法的實現(xiàn)轉變?yōu)镺(1)復雜度的計算模式，從而使整體監(jiān)測系統(tǒng)的響應速度與實現(xiàn)性能再次提升.