转一份关于yaffs文件系统的很好的文章

Independent Study 書面報告

指導教授：張立平 教授

學生：黃千庭

目錄

一、摘要

二、動機

三、YAFFS基本架構及運作

3.1 YAFFS Data Structure

3.2 Tree Node Structure

3.3 YAFFS Garbage Collection

3.4 Wear-Leveling

3.5 Partial Page Programming

四、Benchmark

4.1環境建置

4.2 Andrew Benchmark

4.3 Multiprogramming with/without hot/cold Data

五、結論

一、 摘要

　　在現在Embedded System的廣泛應用下，其硬體及軟體的建置及設計則需要相當大的考量，亦因為其所需要的效率考量下，挑選適用的內部儲存裝置則相當的重要，一般常見的內部儲存裝置為硬碟及快閃記憶體（Flash Memory），雖然硬碟的容量相當大，但是其執行速度相當的慢、體積大且不耐震，較不適用於需要效率、體積及耐震考量的Embedded System，因為Flash Memory速度快，體積小及耐震的特性，大部份的Embedded System皆使用Flash Memory做為其內部儲存裝置。如市面上最常見到的行動電話、PDA（Personal Digital Assistant）內部儲存裝置等或是數位相機所使用的記憶卡，皆使用Flash Memory。因此該怎麼操作或更有效率的使用Flash Memory，都是我們所要去關注的。

二、動機

Flash Memory目前分為兩種：NOR Flash Memory及NAND Flash Memory，尤於NAND Flash Memory有較快的Erase Time、Small Size及成本較低的特性下，使得NAND更適用於Embedded System。Flash Memory是一儲存裝置，若要使用此儲存裝置，亦須要在Flash Memory上使用File System。在一般的Block Device（e.g. Disk）上使用的File System，如：NTFS、FAT32和ext2等等，都可用於Flash Memory上，但是這些File System並非專為Flash所設計的，所以無針對Flash的特性去操作，因些需要透用FTL（Flash Translation Layer）將其做轉換的動作，如下圖所示：

圖一

使用非專為Flash所設計的File System（Flash-Specific File System），則需要透過FTL做轉換，才能存取Flash Memory，但使用FTL會多了一個轉換的過程，會浪費轉換的時間，對於相當要求效率的Embedded System來說，不太適用，因此則有專為Flash Memory所設計（Flash-Specific File System）的File System，如：JFFS、JFFS2和YAFFS等等。使用此種Flash-Specific File System則不再需要透過FTL來做轉換，如圖二所示：

圖二

JFFS主要用於NOR Flash Memory上面，YAFFS則是用於NAND Flash Memory上。YAFFS是由Aleph One公司所製作，適用於相當多的Embedded Operation System，如：eCOS、WinCE等等，並且在GNU GPL的條款下，開放其原始碼，因此可自Aleph One公司取得YAFFS之原始碼並可加以修改，使之符合自己的需要。在此我們主要探討使用NAND Flash Memory的Flash-Specific File System-YAFFS。

三、YAFFS基本架構及運作

　　YAFFS為一For NAND Flash Memory的Flash-Specific File System，它在設計上必會針對NAND Flash Memory的特性來設計，如在Data Structure的設計上與平常的File System必定不同，還有專為Flash Memory設計的wear-leveling Algorithm以避免同一區塊過度存取而造成毀損等等。接下來則會介紹YAFFS所使用的Data Structures、Garbage Collection及Wear-Leveling等的基本架構及運作。

3.1 YAFFS Data Structure

　　

　　在一般的作業系統中，會使用Disk或其他儲存裝置以儲存檔案，並使用較快速度的RAM（Random Access Memory），將欲存取使用的檔案複製至RAM中，再進行存取，最後再寫回儲存裝置。利用RAM可加速整體的執行速度及效能。另外我們會設計一些Data Structure，包括在儲存裝置上使用的Data Structure及在RAM上使用的Data Structure。在儲存裝置上使用的Data Structure是為了管理在儲存裝置上所儲存的資料及其屬性（如User ID、Group ID及存取權限等）等，而RAM-Resident用以管理從儲存裝置所讀出來的檔案及資料或是邏輯位址（Logical Address）對應到儲存裝置實體位址（Physical Address）的記錄表格等，如圖三及圖四。如此系統可在RAM中迅速找到欲存取的資料或從儲存裝置中讀出資料到RAM中。

