基于位圖示法的NSFS文件系統設計

摘 要： 文件系統是操作系統進行數據存儲的核心功能組件，它具有數據的存儲和數據的管理功能。失去了文件系統的操作系統只能進行數據計算處理，而不能存儲計算結果，所有重要的數據和信息在計算機斷電的時候都會消失。可以說文件系統是現代操作系統不可分割的基本功能組件。在信息化高速發展的今天，嵌入式操作系統技術中的文件系統有著越來越重要的地位，航空領域的嵌入式操作系統必須提供一個方便易用高性能高可靠的文件系統。NSFS文件系統是基于位圖示法設計的具有高可用性的文件系統。它的結構簡潔，可以根據文件大小自適應地分配簇大小，空間浪費極小，具有良好的性能和很大的靈活性，并且具備較高的可靠性。

關鍵詞： 位圖示法； 文件系統； 操作系統； NSFS文件系統

中圖分類號： TN911?34； TP316.2 文獻標識碼： A 文章編號： 1004?373X（2013）14?0089?04

Design of NSFS file system based on bitmap method

SHE Nan， XU Xiao?guang， CHEN Xiao?lei， XING Liang

（Aeronautical Computing Technology Research Institute， Xi’an 710119， China）

Abstract： The file system is the core function element for data storage of an operating system. It is applied to data storage and data management. Any operating system without file system can only calculate data， but the calculated results can not reside in random access memory， and all the data and information will be lost after computer power off. Actually file system is a necessary functional component of a modern operating system. As information technology is improving rapidly nowadays， the file system in the embedded operating system has been more and more important in various fields. In aviation industry， the embedded operating system must provide a convenient file system which should be easy to use and provide high performance. NSFS is a file system with high availability based on bitmap method. It is designed as a concise architecture. Moreover， the cluster size can be allocated based on the file size adaptively with minimal wasted storage space. In summary， NSFS is good at performance with high flexibility and reliability.

Keyword： bitmap method； file system； operating system； NSFS file system

0 引 言

隨著計算機存儲器硬件設計水平的提高以及計算機軟件規模的日益增加，操作系統中的文件系統也越來越不能滿足大規模數據存儲和高效數據讀寫的需求，文件系統作為操作系統中的一個重要組件，近些年來它已經在各種存儲設備中有了更多的設計與實現，設計思路和方法都各不相同，但是目的都是為了使得文件系統能夠支持更多的存儲設備，并且能夠在這些存儲設備中具有同樣高效的讀寫能力，數據的插入和刪除具有較好的均衡性，文件系統的復雜性應該盡可能的不影響操作系統的數據讀寫。所有的文件系統在設計上基本都是采用了位圖示法，通過數據位的圖示來表示存儲器數據的存儲情況。但是這些文件系統可能會通過Trie樹或者B*樹等不同方法進行文件的索引。對于不同的存儲器，可能還會采用一些必要的手段來保證存儲器的讀寫平衡和有效讀寫等。

NSFS就是根據位圖示法設計的一種高可靠高性能的文件系統，它具有高效的隨機數據讀寫能力，并且提供數據恢復能力，保證操作系統在突然掉電的情況下文件系統仍然能夠進行數據的恢復，不會導致文件系統的損壞。

在嵌入式領域，這種高可靠高性能的文件系統是非常重要的，相比于其他文件系統，NSFS設計更加簡潔清楚，它在嵌入式操作系統中具有更低的CPU消耗和更高的安全性和實時性，因此它的應用前景非常廣闊。

1 位圖示法文件系統概述

位圖示法是一種根據位圖結構中的數據位來表示存儲卷或分區中的簇的分配和使用情況。它結構簡單，易于實現，大多數文件系統都采用了位圖示法進行存儲空間的管理。

比如，Windows操作系統中的FAT文件系統采用了文件分配表，它是FAT文件系統中用于磁盤數據索引和定位引進的一種鏈式結構。在FAT文件系統中，存儲器具有專門的文件分配表區[1]（FAT區），它描述了文件系統中每個文件所占用的存儲空間大小并將該存儲空間結構化為一個文件的簇分配鏈表。文件的存儲依照FAT表中的簇鏈式數據結構來進行。同時，FAT文件系統將組織數據時使用的目錄也抽象為文件，以簡化對數據的管理。

