嵌入式系統(tǒng)中的內(nèi)存壓縮技術(shù)

1、嵌入式系統(tǒng)中的內(nèi)存壓縮技術(shù) 摘要：介紹內(nèi)存壓縮技術(shù)和一個(gè)基于硬件的內(nèi)存壓縮系統(tǒng)模型，探討內(nèi)存壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用；重點(diǎn)介紹內(nèi)存壓縮系統(tǒng)的硬件要求及操作系統(tǒng)對(duì)內(nèi)存壓縮機(jī)制的支持；簡(jiǎn)單介紹內(nèi)存壓縮中常用的算法lempel-ziv，并就內(nèi)存壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用問(wèn)題作一些探討。 關(guān)鍵詞：嵌入式系統(tǒng) 內(nèi)存壓縮 壓縮內(nèi)存控制器 lempel-ziv算法 1 內(nèi)存壓縮技術(shù)介紹 為節(jié)省存儲(chǔ)空間或傳輸帶寬，人們已經(jīng)在計(jì)算機(jī)系統(tǒng)中廣泛地使用了數(shù)據(jù)壓縮技術(shù)。在磁介質(zhì)存儲(chǔ)數(shù)據(jù)或網(wǎng)絡(luò)傳輸數(shù)據(jù)時(shí)，人們使用基于硬件或軟件的各種壓縮技術(shù)。當(dāng)壓縮技術(shù)在各個(gè)領(lǐng)域都很流行時(shí)，內(nèi)存壓縮技術(shù)卻由于其復(fù)雜性而一直未得到廣

2、泛使用。近年來(lái)，由于在并行壓縮一解壓算法以及在硅密度及速度方面取得的進(jìn)展，使得內(nèi)存壓縮技術(shù)變得可行。 內(nèi)存壓縮技術(shù)的主要思想是將數(shù)據(jù)按照一定的算法壓縮后存入壓縮內(nèi)存中，系統(tǒng)從壓縮內(nèi)存中找到壓縮過(guò)的數(shù)據(jù)，將其解壓后即可以供系統(tǒng)使用。這樣既可以增加實(shí)際可用的內(nèi)存空間，又可以減少頁(yè)面置換所帶來(lái)的開(kāi)銷，從而以較小的成本提高系統(tǒng)的整體性能。 內(nèi)存壓縮機(jī)制是在系統(tǒng)的存儲(chǔ)層次中邏輯地加入一層壓縮內(nèi)存層。系統(tǒng)在該層中以壓縮的格式保存物理頁(yè)面，當(dāng)頁(yè)面再次被系統(tǒng)引用時(shí)，解壓該壓縮頁(yè)后，即可使用。我們將管理這一壓縮內(nèi)存層的相關(guān)硬件及軟件的集合統(tǒng)稱為內(nèi)存壓縮系統(tǒng)。內(nèi)存壓縮系統(tǒng)對(duì)于cpu、i/o設(shè)備、設(shè)備驅(qū)動(dòng)以及應(yīng)用軟

3、件來(lái)說(shuō)是透明的，但是操作系統(tǒng)必須具有管理內(nèi)存大小變化以及壓縮比率變化的功能。 對(duì)于大多數(shù)的操作系統(tǒng)而言，要實(shí)現(xiàn)內(nèi)存壓縮，大部分體系結(jié)構(gòu)都不需要改動(dòng)。在標(biāo)準(zhǔn)的操作系統(tǒng)中，內(nèi)存都是通過(guò)固定數(shù)目的物理頁(yè)框（page frame）來(lái)描述的，由操作系統(tǒng)的vmm來(lái)管理。要支持內(nèi)存壓縮，os要管理的實(shí)際內(nèi)存大小和頁(yè)框數(shù)目是基于內(nèi)存的壓縮比率來(lái)確定的。這里的實(shí)現(xiàn)內(nèi)存是指操作系統(tǒng)可的內(nèi)存大小，它與物理內(nèi)存的關(guān)系如下：假設(shè)pm是物理內(nèi)存，rm（t）是系統(tǒng)在t時(shí)刻的實(shí)際內(nèi)存，而cr（t）是壓縮比率，在給定時(shí)刻t可支持的最大實(shí)際內(nèi)存為rm（t）=cr1（t）pm。然而，由于應(yīng)用程序的數(shù)據(jù)壓縮率是不依賴于os而動(dòng)態(tài)變化