圖三-從儲存裝置讀取資料至RAM中

　　而YAFFS也有使用RAM-Resident Data Structure和On-Flash Data Structure。

以下列幾個YAFFS主要的物件（Object）皆屬於RAM-Resident Data Structure：

• yaffs_Object：一個yaffs_Object可以是檔案（File）、目錄（Directory）、SoftLink 或是Hardlink其中一種，而每一個yaffs_Object都會對應到一個yaffs_ObjectHeader，而yaffs_ObjectHeader則是用以儲存此yaffs_Object的一些屬性值，例如該yaffs_Object是File或是Directory，此yaffs_Object的parentObjectId為何…等等。yaffs_Object亦有如下的目錄結構：
• parent：此欄位用以指向其父目錄（parent Directory）。
• siblings：此欄位用以連結同一個目錄下的所有yaffs_Object
• children：若此yaffs_Object為一個目錄，則此欄位會指向此目錄下的yaffs_Object集合。
• yaffs_Tnode：yaffs_Tnodes構成一棵Tree Structure，此Tree Structure可加速搜尋一個File中的Data Chunk。當其File Size愈來愈大時，其Tree Structure的也會跟著長高，而其最高限制的Level為６。詳細資訊在接下來的部份會加以介紹。
• yaffs_Device：yaffs_Device儲存裝置的相關資訊，類似於VFS（Virtual File System）的SuperBlock。儲存著用來存取MTD（Memory Technology Device）的資料或存取NAND Data的函數（Function）。
  

每個yaffs_Object都會有一個yaffs_ObjectHeader，yaffs_ObjectHeader為On-Flash Data Structure。存在於Flash上，當Flash掛載上時，會為每個yaffs_Object找尋該物件的yaffs_ObjectHeader，讀出yaffs_Object的相關資訊。yaffs_ObjectHeader所儲存的資訊如下：

圖四-yaffs_ObjectHeader記錄內容

• Name：yaffs_Object的名稱。
• ParentObjectID：此欄位記錄yaffs_Object的父Object ID。
• Type：說明此yaffs_Object是File、Directory、SoftLink或是HardLink。
• Protection（Only For File）：表示此yaffs_Object的權限為何。
• UID（File Only）：屬於哪個User ID。
• GID（File Only）：屬於哪個Group ID。
• Time of Last Access（File Only）：最後存取時間。
• Time of Last Modification（File Only）：最後修改時間。
• Time of Last Change（File Only）：
• File Size（File Only）：檔案大小。
• equivalentObjectID（HardLink Only）：僅用於HardLink。
• Alias（SoftLink Only）：僅用於SoftLink。
• CheckSum：Name的Checksum，計算Name避免不一致。

YAFFS的最小儲存單位為一個Page或Chunk，在YAFFS中Page及Chunk所佔的大小相同，因此可視為相同的東西，但實際上兩個名詞所表示的意義不同，Page所指的是NAND Flash Memory上的實體資料儲存區，而Chunk所表示的是yaffs_Object所配置到的邏輯資料儲存區，Chunk的Size可以和Page不同，但在YAFFS中是相同的。如圖五、圖六，當Page與Chunk Size相同時，為一對一的關係，此時Logical-to-Physical Address Translation的Mapping Table則會佔去不少RAM的空間，Page和 Chunk大小不同時，假設為一對二時，此時Logical-to-Physical Address Translation的Mapping Table Size則可減少為一半，如此可有效減少Mapping Table在RAM中所佔的空間。

圖五-Page與Chunk Size相同時的對應關係

圖六-Page與Chunk Size不同時的對應關係（一個Chunk對應兩個Page）

