一種避免頁遷移的混合內存頁管理策略

劉翠梅，楊 璇，賈剛勇，韓光潔

1(常州機電職業技術學院 信息工程學院，江蘇 常州 213164)2(河海大學 物聯網工程學院，江蘇 常州 213022)3(杭州電子科技大學 計算機學院，杭州 310018)

1 引 言

近年來，移動終端和云計算的快速發展都對內存容量的需求日益提高.以動態隨機存儲器為主的內存系統具有易失性和高能耗兩大缺點，于是對散熱系統提出了更高的要求.目前，內存系統的能耗問題已經成為限制移動終端和云計算發展的一大瓶頸[1].

然而，相變存儲器(Phase Change Memory，PCM)憑借其非易失性、能耗低、存儲密度大、字節可尋址等諸多優勢，為內存系統設計帶來了新的前景和契機.

1)字節尋址，可以保證相變存儲器可以按照隨機存儲器的字節訪問方式與處理器進行交互，不用改變內存系統的尋址方式；

2)非易失性，可以提供持久的數據存儲功能；

3)存儲密度大，可以提供遠超于動態隨機存儲器的存儲密度和更低的能耗，非常適合移動終端的體積小和云計算的大容量需求特征.

但是，相變存儲器也存在一些缺陷，主要體現在不能就地更新、讀寫不對稱和有限的壽命.相變存儲器寫前需要擦除，不能直接進行寫操作，而且寫操作的時間遠比讀操作的時間長.相變存儲器的讀延遲約為50n，擁有與動態隨機存儲器相媲美的讀取帶寬.但寫延遲比讀延遲大得多，一般達到200～300ns.相變存儲器元件經過多次的寫操作后，一般在108～109次[2]，其相變元件會失效.基于單一的相變存儲器構建內存系統目前還需解決寫開銷和壽命等問題，還尚未成熟.

基于相變存儲器的特征，目前有兩種主流的混合內存架構，動態隨機存儲器和相變存儲器處在同一層次，共同組成統一的內存系統.混合內存架構即利用了動態隨機存儲器的優勢也開發了相變存儲器的優點，從而滿足需求.

第一種混合內存架構是用動態隨機存儲器作為相變存儲器的緩存[8]，這種架構存在一些問題：

1)內存的大小由相變存儲器的容量決定，跟動態隨機存儲器的大小無關.也就是說動態隨機存儲器只能作為緩存.從而浪費了一些寶貴的存儲資源；

2)實現起來比較復雜.涉及數據一致性問題，內存系統需要保證動態隨機存儲器上的數據和相變存儲器上數據的一致性.這就增加了內存系統的實現復雜度.

3)增加了系統開銷.內存訪問過程需要先訪問動態隨機存儲器，如果動態隨機存儲器中能找到相應數據，那么內存訪問就結束了.但是，如果動態隨機存儲器中沒有找到相應的數據，需要再一次訪問相變存儲器，從而導致了內存平均訪問時間增加.

第二種混合內存架構是將相變存儲器和動態隨機存儲器作為同級存儲介質.這種架構能夠避免第一種架構存在的問題，是目前的研究熱點，本文的研究就是基于這種架構.針對這種內存架構，主要解決的問題就是數據存放.因為相變存儲器和動態隨機存儲器處于相同級別，需要挖掘兩種存儲介質的優點，即將讀頻繁的數據放在相變存儲器中，將寫頻繁的數據放在動態隨機存儲器中.目前主要通過動態遷移策略來完成這一目標.但是動態遷移存在幾個缺點：

1)開銷大.將頁從一種存儲介質遷移到另一種存儲介質中，其實就是內存中兩種存儲介質間的數據拷貝，需要花費大量的處理器時間；

2)影響系統的響應時間.如果被訪問的數據剛好處于遷移過程，那么訪問需要等待，延遲了訪問過程.

本文提出了一種避免頁遷移的混合內存頁管理策略(PMP)提高混合內存系統訪問效率.本文提出的避免頁遷移的混合內存頁管理策略在給數據分配物理頁框前，先通過模擬的方法分析每個虛擬頁的使用行為，將虛擬頁劃分成兩種類型，一種是讀頻繁頁，一種是寫頻繁頁.在給虛擬頁分配物理頁框時，根據虛擬頁的類型映射到相應的存儲介質中.讀頻繁頁映射到相變存儲器，寫頻繁頁映射到動態隨機存儲器.系統運行過程中不再進行頁遷移操作，避免因頁遷移而導致的系統開銷.實驗數據顯示，本文提出的避免頁遷移的混合內存頁管理策略能夠有效的提高混合內存系統的效率.

