關(guān)鍵詞：嵌入式系統(tǒng) 內(nèi)存壓縮 壓縮內(nèi)存控制器 Lempel-Ziv算法

1 內(nèi)存壓縮技術(shù)介紹

為節(jié)省存儲空間或傳輸帶寬，人們已經(jīng)在計算機系統(tǒng)中廣泛地使用了數(shù)據(jù)壓縮技術(shù)。在磁介質(zhì)存儲數(shù)據(jù)或網(wǎng)絡(luò)傳輸數(shù)據(jù)時，人們使用基于硬件或軟件的各種壓縮技術(shù)。當壓縮技術(shù)在各個領(lǐng)域都很流行時，內(nèi)存壓縮技術(shù)卻由于其復(fù)雜性而一直未得到廣泛使用。近年來，由于在并行壓縮一解壓算法以及在硅密度及速度方面取得的進展，使得內(nèi)存壓縮技術(shù)變得可行。

內(nèi)存壓縮技術(shù)的主要思想是將數(shù)據(jù)按照一定的算法壓縮后存入壓縮內(nèi)存中，系統(tǒng)從壓縮內(nèi)存中找到壓縮過的數(shù)據(jù)，將其解壓后即可以供系統(tǒng)使用。這樣既可以增加實際可用的內(nèi)存空間，又可以減少頁面置換所帶來的開銷，從而以較小的成本提高系統(tǒng)的整體性能。

內(nèi)存壓縮機制是在系統(tǒng)的存儲層次中邏輯地加入一層——壓縮內(nèi)存層。系統(tǒng)在該層中以壓縮的格式保存物理頁面，當頁面再次被系統(tǒng)引用時，解壓該壓縮頁后，即可使用。我們將管理這一壓縮內(nèi)存層的相關(guān)硬件及軟件的集合統(tǒng)稱為內(nèi)存壓縮系統(tǒng)。內(nèi)存壓縮系統(tǒng)對于CPU、I/O設(shè)備、設(shè)備驅(qū)動以及應(yīng)用軟件來說是透明的，但是操作系統(tǒng)必須具有管理內(nèi)存大小變化以及壓縮比率變化的功能。

對于大多數(shù)的操作系統(tǒng)而言，要實現(xiàn)內(nèi)存壓縮，大部分體系結(jié)構(gòu)都不需要改動。在標準的操作系統(tǒng)中，內(nèi)存都是通過固定數(shù)目的物理頁框（page frame）來描述的，由操作系統(tǒng)的VMM來管理。要支持內(nèi)存壓縮，OS要管理的實際內(nèi)存大小和頁框數(shù)目是基于內(nèi)存的壓縮比率來確定的。這里的實現(xiàn)內(nèi)存是指操作系統(tǒng)可的內(nèi)存大小，它與物理內(nèi)存的關(guān)系如下：假設(shè)PM是物理內(nèi)存，RM（t）是系統(tǒng)在t時刻的實際內(nèi)存，而CR（t）是壓縮比率，在給定時刻t可支持的最大實際內(nèi)存為RM（t）=CR1（t）×PM。然而，由于應(yīng)用程序的數(shù)據(jù)壓縮率是不依賴于OS而動態(tài)變化的，未壓縮的數(shù)據(jù)可能會耗盡物理內(nèi)存，因此當物理內(nèi)存接近耗盡時，操作系統(tǒng)必須采取行動來解決這個問題。

2 內(nèi)存壓縮系統(tǒng)的硬件模型

目前由于內(nèi)存壓縮的思想越來越引起人們的注意市場上也出現(xiàn)了一些基于軟件的內(nèi)存壓縮器。這些內(nèi)存壓縮器主要是通過軟件對數(shù)據(jù)進行壓縮，但由于訪問壓縮數(shù)據(jù)帶來的延遲，它在系統(tǒng)性能方面改進并不明顯，有些甚至降低了系統(tǒng)性能。本節(jié)介紹一種基于硬件的內(nèi)存壓縮系統(tǒng)模型。

圖1是一個典型的內(nèi)存壓縮系統(tǒng)的硬件模型，包括了壓縮內(nèi)存、L3高速緩沖、壓縮內(nèi)存控制器等硬件部分。