資料儲存時是以一個Page一個Page的方式寫入。Block為多個Page所組成的一個單位，一個Block中有32個Page，Block亦為一個Erase Unit（即是以一個Block為單位做清除的動作）。如圖七示：

圖七

在Flash Memory掛載上時，其會先掃瞄過所有中的Block所有Pages，以便把所有的yaffs_Object在RAM中建立起來。根據讀到的Page其Spare Area中Tag的chunkID值的不同，會有下列不同的處理方法：

1. chunkID >0：表示該Page為儲存某個yaffs_Object的Data，並根據該Tag中的ObjectID到RAM中尋找該yaffs_Object是否在RAM中已建立，若建立則將該Page加入至所屬的yaffs_Object中，若未建立則根據ObjectID去建立一個對應的yaffs_Object，並將該Page加入至對應的yaffs_Object中。

2. chunkID =0：表示該Page為yaffs_ObjectHeader，並根據此Page的Spare Area中Tag的ObjectID到RAM中尋找該yaffs_Object是否在RAM中已建立，若建立則將該Page加入至所屬的yaffs_Object中，若未建立則根據ObjectID去建立一個對應的yaffs_Object。建立完後再根據yaffs_ObjectHeader 中的ParentObjectID到RAM中尋找對應的Parent yaffs_Object，並將原yaffs_Object中的Parent指向Parent yaffs_Object。

在掃描完所有的Block後，會把Flash Memory上的所有File、Directory、SoftLink或HardLink建立成對應的yaffs_Object，以便修改其屬性值。在建立完所有yaffs_Object及其與目錄之間的關係後，會在RAM中形成一種階層式（Hierarchy）的架構，如圖八所示：

圖八

在YAFFS中，File中的Data是儲存在固定大小的Page中，其大小為512 Bytes，每一個Page亦會有一個對應的Spare，其大小為16 Bytes，用以儲存該Page的相關資料。

圖九

Spare所儲存的資料如下所示：

圖十

• Tags：
• chunkID：指相對於此yaffs_Object的第幾個Chunk。當Chunk ID為0時，則表此Chunk所儲存的是yaffs_ObjectHeader。
• serialNumber：用以辨別哪個Chunk為最新的Chunk。當更新此Chunk時，其serialNumber會加1並寫入至其他Block的Chunk中，並將原Chunk的設為Invalid（表此Data Chunk已無效），但若在將該Chunk設為Invalid之前則發生了斷電（Power Lost）的突發事件，當電源回復並再重新掃描Flash Memory時，會檢查某一yaffs_Object到有兩個一樣的Chunk（其ChunkID相同），但其serialNumber不同，則會比較此二Chunk的serialNumber，以辨別出哪個Chunk為較新的Data，並將較舊Data的Chunk設為Invalid。如下表所示：
  

說明： 當系統發現有兩個相同chunkID的chunk，則檢查兩個chunk的serialNumber。此圖可確定serialNumber為2的必定比serialNumber為1的還新，則將serialNumber為1的chunk設為Invalid。	說明： 若兩chunk的serialNumber如上，則比較方法為將其中一個chunk的serialNumber值取出，並做(serialNumber+1) mod 4，運算後的值x。若x等於另一個chunk的serialNumber，表示此chunk為較新的，則把另一個chunk設為Invalid。此圖即可確定serialNumber為0的較serialNumber為3的更新。

* byteCount：表示該yaffs_Object佔此Chunk多少個Byte。

• objectID：此Chunk屬於哪個Object的Objecct ID。
• ECC：Tags的Error Correction Code。
• unusedStaff：保留未使用的欄位。
• ECC Data：Data Chunk的Error Correction Code。
• Page Status：當值為0時，表示此值為Invalid。
• Block Status：保留未使用的欄位。

3.2 Tree Node Structure(Tnode Structure)