4、的，未壓縮的數(shù)據(jù)可能會(huì)耗盡物理內(nèi)存，因此當(dāng)物理內(nèi)存接近耗盡時(shí)，操作系統(tǒng)必須采取行動(dòng)來(lái)解決這個(gè)問(wèn)題。 2 內(nèi)存壓縮系統(tǒng)的硬件模型 目前由于內(nèi)存壓縮的思想越來(lái)越引起人們的注意市場(chǎng)上也出現(xiàn)了一些基于軟件的內(nèi)存壓縮器。這些內(nèi)存壓縮器主要是通過(guò)軟件對(duì)數(shù)據(jù)進(jìn)行壓縮，但由于訪問(wèn)壓縮數(shù)據(jù)帶來(lái)的延遲，它在系統(tǒng)性能方面改進(jìn)并不明顯，有些甚至降低了系統(tǒng)性能。本節(jié)介紹一種基于硬件的內(nèi)存壓縮系統(tǒng)模型。 圖1是一個(gè)典型的內(nèi)存壓縮系統(tǒng)的硬件模型，包括了壓縮內(nèi)存、l3高速緩沖、壓縮內(nèi)存控制器等硬件部分。 其中壓縮內(nèi)存（133mhz sdram）包含了壓縮數(shù)據(jù)。l3高速緩沖是一個(gè)共享的、32mb、4路組相聯(lián)、可回寫的高速緩沖，

5、每行大小為1kb，由兩倍數(shù)據(jù)率（ddr）sdram制定。l3高速緩沖包含了未壓縮的緩沖行，由于大部分的訪問(wèn)都可以在l3高速緩沖中命中，因此它隱藏了訪問(wèn)壓縮主存引起的延遲。l3高速緩沖對(duì)于存儲(chǔ)分級(jí)體系中的上層而言就是主存，它的操作對(duì)于其它硬件，包括處理器和i/o來(lái)說(shuō)都是透明的。壓縮內(nèi)存控制器是整個(gè)內(nèi)存壓縮系統(tǒng)的控制中心，它負(fù)責(zé)數(shù)據(jù)的壓縮/解壓，監(jiān)控物理內(nèi)存的使用情況以及實(shí)際地址到物理地址的尋址過(guò)程。 數(shù)據(jù)壓縮過(guò)程是這樣的：壓縮內(nèi)存控制將1kb的高速緩沖行壓縮后寫入壓縮內(nèi)存中，然后將它們從壓縮內(nèi)存中讀出后解壓。其壓縮算法就是lempel-ziv算法，我們會(huì)在下一部分介紹這個(gè)算法。壓縮機(jī)制將壓縮的數(shù)

6、據(jù)塊以不同的長(zhǎng)度格式存放到內(nèi)存中。壓縮內(nèi)存的存儲(chǔ)單元是一個(gè)256字節(jié)的區(qū)域。按照壓縮比率不同，一個(gè)1kb的內(nèi)存塊（正好是l3每行的大?。┛梢哉紦?jù)04個(gè)壓縮區(qū)域。 壓縮內(nèi)存控制器必須根據(jù)長(zhǎng)度格式的不同將系統(tǒng)總線上的實(shí)際地址翻譯成物理內(nèi)存的中的物理地址。實(shí)際地址是出現(xiàn)在處理器外部總線上常規(guī)地址。篁 址用來(lái)錄十壓縮內(nèi)存的256字節(jié)區(qū)域。實(shí)際地址空間存在于l1/l2/l3高速緩沖中，用于立即訪問(wèn)。而其余的內(nèi)存內(nèi)容部分以壓縮形式存在于物理內(nèi)存中。內(nèi)存控制器通過(guò)查詢壓縮翻譯表（ctt）執(zhí)行從實(shí)際地址到物理地址的翻譯，這個(gè)表被保留在物理內(nèi)存的某個(gè)位置。圖2是ctt表的格式及內(nèi)存控制器的尋址模式。 每個(gè)1kb

7、內(nèi)存塊的實(shí)際地址映射到ctt的一項(xiàng)，而ctt每項(xiàng)共16字節(jié)，包括四個(gè)物理區(qū)域地址，每個(gè)地址指向物理內(nèi)存聽(tīng)一個(gè)256字節(jié)區(qū)域。對(duì)于少于120位的塊，如一個(gè)全為零的塊，則使用一種特殊的ctt格式，稱為通用行格式。在這種格式中，壓縮數(shù)據(jù)全部存放在ctt項(xiàng)中，代替了四個(gè)地址指針。因此，一個(gè)1kb的通用塊僅占用物理內(nèi)存中的16字節(jié)，其壓縮比率達(dá)到64：1。 壓縮內(nèi)存控制器中有一系列的寄存器用于監(jiān)控物理內(nèi)存使用。sectors used register(sur)向操作系統(tǒng)報(bào)告壓縮內(nèi)存的使用情況。the sectors used threshold registers,suthr和sutlr，用于設(shè)置內(nèi)存

