針對電力監控系統的改進頁面交換算法*

虢 韜，楊 洋，楊 恒，沈 平

(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)復雜度的計算模式，從而使整體監測系統的響應速度與實現性能再次提升.