　　系統欲存取裝置上的Data時是以Logical Address（相對於該File所產生出來的偏移位址）的方式到所指定的位址進行存取，若欲到實體儲存裝置上取得Data，則須再經過一個機制的轉換，將Logical Address轉換為Physical Address（實際儲存裝置的位址），才可從儲存裝置上讀出Data至RAM中。這個機制最簡單的方法就是在RAM上建立一個Logical Address到Physical Address的對映表格（Mapping Table）。直接將Logical Address對映至Physical Address。如圖十一所示：

圖十一-在RAM中建立Logical Address對應至Physical Address的對映表格

在YAFFS中也使用了Logical Address到Physical Address 的對映機制。所使用的機制稱之為Tree Node Structure或Tnode Structure。

　　Flash Memory掛載時，YAFFS會為每個File在RAM中建立一個Tree，當有一個要求要存取某個Chunk（或Logical Address）時，則會經由Tree Node Structure的轉換方式，找到Chunk的Physical Address。

使用Tree Node Structure的優點為位址轉換時間較迅速。Tree Node Structure的轉換Time Complexity為O(log N)，若是直接使用Logical Address to Physical Address的Mapping Table，則位址轉換為線性搜尋（Linear Search），此種搜尋方式的Time Complexity為O(N)。YAFFS採用此種方式來做為位址轉換的機制可提升整體的存取速度。

　　Tree Node Structure是由多個Tree Node（或Tnode）所組成。依據Level的不同而分成兩個部份：

• Internal Tnode：每個Internal Tnode由8個Pointers所組成。
• Lowest-Level Tnode（Level 0 Tnode）：每個Lowest-Level Tnode由16個Entries所組成。

圖十二

在Tree建立好後，當系統發出要存取該File的某個Chunk時，例如：Chunk 0x235，就要在Tree上做Traverse的動作，以找尋到要求的Chunk。Traverse的步驟如下：

1. 將十六進制轉化為二進制：0x235  0000001000110101

2. 將二進制切割成000.000.100.011.0101，每一個切割區代表一個Level，由於Lowest-Level包含有16個Entries，因此切割出4個Bit（Bit 3 to 0）。Internal Level的Tnode皆包含8個Pointer，因此其餘皆切割為3個Bit。

3. 根據所切割出來的Bit整理成下表：

Level	Bits	Selected Value
3 or more if they exist	>=10	Zero
2	9 to 7	100 binary = 4
1	6 to 4	011 binary = 3
0	3 to 0	0101 binary = 5

4. 根據表格中各Level的值進行Traverse。

Step1：Level 2100=4	Step2：Level 1011=3
Step3：Level 00101=5

當Tree Node Structure剛開始建立時，僅會建立Lowest-Level Tnode，當File所配置的Chunk數超過16個時，則此Tree會建立一個internal Tnode，並將其第0個Pointer指向原本的Lowest-Level Tnode。當讀取到的Chunk數愈來愈多時，會一直新增Tnode，且Tree亦會愈來愈高，其Max-Level最大為6。

Step1	Step2
Step3	Step4

　　在File已在RAM建立好Tree Node Structure後，若此File的Size變大時，則會再多配置Chunk給此File，在將Data寫入至Page後，則會去更新File的Tree Node Structure，將新配置到的Chunk加入至Tree Node Structure中，更改步驟如下：

1. 搜尋新配置到的Chunk ID。

2. 若在Internal-Level搜尋的過程中，發現沒有Tnode，則建立一個Internal-Level的Tnode。

3. 當搜尋到Lowest-Level時，若也無Tnode存在，則建立一個Lowest-Level的Tnode。

4. 根據Chunk ID中Level 0所代表的值x，到Lowest-Level Tnode中的第x個Entry中檢查有無該Chunk的實體位址存在，若沒有則將實體位址填入該Entry，若已存在則將比較兩Chunk在Spare中的serialNumber，將較新的Chunk的實體位址寫入該Entry中，並將舊的Chunk設為Invalid。

1. 搜尋新配置到的Chunk ID	2. 在Internal-Level搜尋過程中，發現無Tnode存在，建立一Tnode
3. 在搜尋過程中，發現無Lowest-Level Tnode存在，則建立一Lowest-Level Tnode，並將該Chunk ID寫入對應的Entry中