本文在第二部分著重介紹相關的工作和存在的問題，第三部分詳細闡述了本文的動機；第四部分給出了算法的流程，第五部分介紹了實驗驗證方法及實驗結果；最后，總結全文.

2 相關工作

目前基于相變存儲器和動態隨機存儲器的混合內存管理主要有兩種方法：一種是基于數據冷熱度進行內存分配，一種是基于頁的讀寫傾向進行內存分配.

一種比較典型的基于數據冷熱度分配物理頁框的算法是由Lee等人提出的混合內存置換算法CLOCK-DWF(CLOCK with dirty bits and write frequency)[9].該算法根據請求類型分配物理內存空間.為讀請求頁面分配相變存儲器，為寫請求頁面分配到動態隨機存儲器.當在相變存儲器上進行寫操作時，把相應的頁面遷移至動態隨機存儲器.若此時動態隨機存儲器已滿，替換動態隨機存儲器中的最近最久未使用的頁面，并將相變存儲器中頁遷移到該頁.這種算法將所有涉及寫操作的頁全部放在動態隨機存儲器中，當動態隨機存儲器空間不足時，會導致頻繁的替換，甚至抖動，降低性能.同時算法會增加大量從相變存儲器到動態隨機存儲器的遷移操作，也就是增加了大量的性能開銷，降低了系統性能.

一種比較典型的基于讀寫傾向分配物理頁框的算法是由Seok等人提出的LRU-WPAM算法[10,11].LRU-WPAM算法對每個頁面進行實時監控，記錄每個頁面的讀寫操作.根據頁面的歷史讀寫信息，基于一個權值的計算公式，通過這個權值確定頁面的讀寫傾向.并且為動態隨機存儲器和相變存儲器分別維護一個讀傾向鏈表和寫傾向鏈表.如果在動態隨機存儲器的讀傾向鏈表中一個頁面讀傾向性超過一定閾值時，則將該頁從動態隨機存儲器遷移到相變存儲器中.如果在相變存儲器的寫傾向鏈表中一個頁面寫傾向性超過一定閾值時，則將該頁從相變存儲器遷移到動態隨機存儲器中.這種算法會導致一些頁面在兩種存儲介質間來回反復遷移，增加大量的性能開銷，降低系統性能.

不同于上面兩種算法，MHR-LRU算法[12]維護了一個動態隨機存儲器的寫鏈表DWL，只有在寫命中時，鏈表才會發生改變，寫命中的頁面移動到鏈表的MRU端，這樣使得MRU端的頁面寫操作更頻繁，而LRU端頁面寫操作更少.當頁面在LRU鏈表的非LRU端或在DWL鏈表的LRU端，有寫請求到達，為了在動態隨機存儲器中為寫請求騰出空間，會把在DWL鏈表LRU端的頁面遷移至相變存儲器中.如果數據不在DWL鏈表中或同時在兩個鏈表的LRU端則不進行遷移而是直接進行置換.因為并不監控相變存儲器的寫操作，所以相變存儲器中寫頻繁的頁面會一直在相變存儲器中進行寫操作.降低了相變存儲器的壽命.

APP-LRU算法[13]額外維護了一個歷史元數據信息，記錄訪問過磁盤的物理頁的讀寫歷史，基于歷史元數據信息來預測頁面的讀寫趨勢，在分配物理頁框時將寫傾向頁面分配到動態隨機存儲器中.但是，這種算法存在幾個問題：

1)進程的運行是動態的，即使同一個進程的兩次運行其使用的物理內存也是不同的，所以記錄物理內存頁框來預測頁的讀寫傾向性是不準確的[15]；

2)該算法也采用了遷移，同樣增加了系統開銷，降低了系統性能[16].

以上的這些方法在進行混合內存頁管理時，數據采集都是通過監控物理頁面的讀寫，或是基于單次的讀寫請求直接分配頁面的存儲介質，之后再通過遷移來實現物理分配[17].然而這些依賴遷移的混合內存管理方式存在大量的來回遷移操作，這些遷移增加了大量的系統開銷，降低系統的性能.

3 動 機

3.1 評價模型

為了評價各算法的效果，本文提出了一個評價模型.首先，判斷頁面最適合位置的算法，因為相變存儲器元件的理論寫入次數一般是108次，運行時間按照連續運行時間計算，相變存儲器的最大運行時間和相變存儲器的寫入頻率成反比.相變存儲器的寫入頻率可以按照相變存儲器單位內存(頁)在單個進程的運行周期內被寫入次數來表示.而且可以獲得滿足預期運行時間的頁面被寫入次數的閾值.一個頁面被寫次數不超過該閾值時，該頁面可以被分配到相變存儲器中.本文使用Th表示讀寫比例的一個閾值，如果一個頁面讀寫比例大于Th時，將該頁面分配到相變存儲器.