其中壓縮內(nèi)存（133MHz SDRAM）包含了壓縮數(shù)據(jù)。L3高速緩沖是一個共享的、32MB、4路組相聯(lián)、可回寫的高速緩沖，每行大小為1KB，由兩倍數(shù)據(jù)率（DDR）SDRAM制定。L3高速緩沖包含了未壓縮的緩沖行，由于大部分的訪問都可以在L3高速緩沖中命中，因此它隱藏了訪問壓縮主存引起的延遲。L3高速緩沖對于存儲分級體系中的上層而言就是主存，它的操作對于其它硬件，包括處理器和I/O來說都是透明的。壓縮內(nèi)存控制器是整個內(nèi)存壓縮系統(tǒng)的控制中心，它負責數(shù)據(jù)的壓縮/解壓，監(jiān)控物理內(nèi)存的使用情況以及實際地址到物理地址的尋址過程。

數(shù)據(jù)壓縮過程是這樣的：壓縮內(nèi)存控制將1KB的高速緩沖行壓縮后寫入壓縮內(nèi)存中，然后將它們從壓縮內(nèi)存中讀出后解壓。其壓縮算法就是Lempel-Ziv算法，我們會在下一部分介紹這個算法。壓縮機制將壓縮的數(shù)據(jù)塊以不同的長度格式存放到內(nèi)存中。壓縮內(nèi)存的存儲單元是一個256字節(jié)的區(qū)域。按照壓縮比率不同，一個1KB的內(nèi)存塊（正好是L3每行的大小）可以占據(jù)0～4個壓縮區(qū)域。

壓縮內(nèi)存控制器必須根據(jù)長度格式的不同將系統(tǒng)總線上的實際地址翻譯成物理內(nèi)存的中的物理地址。實際地址是出現(xiàn)在處理器外部總線上常規(guī)地址。篁 址用來錄十壓縮內(nèi)存的256字節(jié)區(qū)域。實際地址空間存在于L1/L2/L3高速緩沖中，用于立即訪問。而其余的內(nèi)存內(nèi)容部分以壓縮形式存在于物理內(nèi)存中。內(nèi)存控制器通過查詢壓縮翻譯表（CTT）執(zhí)行從實際地址到物理地址的翻譯，這個表被保留在物理內(nèi)存的某個位置。圖2是CTT表的格式及內(nèi)存控制器的尋址模式。

每個1KB內(nèi)存塊的實際地址映射到CTT的一項，而CTT每項共16字節(jié)，包括四個物理區(qū)域地址，每個地址指向物理內(nèi)存聽一個256字節(jié)區(qū)域。對于少于120位的塊，如一個全為零的塊，則使用一種特殊的CTT格式，稱為通用行格式。在這種格式中，壓縮數(shù)據(jù)全部存放在CTT項中，代替了四個地址指針。因此，一個1KB的通用塊僅占用物理內(nèi)存中的16字節(jié)，其壓縮比率達到64：1。

壓縮內(nèi)存控制器中有一系列的寄存器用于監(jiān)控物理內(nèi)存使用。Sectors Used Register(SUR)向操作系統(tǒng)報告壓縮內(nèi)存的使用情況。The Sectors Used Threshold Registers,SUTHR和SUTLR，用于設(shè)置內(nèi)存耗盡情況的中斷入口點。SUTLR寄存器是PCI中斷電路INTA的入口，而SUTHR寄存器是NMI中斷的入口。當SUR超過了SUTLR的值，內(nèi)存控制器產(chǎn)生一個中斷，則操作系統(tǒng)采取措施來阻止內(nèi)存消耗。

在實際地址到物理地址的轉(zhuǎn)換中，一個有用的方法是快速頁操作。它允許控制器僅修改CTT項的四個指針，從而將4KB的頁面內(nèi)容換出或清空?？焖夙摬僮魍ㄟ^將與4KB頁面相關(guān)的CTT項全部修改通用行格式（即全為零），從而將這4KB頁面的內(nèi)容全部清空。同樣，一對頁面可以通過交換它們相關(guān)的CTT項的區(qū)域指針來交換頁面內(nèi)容。由于沒有大量的數(shù)據(jù)移動發(fā)生，快速頁面操作速度相當快。

