嵌入式系統的高速緩存管理

摘要：本文針對嵌入式文件系統提出了一套基于最久未使用頁面替換算法的高速緩存管理方案。該高速緩存管理模塊的使用，較好地提高文件系統的讀寫性能。以NorFlash操作為例，使用高速緩存以后，可以使多數量、小文件的寫入速度提升20%左右，讀出速度提升30%-40%。對于大容量數據傳輸，適當地調整緩存的容量，也可使得寫入速度提升2%，讀出速度提升10%左右。

關鍵詞：高速緩存管理方案；回寫；最久未使用頁面替換算法；塊設備

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)14-20000-00

Embedded System Cache Management

ZHONG Rui1，FANG Wen-kai2

(1.School of Electronics Science and Engeering， Southeast University， Nanjing 210096，China;2.School of Integrated Circuit， Southeast University，Nanjing 210096，China)

Abstract: A new file cache management based on Least Recently Used (LRU) was bring forward and realized in this paper. The impact of this cache management on embedded system files is proved to be positive. NorFlash as an example， after the use of this cache management， the write speed of mass and little files upgrade 20%， and read speed upgrade from 30% to 40%. To large-capacity data transmission， proper adjustment of cache capacity， we can also makes writing speed upgrade 2% and read rate increase of around 10%.

Key words: Cache Management; Write-back; Least Recently Used; Block device

1 論文研究背景

嵌入式系統的運行環境遠不同于PC機；嵌入式系統的存儲介質多為塊設備，其存儲原理與磁盤設備差異很大；桌面文件系統為提高讀寫性能盡可能使用較大的文件緩存，嵌入式系統必須針對資源限制設計特定的緩存管理單元，并盡量適應于塊設備的操作特點。

目前，嵌入式領域有多種文件系統可供選擇：RomFS是只讀文件系統，可以放在ROM空間，也可以放在系統RAM中，通常用作嵌入式Linux的根文件系統；JFFS/JFFS2是專為Flash設計的日志文件系統，它們提供了很好的掉電保護措施，并能平衡讀寫Flash設備，但是它們需要占用大量RAM空間，在文件系統接近滿時，它們速度會變得很慢，同時啟動的時候需要掃描日志節點，不太適合大容量存儲應用；Yaffs是專為NandFlash設計的日志文件系統，其針對NandFlash訪問的特點進行優化（如塊的讀寫、壞塊管理等），但欠缺通用性；Ext2是Linux下使用的文件系統，具有支持存儲容量大，訪問速度快等優點，但是對Flash存儲設備支持不好；FAT文件系統是目前桌面系統中使用最廣泛的文件系統，其文件管理方便、通用性好，但是同樣不能直接用于嵌入式應用，它的緩存管理單元主要針對pc機的磁盤管理，運用于塊存儲設備并不能有效提升文件的讀寫速度。我們由此進行了專項開發。東南大學國家專用集成電路工程技術中心針對這一需求進行了將FAT文件系統運用到嵌入式系統的研究工作。

2 高速緩存管理原理

高速緩沖存儲器（Cache），是一種加速內存或磁盤存取的技術，主要用來提升系統響應的速度。其作用的原理在于使用較快速的存儲裝置保留一份從慢速存儲裝置中所讀取的數據，當需要再從較慢的存儲體中讀寫數據時，Cache能夠使讀寫的動作先在快速的裝置上完成。這樣可以使得系統的響應較為快速。

這種技術如果僅僅使用在讀數據這一方面，則沒有任何問題。如果還要用在寫上，即寫入Cache中的數據不立即回寫真正的存儲體，則一旦電源中斷或出現其它意外會導致數據的流失。而每次都將數據寫入真正的存儲體，會使Cache只能發揮加速讀取的功能，而不能加速寫入。這樣的情況使Cache的寫入方式分為兩類：

（1）直寫式（Write-through）：每次遇到寫入Cache的同時，也把數據寫入真正的存儲設備，以保證Cache和真正的存儲設備中的單元數據的一致性。直寫式系統簡單可靠，但每次更新Cache時都要對真正的存儲設備寫入，因此速度受到了影響。