FAT文件系統之所以有12，16，32不同的版本之分，其根本在于文件分配表用來記錄任意一簇鏈節點的二進制位數。以FAT16為例，每一簇在FAT表中占據2字節（二進制16位）。所以，FAT16最大可以表示的簇號為0xFFFF（十進制的65 535），以32 KB為簇的大小的話，FAT16可以管理的最大磁盤空間為：32 KB×65 535=2 048 MB，這就是為什么FAT16不支持超過2 GB分區的原因。

FAT文件系統的特點是通過文件分配表進行磁盤空間的管理和文件空間分配，邏輯清晰，文件的創建和刪除效率很高，文件數據則是根據存儲的局部化原理進行讀寫，目錄以及文件的數量無限制，文件組織方式為樹型的目錄層次結構。

對于Unix/Linux操作系統中常用的UFS以及ExtX文件系統來說，它采用了inode節點結構來表示每一個文件。然而存儲塊和inode節點的管理方式依然是采用位圖示法。

以Linux操作系統中的ExtX文件系統為例，存儲器的0號塊組中的超級塊[2]定義了文件系統的主要常數信息，組描述符表[3]表示了文件系統中的塊組信息，塊位圖塊則是塊組內所有塊的管理結構位圖，它表示了塊組內的塊使用以及分配情況。同樣，i節點位圖是塊組內所有inode節點的管理結構位圖，它表示了塊組內的inode節點使用以及分配情況。

綜合幾種文件系統的特點，它們的簇大小都是固定的，在卷或者分區的格式化時已經確定，不同的文件系統都有一些缺點。FAT文件系統中的大文件隨機讀寫性能較差，空間使用效率相對較低。ExtX文件系統中位圖表示中i節點位圖的大小決定了inode節點的數量，ExtX文件系統的結構較為復雜，可擴展性較差。

2 文件系統原型

針對嵌入式操作系統對文件系統高性能、高可靠的要求，本文提出了一種具有可變簇大小并且能夠自適應動態分配[4]的文件系統模型。可變的簇大小不僅能夠有效地使用存儲空間，做到存儲資源的極大利用，而且能夠較好地提高數據的隨機存取性能。自適應動態分配算法是對用戶透明的，用戶不必關心簇的分配策略和方法，因此在文件系統的使用中具有較好的移植性和重用性。該文件系統在設計實現中將其命名為NSFS文件系統。NSFS文件系統的結構定義如圖1所示。

圖1 NSFS文件系統架構

NSFS文件系統是基于位圖示法的數據管理模型，采用了自適應的動態簇分配方法。其主要特征是根據文件的大小自動決定數據分配簇的大小，這樣生成的文件具有較好地隨機讀寫性能。對于小文件來說，分配較小的數據簇，從而減少存儲空間位圖中的文件簇鏈式結構的位圖項大小，這樣每次可以讀取更多的文件簇信息，減少定位文件偏移的讀操作次數。對于大文件來說，分配較大的數據簇，這樣的文件中簇鏈式結構的位圖鏈就會較短，從而在每次讀寫文件數據時可以在計算文件讀寫位置指針時更快地找到待讀寫的數據簇。對于存儲設備的存儲容量日益增加的情況下，文件系統的存儲卷或分區的容量也越來越大，對于存儲器的大容量分區中的大型文件，NSFS文件系統的空間位圖可以減少尋找文件偏移時讀取磁盤的次數，降低外部設備的IO操作對于系統性能的提升非常重要，文件系統讀寫性能的提升會非常明顯，因此NSFS文件系統可以極大地提升操作系統的數據讀寫能力。

NSFS文件系統的配置能力很高，許多參數都能夠動態配置，只有諸如扇區大小這種存儲器硬件相關的定義無法配置。其中可配置的參數定義包括磁盤根的保留扇區數目，分區的頭保留扇區數目，分區的尾保留扇區數目，磁盤分區表的擴展扇區數目，文件系統的大端存儲標識[5]。在這些參數需要確定下來之后，文件系統就可以進行初始化工作。如果文件系統還未進行格式化，那么根據文件系統需要的分區數目以及分區信息，就可以格式化該文件系統。如果文件系統已經格式化，那么可以從磁盤根的磁盤分區表中讀出文件系統的分區信息。

