針對電力監(jiān)控系統(tǒng)的改進(jìn)頁面交換算法*

虢 韜，楊 洋，楊 恒，沈 平

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

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

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

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

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

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

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

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

2 最久未使用算法及改進(jìn)

LRU算法是依據(jù)頁面調(diào)入內(nèi)存的實(shí)際使用情況來進(jìn)行置換決策的，該算法的基本想法是選擇當(dāng)前一段時(shí)間內(nèi)最久沒有被使用過的頁面，予以進(jìn)行新頁面的交換.算法本身在實(shí)現(xiàn)上并不復(fù)雜，可以采用給每個(gè)調(diào)入內(nèi)存的頁面進(jìn)行計(jì)時(shí)，即增加時(shí)間標(biāo)記位來實(shí)現(xiàn)；或者進(jìn)行計(jì)數(shù)，即增加累計(jì)值標(biāo)記位來實(shí)現(xiàn).對于計(jì)時(shí)算法，固有頁面的訪問帶來計(jì)時(shí)清零操作，需要進(jìn)行替換的頁面是內(nèi)存所有頁面中時(shí)間數(shù)值最大的.計(jì)數(shù)實(shí)現(xiàn)算法的操作原理和計(jì)時(shí)方法相同，只是因計(jì)數(shù)方法操作的是累加器，而無需獲取時(shí)間.在計(jì)算上不是浮點(diǎn)模式，因而對于淘汰緩存以及改善算法性能更優(yōu).本文采用的是基于計(jì)數(shù)法實(shí)現(xiàn)的LRU算法，對于一個(gè)設(shè)定為具有4個(gè)物理存儲(chǔ)空間的調(diào)用分配頁面置換示意圖如圖2所示.其中，調(diào)用的頁面訪問次序標(biāo)記調(diào)整為對應(yīng)的電能質(zhì)量監(jiān)測裝置A～G，僅作為示意.一個(gè)實(shí)際監(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)計(jì)需要訪問頁面不在內(nèi)存中的次數(shù)占總訪問次數(shù)的比例，便能得到其缺頁率，圖2中的缺頁率為50%.從上述分析可以看出，實(shí)際出現(xiàn)的頁面頻率以及次序均直接影響了缺頁率.而在系統(tǒng)物理可用存儲(chǔ)不變的情況下，提高效能的關(guān)鍵就在于對所出現(xiàn)頁面的頻率有更加準(zhǔn)確的先驗(yàn)知識(shí)，即能夠分析出該頁面是否是常用頁面.若其屬于常用頁面，便讓其被更換的可能性再降低.換言之，對于LRU算法的改進(jìn)，在于不是讓其簡單計(jì)數(shù)，而是能夠使其了解當(dāng)前時(shí)刻何種頁面的存在時(shí)間更久，還包括引入學(xué)習(xí)歷史數(shù)據(jù)，增加一個(gè)先驗(yàn)知識(shí)，結(jié)合概率來重新確定該頁面是否需要被置換.

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

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

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

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

3 結(jié)果與分析討論

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

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

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

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

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

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

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

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

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

表2 算法效能對比

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

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

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

4 結(jié) 論

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