算法1.頁面分配算法

輸入：

Th：讀寫閾值

Tpcm：相變存儲器預期運行時間

C：相變存儲器寫上限

T：進程運行時間

W：寫閾值

Wn：第n個頁的寫次數

Rn：第n個頁的讀次數

N：進程占用內存總頁數

輸出：

適合的存儲介質

算法：

Begin：

1：Tpcm= C*T/W;

2：W=Tpcm/(C*T);

3：if Wn>W

4： 分配DRAM；

5：else

6： if Rn/Wn >Th

7： 分配PCM；

8： else

9： 分配DRAM；

End

算法1給出了一種頁面分配算法用于判斷一個頁面最適合的存儲介質.根據這個算法，同時結合其他頁面分配算法的結果(不包括遷移)，可以對不同算法頁面錯誤的分配做出評價.進程運行過程中頁面遷移的總次數，以及被分配至相變存儲器中頁面的寫次數也分別作為評價指標之一.如果僅使用動態隨機存儲器而不使用相變存儲器時，相變存儲器中的寫次數和兩種存儲介質間的遷移操作都是最優的，但這種情景無法發揮混合內存的優勢，也無法發揮相變存儲器大容量和非易失性優點，無法解決目前動態隨機存儲器的瓶頸問題，所以動態隨機存儲器和相變存儲器的利用率也會作為評價指標之一.

3.2 現有算法的量化分析

現有對于混合內存架構的內存分配算法主要有以下幾個缺點：

1)增加大量的遷移，從而增加系統性能開銷；

2)增加不必要的寫操作，從而導致相變存儲器壽命縮短；

3)對動態隨機存儲器的大量需求，無法解決能耗問題.

3.2.1 遷移問題的分析

圖1給出了四種不同算法在讀取一個文件時的所產出的總遷移次數.這四種算法都涉及不同程度的遷移操作.LRU-WPAM算法需要4000多次的遷移操作，最少的APP-LRU算法，也需要100多次的遷移操作.這么多的遷移操作給系統帶來了巨大的性能開銷，嚴重的降低了系統的性能.

圖1 各算法遷移次數Fig.1 Migration times of algorithms

為了詳細分析各頁面在系統運行過程中的遷移情況，圖2給出了LRU-WPAM算法不同類型頁面的遷移情況.頁面遷移具有較強的聚集特征，大量遷移聚集在少量頁面，其中單個頁面的最大遷移次數3254，這部分頁面的讀操作和寫操作均十分頻繁，所以其頁面的權值波動很大，導致頁面頻繁的在兩種介質間遷移，造成該問題的原因是權值的計算具有局部性，受到局部訪存行為的影響，無法描述頁面在全局的訪存行為.

3.2.2 相變存儲器寫操作分析

圖3給出了4種不同算法在相變存儲器中進行寫操作的次數.雖然APP-LRU和MHR-LRU在遷移次數上相對較少，但是這兩種算法存在大量的相變存儲器寫操作.APP-LRU算法的主要問題在于，頁面遷移發生在頁面分配的過程中，歷史訪存元數據信息只有在頁面再次進入內存時為其分配合適的位置.合適位置和LRU-WPAM算法一樣，具有局部性.而且對于一個頻繁訪問的頁面，因為該頁面在LRU鏈表中始終處于MRU端，那么這個頁面被遷移的概率很小，即使這個頁面在相變存儲器中且進行了很多的寫操作，該算法也無法將頁面遷移至動態隨機存儲器，這就導致了相變存儲器執行了大量的寫操作.而MHR-LRU算法既有大量的遷移操作又有大量的相變存儲器寫操作.MHR-LRU算法產生大量寫操作的原因在于它注重于把動態隨機存儲器中寫較冷的頁面遷移至相變存儲器，但對于相變存儲器中頻繁進行寫操作的頁面并沒有進行相應的處理，這導致了該算法雖然遷移次數較少，但其并沒有有效的減少相變存儲器中的寫操作次數.在相變存儲器中進行大量的寫操作，對于相變存儲器元件壽命損耗巨大，降低系統的執行效率，帶來包括時間成本和設備成本的大量開銷.