采用動態簇大小的NSFS文件系統中的常量信息采用8 B數據記錄，理論上可以支持的最大存儲器容量可以達到（264-1）×（29）B，約為8 192 EB。NSFS文件系統理論上可支持的最大文件可以達到（264-1） B，約為18 EB。由于硬件配置的不同以及根據工業標準對磁盤扇區大小以及最大數目的限制，實際的分區大小目前只有2 TB。

NSFS文件系統中的每個文件的簇大小是不固定的，這主要通過該文件所屬目錄項中的文件簇大小進行標識。這樣創建一個文件時，文件的簇既可以通過系統默認配置分配，也可以通過指定參數進行分配，系統默認的簇大小分配如下：

小于等于1 MB的文件的簇大小為512 B；

大于1 MB且小于等于64 MB的文件的簇大小為2 KB；

大于64 MB且小于等于4 GB的文件的簇大小為128 KB；

大于4 GB且小于等于256 GB的文件的簇大小為8 MB；

大于等于256 GB的文件的簇大小為512 MB。

這樣的簇大小分配保證了文件系統的空間浪費最大小于=0.195 3%，平均來說空間浪費小于·2=0.097 7%，即文件系統的空間使用效率極高。

對于某個特定文件大小的文件，在創建文件時可以根據需要配置該文件的簇大小而不必局限于系統默認的定義，這樣可以極大地提高文件系統的靈活性。

NSFS文件系統首先將整個存儲器分為磁盤根區和數據區2部分。磁盤根區從存儲器開始部分（0柱面，0磁道，1扇區）起，其大小可以根據需要改變，但是磁盤根區只能有一個。數據區的缺省配置中最多可以有16個，也可以根據需要進行無限制的擴展，任何一個分區的大小和起始位置可以根據格式化的參數進行劃分。

磁盤根區用來從存儲器加載并引導操作系統，其不固定的大小可以保證不同的操作系統加載程序都能夠從存儲器引導。首先，計算機上電后加載存儲器的第一個扇區（引導扇區）到內存中，引導扇區的引導程序[6]將讀取第二個扇區（磁盤分區表）獲取磁盤的文件系統信息。然后讀取操作系統啟動分區中的內核文件到內存并跳轉到內核中執行硬件的初始化、操作系統初始化以及文件系統初始化。

數據區包括3部分：頭保留區、文件分配表區、數據區和尾保留區。

頭保留區：用來進行操作系統的第二段加載或者存儲其他操作系統信息，從而提高文件系統的靈活性和兼容性，可以讓文件系統同時支持不同的操作系統。

文件分配表區：用來記錄文件數據區的分配情況，其表項長度為8 B，它以位圖示法表示了存儲器的空間分配情況，它還主要用來管理存儲器的目錄和文件。

數據區：用來存儲數據的區域，該區域的數據通過讀寫保護標志來保證數據的可靠性以及文件系統的完整性。其中目錄與文件都作為基本文件由操作系統統一管理。

尾保留區：用來存儲其他的備份或者校驗信息，也可以根據情況定義文件系統的擴展功能，極大地提高了NSFS文件系統的靈活性。

3 性能評價

文件系統的操作從根本上來講，都是存儲設備的讀寫。對于文件系統的基本接口創建、刪除、打開、關閉，讀文件、寫文件等操作來說，在文件系統上層通過文件系統的管理層進行文件以及目錄的邏輯管理，底層都是文件系統對于存儲設備上文件的讀寫操作。文件系統管理接口的性能差異可以忽略不計，而順序讀寫效率則主要依賴于硬件I/O操作的性能。文件系統的性能主要是指數據文件的隨機讀寫操作的效率。文件的隨機讀寫操作中，最重要的步驟是文件定位，該步驟需要通過多次I/O操作來定位讀寫文件的偏移位置。定位文件偏移之后的讀寫操作大多都是順序讀寫，其性能一般取決于設備硬件。因此要評價文件系統的性能，最重要的評價指標就是文件的隨機讀寫操作中文件定位的效率。以下分為目錄讀寫、小文件讀寫、大文件讀寫來討論NSFS文件系統的性能。

