|
1 內存壓縮技術(shù)介紹 為節省存儲空間或傳輸帶寬，人們已經(jīng)在計算機系統中廣泛地使用了數據壓縮技術(shù)。在磁介質(zhì)存儲數據或網(wǎng)絡(luò )傳輸數據時(shí)，人們使用基于硬件或軟件的各種壓縮技術(shù)。當壓縮技術(shù)在各個(gè)領(lǐng)域都很流行時(shí)，內存壓縮技術(shù)卻由于其復雜性而一直未得到廣泛使用。近年來(lái)，由于在并行壓縮一解壓算法以及在硅密度及速度方面取得的進(jìn)展，使得內存壓縮技術(shù)變得可行。 內存壓縮技術(shù)的主要思想是將數據按照一定的算法壓縮后存入壓縮內存中，系統從壓縮內存中找到壓縮過(guò)的數據，將其解壓后即可以供系統使用。這樣既可以增加實(shí)際可用的內存空間，又可以減少頁(yè)面置換所帶來(lái)的開(kāi)銷(xiāo)，從而以較小的成本提高系統的整體性能。 內存壓縮機制是在系統的存儲層次中邏輯地加入一層——壓縮內存層。系統在該層中以壓縮的格式保存物理頁(yè)面，當頁(yè)面再次被系統引用時(shí)，解壓該壓縮頁(yè)后，即可使用。我們將管理這一壓縮內存層的相關(guān)硬件及軟件的集合統稱(chēng)為內存壓縮系統。內存壓縮系統對于CPU、 I/O設備、設備驅動(dòng)以及應用軟件來(lái)說(shuō)是透明的，但是操作系統必須具有管理內存大小變化以及壓縮比率變化的功能。 對于大多數的操作系統而言，要實(shí)現內存壓縮，大部分體系結構都不需要改動(dòng)。在標準的操作系統中，內存都是通過(guò)固定數目的物理頁(yè)框（page frame）來(lái)描述的，由操作系統的VMM來(lái)管理。要支持內存壓縮，OS要管理的實(shí)際內存大小和頁(yè)框數目是基于內存的壓縮比率來(lái)確定的。這里的實(shí)現內存是指操作系統可的內存大小，它與物理內存的關(guān)系如下：假設PM是物理內存，RM（t）是系統在t時(shí)刻的實(shí)際內存，而CR（t）是壓縮比率，在給定時(shí)刻t可支持的最大實(shí)際內存為RM（t）=CR1（t）×PM。然而，由于應用程序的數據壓縮率是不依賴(lài)于OS而動(dòng)態(tài)變化的，未壓縮的數據可能會(huì )耗盡物理內存，因此當物理內存接近耗盡時(shí)，操作系統必須采取行動(dòng)來(lái)解決這個(gè)問(wèn)題。 2 內存壓縮系統的硬件模型 目前由于內存壓縮的思想越來(lái)越引起人們的注意市場(chǎng)上也出現了一些基于軟件的內存壓縮器。這些內存壓縮器主要是通過(guò)軟件對數據進(jìn)行壓縮，但由于訪(fǎng)問(wèn)壓縮數據帶來(lái)的延遲，它在系統性能方面改進(jìn)并不明顯，有些甚至降低了系統性能。本節介紹一種基于硬件的內存壓縮系統模型。 圖1是一個(gè)典型的內存壓縮系統的硬件模型，包括了壓縮內存、L3高速緩沖、壓縮內存控制器等硬件部分。 
其中壓縮內存（133MHz SDRAM）包含了壓縮數據。L3高速緩沖是一個(gè)共享的、32MB、4路組相聯(lián)、可回寫(xiě)的高速緩沖，每行大小為1KB，由兩倍數據率（DDR）SDRAM 制定。L3高速緩沖包含了未壓縮的緩沖行，由于大部分的訪(fǎng)問(wèn)都可以在L3高速緩沖中命中，因此它隱藏了訪(fǎng)問(wèn)壓縮主存引起的延遲。L3高速緩沖對于存儲分級體系中的上層而言就是主存，它的操作對于其它硬件，包括處理器和I/O來(lái)說(shuō)都是透明的。壓縮內存控制器是整個(gè)內存壓縮系統的控制中心，它負責數據的壓縮 /解壓，監控物理內存的使用情況以及實(shí)際地址到物理地址的尋址過(guò)程。 數據壓縮過(guò)程是這樣的：壓縮內存控制將1KB的高速緩沖行壓縮后寫(xiě)入壓縮內存中，然后將它們從壓縮內存中讀出后解壓。其壓縮算法就是Lempel-Ziv算法，我們會(huì )在下一部分介紹這個(gè)算法。壓縮機制將壓縮的數據塊以不同的長(cháng)度格式存放到內存中。壓縮內存的存儲單元是一個(gè)256字節的區域。按照壓縮比率不同，一個(gè)1KB的內存塊（正好是L3每行的大�。┛梢哉紦�0～4個(gè)壓縮區域。 壓縮內存控制器必須根據長(cháng)度格式的不同將系統總線(xiàn)上的實(shí)際地址翻譯成物理內存的中的物理地址。實(shí)際地址是出現在處理器外部總線(xiàn)上常規地址。篁 址用來(lái)錄十壓縮內存的256字節區域。實(shí)際地址空間存在于L1/L2/L3高速緩沖中，用于立即訪(fǎng)問(wèn)。而其余的內存內容部分以壓縮形式存在于物理內存中。內存控制器通過(guò)查詢(xún)壓縮翻譯表（CTT）執行從實(shí)際地址到物理地址的翻譯，這個(gè)表被保留在物理內存的某個(gè)位置。圖2是CTT表的格式及內存控制器的尋址模式。
每個(gè)1KB內存塊的實(shí)際地址映射到CTT的一項，而 CTT每項共16字節，包括四個(gè)物理區域地址，每個(gè)地址指向物理內存聽(tīng)一個(gè)256字節區域。對于少于120位的塊，如一個(gè)全為零的塊，則使用一種特殊的 CTT格式，稱(chēng)為通用行格式。在這種格式中，壓縮數據全部存放在CTT項中，代替了四個(gè)地址指針。因此，一個(gè)1KB的通用塊僅占用物理內存中的16字節，其壓縮比率達到64：1。 壓縮內存控制器中有一系列的寄存器用于監控物理內存使用。Sectors Used Register(SUR)向操作系統報告壓縮內存的使用情況。The Sectors Used Threshold Registers,SUTHR和SUTLR，用于設置內存耗盡情況的中斷入口點(diǎn)。SUTLR寄存器是PCI中斷電路INTA的入口，而SUTHR寄存器是NMI中斷的入口。當SUR超過(guò)了SUTLR的值，內存控制器產(chǎn)生一個(gè)中斷，則操作系統采取措施來(lái)阻止內存消耗。 在實(shí)際地址到物理地址的轉換中，一個(gè)有用的方法是快速頁(yè)操作。它允許控制器僅修改CTT項的四個(gè)指針，從而將4KB的頁(yè)面內容換出或清空�？焖夙�(yè)操作通過(guò)將與4KB頁(yè)面相關(guān)的CTT項全部修改通用行格式（即全為零），從而將這4KB頁(yè)面的內容全部清空。同樣，一對頁(yè)面可以通過(guò)交換它們相關(guān)的CTT項的區域指針來(lái)交換頁(yè)面內容。由于沒(méi)有大量的數據移動(dòng)發(fā)生，快速頁(yè)面操作速度相當快。 壓縮內存控制器的壓縮/解壓功能是基于LempelZiv算法來(lái)進(jìn)行的，因此下一節將簡(jiǎn)單介紹一下該算法的思想。 3 內存壓縮算法Lempel-Ziv 絕大多數的壓縮算法，包括用得特別流行的Lempel-Ziv壓縮算法家庭，都是基于對原子記錄（Token）字符串的完全重復檢測。這個(gè)算法雖然不是最好的算法，但是，Lempel-Ziv算法強調的是算法的簡(jiǎn)單與取得高壓縮率的速率，因此它還是在內存壓縮中得到了廣泛的應用。 Lemple-Ziv算法（簡(jiǎn)稱(chēng)LZ）是編碼時(shí)將一個(gè)位串分成詞組，然后將數據流描述成一系列的對。每個(gè)對組成一個(gè)新的詞組，它包含一個(gè)數字（前一個(gè)詞組的標識）和一個(gè)位（被附加到前一個(gè)詞組上）。這種編碼方式很龐大，可是一旦應用到適合的字符串，它就是相當有效率的編碼方式。下面舉例說(shuō)明這種算法是如何編碼的。 ++表示連接（010++1=0101），U=0010001101是未被壓縮的字符串。C是壓縮后的字符串。P（x）表示詞組數x。先看一下U=0010001101發(fā)現，它可以被寫(xiě)為U=0++010001101，因此得到P（1）=P(0)++0�，F在繼續將其寫(xiě)為U=0++02++0001101，可得到P(2)=P（1）++1�，F在我們已經(jīng)將P（2）描述為上一詞組和一個(gè)新的位的組合。下一步，U=0++01++00++01101，并得到P（3）=P（1）++0�，F在我們注意到，有U=0++01+00+011++01，而 P（4）=011=P(2)++1，最后得到P（5）=P(1)++1。運算的步驟如表1所列。 一旦創(chuàng )建了表1，就有了整個(gè)編碼的圖表。要創(chuàng )建Lempel-Ziv數據流，則依照公式創(chuàng )建對。如果公式是 P(x)=P(A)++B，則每個(gè)對為（A++B）。因此P（1）=P(0)++0變?yōu)椋?0++0），P（2）=P(1)++0變?yōu)椋?1++0），依此類(lèi)推，將所有這些對連接起來(lái)，就得到了最后的字符串，結果如表2所列。這樣，C就變成000011010101011，看來(lái)比U要長(cháng)得多。但這里由于U 的長(cháng)度短，因此未能看出優(yōu)勢，而且包含P（0）的公式都沒(méi)有壓縮，所以也引起了長(cháng)度增加。 Lempel-Ziv字符串的解碼是很簡(jiǎn)單的，就是抓住其中的對，對照表1進(jìn)行重構。 表 1 編碼過(guò)程
表2 如何創(chuàng )建編碼字符串
4 操作系統對內存壓縮的支持 在壓縮內存系統中，內存大小指的是實(shí)際內存大小，它比物理內存大。在引導時(shí)，BIOS向操作系統報告的內存大小就比實(shí)際安裝的物理內存要大。例如，硬件原型安裝的是512MB的SDRAM，但BIOS向操作系統報告的內存大小為1GB。當應用程序數據以2：1 或更高的比率壓縮時(shí)，實(shí)際內存的工作方式與一般操作系統的內存工作方式是相同的。但當應用程序以未壓縮數據來(lái)填充內存時(shí)（如一個(gè)zip文件不可能達到 2：1的壓縮比率），由于一般的OS只看到實(shí)際地址空間，因此不能意識到物理內存已經(jīng)耗盡。例如，一個(gè)操作系統的實(shí)際內存為1024MB，而牧師內存為 512MB。這時(shí)實(shí)際內存已經(jīng)分配了600MB，系統顯示還有424MB的空閑內存。但是由于已分配內存的壓縮率很低，此時(shí)物理內存的耗用已經(jīng)接近 512MB。如果再近一步地分配內存，那么系統就會(huì )因為物理內存的耗盡而崩潰，盡管它仍然顯示還有424MB的空閑內存。這種情況下，必須由操作系統提供對壓縮內存進(jìn)行管理的支持。 由于內存壓縮是一個(gè)比較新的概念，一般的情況作系統都沒(méi)有這樣的機制來(lái)區分實(shí)際地址和物理地址，也不能處理“物理內存耗盡”的情況。不過(guò)，只要對操作系統內核做一些小的改動(dòng)或者在操作系統之上增加一個(gè)設備驅動(dòng)程序，即可達到目的。 一般來(lái)說(shuō)，要從以下幾方面對壓縮內存進(jìn)行管理。 （1）監控物理內存使用情況 通過(guò)輪詢(xún)或中斷法，查看物理內存的使用情況，并在物理內存耗盡前給出警告。壓縮內存管理例程是通過(guò)壓縮內存控制器中的一些寄存器來(lái)實(shí)現對物理內存的監控。SUR報告物理內存的使用情況，SUTHR和SUTLR用于設置中斷臨界值。壓縮內存管理算法是基于物理內存使用的四種狀態(tài)，分別為steady、acquire、danger和 interrupt，其臨界值的關(guān)系是mc_th_acquire 我們可以使用輪詢(xún)和中斷相結合的方法進(jìn)行監控，并對物理內存使用的變化作出反應。通過(guò)時(shí)鐘中斷來(lái)驅動(dòng)輪例程，該例程每10ms讀取一次SUR的值，并將它與系統設定的臨界值比較。當系統處于steady狀態(tài)時(shí)，不用采取任何行動(dòng)；當使用超過(guò) mc_th_acquire，應該增加nr_rsrv_pages來(lái)限制內存分配，但這并未引起內存缺乏；當使用超過(guò)mc_th_danger，應該增加 nr_rsrv_pages到引起內存缺乏，并導致頁(yè)面分配器和置換進(jìn)程回收內存頁(yè)面，一旦進(jìn)入到該狀態(tài)，物理內存管理例程會(huì )喚醒置換進(jìn)程回收內存。 （2）回收內存以及清空空閑頁(yè)面內容以減少使用 以標準的Linux內核為例，操作系統中有兩具主要的變量來(lái)管理內存太少的情形。這兩個(gè)變量是 nr_free_pages和struct freepages。為了檢測內存是否已耗盡，在分配內存前要進(jìn)行檢查。 if(nr_free_pages } else {/*可以進(jìn)行分配*/ 在內存壓縮系統中，通過(guò)增加一個(gè)新變量nr_rsrv_pages來(lái)完成此功能。這樣就使最小空閑頁(yè)面數量變?yōu)椋篺reepages.min‘=freepages.min+nr_rsrv_pages。 通過(guò)動(dòng)態(tài)地調整nr_rsrv_pages變量，壓縮內存管理例程可以人為地造成內存缺乏的現象，從而引起置換進(jìn)程回收頁(yè)面，此時(shí)會(huì )將調用進(jìn)程暫時(shí)掛起�；厥諆却姘s減各種緩沖，并將進(jìn)程頁(yè)面置換到磁盤(pán)上。當頁(yè)面返回到空閑頁(yè)面池時(shí)，它們會(huì )被清零。我們可以使用前面提到的快速頁(yè)面操作來(lái)減少清空頁(yè)面操作所帶來(lái)的開(kāi)銷(xiāo)。 （3）阻塞CPU周期以減少物理內存使用率 當物理內存使用超過(guò)監界值mc_th_interrupt，控制器就中斷處理器，nr_rsrv_pages進(jìn)一步增加，然后 CPU blocker就開(kāi)始運行。我們在輪詢(xún)機制的基礎上還使用了中斷機制，因為中斷機制比輪詢(xún)機制更加快速。如果在10ms的間隔中，物理內存使用突然上升，硬件中斷會(huì )比輪詢(xún)例程更早檢測到這一情況。為了更加安全，我們使用CPUblocker來(lái)阻塞引起物理內存使用的進(jìn)程。CPU blocker是空閑線(xiàn)程，它們可以使CPU空忙。由于頁(yè)面被置換到磁盤(pán)是以機器速度運行的，而物理內存使用卻可以以?xún)却嬖L(fǎng)問(wèn)速度運行，速度從而得到增加。當牧師內存使用持續增加，以至換頁(yè)也無(wú)法緩解時(shí)，進(jìn)程需要被阻塞。我們就通過(guò)啟動(dòng)CPUblocker來(lái)阻塞CPU周期直到換頁(yè)機制能有效地降低物理內存使用。CPUblocker不會(huì )阻塞中斷，而且每40ms它就會(huì )讓出CPU以免其它進(jìn)程被餓死。 5 內存壓縮技術(shù)在嵌入式系統中的應用 嵌入式系統是一種特殊的計算機系統，它是一個(gè)更大的系統或設備的一部分。通常，一個(gè)嵌入式系統是駐留在單處理機底板上的，其應用程序存儲在ROM中。事實(shí)上，所有具有數字接口的設備——監視器、微波爐、VCRs、汽車(chē)等，都使用了嵌入式系統。一些嵌入式系統包含了操作系統，稱(chēng)為嵌入式操作系統。為了滿(mǎn)足嵌入式應用的特殊要求，嵌入式微處理器雖然在功能上和標準微處理器基本是一樣的，但和工業(yè)控制計算機相比，嵌入式微處理器具有體積小、重量輕、成本低、可靠性中，內存仍然是珍貴的資源，因此研究?jì)却鎵嚎s技術(shù)在嵌入式系統中的應用具有一定的價(jià)值。 內存壓縮的思想在一些嵌入式操作系統中，實(shí)際上已經(jīng)得到了體現。例如在VxWorks中，當操作系統下載到目標機上時(shí)，其中一種方式是將引導程序和VxWorks映像都存放在ROM中。為了將其解壓后再從ROM拷貝到RAM。這種基于軟件的壓縮方式，可以節省ROM空間，但其引導過(guò)程相對較慢。 以上的內存壓縮技術(shù)在ROM中得到了應用，但對于RAM來(lái)講，基于軟件內存壓縮技術(shù)，由于其訪(fǎng)問(wèn)壓縮數據可能造成的延遲和不確定性，會(huì )對嵌入式系統的實(shí)時(shí)性造成和。因此它與虛擬內存技術(shù)一樣，在嵌入式系統中未得到廣泛應用。 本文所介紹的內存壓縮系統是基于硬件的。在相同基準下，測試結果顯示出，該系統的運行速度比標準系統的運行速度快1.3倍。如果要實(shí)現相同大小的內存，采用內存壓縮系統的硬件費用比購買(mǎi)RAM的費用要低，而且內存越大，其節省的費用越多，可以達到一半的價(jià)錢(qián)。因此筆者認為在內存資源極其寶貴的嵌入式系統中，實(shí)現基于硬件的內存壓縮系統具有較大的價(jià)值。 結語(yǔ) 本文介紹的內存壓縮系統是基于專(zhuān)門(mén)的硬件支持，即L3高速緩沖和內存控制器。在目前大多數Pentium 以上架構的硬件平臺上，只需要對操作系統內核做一些小的屐，或者增加一個(gè)設備驅動(dòng)及服務(wù)程序，即可完成此項功能。由于嵌入式系統對實(shí)時(shí)性的要求，基于硬件的內存壓縮技術(shù)可以在增大可用內存的同時(shí)不影響系統的實(shí)時(shí)性，其硬件費用相對RAM的價(jià)格更低，具有一定的實(shí)用價(jià)值。 參考文獻 1. Hovis W Compression Architecture for System Memory Application 1998 2. Red Hat TUX Web Server 2.0 2001 3. Bulent Abali Hardware Compressed Main Memory:Operating system Support and Performance Evaluation 4. Mark Gooch Design and Performance of a Main Memory Hardware Data Compressor 作 者：電子科技大學(xué) 徐蓉 來(lái) 源：單片機與嵌入式系統應用2004（2） |