8、耗盡情況的中斷入口點(diǎn)。sutlr寄存器是pci中斷電路inta的入口，而suthr寄存器是nmi中斷的入口。當(dāng)sur超過(guò)了sutlr的值，內(nèi)存控制器產(chǎn)生一個(gè)中斷，則操作系統(tǒng)采取措施來(lái)阻止內(nèi)存消耗。 在實(shí)際地址到物理地址的轉(zhuǎn)換中，一個(gè)有用的方法是快速頁(yè)操作。它允許控制器僅修改ctt項(xiàng)的四個(gè)指針，從而將4kb的頁(yè)面內(nèi)容換出或清空。快速頁(yè)操作通過(guò)將與4kb頁(yè)面相關(guān)的ctt項(xiàng)全部修改通用行格式（即全為零），從而將這4kb頁(yè)面的內(nèi)容全部清空。同樣，一對(duì)頁(yè)面可以通過(guò)交換它們相關(guān)的ctt項(xiàng)的區(qū)域指針來(lái)交換頁(yè)面內(nèi)容。由于沒(méi)有大量的數(shù)據(jù)移動(dòng)發(fā)生，快速頁(yè)面操作速度相當(dāng)快。 壓縮內(nèi)存控制器的壓縮/解壓功能是基于le

9、mpelziv算法來(lái)進(jìn)行的，因此下一節(jié)將簡(jiǎn)單介紹一下該算法的思想。 3 內(nèi)存壓縮算法lempel-ziv 絕大多數(shù)的壓縮算法，包括用得特別流行的lempel-ziv壓縮算法家庭，都是基于對(duì)原子記錄（token）字符串的完全重復(fù)檢測(cè)。這個(gè)算法雖然不是最好的算法，但是，lempel-ziv算法強(qiáng)調(diào)的是算法的簡(jiǎn)單與取得高壓縮率的速率，因此它還是在內(nèi)存壓縮中得到了廣泛的應(yīng)用。 lemple-ziv算法（簡(jiǎn)稱lz）是編碼時(shí)將一個(gè)位串分成詞組，然后將數(shù)據(jù)流描述成一系列的對(duì)。每個(gè)對(duì)組成一個(gè)新的詞組，它包含一個(gè)數(shù)字（前一個(gè)詞組的標(biāo)識(shí)）和一個(gè)位（被附加到前一個(gè)詞組上）。這種編碼方式很龐大，可是一旦應(yīng)用到適合的字

10、符串，它就是相當(dāng)有效率的編碼方式。下面舉例說(shuō)明這種算法是如何編碼的。 +表示連接（010+1=0101），u=0010001101是未被壓縮的字符串。c是壓縮后的字符串。p（x）表示詞組數(shù)x。先看一下u=0010001101發(fā)現(xiàn)，它可以被寫為u=0+010001101，因此得到p（1）=p(0)+0?，F(xiàn)在繼續(xù)將其寫為u=0+02+0001101，可得到p(2)=p（1）+1?，F(xiàn)在我們已經(jīng)將p（2）描述為上一詞組和一個(gè)新的位的組合。下一步，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，最后得到

11、p（5）=p(1)+1。運(yùn)算的步驟如表1所列。一旦創(chuàng)建了表1，就有了整個(gè)編碼的圖表。要?jiǎng)?chuàng)建lempel-ziv數(shù)據(jù)流，則依照公式創(chuàng)建對(duì)。如果公式是p(x)=p(a)+b，則每個(gè)對(duì)為（a+b）。因此p（1）=p(0)+0變?yōu)椋?0+0），p（2）=p(1)+0變?yōu)椋?1+0），依此類推，將所有這些對(duì)連接起來(lái)，就得到了最后的字符串，結(jié)果如表2所列。這樣，c就變成000011010101011，看來(lái)比u要長(zhǎng)得多。但這里由于u的長(zhǎng)度短，因此未能看出優(yōu)勢(shì)，而且包含p（0）的公式都沒(méi)有壓縮，所以也引起了長(zhǎng)度增加。 lempel-ziv字符串的解碼是很簡(jiǎn)單的，就是抓住其中的對(duì)，對(duì)照表1進(jìn)行重構(gòu)。 表1 編碼