3.3 YAFFS Garbage Collection

Garbage Collection主要是用於將已不必要存在且浪費空間的Block做回收的動作，以增加可用的Block數。而Garbage Collection只有某些事件發生時才會執行。

在YAFFS中只有在下列事件發生時會執行Garbage Collection：

• 將Data寫入Flash Memory
• 更新yaffs_ObjectHeader

而YAFFS的Garbage Collection又分成兩種Mode：Aggressive Mode及Passive Mode，其相異點如下表所示：

	Aggressive Mode	Passive Mode
執行條件	ErasedBlocks <= (PreservedBlocks + 1) ErasedBlocks：空Block數 PreservedBlocks：保留Block數	ErasedBlocks > (PreservedBlocks + 1)
檢查回合數	Iterations = (EndBlock-StartBlock) + 1	1. Iterations=(EndBlock-StartBlock) + 1 2. Iterations = Iterations / 16 3. Iterations = 200 if Iterations >200

　　YAFFS的Garbage Collection執行步驟如下：

1. 從currentDirtyChecker到End Block之間尋找Dirtiest Block（包含最多Invalid Chunk的Block）

圖十三

2. 將currentDirtyChecker重置至所發現的Dirtiest Block的位置

圖十四

3. 將Dirtiest Block中的Valid Page複製至其他的Empty Chunk中。

圖十五

4. 再將Dirtiest Block清除成Empty Block。

圖十六

3.4 Wear-Leveling

　　當Flash Memory在使用時，常常會對Flash Memory內的某個檔案做修改的動作，若此時檔案的大小更動而需要更多Page時，且在Flash Memory內仍有空的Block，則會配置空的Block給該檔案，若Flash Memory內已無空的Block，則會執行Garbage Collection的動作，清出空的Block以供使用。而在挑選空Block或使用Garbage Collection時挑選Dirtiest Block時，可能會造成部份的Block常常被挑選，而其他Block則很少被挑選配置。

圖十七

由於Flash Memory的特性，那些常常被挑選的Block可能會因為過度的使用而造成損毀，為了避免這種負擔不均的情形發生，因此在大部份的Flash-Specific File System上都會設計一種方法以避免此種情形發生，此方法即稱為Wear-Leveling。

使用Wear-Leveling時，在挑選Block時不會常常固定在某幾個Block上，而可使大部份Block的存取次數能夠平均，不會造成部份Block過度存度而造成毀損。

圖十八

　　

　　在YAFFS中並沒有明確的使用Wear-Leveling，而是以下面兩種策略取代：

1. 保留部份Block，若部份Block毀損時可使用保留的Block取代。

2. 使用「隨機挑選Block」（Random Block Selection），如此可避免不常被挑選的Block一直沒人使用。

但是實際在觀察YAFFS的原始碼時，並未發現有使用"Random Block Selection"，在詢問YAFFS作者Charles Manning是否有將"Random Block Selection"實作出來後，其回信如下：

「No it is not.

For the most part wear levelling is not a problem for a log-structured file
system like yaffs because usage cycles tend to clear out and reuse areas.

Wear levelling is much more an issue for file systems like FAT which use block
locations. Some blocks (eg. those used for storing the FAT tables) get
heavily used.

I have done some very heavy accelerated lifetime testing (eg writing over
150Gbytes of data into a device) with no indications of any wear levelling
issues. Very few blocks had reached even one tenth of their lifetime」

在Charles Manning信中提到YAFFS實際上並未使用"Random Block Selection"，因此YAFFS的Wear-Leveling所依賴的只有第一個策略而已。

3.5 Partial Page Programming

當我們要將Data寫入某個Page時，會先將該Page清除（Erase），即該Page的內容全為1，因為在Flash Memory中，僅能將Bit 1改成Bit 0，所以在清除過後所有的Bits皆會為1。在清除Page後才能將資料寫入，例如Page內的Data為10111010，要將之改成01010101，則會先將Page清除為11111111，再更改成01010101。

圖十九