（2）回寫式（Write-back）：數據一般只寫到Cache，這樣可能出現Cache中的數據得到更新而存儲體中的數據不變的情況。但此時可在Cache中設一標志表示數據是否需要回寫，等系統有空或這部分Cache需要存儲其它數據或等到一定的時間后，再將數據寫回存儲設備，這種做法是用承擔一點風險來換取效率的。

在嵌入式文件系統中，同樣需要使用高速緩沖技術來提升文件系統的性能。由于嵌入式系統的資源有限，同時針對嵌入式系統塊設備的存儲特點（塊讀、塊寫），需要設計針對嵌入式應用特點的高速緩存管理。本論文設計了一種針對嵌入式應用特點的高速緩存管理單元，其具有如下特點：(1)軟件模塊化設計，提供統一接口，便于移植到不同平臺；(2)采用回寫方式提升寫入效率，同時具有一定的掉電保護措施；(3)設計最久未使用頁面替換算法（LRU）提升Cache系統的命中率；(4)以塊設備的塊大小為緩沖單元，實現對塊設備讀寫的優化；下面將具體介紹本論文設計的高速緩存管理模塊的實現方法。

3 實現代碼

3.1 文件系統Cache的主數據結構

本論文的Cache管理系統將Cache設計成保存在內存中的一個結構體數組。數組的每一個元素緩沖了存儲設備的一個簇的數據，同時還保存了為便于操作的其他必要信息。Cache結構定義的代碼清單如List 3.1所示：

List 3.1 文件系統Cache的主要數據結構

typedef struct _Disk_Cache{

U8DriveNo;//設備號，

U8 Flag;//狀態

U16RW_ID;//讀/寫標志

U32CluNo; //緩沖的簇號

U8 buf[DISK_CACHE_SIZE]; //緩沖//數據區

}DISK_CACHE;

Cache的大小可以采用靜態分配的方法，其代碼見List 3.2。

List 3.2 Cache存儲大小分配

DISK_CACHE DiskCache[MAX_DISK_CACHE] //Cache大小

其中MAX_DISK_CACHE的值，如果太小則Cache性能提升不明顯，太大則占據大量系統內存資源。在實際應用中，需要根據系統資源和性能要求作出合理的折衷。

3.2 Cache管理的主要操作

本論文設計的Cache管理可以作為一個獨立的Cache管理模塊，與文件系統本身有一定的獨立性。Cache管理模塊對文件系統提供了統一的API接口。表1為所使用API的列表，本節將介紹這些函數的實現過程。

3.2.1 初始化操作

在使用Cache前必須要對各Cache元素進行初始化操作. Cache初始化是調用函數CacheInit()完成的。函數CacheInit()的代碼如List 3.3所示。代碼很簡單，僅僅是把Cache數組所有元素的所有成員賦一定的初值。

3.2.2 打開存儲設備的簇

在讀寫存儲設備的扇區之前必須打開它，這時通過調用函數OpenClu()實現的。函數OpenClu()有兩個參數，其中DriverNo指出需要操作的設備號，index指出在指定設備上需要操作的簇號。此函數將返回一個指針指向簇數據的讀寫位置。如果返回值為NULL，則表示簇打開失敗。函數原型如List 3.4所示。

List 3.4 函數OpenClu()的原型

U8 * OpenClu(U8 DriveNo， U32 index)

3.2.3 分配Cache項

在前面的打開簇函數中使用到了為簇分配Cache項函數GetCache()，該函數是Cache管理的核心，它提供了一種Cache頁面替換算法。

所謂Cache頁面替換算法，就是當Cache空間已滿時，文件系統必須從Cache中選擇一項刪除掉以便為即將被調入的數據讓出空間。被刪除的項將根據被修改與否決定是否直接從Cache刪除還是回寫如存儲設備。