12、過(guò)程 步 驟值公 式u 0-p(0)001000110110p(1)=p(0)+00+010001101201p(2)=p(1)+10+01+00+01101300p(3)=p(1)+00+01+00+011014011p(4)=p(2)+10+01+00+011+01501p(5)=p(1)+10+01+00+011+01表2 如何創(chuàng)建編碼字符串 公 式p(1)=p(0)+0p(2)=p(1)+1p(3)=p(1)+0p(4)=p(2)+1p(5)=p(1)+1對(duì)00+0=00001+1=01101+0=01010=+1=10101+1=011c 000+011+010+101+011=00

13、00110101010114 操作系統(tǒng)對(duì)內(nèi)存壓縮的支持 在壓縮內(nèi)存系統(tǒng)中，內(nèi)存大小指的是實(shí)際內(nèi)存大小，它比物理內(nèi)存大。在引導(dǎo)時(shí)，bios向操作系統(tǒng)報(bào)告的內(nèi)存大小就比實(shí)際安裝的物理內(nèi)存要大。例如，硬件原型安裝的是512mb的sdram，但bios向操作系統(tǒng)報(bào)告的內(nèi)存大小為1gb。當(dāng)應(yīng)用程序數(shù)據(jù)以2：1或更高的比率壓縮時(shí)，實(shí)際內(nèi)存的工作方式與一般操作系統(tǒng)的內(nèi)存工作方式是相同的。但當(dāng)應(yīng)用程序以未壓縮數(shù)據(jù)來(lái)填充內(nèi)存時(shí)（如一個(gè)zip文件不可能達(dá)到2：1的壓縮比率），由于一般的os只看到實(shí)際地址空間，因此不能意識(shí)到物理內(nèi)存已經(jīng)耗盡。例如，一個(gè)操作系統(tǒng)的實(shí)際內(nèi)存為1024mb，而牧師內(nèi)存為512mb。這時(shí)實(shí)

14、際內(nèi)存已經(jīng)分配了600mb，系統(tǒng)顯示還有424mb的空閑內(nèi)存。但是由于已分配內(nèi)存的壓縮率很低，此時(shí)物理內(nèi)存的耗用已經(jīng)接近512mb。如果再近一步地分配內(nèi)存，那么系統(tǒng)就會(huì)因?yàn)槲锢韮?nèi)存的耗盡而崩潰，盡管它仍然顯示還有424mb的空閑內(nèi)存。這種情況下，必須由操作系統(tǒng)提供對(duì)壓縮內(nèi)存進(jìn)行管理的支持。 由于內(nèi)存壓縮是一個(gè)比較新的概念，一般的情況作系統(tǒng)都沒(méi)有這樣的機(jī)制來(lái)區(qū)分實(shí)際地址和物理地址，也不能處理“物理內(nèi)存耗盡”的情況。不過(guò)，只要對(duì)操作系統(tǒng)內(nèi)核做一些小的改動(dòng)或者在操作系統(tǒng)之上增加一個(gè)設(shè)備驅(qū)動(dòng)程序，即可達(dá)到目的。 一般來(lái)說(shuō)，要從以下幾方面對(duì)壓縮內(nèi)存進(jìn)行管理。 （1）監(jiān)控物理內(nèi)存使用情況 通過(guò)輪詢或中斷法

15、，查看物理內(nèi)存的使用情況，并在物理內(nèi)存耗盡前給出警告。壓縮內(nèi)存管理例程是通過(guò)壓縮內(nèi)存控制器中的一些寄存器來(lái)實(shí)現(xiàn)對(duì)物理內(nèi)存的監(jiān)控。sur報(bào)告物理內(nèi)存的使用情況，suthr和sutlr用于設(shè)置中斷臨界值。壓縮內(nèi)存管理算法是基于物理內(nèi)存使用的四種狀態(tài)，分別為steady、acquire、danger和interrupt，其臨界值的關(guān)系是mc_th_acquire 我們可以使用輪詢和中斷相結(jié)合的方法進(jìn)行監(jiān)控，并對(duì)物理內(nèi)存使用的變化作出反應(yīng)。通過(guò)時(shí)鐘中斷來(lái)驅(qū)動(dòng)輪例程，該例程每10ms讀取一次sur的值，并將它與系統(tǒng)設(shè)定的臨界值比較。當(dāng)系統(tǒng)處于steady狀態(tài)時(shí)，不用采取任何行動(dòng)；當(dāng)使用超過(guò)mc_th_a