　在NAND Flash Memory中，存取資料的最小單位為一個Page。若使用Partial Page Programming則修改Page中的Data時可以更改部份的Bit而不需要將Page Erase後才更改。例如Page中的Data為10111010，要將該Data改成10100010則只需將其中兩個Bit更改為0即可，不需先Erase再寫入。

圖二十

使用Partial Page Programming常會發生一種問題，即是在更改Bit的時候可能會有"走樣"的情況而有沒有完全更改過來，例如Page中的Data為11111111，欲將之改成00000000，但在更改的時候卻未完全更改過來，而使的更改後的資料可能變為00111101，仍有部份的Bit未更改為0。

圖二十一

　　在YAFFS中也使用了Partial Page Programming，主要用於將某個Page設為Invalid，即更改該Page的Spare中pageStatus。當Page為Valid時，其Spare內的pageStatus內容為全1的狀態，即未更改pageStatus，若要將近改為Invalid，則將pageStatus內容改為0（即全為0）即可。但是由於Partial Page Programming會導致的錯誤，使得pageStatus的內容可能會無法更改為0，因此在YAFFS中則採用了一種方法，即更改後的值，其值的二進制中，Bit為1的個數若小於6，則表示該Page為Invalid。否則視為Valid Page。

圖二十二

四、Performance Measurements

　　Flash-Specific File System有相當多的選擇，欲使用何種File System端看於設計者的需求，但在相同的需求下，該挑選何種File System則可依其執行效能及該File System可能額外所耗去的資源來做考量，在此則會評估使用yaffs在nandsim上時的效能及其可能所耗用的額外資源等。

4.1 環境建置

　　測試yaffs與nandsim的效能之Hardware及Software環境如下：

Hardware	Software
CPU Intel Dual Core 3.0GHz RAM 1.0 GHz Dual Channel Number of CPUs 1 Disk subsystem SATA	OS Windows XP SP2 Other VMWare 5.0（Fedora Core 5+512 MB+yaffs2+Linux Kernel 2.6.17.9+nandsim）

在Fedora Core 5的NANDSim掛載時，亦需加入參數如下：

modprobe nandsim second_id_byte=0x71 access_delay=180 programm_delay=520 erase_delay=1.85
second_id_byte：設定Nandsim大小，其參數值參考nand_ids.c
access_delay：Initial page access delay（micro second）
programm_delay：Page Program Delay（micro second）
erase_delay：Sector erase delay（milli second）

4.2 Andrew Benchmark

　　Andrew Benchmark主要的測試步驟分為五個階段：

• Phase 1：Creating Directories
• 使用指令為：mkdir
• Phase 2：Copying Files
• 使用指令為：cp
• Phase 3：Recursive Directory Stats
• 使用指令為：ls -l
• Phase 4：Scanning each file
• 使用指令為：grep+wc
• Phase 5：Compilation
• 使用指令為：make

使用Andrew Benchmark會挑選一合適的Source Tree來做Benchmark，其中會包含多個檔案以供執行Andrew Benchmark的時候使用，在此測試中共有71個檔案。其File Size Range所佔的百分比如下：

圖二十三

在完成所有環境建置後，即開始進行Andrew Benchmark的測試，其測試的結果如下圖：

圖二十四

在執行Andrew Benchmark時，其執行過程中會將其Source Tree的內容複製至目的地，在此我們則要測試除了原本的Source Tree所佔的空間外，yaffs額外所使用的管理空間約佔多少。

在執行完Andrew Benchmark後，算出原本Andrew Benchmark Source Tree所佔的空間及執行後Source Tree在nandsim上所佔的空間如下圖所示：

圖二十五

　　在執行完Andrew Benchmark後發現，在nandsim上一模一樣的Source Tree卻比原本的Source Tree多出了59.47k，這是yaffs在管理檔案所花費的額外成本，例如每個檔案所佔的Spare Area等等，都會耗用額外的空間。

4.3 Multiprogramming with/without hot/cold Data

　　在此測試中，會包含兩種Task：