壓縮內(nèi)存控制器的壓縮/解壓功能是基于LempelZiv算法來進行的，因此下一節(jié)將簡單介紹一下該算法的思想。

3 內(nèi)存壓縮算法Lempel-Ziv

絕大多數(shù)的壓縮算法，包括用得特別流行的Lempel-Ziv壓縮算法家庭，都是基于對原子記錄（Token）字符串的完全重復(fù)檢測。這個算法雖然不是最好的算法，但是，Lempel-Ziv算法強調(diào)的是算法的簡單與取得高壓縮率的速率，因此它還是在內(nèi)存壓縮中得到了廣泛的應(yīng)用。

Lemple-Ziv算法（簡稱LZ）是編碼時將一個位串分成詞組，然后將數(shù)據(jù)流描述成一系列的對。每個對組成一個新的詞組，它包含一個數(shù)字（前一個詞組的標識）和一個位（被附加到前一個詞組上）。這種編碼方式很龐大，可是一旦應(yīng)用到適合的字符串，它就是相當有效率的編碼方式。下面舉例說明這種算法是如何編碼的。

++表示連接（010++1=0101），U=0010001101是未被壓縮的字符串。C是壓縮后的字符串。P（x）表示詞組數(shù)x。先看一下U=0010001101發(fā)現(xiàn)，它可以被寫為U=0++010001101，因此得到P（1）=P(0)++0。現(xiàn)在繼續(xù)將其寫為U=0++02++0001101，可得到P(2)=P（1）++1?，F(xiàn)在我們已經(jīng)將P（2）描述為上一詞組和一個新的位的組合。下一步，U=0++01++00++01101，并得到P（3）=P（1）++0?，F(xiàn)在我們注意到，有U=0++01+00+011++01，而P（4）=011=P(2)++1，最后得到P（5）=P(1)++1。運算的步驟如表1所列。

一旦創(chuàng)建了表1，就有了整個編碼的圖表。要創(chuàng)建Lempel-Ziv數(shù)據(jù)流，則依照公式創(chuàng)建對。如果公式是P(x)=P(A)++B，則每個對為（A++B）。因此P（1）=P(0)++0變?yōu)椋?0++0），P（2）=P(1)++0變?yōu)椋?1++0），依此類推，將所有這些對連接起來，就得到了最后的字符串，結(jié)果如表2所列。這樣，C就變成000011010101011，看來比U要長得多。但這里由于U的長度短，因此未能看出優(yōu)勢，而且包含P（0）的公式都沒有壓縮，所以也引起了長度增加。

Lempel-Ziv字符串的解碼是很簡單的，就是抓住其中的對，對照表1進行重構(gòu)。

表1 編碼過程

表2 如何創(chuàng)建編碼字符串

4 操作系統(tǒng)對內(nèi)存壓縮的支持

在壓縮內(nèi)存系統(tǒng)中，內(nèi)存大小指的是實際內(nèi)存大小，它比物理內(nèi)存大。在引導(dǎo)時，BIOS向操作系統(tǒng)報告的內(nèi)存大小就比實際安裝的物理內(nèi)存要大。例如，硬件原型安裝的是512MB的SDRAM，但BIOS向操作系統(tǒng)報告的內(nèi)存大小為1GB。當應(yīng)用程序數(shù)據(jù)以2：1或更高的比率壓縮時，實際內(nèi)存的工作方式與一般操作系統(tǒng)的內(nèi)存工作方式是相同的。但當應(yīng)用程序以未壓縮數(shù)據(jù)來填充內(nèi)存時（如一個zip文件不可能達到2：1的壓縮比率），由于一般的OS只看到實際地址空間，因此不能意識到物理內(nèi)存已經(jīng)耗盡。例如，一個操作系統(tǒng)的實際內(nèi)存為1024MB，而牧師內(nèi)存為512MB。這時實際內(nèi)存已經(jīng)分配了600MB，系統(tǒng)顯示還有424MB的空閑內(nèi)存。但是由于已分配內(nèi)存的壓縮率很低，此時物理內(nèi)存的耗用已經(jīng)接近512MB。如果再近一步地分配內(nèi)存，那么系統(tǒng)就會因為物理內(nèi)存的耗盡而崩潰，盡管它仍然顯示還有424MB的空閑內(nèi)存。這種情況下，必須由操作系統(tǒng)提供對壓縮內(nèi)存進行管理的支持。