3.1 目錄讀寫性能

由于NSFS文件系統將文件目錄都抽象為文件。因此執行創建、刪除、打開、關閉文件時，NSFS文件系統實際上是讀寫文件所屬的目錄文件，而目錄文件一般來說屬于小文件類型，其性能可以參考以下對于小文件進行讀寫的性能對比。

3.2 小文件讀寫性能

對于小文件讀寫來說，以讀寫偏移32 KB的一個64 KB文件為例，以下討論了USF/ExtX，FAT32與NSFS的性能對比。

在NSFS文件系統中，假設待讀取文件的文件分配表中的表項為扇區內連續的，文件簇大小為512 B，則需讀取的文件分配表表項為=128，需讀取的文件分配表表項扇區數目為=2，即需要通過2次I/O操作就來定位到64 KB文件的32 KB偏移。

對于UFS或ExtX文件系統來說，小文件的隨機讀寫操作一般通過12個一級直接塊指針或者一個一級間接塊指針即可完成，文件定位所需的I/O操作次數一般不超過2次。

在FAT32文件系統中，假設待讀取文件的FAT表中的表項為扇區內連續的，文件簇大小為32 KB，則需讀取的FAT表項為=2，需讀取的FAT表項扇區數目為向上取整=1，即需要通過1次I/O操作就可以定位到64 KB文件的32 KB偏移。

對于小文件來說，大多數文件系統的文件定位所需的I/O讀寫操作是區別不大的，特別是如果最優化定義文件的分配簇大小時，NSFS文件系統還可以更進一步減少文件定位的I/O操作，比如將該64 KB文件的簇大小設置為8 KB時，文件定位的I/O操作也只需要一次，可以達到同FAT32的相同讀寫性能。可以說讀寫小文件時，UFS/ExtX文件系統、FAT文件系統與NSFS文件系統具有相近的讀寫性能。

3.3 大文件讀寫

對于大文件讀寫來說，以讀寫偏移512 MB的一個1 GB文件為例，以下討論了USF/ExtX，FAT32與NSFS的性能對比。

在NSFS文件系統中，假設待讀取文件的文件分配表中的表項為扇區內連續的，文件簇大小為1 MB，則需讀取的文件分配表表項為512×1 024××1 024×1 024=512，需讀取的文件分配表表項扇區數目為512×=4，即需要通過4次I/O操作就能夠定位到1 GB文件的512 MB偏移。在UFS/ExtX文件系統中，大文件的隨機讀寫操作一般通過三級間接塊指針進行文件偏移的定位。首先通過一次i節點結構讀取的I/O操作，然后通過其中的3級間接塊指針進行3次遞歸I/O操作取得最終的文件偏移地址，即需要通過4次I/O操作就能夠定位到1 GB文件的512 MB偏移。

在FAT32文件系統中，假設待讀取文件的FAT表中的表項為扇區內連續的，文件簇大小為32 KB，則需讀取的FAT表項為512×1 024×1 024=16 KB，需讀取的FAT表項扇區數目為16 KB×=128，即需要通過128次I/O操作才能夠定位到1 GB文件的512 MB偏移。

在本例中，對于1 GB的大文件讀寫時，FAT文件系統中文件讀寫指針的偏移位置定位需要128次I/O操作，而NSFS文件系統和UFS/ExtX文件系統中文件讀寫指針的偏移位置定位僅需要4次I/O操作。減少的124次I/O操作可以極大地提高文件系統的讀寫性能。因此在大文件讀寫中，NSFS文件系統和UFS/ExtX文件系統相比FAT文件系統具有明顯的性能提升。

綜上所述，NSFS文件系統對于目錄和小文件的讀寫操作具有和UFS/ExtX文件系統、FAT文件系統相同的性能，而在大文件讀寫操作上，NSFS和UFS/ExtX文件系統與FAT文件系統相比，NSFS文件系統和UFS/ExtX文件系統具有很明顯的性能優勢。