圖2 LRU-WPAM算法遷移頁面百分比及對應的遷移次數Fig.2 Migration page ratio/migration times of LRU-WPAM algorithm

圖3 不同算法在相變存儲器中執行寫操作的次數Fig.3 PCM write times of different algorithms

3.2.3 動態隨機存儲器需求分析

圖4給出了四種算法在動態隨機存儲器上讀操作次數.本文使用動態隨機存儲器上讀操作次數來反映各種算法對動態隨機存儲器的需求大小.從圖1到圖3可以看出Clock-DWF算法遷移次數和相變存儲器中寫操作次數相對比較合理，但是圖4可以發現Clock-DWF算法對于動態隨機存儲器的需求最大，遠遠大于其他算法.對于動態隨機存儲器需求越大，功耗也就越大.

通過對現有算法的量化分析，特別針對遷移次數、相變存儲器上寫次數和動態隨機存儲器上讀次數，我們可以發現，現有的算法存在一個主要的問題，無法獲取頁面的讀寫行為，從而導致內存頁分配存在一定的錯誤.進而只能通過遷移來彌補.本文正是針對這個問題提出了一種新的解決方法.

圖4 四種算法在動態隨機存儲器上讀操作次數Fig.4 DRAM read times of four different algorithms

3.2.4 現有算法總結

現有算法存在的大量遷移操作主要原因在于：在進行數據劃分時統計物理頁框的訪問行為特征.然而物理頁框的訪問行為特征無法預先獲取，這是因為物理頁框是由操作系統的內存管理系統分配的.而且物理頁框的分配是實時動態的，無法重現的一種行為.

但是，虛擬頁的訪存行為特征相對就比較固定，可以更加準確的反映數據的讀寫傾向性，從而可以更加有效的用于數據劃分.而且虛擬頁的訪存行為可以通過模擬獲取.基于這個特征，本文提出了避免遷移的混合內存管理策略.

4 避免遷移的混合內存管理策略(PMP)

因為模擬器可以獲取進程每個虛擬頁的讀寫行為特征，基于這個讀寫行為特征可以指導操作系統混合物理內存頁管理，將讀頻繁頁分配到相變存儲器中，將寫頻繁頁分配到動態隨機存儲器中.并且獲得的虛擬頁讀寫行為特征比物理頁讀寫行為特征更能準確的反映頁行為特征.物理頁框是動態的，而虛擬頁是靜態的.所以本文提出的避免遷移的混合內存管理策略(PMP)是基于模擬器獲得的頁讀寫行為特征進行指導操作系統混合內存物理頁框分配，一旦給虛擬頁分配了物理頁框，在系統運行的過程中不進行遷移的操作.從而避免了遷移帶來的系統開銷.

圖5給出了避免遷移的混合內存管理策略(PMP)的整體架構圖.圖中主要包括4部分的內容.第1部分通過模擬器統計進程每個頁面的讀寫操作；第2部分在系統中構建一個進程級的頁面行為統計表，統計各進程所有頁面的讀寫；第3部結合系統混合內存配置以及系統進程行為，判斷各頁面是讀頻繁型還是寫頻繁型；第4部分根據頁面的讀/寫頻繁型，分配相應存儲介質.將讀頻繁型頁面分配到相變存儲器中，將寫頻繁型頁面分配到動態隨機存儲器中.

1)基于模擬器統計進程頁面的讀寫操作.避免遷移的混合內存管理策略(PMP)預先使用模擬器運行進程，模擬器中可以獲取進程各頁面的讀寫次數.因為涉及內存管理，PMP在統計進程頁面的讀寫次數時，采用的是進程的虛擬頁.如果基于物理頁框記錄讀寫次數準確度會受到影響.同一個虛擬頁面由于頁替換策略，導致映射到不同的物理頁框.所以采用虛擬頁面作為統計基礎能夠得到準確的結果.

圖5 避免遷移的混合內存管理策略(PMP)的整體架構圖Fig.5 Framework of PMP

2)構建進程級的頁面行為統計表.在系統中需要給每個進程分配一個獨立的數據結構，即進程的頁面行為統計表，如表1.在這個統計表中，進程每個頁面占用一個記錄，進程的頁面數決定了進程所對應頁面行為統計表的大小.在頁面行為統計表中主要記錄了每個頁面的讀操作次數以及寫操作次數.

表1 進程的頁面行為統計表Table 1 Page behavior of process