• TaskA：Sequentially Write 16K Bytes of Data（Hot Data）
• TaskB：Repeatedly Update 16 Bytes of Data（Cold Data）

根據上述Tasks，執行下列六種執行方式，並會在各個方式下產生Response Time及Throughput，其中(x,y)表示有x個TaskA及y個TaskB同時執行：

• (0,1)：Update 16 Bytes of Data
• (1,0)：Write 16K Bytes of Data
• (1,1)：Mixture of Hot Data and Cold Data
• (2,2)：Multiprogramming Testing
• (4,4)：Multiprogramming Testing
• (8,8)：Multiprogramming Testing

在執行完後，針對TaskA及TaskB觀察在各種執行方式下的Response Time及Throughput。針對Response Time的部份，是以RDTSC的方式取得暫存器中的Clock數，Clock數愈多，表示其所花費的時間愈長。

• TaskA
• Response Time

圖二十六-Response Time of TaskA

在TaskA的Response Time中，在各種執行方式下，由於其TaskA的數量是以指數遞增，而其Respnose Time在統計圖中亦以指數呈現上升的趨勢，可知在TaskA數量愈多的情況下，其回應時間愈長。

• Throughput

圖二十七-Throughput of TaskA

在TaskA的Throughput中，其統計圖與TaskA的Response Time呈現相反的情況，亦即其圖形是以指數遞減的趨勢，表示當TaskA的數量愈來愈多時，其Throughput愈低。

• TaskB
• Response Time

圖二十八-Response Time of TaskB

在統計圖中TaskB的Response Time亦與TaskA相同，當TaskB數量愈多，其Respnose Time亦愈高（表示愈慢）。

• Throughput

圖二十九-Throughput of TaskB

TaskB的Throughput亦會因為TaskB的個數增加而逐漸降低，表示當系統對nandsim做存取時，TaskB個數愈多，其每秒寫入的Byte數會逐漸減少。

五、結論

　　

YAFFS為目前常用的一種NAND Flash Memory的Flash-Specific File System。因此對YAFFS有個深度的了解將對Flash-Specific File System的製作或對YAFFS的修改都有很大的幫助。在比較YAFFS和JFFS2之後，針對YAFFS相對於JFFS2的優劣做以下的禪述。

在Trace YAFFS的程式碼時，發現YAFFS的Garbage Collection尋找Dirtiest Block及尋找Empty Block出來配置時所使用的方式皆為Linear Search的方式，其Time Complexity為O(N)，而不像JFFS2是以Link List的方式去管理Dirty Block和Empty Block，在尋找Dirty Block及Empty Block時，只需從List的頭或尾取出即可，其Time Complexity為O(1)。因此在這邊發現，YAFFS在這邊的效率是明顯的比JFFS2差了一點。

　　YAFFS採用Tree Node Structure，將之儲存在RAM中，當系統需要某一File的某一Chunk時，即可透過Tree Node Structure進行搜尋的動作，其搜尋的Time Complexity相當於O(log N)，可迅速的找到所需要的Chunk。

　　YAFFS並未實際的做出Wear-Leveling，因此還是會造成部份的Block過度存取，會造成此結果的另一原因也是因為YAFFS在Wear-Leveling的應對策略"Random Block Selection"上並未實際做出來。在YAFFS的Wear-Leveling上可參考yaffs2的做法，在某個次數下則使用"Random Block Selection"，可有效的平均每個Block的存取次數。

　　使用Partial Page Programming會使得NAND Flash Memory的硬體設計上相對的較困難，因此新的NAND Flash Memory已不允許再使用Partial Page Programming，所以在YAFFS2上已不再使用Partial Page Programming。YAFFS亦不可在新的NAND Flash Memory上使用，因為其使用的Partial Page Programming可能會造成資料上的錯誤。

針對YAFFS劣於JFFS2的部份，也許可以將其部份加以修改，優化其執行效率，使之符合我們的需求。

References

• Aleph One
• Memory Technology Device(MTD) Subsystem for Linux

Retrieved from ""