4 可靠性保證

在可靠性方面，FAT文件系統是無可靠性保障的文件系統，突然斷電的情形很容易讓當前讀寫文件或目錄遭到破壞，再次上電時文件系統甚至可能遭到破壞。而UFS/ExtX文件系統系列中，只有Ext3及以后的文件系統才加入了文件系統日志功能，之前的版本基本都沒有強健的恢復策略。

NSFS文件系統在可靠性保障方面，采取了多級控制完全保障的目錄項備份策略，保證了當前的NSFS文件系統不會被破壞，保證了文件系統的完整性，提高了文件系統的可靠性。

目錄項備份策略是根據NSFS文件系統的層次存儲結構原理設計的，即文件或者目錄都是其所在目錄中的一個目錄項。在讀寫任何文件或目錄時，當前讀寫的目錄或文件都會先將該目錄或文件的目錄項寫入引導區的最后一個扇區，然后該目錄項中的臟數據位置1，然后再進行該目錄或文件的讀寫操作，讀寫操作結束之后再將目錄項的臟數據位置0，以此來保證NSFS文件系統的完整性。如果在寫文件時突然斷電，那么操作系統再次啟動之后會根據引導區的最后一個扇區中目錄項所在的目錄信息，將發生寫錯誤的文件目錄項標記為不完整文件，而不會影響NSFS文件系統。

如果NSFS文件系統中配置了高級數據可靠恢復策略時，寫文件之前還會將該文件進行數據區備份，然后再進行寫操作，這樣即使斷電之后，標記的不完整文件還能夠根據數據區備份進行完整的恢復。靈活的文件系統配置策略[7]可以讓操作系統的重要數據保證不被丟失或損壞，而且整個文件系統還能夠具有足夠的靈活性和可靠性來保證操作系統的穩定運行。

5 結 語

本文提出了一種基于位圖示法的NSFS文件系統，描述了NSFS文件系統的架構和原理，討論了NSFS文件系統的特點，比較了NSFS文件系統與UFS/ExtX文件系統、FAT文件系統的性能和可靠性。證明了NSFS文件系統具有比FAT文件系統更好的性能和更高的可靠性，具有比UFS/ExtX文件系統更簡潔的架構，更好的移植擴展性。總之，NSFS文件系統具有結構簡潔、性能優良、可靠性高和移植擴展性好等特點，非常適用于航空嵌入式領域的計算機系統軟件。

NSFS文件系統是一種完全基于位圖示法進行存儲管理的文件系統，對于文件的移動以及文件系統碎片的整理其先天能力不足，處理方式還不夠高效。在FLASH存儲器中，NSFS的文件系統還需要提供讀寫平衡能力才能夠更好地支持閃存設備。綜上所述，NSFS文件系統雖然具有良好的性能，但是仍然有很多需要改進的地方，希望NSFS文件系統在未來能夠有更多的改進以適應新一代航空電子裝備的需要。

參考文獻

[1] Microsoft Company. FAT32 file system specification [S]. US： Microsoft Company， 2000.

[2] Aleph One Company. The yet another flash filing system [EB/S]. [2007?02?16]. http：//www. verysource.com/.../yaffs_tagscompat.h.html.

[3] WOODHOUSE D. JFFS： the journaling flash file system [EB/OL]. [2001?10?10]. sourceware.org/jffs2/jffs2?html.

[4] HUGHES J P， FEIST C J. Architecture of secure file system [C]// Eighteenth IEEE Symposium on Mass Storage Systems and Technologies. [S.l.]： IEEE， 2000： 111?121.

[5] CAI Xiang， GUI Yu?wei， JOHNSON Rob. Exploiting unix file?system races via algorithmic complexity attacks [C]// 30th IEEE Symposium and Privacy. [S.l.]： IEEE， 2009： 234?239.

[6] 鄧劍，楊曉非，廖俊卿.FAT文件系統原理及實現[J].計算機與數字工程，2005（3）：9?11.

[7] 馬林.數據重現[M].北京：清華大學出版社，2009.