3)確定進程各頁面的讀/寫頻繁型.雖然通過各進程的頁面行為統計表可以獲得了進程各頁面的讀/寫次數，但是還是無法判斷各頁面的讀/寫頻繁型.頁面的讀/寫頻繁型還與混合物理內存的配置有關，即混合物理內存中相變存儲器占用多少物理內存空間，動態隨機存儲器占用多少物理內存空間.算法2給出了確定進程各頁面的讀/寫頻繁型的過程.

4)分配物理內存.根據頁面的讀/寫頻繁型，分配物理內存.如果是讀頻繁型，分配相變存儲器，如果是寫頻繁型，分配動態隨機存儲器.

算法2.確定頁面讀/寫頻繁型的算法

輸入：

Ri：頁面的讀次數

Wi：頁面的寫次數

PCM：相變存儲器的容量

DRAM：動態隨機存儲器的容量

輸出：

讀頻繁型/寫頻繁型

算法：

Begin：

1：T = Ri/Wi;

2：T1 = PCM/DRAM;

3：if T>T1

4： 讀頻繁型；

5：else

6： 寫頻繁型；

End

5 實驗結果

本文使用Multi2Sim模擬器對測試程序進行了仿真運行，來獲取不同進程頁面的讀寫行為.使用真實的訪存痕跡對不同的算法進行模擬.并按本文提出的避免遷移的混合內存頁管理策略對頁面進行劃分.

5.1 實驗配置和方法

為了實現進程頁行為特征分析，在默認的Multi2Sim模擬器上進行修改，增加進程頁面的行為統計表.本文采用的進程頁面大小為操作系統默認的4KB.基于大量的程序訪存行為的特征分析，用于評價多種不同的算法，并在其中挑出了三類有代表性的訪存應用作為測試程序，如表2所示.

表2 測試程序集Table 2 Benchmarks

因為實驗所測試程序是單個進程運行時產生的訪存行為，單個進程實際使用的頁面數量有限，所以我們設置了總的混合內存大小為400個物理頁框的大小，既1.6MB.其中相變存儲器占3/4，即300個頁框，而動態隨機存儲器占1/4，即100個頁框.FFT的測試程序用于驗證所需頁框小于系統配置的混合內存大小，但是大于系統配置的動態隨機存儲器大小.OCEAN測試程序用于驗證所需頁框大小略大于系統配置的混合內存大小.而OpenFile測試程序用于驗證所需頁框大小大于系統配置的混合內存大小.

5.2 實驗結果

圖6給出了FFT測試程序在不同算法下對比結果.圖6(a)給出了不同算法遷移次數的對比，圖6(b)給出了不同算法對相變存儲器的寫操作次數對比，圖6(c)給出了不同算法對動態隨機存取讀操作次數對比.算法在動態隨機存儲器讀操作次數主要用于反映算法對動態隨機存儲器的容量敏感度.

圖6 FFT測試程序在不同算法下的對比結果Fig.6 Comparisons of FFT test programs under different algorithms

圖7 OCEAN測試程序不同算法下的對比結果Fig.7 Comparisons of OCEAN test programs under different algorithms

從圖6中可以發現,LRU-WPAM算法所需遷移次數遠遠大于其他算法，而且該算法對相變存取的寫操作和對動態隨機存儲器的需求都比較大.MHR-LRU和APP-LRU兩個算法雖然跟本文提出的PMP算法一樣沒有遷移，但是這兩個算法產生大量的相變存儲器寫操作.CLOCK-DWF算法在運行FFT測試程序時跟本文提出的算法在性能比較接近，但是CLOCK-DWF需要少量的遷移，而PMP不需要任何遷移，所以PMP還是優于CLOCK-DWF.

圖7給出了OCEAN測試程序在不同算法下對比結果.當進程所需頁框大小略大于系統配置的混合內存大小時，PMP同樣呈現出很好的結果.

圖8給出了OPENFILE測試程序在不同算法下對比結果.針對進程所需頁框大小大于系統配置的混合內存大小時，PMP也能獲得很好的結果.

6 結束語

本文提出了一種避免頁遷移的混合內存頁管理策略(PMP)提高混合內存系統訪問效率.PMP主要包括四部分的內容.第一部分通過模擬器統計進程每個頁面的讀寫操作；第二部分在系統中構建一個進程級的頁面行為統計表，統計各進程所有頁面的讀寫；第三部結合系統混合內存配置以及系統進程行為，判斷各頁面是讀頻繁型還是寫頻繁型；第四部分根據頁面的讀/寫頻繁型，分配相應介質的物理內存頁.將讀頻繁型頁面分配到相變存儲器中，將寫頻繁型頁面分配到動態隨機存儲器中.實驗結果表明本文提出的PMP算法能夠高效的管理混合內存.