Cache的效能依算法的不同有好壞之分，估量的單位通常使用命中率。很明顯把最不常使用的頁面替換出緩存是提高命中率的好方法。為了找出最不常使用的緩存項替換掉，人們已經在理論和實踐上對頁面替換算法進行了深入的研究。

目前研究的頁面替換算法主要有：最近未使用頁面替換算法、先進先出頁面替換算法、時鐘頁面替換算法、最久未使用頁面替換算法等。

本論文使用的是最久未使用頁面替換算法（LRU）。該算法是基于這樣的設想：很久沒有使用的數據簇可能在未來較長一段時間內也不會被使用。因此LRU算法的替換策略是替換那些最久未被使用的數據簇。

本論文分配Cache項函數GetCache()核心的工作就是使用LRU算法找出可以被替換的數據簇。該函數結合函數OpenClu()中每次訪問Cache都把所有Cache元素RW_ID成員加1的功能，找出RW_ID參數值最大的一個Cache元素（可能有多個，選擇最先找到的），將其回寫存儲設備（如果需要的話）并替換出去。

List 3.5 函數GetCache()

U16 GetCache(void){

U16 Max;

U16 i，j;

Max = 0;

j = 0;

for(i = 0; i

if(Max<=DiskCache[i].RW_ID){

Max = DiskCache[i].RW_ID;

j = i;

}

if(Max == (U16)(-1)){

break;//如Max已是最大值，

//則不要繼續搜索

}

}

if(j

{

if(DiskCache[j].DriveNo !=

EMPTY_DRIVE){(1)

if((DiskCache[j].Flag

CACHE_WRITE)!=0) {

CacheWriteBack(j);

}

}

}

return j;}

List 3.5(1)中DiskCache[j]即為要替換的Cache數組元素。CacheWriteBack()函數實現了將緩沖數據寫回物理存儲設備的功能。Cache管理系統中，此部分需要跟物理設備操作有關，移植的時候需要加以改寫。

3.2.4 從設備讀數據到Cache

函數OpenClu()僅僅為設備的簇分配了Cache，如果程序需要事先把簇中的數據讀出來，需要調用函數ReadClu()。函數ReadClu()的參數同樣是需要讀取簇的設備號和設備內簇號。此函數將返回一個狀態碼，其中RETURN_OK表示成功，SECTOR_READ_ERR表示底層驅動讀操作失敗，NOT_FIND_DISK表明沒有找到指定的設備等。

3.2.5 置寫標志函數

根據前面對于Cache數據結構的介紹，需要回寫的Cache塊的Flag元素需標記為已被修改。函數WriteClu()就是完成這樣的功能。它有兩個參數，設備號和要操作的設備簇號，該函數首先根據設備號和簇號查找Cache數組DiskCache[]，找到設備簇在Cache中的緩存數組元素，然后將該元素的Flag標志置為CACHE_WRITE（或操作）。

3.2.6 回寫存儲設備

函數CacheWriteBack()實現改動數據的回寫。該函數只有一個參數index，為Cache數組的下標號，即根據下標號，讀取指定Cache項的設局結構，根據DriveNo成員決定的設備號，讀取設備的DROBJ結構（在其它文件系統中可能不同）以獲取操作設備的信息，然后將Cache的Flag標記置回無需回寫狀態并調用設備驅動完成回寫操作。

3.3 Cache管理的掉電處理

本論文采用回寫式的Cache管理。前面提到這種方法為提升性能而承擔了一定的風險，即有可能在Cache中數據尚未回寫時發生了掉電等異常情況導致系統失去響應，這樣新寫入的數據將丟失，之前的寫入操作失敗。為了在一定程度上解決此問題，本論文采用如下規則：(1)在設備關閉時Cache中所有與之相關的項必須回寫；(2)在系統空閑的時候，可以運行一個優先級較低的回寫任務，該任務完成查找Cache數組中所有成員標志為已改寫的元素，將其回寫。

另外，文件系統掉電保護還包括FAT表與文件數據一致性的問題，即在文件數據操作和FAT表更新操作之間發生掉電等異常，導致文件數據與FAT表數據不一致。對于此問題的處理，本論文采用如下的規則：

(1)有修改完FAT表后，才允許刪除對應簇的無效數據；(2)應用程序調用了一個文件操作接口之后返回之前，必須完成FAT表的更新以及FAT表的備份；(3)文件的新數據在寫入物理存儲設備之后，才允許修改FAT表。

采用上述措施后，即使寫入某簇的時候發生錯誤，也可以采取錯誤處理進行補救，或者直接返回給上層的應用，或者重新申請一個新的簇?？傊恢劣谠贔AT表上出現不合事實的錯誤。

3.4 Cache管理在文件系統中的應用

上述Cache管理操作是以文件簇為單位的，而文件系統最終通過設備驅動以簇為單位操作設備上的數據的，因此只需對設備驅動作一定的修改，在驅動中調用表3.1中的Cache管理API函數就可以實現用上述Cache管理方法管理設備上的數據了。

以NorFlash驅動為例，介紹Cache管理的添加。根據2.5.1節關于驅動的介紹可知NorFlash驅動中與存儲介質進行數據交互的函數是nor_rd_io()，需要對此函數進行改寫。為便于說明，將此函數的原型列如下：

int nor_rd_io(U16 driveno， U32 page， void *buffer， U16 count， int do_read)

函數中driveno為操作扇區號，page為操作的簇號，buffer為讀寫數據的緩沖區，count為操作的次數，do_read為讀寫的標志（1為讀，0為寫）。

首先根據函數的讀寫標志確定操作類型。如果是讀操作，則先調用函數CluinCache()判斷要讀取的文件簇是否在Cache中已經緩存，如已經緩存，則根據緩存的數組下標，直接讀Cache項buf[]中存儲的數據到buffer中；若不在緩存中，則通過替換算法在Cache中找到一項用于替換，調用NorFlash驅動，將設備上的數據同時寫入buffer和Cache項的buf[]元素中，以便于下次訪問使用方便。對于寫操作，可以首先判斷所寫的簇是否在Cache中，如在，則更新Cache項中buf[]內容；如不在，則根據替換算法找到新的Cache項，并將buffer寫入新Cache項中buf[]。寫操作采用的是Cache回寫策略，此時并沒有回寫物理設備，回寫物理設備的操作是在Cache回寫函數中完成的。

上述高速緩存的使用，有效地減少了設備的存取次數，提高了系統的通過能力并降低平均響應時間，特別是在做數據傳輸時，數據停留在高速緩存中，直到系統認為適當的時候才進行數據傳輸。另外，最久未使用頁面替換算法（LRU）的使用大大提高了Cache系統的命中率，提高了文件系統的讀寫性能。

4 測試與評估

4.1 測試平臺

本調試平臺由基于SEP3203的實驗開發板，JTAG仿真器和運行于主機上的集成開發環境(IDE)組成。將開發板通過JTAG仿真器連接到PC機上的集成調試環境(IDE)軟件平臺，在IDE中統一完成匯編/C 語言的編輯、編譯、連接。IDE選擇ARM 公司的開發軟件（SDT2.5、ADS1.2），利用處理機的Embedded-ICE 性能，通過JTAG 接口實現實時的仿真調試。使用ARM ADS，并通過JTAG仿真器，就可以實現針對ARM處理器開發板的板極調試。目前ARM ADS的最新版本為1.2。本論文使用ADS的集成開發環境CodeWarrior IDE作為代碼編譯的工具，運用ARM擴展調試器AXD進行代碼的調試和結果觀察。

為了全面測試加上Cache管理模塊后文件系統性能的提升，現以NorFlash的讀寫為例，將測試過程分為如下三步驟：

4.1.1 小文件寫入測試

將Cache數組的元素參數MAX_DISK_CACHE設為20，根據第三章介紹的文件系統API函數，在設備上建立10個文件，每個文件中寫入512字節的任意數據，寫完之后關閉上述文件。測試整個過程的完成時間。將文件數目增加到20，文件大小增加到1024字節，重復測試得下表所示結果。

未使用Cache管理系統的情況下，重復上述測試過程結果如下。

通過比較兩次測試的結果可知，采用回寫式Cache管理的文件系統在寫入操作時減少了對存儲設備的訪問次數，大大提升了對多次、小文件的寫入速度。上述兩表中對于寫入相同文件數目而文件大小不同情況下，寫入速度差別并不大。這是因為文件大小都沒有超過NorFlash操作的基本單位——塊。

4.1.2 小文件讀出測試

對于上面創建的文件再調用文件系統API函數，測試文件的讀出速度。測試分兩種情況。首先，在寫入后立即讀出，此時數據仍在Cache中，可以作為使用Cache情況下讀出速度的測試；然后，將設備掉電，Cache中數據清除，再測量讀出時間，此時可以作為未使用Cache下的讀速度。按照這樣的測試過程，得到如下兩表。

根據上面兩表結果可以看出在使用Cache和未使用Cache的情況下，小文件的讀出速度提高明顯，約有30％-40％的提升。

4.1.3 大容量數據的讀寫測試

在Flash上只建立一個文件，向文件中分別寫入大小不等的數據，測試文件的寫入速度如下表所示。

從上表可以看出，當寫入的容量較大時，寫入速度提升的并不明顯。這是因為當寫入的數據比Cache的容量大的多時，寫入數據Cache的緩沖作用將不大，數據近似地等價于是直接地寫入物理設備。測試的結果與理論分析相吻合。

將寫入的大容量數據進行讀出測試，測試的結果如表7所示。

可見讀出與Cache容量相差越大的數據，讀速度差別越小。從理論上分析可知，Cache中不能夠為大容量的數據緩存，每次讀取數據時Cache的命中率很低，均須訪問實際物理設備，因而讀速度提升不明顯。

實際應用中，應該首先知道系統可供文件系統使用的內存大小，根據可用內存情況設置高速緩存的大小。同時還應該知道，應用中需要經常傳輸文件的大小，如容量較小，則緩存單元可選用塊的大小，如需要傳輸的文件都很大，也可將數塊作為基本緩沖單元?？傊?，實際應用中，可以根據需要合理定制緩存參數，最終達到性能和資源消耗的較好折衷。

5 結束語

本文介紹了一種針對嵌入式應用的高速緩存管理方案。該高速緩存管理具有模塊化、易于移植的特點，且采用了最久未使用頁面替換算法（LRU）作為緩存替換策略，方法簡潔、資源占有率低且具有較高的緩存命中率，同時該緩存管理還具有一定的掉電保護措施。經實踐測試本方案能有效的提升嵌入式系統的讀寫速度。

參考文獻：

[1] 卓越. FAT文件系統在嵌入式塊設備系統中的優化[D].東南大學，2007.

[2] 硬盤FAT文件系統原理的詳細分析[DB/OL]. http://www.vshj.com/.

[3] Microsoft Crop. FAT32 File System Specification， 2000.

[4] 湯錚.基于嵌入式技術的電力裝置文件系統及邏輯組態的研究[D].南京 東南大學電力系統及其自動化系，2005.

[5] 孫濤. 基于ARM的嵌入式閃存文件系統的研究與實踐[D].湖北工業大學計算機系，2005.

[6] 趙俊才.DOS文件系統在Flash存儲介質上的實現[D].中國科學院計算機計數研究所，1999.

[7] 張延虎.嵌入式設備中文件系統的研究與實現[D].北京科技大學控制理論與控制工程系，2001.

[8] 馮福香.LINUX文件系統的性能、可擴展性和緩沖技術研究[D].南京大學軟工程系，2004.

[9] Bart Broekman，Edwin Notenboom(美) .嵌入式軟件測試[M].電子工業出版社，2004.

[10] Patton(美) .軟件測試(原書第2版) [M].機械工業出版社.2001.

收稿日期：2007-12-17