由于內(nèi)存壓縮是一個比較新的概念，一般的情況作系統(tǒng)都沒有這樣的機制來區(qū)分實際地址和物理地址，也不能處理“物理內(nèi)存耗盡”的情況。不過，只要對操作系統(tǒng)內(nèi)核做一些小的改動或者在操作系統(tǒng)之上增加一個設(shè)備驅(qū)動程序，即可達到目的。

一般來說，要從以下幾方面對壓縮內(nèi)存進行管理。

（1）監(jiān)控物理內(nèi)存使用情況

通過輪詢或中斷法，查看物理內(nèi)存的使用情況，并在物理內(nèi)存耗盡前給出警告。壓縮內(nèi)存管理例程是通過壓縮內(nèi)存控制器中的一些寄存器來實現(xiàn)對物理內(nèi)存的監(jiān)控。SUR報告物理內(nèi)存的使用情況，SUTHR和SUTLR用于設(shè)置中斷臨界值。壓縮內(nèi)存管理算法是基于物理內(nèi)存使用的四種狀態(tài)，分別為steady、acquire、danger和interrupt，其臨界值的關(guān)系是mc_th_acquire

我們可以使用輪詢和中斷相結(jié)合的方法進行監(jiān)控，并對物理內(nèi)存使用的變化作出反應(yīng)。通過時鐘中斷來驅(qū)動輪例程，該例程每10ms讀取一次SUR的值，并將它與系統(tǒng)設(shè)定的臨界值比較。當系統(tǒng)處于steady狀態(tài)時，不用采取任何行動；當使用超過mc_th_acquire，應(yīng)該增加nr_rsrv_pages來限制內(nèi)存分配，但這并未引起內(nèi)存缺乏；當使用超過mc_th_danger，應(yīng)該增加nr_rsrv_pages到引起內(nèi)存缺乏，并導(dǎo)致頁面分配器和置換進程回收內(nèi)存頁面，一旦進入到該狀態(tài)，物理內(nèi)存管理例程會喚醒置換進程回收內(nèi)存。

（2）回收內(nèi)存以及清空空閑頁面內(nèi)容以減少使用

以標準的Linux內(nèi)核為例，操作系統(tǒng)中有兩具主要的變量來管理內(nèi)存太少的情形。這兩個變量是nr_free_pages和struct freepages。為了檢測內(nèi)存是否已耗盡，在分配內(nèi)存前要進行檢查。

if(nr_free_pages

/*內(nèi)存太少，回收頁面*/

}

else

{/*可以進行分配*/

在內(nèi)存壓縮系統(tǒng)中，通過增加一個新變量nr_rsrv_pages來完成此功能。這樣就使最小空閑頁面數(shù)量變?yōu)椋篺reepages.min'=freepages.min+nr_rsrv_pages。

通過動態(tài)地調(diào)整nr_rsrv_pages變量，壓縮內(nèi)存管理例程可以人為地造成內(nèi)存缺乏的現(xiàn)象，從而引起置換進程回收頁面，此時會將調(diào)用進程暫時掛起?；厥諆?nèi)存包含縮減各種緩沖，并將進程頁面置換到磁盤上。當頁面返回到空閑頁面池時，它們會被清零。我們可以使用前面提到的快速頁面操作來減少清空頁面操作所帶來的開銷。

（3）阻塞CPU周期以減少物理內(nèi)存使用率

