摘要：介紹內存壓縮技術和一個基于硬件的內存壓縮系統模型，探討內存壓縮技術在嵌入式系統中的應用；重點介紹內存壓縮系統的硬件要求及操作系統對內存壓縮機制的支持；簡單介紹內存壓縮中常用的算法lempel-ziv，并就內存壓縮技術在嵌入式系統中的應用問題作一些探討。 關鍵詞：嵌入式系統 內存壓縮 壓縮內存控制器 lempel-ziv算法 1 內存壓縮技術介紹 為節省存儲空間或傳輸帶寬，人們已經在計算機系統中廣泛地使用了數據壓縮技術。在磁介質存儲數據或網絡傳輸數據時，人們使用基于硬件或軟件的各種壓縮技術。當壓縮技術在各個領域都很流行時，內存壓縮技術卻由于其復雜性而一直未得到廣泛使用。近年來，由于在并行壓縮一解壓算法以及在硅密度及速度方面取得的進展，使得內存壓縮技術變得可行。 內存壓縮技術的主要思想是將數據按照一定的算法壓縮后存入壓縮內存中，系統從壓縮內存中找到壓縮過的數據，將其解壓后即可以供系統使用。這樣既可以增加實際可用的內存空間，又可以減少頁面置換所帶來的開銷，從而以較小的成本提高系統的整體性能。 內存壓縮機制是在系統的存儲層次中邏輯地加入一層——壓縮內存層。系統在該層中以壓縮的格式保存物理頁面，當頁面再次被系統引用時，解壓該壓縮頁后，即可使用。我們將管理這一壓縮內存層的相關硬件及軟件的集合統稱為內存壓縮系統。內存壓縮系統對于cpu、i/o設備、設備驅動以及應用軟件來說是透明的，但是操作系統必須具有管理內存大小變化以及壓縮比率變化的功能。 對于大多數的操作系統而言，要實現內存壓縮，大部分體系結構都不需要改動。在標準的操作系統中，內存都是通過固定數目的物理頁框（page frame）來描述的，由操作系統的vmm來管理。要支持內存壓縮，os要管理的實際內存大小和頁框數目是基于內存的壓縮比率來確定的。這里的實現內存是指操作系統可的內存大小，它與物理內存的關系如下：假設pm是物理內存，rm（t）是系統在t時刻的實際內存，而cr（t）是壓縮比率，在給定時刻t可支持的zui大實際內存為rm（t）=cr1（t）%26;#215;pm。然而，由于應用程序的數據壓縮率是不依賴于os而動態變化的，未壓縮的數據可能會耗盡物理內存，因此當物理內存接近耗盡時，操作系統必須采取行動來解決這個問題。 2 內存壓縮系統的硬件模型 目前由于內存壓縮的思想越來越引起人們的注意市場上也出現了一些基于軟件的內存壓縮器。這些內存壓縮器主要是通過軟件對數據進行壓縮，但由于訪問壓縮數據帶來的延遲，它在系統性能方面改進并不明顯，有些甚至降低了系統性能。本節介紹一種基于硬件的內存壓縮系統模型。 圖1是一個典型的內存壓縮系統的硬件模型，包括了壓縮內存、l3高速緩沖、壓縮內存控制器等硬件部分。 其中壓縮內存（133mhz sdram）包含了壓縮數據。l3高速緩沖是一個共享的、32mb、4路組相聯、可回寫的高速緩沖，每行大小為1kb，由兩倍數據率（ddr）sdram制定。l3高速緩沖包含了未壓縮的緩沖行，由于大部分的訪問都可以在l3高速緩沖中命中，因此它隱藏了訪問壓縮主存引起的延遲。l3高速緩沖對于存儲分級體系中的上層而言就是主存，它的操作對于其它硬件，包括處理器和i/o來說都是透明的。壓縮內存控制器是整個內存壓縮系統的控制中心，它負責數據的壓縮/解壓，監控物理內存的使用情況以及實際地址到物理地址的尋址過程。 數據壓縮過程是這樣的：壓縮內存控制將1kb的高速緩沖行壓縮后寫入壓縮內存中，然后將它們從壓縮內存中讀出后解壓。其壓縮算法就是lempel-ziv算法，我們會在下一部分介紹這個算法。壓縮機制將壓縮的數據塊以不同的長度格式存放到內存中。壓縮內存的存儲單元是一個256字節的區域。按照壓縮比率不同，一個1kb的內存塊（正好是l3每行的大小）可以占據0～4個壓縮區域。 壓縮內存控制器必須根據長度格式的不同將系統總線上的實際地址翻譯成物理內存的中的物理地址。實際地址是出現在處理器外部總線上常規地址。篁 址用來錄十壓縮內存的256字節區域。實際地址空間存在于l1/l2/l3高速緩沖中，用于立即訪問。而其余的內存內容部分以壓縮形式存在于物理內存中。內存控制器通過查詢壓縮翻譯表（ctt）執行從實際地址到物理地址的翻譯，這個表被保留在物理內存的某個位置。圖2是ctt表的格式及內存控制器的尋址模式。 每個1kb內存塊的實際地址映射到ctt的一項，而ctt每項共16字節，包括四個物理區域地址，每個地址指向物理內存聽一個256字節區域。對于少于120位的塊，如一個全為零的塊，則使用一種特殊的ctt格式，稱為通用行格式。在這種格式中，壓縮數據全部存放在ctt項中，代替了四個地址指針。因此，一個1kb的通用塊僅占用物理內存中的16字節，其壓縮比率達到64：1。 壓縮內存控制器中有一系列的寄存器用于監控物理內存使用。sectors used register(sur)向操作系統報告壓縮內存的使用情況。the sectors used threshold registers,suthr和sutlr，用于設置內存耗盡情況的中斷入口點。sutlr寄存器是pci中斷電路inta的入口，而suthr寄存器是nmi中斷的入口。當sur超過了sutlr的值，內存控制器產生一個中斷，則操作系統采取措施來阻止內存消耗。 在實際地址到物理地址的轉換中，一個有用的方法是快速頁操作。它允許控制器僅修改ctt項的四個指針，從而將4kb的頁面內容換出或清空。快速頁操作通過將與4kb頁面相關的ctt項全部修改通用行格式（即全為零），從而將這4kb頁面的內容全部清空。同樣，一對頁面可以通過交換它們相關的ctt項的區域指針來交換頁面內容。由于沒有大量的數據移動發生，快速頁面操作速度相當快。 壓縮內存控制器的壓縮/解壓功能是基于lempelziv算法來進行的，因此下一節將簡單介紹一下該算法的思想。 3 內存壓縮算法lempel-ziv 絕大多數的壓縮算法，包括用得特別流行的lempel-ziv壓縮算法家庭，都是基于對原子記錄（token）字符串的*重復檢測。這個算法雖然不是的算法，但是，lempel-ziv算法強調的是算法的簡單與取得高壓縮率的速率，因此它還是在內存壓縮中得到了廣泛的應用。 lemple-ziv算法（簡稱lz）是編碼時將一個位串分成詞組，然后將數據流描述成一系列的對。每個對組成一個新的詞組，它包含一個數字（前一個詞組的標識）和一個位（被附加到前一個詞組上）。這種編碼方式很龐大，可是一旦應用到適合的字符串，它就是相當有效率的編碼方式。下面舉例說明這種算法是如何編碼的。 ++表示連接（010++1=0101），u=0010001101是未被壓縮的字符串。c是壓縮后的字符串。p（x）表示詞組數x。先看一下u=0010001101發現，它可以被寫為u=0++010001101，因此得到p（1）=p(0)++0。現在繼續將其寫為u=0++02++0001101，可得到p(2)=p（1）++1。現在我們已經將p（2）描述為上一詞組和一個新的位的組合。下一步，u=0++01++00++01101，并得到p（3）=p（1）++0。現在我們注意到，有u=0++01+00+011++01，而p（4）=011=p(2)++1，zui后得到p（5）=p(1)++1。運算的步驟如表1所列。 一旦創建了表1，就有了整個編碼的圖表。要創建lempel-ziv數據流，則依照公式創建對。如果公式是p(x)=p(a)++b，則每個對為（a++b）。因此p（1）=p(0)++0變為（00++0），p（2）=p(1)++0變為（01++0），依此類推，將所有這些對連接起來，就得到了zui后的字符串，結果如表2所列。這樣，c就變成000011010101011，看來比u要長得多。但這里由于u的長度短，因此未能看出優勢，而且包含p（0）的公式都沒有壓縮，所以也引起了長度增加。 lempel-ziv字符串的解碼是很簡單的，就是抓住其中的對，對照表1進行重構。 表1 編碼過程 步 驟值公 式 u 0 - p(0) 0010001101 1 0 p(1)=p(0)++0 0++010001101 2 01 p(2)=p(1)++1 0++01++00++01101 3 00 p(3)=p(1)++0 0++01++00++01101 4 011 p(4)=p(2)++1 0++01++00++011++01 5 01 p(5)=p(1)++1 0++01++00++011++01 表2 如何創建編碼字符串 公 式 p(1)=p(0)++0 p(2)=p(1)++1 p(3)=p(1)++0 p(4)=p(2)++1 p(5)=p(1)++1 對 00++0=000 01++1=011 01++0=010 10=++1=101 01++1=011 c 000++011++010++101++011=000011010101011 4 操作系統對內存壓縮的支持 在壓縮內存系統中，內存大小指的是實際內存大小，它比物理內存大。在引導時，bios向操作系統報告的內存大小就比實際安裝的物理內存要大。例如，硬件原型安裝的是512mb的sdram，但bios向操作系統報告的內存大小為1gb。當應用程序數據以2：1或更高的比率壓縮時，實際內存的工作方式與一般操作系統的內存工作方式是相同的。但當應用程序以未壓縮數據來填充內存時（如一個zip文件不可能達到2：1的壓縮比率），由于一般的os只看到實際地址空間，因此不能意識到物理內存已經耗盡。例如，一個操作系統的實際內存為1024mb，而牧師內存為512mb。這時實際內存已經分配了600mb，系統顯示還有424mb的空閑內存。但是由于已分配內存的壓縮率很低，此時物理內存的耗用已經接近512mb。如果再近一步地分配內存，那么系統就會因為物理內存的耗盡而崩潰，盡管它仍然顯示還有424mb的空閑內存。這種情況下，必須由操作系統提供對壓縮內存進行管理的支持。 由于內存壓縮是一個比較新的概念，一般的情況作系統都沒有這樣的機制來區分實際地址和物理地址，也不能處理“物理內存耗盡”的情況。不過，只要對操作系統內核做一些小的改動或者在操作系統之上增加一個設備驅動程序，即可達到目的。 一般來說，要從以下幾方面對壓縮內存進行管理。 （1）監控物理內存使用情況 通過輪詢或中斷法，查看物理內存的使用情況，并在物理內存耗盡前給出警告。壓縮內存管理例程是通過壓縮內存控制器中的一些寄存器來實現對物理內存的監控。sur報告物理內存的使用情況，suthr和sutlr用于設置中斷臨界值。壓縮內存管理算法是基于物理內存使用的四種狀態，分別為steady、acquire、danger和interrupt，其臨界值的關系是mc_th_acquirefunction imgzoom(id)//重新設置圖片大小 防止撐破表格{var w = $(id).width;var m = 550;if(w < m){return;}else{var h = $(id).height;$(id).height = parseint(h＊m/w);$(id).width = m;}}window.onload = function(){var imgs = $("content").getelementsbytagname("img");var i=0;for(;i