16、cquire，應(yīng)該增加nr_rsrv_pages來(lái)限制內(nèi)存分配，但這并未引起內(nèi)存缺乏；當(dāng)使用超過(guò)mc_th_danger，應(yīng)該增加nr_rsrv_pages到引起內(nèi)存缺乏，并導(dǎo)致頁(yè)面分配器和置換進(jìn)程回收內(nèi)存頁(yè)面，一旦進(jìn)入到該狀態(tài)，物理內(nèi)存管理例程會(huì)喚醒置換進(jìn)程回收內(nèi)存。 （2）回收內(nèi)存以及清空空閑頁(yè)面內(nèi)容以減少使用 以標(biāo)準(zhǔn)的linux內(nèi)核為例，操作系統(tǒng)中有兩具主要的變量來(lái)管理內(nèi)存太少的情形。這兩個(gè)變量是nr_free_pages和struct freepages。為了檢測(cè)內(nèi)存是否已耗盡，在分配內(nèi)存前要進(jìn)行檢查。 if(nr_free_pages /*內(nèi)存太少，回收頁(yè)面*/ else /*可以進(jìn)

17、行分配*/ 在內(nèi)存壓縮系統(tǒng)中，通過(guò)增加一個(gè)新變量nr_rsrv_pages來(lái)完成此功能。這樣就使最小空閑頁(yè)面數(shù)量變?yōu)椋篺reepages.min=freepages.min+nr_rsrv_pages。 通過(guò)動(dòng)態(tài)地調(diào)整nr_rsrv_pages變量，壓縮內(nèi)存管理例程可以人為地造成內(nèi)存缺乏的現(xiàn)象，從而引起置換進(jìn)程回收頁(yè)面，此時(shí)會(huì)將調(diào)用進(jìn)程暫時(shí)掛起?；厥諆?nèi)存包含縮減各種緩沖，并將進(jìn)程頁(yè)面置換到磁盤上。當(dāng)頁(yè)面返回到空閑頁(yè)面池時(shí)，它們會(huì)被清零。我們可以使用前面提到的快速頁(yè)面操作來(lái)減少清空頁(yè)面操作所帶來(lái)的開(kāi)銷。 （3）阻塞cpu周期以減少物理內(nèi)存使用率 當(dāng)物理內(nèi)存使用超過(guò)監(jiān)界值mc_th_interru

18、pt，控制器就中斷處理器，nr_rsrv_pages進(jìn)一步增加，然后cpu blocker就開(kāi)始運(yùn)行。我們?cè)谳喸儥C(jī)制的基礎(chǔ)上還使用了中斷機(jī)制，因?yàn)橹袛鄼C(jī)制比輪詢機(jī)制更加快速。如果在10ms的間隔中，物理內(nèi)存使用突然上升，硬件中斷會(huì)比輪詢例程更早檢測(cè)到這一情況。為了更加安全，我們使用cpublocker來(lái)阻塞引起物理內(nèi)存使用的進(jìn)程。cpu blocker是空閑線程，它們可以使cpu空忙。由于頁(yè)面被置換到磁盤是以機(jī)器速度運(yùn)行的，而物理內(nèi)存使用卻可以以內(nèi)存訪問(wèn)速度運(yùn)行，速度從而得到增加。當(dāng)牧師內(nèi)存使用持續(xù)增加，以至換頁(yè)也無(wú)法緩解時(shí)，進(jìn)程需要被阻塞。我們就通過(guò)啟動(dòng)cpublocker來(lái)阻塞cpu周期直

19、到換頁(yè)機(jī)制能有效地降低物理內(nèi)存使用。cpublocker不會(huì)阻塞中斷，而且每40ms它就會(huì)讓出cpu以免其它進(jìn)程被餓死。 5 內(nèi)存壓縮技術(shù)在嵌入式系統(tǒng)中的應(yīng)用 嵌入式系統(tǒng)是一種特殊的計(jì)算機(jī)系統(tǒng)，它是一個(gè)更大的系統(tǒng)或設(shè)備的一部分。通常，一個(gè)嵌入式系統(tǒng)是駐留在單處理機(jī)底板上的，其應(yīng)用程序存儲(chǔ)在rom中。事實(shí)上，所有具有數(shù)字接口的設(shè)備監(jiān)視器、微波爐、vcrs、汽車等，都使用了嵌入式系統(tǒng)。一些嵌入式系統(tǒng)包含了操作系統(tǒng)，稱為嵌入式操作系統(tǒng)。為了滿足嵌入式應(yīng)用的特殊要求，嵌入式微處理器雖然在功能上和標(biāo)準(zhǔn)微處理器基本是一樣的，但和工業(yè)控制計(jì)算機(jī)相比，嵌入式微處理器具有體積小、重量輕、成本低、可靠性中，內(nèi)存仍然是珍貴的資源，因