當物理內(nèi)存使用超過監(jiān)界值mc_th_interrupt，控制器就中斷處理器，nr_rsrv_pages進一步增加，然后CPU blocker就開始運行。我們在輪詢機制的基礎(chǔ)上還使用了中斷機制，因為中斷機制比輪詢機制更加快速。如果在10ms的間隔中，物理內(nèi)存使用突然上升，硬件中斷會比輪詢例程更早檢測到這一情況。為了更加安全，我們使用CPUblocker來阻塞引起物理內(nèi)存使用的進程。CPU blocker是空閑線程，它們可以使CPU空忙。由于頁面被置換到磁盤是以機器速度運行的，而物理內(nèi)存使用卻可以以內(nèi)存訪問速度運行，速度從而得到增加。當牧師內(nèi)存使用持續(xù)增加，以至換頁也無法緩解時，進程需要被阻塞。我們就通過啟動CPUblocker來阻塞CPU周期直到換頁機制能有效地降低物理內(nèi)存使用。CPUblocker不會阻塞中斷，而且每40ms它就會讓出CPU以免其它進程被餓死。

5 內(nèi)存壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用

嵌入式系統(tǒng)是一種特殊的計算機系統(tǒng)，它是一個更大的系統(tǒng)或設(shè)備的一部分。通常，一個嵌入式系統(tǒng)是駐留在單處理機底板上的，其應(yīng)用程序存儲在ROM中。事實上，所有具有數(shù)字接口的設(shè)備——監(jiān)視器、微波爐、VCRs、汽車等，都使用了嵌入式系統(tǒng)。一些嵌入式系統(tǒng)包含了操作系統(tǒng)，稱為嵌入式操作系統(tǒng)。為了滿足嵌入式應(yīng)用的特殊要求，嵌入式微處理器雖然在功能上和標準微處理器基本是一樣的，但和工業(yè)控制計算機相比，嵌入式微處理器具有體積小、重量輕、成本低、可靠性中，內(nèi)存仍然是珍貴的資源，因此研究內(nèi)存壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用具有一定的價值。

內(nèi)存壓縮的思想在一些嵌入式操作系統(tǒng)中，實際上已經(jīng)得到了體現(xiàn)。例如在VxWorks中，當操作系統(tǒng)下載到目標機上時，其中一種方式是將引導(dǎo)程序和VxWorks映像都存放在ROM中。為了將其解壓后再從ROM拷貝到RAM。這種基于軟件的壓縮方式，可以節(jié)省ROM空間，但其引導(dǎo)過程相對較慢。

以上的內(nèi)存壓縮技術(shù)在ROM中得到了應(yīng)用，但對于RAM來講，基于軟件內(nèi)存壓縮技術(shù)，由于其訪問壓縮數(shù)據(jù)可能造成的延遲和不確定性，會對嵌入式系統(tǒng)的實時性造成和。因此它與虛擬內(nèi)存技術(shù)一樣，在嵌入式系統(tǒng)中未得到廣泛應(yīng)用。

本文所介紹的內(nèi)存壓縮系統(tǒng)是基于硬件的。在相同基準下，測試結(jié)果顯示出，該系統(tǒng)的運行速度比標準系統(tǒng)的運行速度快1.3倍。如果要實現(xiàn)相同大小的內(nèi)存，采用內(nèi)存壓縮系統(tǒng)的硬件費用比購買RAM的費用要低，而且內(nèi)存越大，其節(jié)省的費用越多，可以達到一半的價錢。因此筆者認為在內(nèi)存資源極其寶貴的嵌入式系統(tǒng)中，實現(xiàn)基于硬件的內(nèi)存壓縮系統(tǒng)具有較大的價值。

結(jié)語

本文介紹的內(nèi)存壓縮系統(tǒng)是基于專門的硬件支持，即L3高速緩沖和內(nèi)存控制器。在目前大多數(shù)Pentium以上架構(gòu)的硬件平臺上，只需要對操作系統(tǒng)內(nèi)核做一些小的屐，或者增加一個設(shè)備驅(qū)動及服務(wù)程序，即可完成此項功能。由于嵌入式系統(tǒng)對實時性的要求，基于硬件的內(nèi)存壓縮技術(shù)可以在增大可用內(nèi)存的同時不影響系統(tǒng)的實時性，其硬件費用相對RAM的價格更低，具有一定的實用價值。