杭電簡單文件系統的實現

⑴ 如何實現一個文件系統

摘要：本文目的是分析在linux系統中如何實現新的文件系統。在介紹文件系統具體實現前先介紹文件系統的概念和作用，抽象出了文件系統概念模型。熟悉文件系統的內涵後，我們再近一步討論Linux系統中和文件系統的特殊風格和具體文件系統在Linux中組成結構，為讀者勾畫出Linux中文件系統工作的全景圖。最後，我們再通過Linux中最簡單的Romfs作實例分析實現文件系統的普遍步驟。（我們假定讀者已經對Linux文件系統初步了解）
什麼是文件系統
首先要談的概念就是什麼是文件系統，它的作用到底是什麼。
文件系統的概念雖然許多人都認為是再清晰不過的了，但其實我們往往在談論中或多或少地誇大或片縮小了它的實際概念（至少我時常混淆），或者說，有時借用了其它概念，有時說的又不夠全面。
比如在操作系統中，文件系統這個術語往往既被用來描述磁碟中的物理布局，比如有時我們說磁碟中的「文件系統」是EXT2或說把磁碟格式化成FAT32格式的「文件系統」等——這時所說的「文件系統」是指磁碟數據的物理布局格式；另外，文件系統也被用來描述內核中的邏輯文件結構，比如有時說的「文件系統」的介面或內核支持Ext2等「文件系統」——這時所說的文件系統都是內存中的數據組織結構而並非磁碟物理布局。還有些時候說「文件系統」負責管理用戶讀寫文件——這時所說的「文件系統」往往描述操作系統中的「文件管理系統」，也就是文件子系統。
雖然上面我們列舉了混用文件系統的概念的幾種情形，但是卻也不能說上述說法就是錯誤的，因為文件系統概念本身就囊括眾多概念，幾乎可以說在操作系統中自內存管理、系統調度到I/O系統、設備驅動等各個部分都和文件系統聯系密切，有些部分和文件系統甚至未必能明確劃分——所以不能只知道文件系統是系統中數據的存儲結構，一定要全面認識文件系統在操作系統中的角色，才能具備自己開發新文件系統的能力。
為了澄清文件系統的概念，必須先來看看文件系統在操作系統中處於何種角色，分析文件系統概念的內含外延。所以我們先拋開Linux文件系統的實例，而來看看操作系統中文件系統的普遍體系結構，從而增強對文件系統的理論認識。
下面以軟體組成的結構圖[1]的方式描述文件系統所涉及的內容。

我們針對各層做以簡要分析：
首先我們來分析最低層——設備驅動層，該層負責與外設——磁碟等——通訊。基於磁碟的文件系統都需要和存儲設備打交道，而系統操作外設離不開驅動程序。所以內核對文件的最後操作行為就是調用設備驅動程序完成從主存（內存）到輔存（磁碟）的數據傳輸。文件系統相關的多數設備都屬於塊設備，常見的塊設備驅動程序有磁碟驅動，光碟機驅動等，之所以稱它們為塊設備，一個原因是它們讀寫數據都是成塊進行的，但是更重要的原因是它們管理的數據能夠被隨機訪問——不需要向字元設備那樣必須順序訪問。
設備驅動層的上一層是物理I/O層，該層主要作為計算機外部環境和系統的介面，負責系統和磁碟交換數據塊。它要知道據塊在磁碟中存儲位置，也要知道文件數據塊在內存緩沖中的位置，另外它不需要了解數據或文件的具體結構。可以看到這層最主要的工作是標識別磁碟扇區和內存緩沖塊[2]之間的映射關系。
再上層是基礎I/O監督層，該層主要負責選擇文件 I/O需要的設備，調度磁碟請求等工作，另外分配I/O緩沖和磁碟空間也在該層完成。由於塊設備需要隨機訪問數據，而且對速度響應要求較高，所以操作系統不能向對字元設備那樣簡單、直接地發送讀寫請求，而必須對讀寫請求重新優化排序，以能節省磁碟定址時間，另外也必須對請求提交採取非同步調度（尤其寫操作）的方式進行。總而言之，內核對必須管理塊設備請求，而這項工作正是由該層負責的。
倒數第二層是邏輯I/O層，該層允許用戶和應用程序訪問記錄。它提供了通用的記錄（record）I/O操作，同時還維護基本文件數據。由於為了方便用戶操作和管理文件內容，文件內容往往被組織成記錄形式，所以操作系統為操作文件記錄提供了一個通用邏輯操作層。
和用戶最靠近的是訪問方法層，該層提供了一個從用戶空間到文件系統的標准介面，不同的訪問方法反映了不同的文件結構，也反映了不同的訪問數據和處理數據方法。這一層我們可以簡單地理解為文件系統給用戶提供的訪問介面——不同的文件格式（如順序存儲格式、索引存儲格式、索引順序存儲格式和哈希存儲格式等）對應不同的文件訪問方法。該層要負責將用戶對文件結構的操作轉化為對記錄的操作。

對比上面的層次圖我們再來分析一下數據流的處理過程，加深對文件系統的理解。
假如用戶或應用程序操作文件（創建/刪除），首先需要通過文件系統給用戶空間提供的訪問方法層進入文件系統，接著由使用邏輯I/O層對記錄進行給定操作，然後記錄將被轉化為文件塊，等待和磁碟交互。這里有兩點需要考慮——第一，磁碟管理（包括再磁碟空閑區分配文件和組織空閑區）；第二，調度塊I/O請求——這些由基礎I/O監督層的工作。再下來文件塊被物理I/O層傳遞給磁碟驅動程序，最後磁碟驅動程序真正把數據寫入具體的扇區。至此文件操作完畢。

當然上面介紹的層次結構是理想情況下的理論抽象，實際文件系統並非一定要按照上面的層次或結構組織，它們往往簡化或合並了某些層的功能（比如Linux文件系統因為所有文件都被看作位元組流，所以不存在記錄，也就沒有必要實現邏輯I/O層，進而也不需要在記錄相關的處理）。但是大體上都需要經過類似處理。如果從處理對象上和系統獨立性上劃分，文件系統體系結構可以被分為兩大部分：——文件管理部分和操作系統I/O部分。文件管理系統負責操作內存中文件對象，並按文件的邏輯格式將對文件對象的操作轉化成對文件塊的操作；而操作系統I/O部分負責內存中的塊與物理磁碟中的數據交換。
數據表現形式再文件操作過程中也經歷了幾種變化：在用戶訪問文件系統看到的是位元組序列，而在位元組序列被寫入磁碟時看到的是內存中文件塊（在緩沖中），在最後將數據寫入磁碟扇區時看到的是磁碟數據塊[3]。
本文所說的實現文件系統主要針對最開始講到第二種情況——內核中的邏輯文件結構（但其它相關的文件管理系統和文件系統磁碟存儲格式也必須了解），我們用數據處理流圖來分析一下邏輯文件系統主要功能和在操作系統中所處的地位。

其中文件系統介面與物理布局管理是邏輯文件系統要負責的主要功能。
文件系統介面為用戶提供對文件系統的操作，比如open、close、read、write和訪問控制等，同時也負責處理文件的邏輯結構。
物理存儲布局管理，如同虛擬內存地址轉化為物理內存地址時，必須處理段頁結構一樣，邏輯文件結構必須轉化到物理磁碟中，所以也要處理物理分區和扇區的實際存儲位置，分配磁碟空間和內存中的緩沖也要在這里被處理。
所以說要實現文件系統就必須提供上面提到的兩種功能，缺一不可。

在了解了文件系統的功能後，我們針對Linux操作系統分析具體文件系統如何工作，進而掌握實現一個文件系統需要的步驟。
Linux 文件系統組成結構
Linux 文件系統的結構除了我們上面所提到的概念結構外，最主要有兩個特點，一個是文件系統抽象出了一個通用文件表示層——虛擬文件系統或稱做VFS。另外一個重要特點是它的文件系統支持動態安裝（或說掛載、登陸等），大多數文件系統都可以作為根文件系統的葉子接點被掛在到根文件目錄樹下的子目錄上。另外Linux系統在文件讀寫的I/O操作上也採取了一些先進技術和策略。
我們先從虛擬文件系統入手分析linux文件系統的特性，然後介紹有關文件系統的安裝、注冊和讀寫等概念。
虛擬文件系統
虛擬文件系統為用戶空間程序提供了文件系統介面。系統中所有文件系統不但依賴VFS共存，而且也依靠VFS系統協同工作。通過虛擬文件系統我們可以利用標準的UNIX文件系統調用對不同介質上的不同文件系統進行讀寫操作[4]。
虛擬文件系統的目的是為了屏蔽各種各樣不同文件系統的相異操作形式，使得異構的文件系統可以在統一的形式下，以標准化的方法訪問、操作。實現虛擬文件系統利用的主要思想是引入一個通用文件模型——該模型抽象出了文件系統的所有基本操作(該通用模型源於Unix風格的文件系統)，比如讀、寫操作等。同時實際文件系統如果希望利用虛擬文件系統，既被虛擬文件系統支持，也必須將自身的諸如，「打開文件」、「讀寫文件」等操作行為以及「什麼是文件」，「什麼是目錄」等概念「修飾」成虛擬文件系統所要求的（定義的）形式，這樣才能夠被虛擬文件系統支持和使用。
我們可以借用面向對象的一些思想來理解虛擬文件系統，虛擬文件系統好比一個抽象類或介面，它定義（但不實現）了文件系統最常見的操作行為。而具體文件系統好比是具體類，它們是特定文件系統的實例。具體文件系統和虛擬文件系統的關系類似具體類繼承抽象類或實現介面。而在用戶看到或操作的都是抽象類或介面，但實際行為卻發生在具體文件系統實例上。至於如何將對虛擬文件系統的操作轉化到對具體文件系統的實例，就要通過注冊具體文件系統到系統，然後再安裝具體文件系統才能實現轉化，這點可以想像成面向對象中的多態概念。
我們個實舉例來說明具體文件系統如何通過虛擬文件系統協同工作。
例如：假設一個用戶輸入以下shell命令：
$ cp /hda/test1 /removable/test2
其中 /removable是MS-DOS磁碟的一個安裝點，而 /hda 是一個標準的第二擴展文件系統（ Ext2）的目錄。cp命令不用了解test1或test2的具體文件系統，它所看到和操作的對象是VFS。cp首先要從ext3文件系統讀出test1文件，然後寫入MS-DOS文件系統中的test2。VFS會將找到ext3文件系統實例的讀方法，對test1文件進行讀取操作；然後找到MS-DOS（在Linux中稱VFAT）文件系統實例的寫方法，對test2文件進行寫入操作。可以看到 VFS是讀寫操作的統一界面，只要具體文件系統符合VFS所要求的介面，那麼就可以毫無障礙地透明通訊了。

Unix風格的文件系統
虛擬文件系統的通用模型源於Unix風格的文件系統，所謂Unix風格是指Unix傳統上文件系統傳統上使用了四種和文件系統相關的抽象概念：文件(file)、目錄項(dentry)、索引節點(inode)和安裝點(mount point)。
文件——在Unix中的文件都被看做是一有序位元組串，它們都有一個方便用戶或系統識別的名稱。另外典型的文件操作有讀、寫、創建和刪除等。
目錄項——不要和目錄概念搞混淆，在Linux中目錄被看作文件。而目錄項是文件路徑中的一部分。一個文件路徑的例子是「/home/wolfman/foo」——根目錄是/，目錄home,wolfman和文件foo都是目錄項。
索引節點——Unix系統將文件的相關信息（如訪問控制許可權、大小、擁有者、創建時間等等信息），有時被稱作文件的元數據（也就是說，數據的數據）被存儲在一個單獨的數據結構中，該結構被稱為索引節點(inode)。
安裝點——在Unix中，文件系統被安裝在一個特定的安裝點上，所有的已安裝文件系統都作為根文件系統樹中的葉子出現在系統中。
上述概念是Unix文件系統的邏輯數據結構，但相應的Unix文件系統（Ext2等）磁碟布局也實現了部分上述概念，比如文件信息（文件數據元）存儲在磁碟塊中的索引節點上。當文件被載如內存時，內核需要使用磁碟塊中的索引點來裝配內存中的索引接點。類似行為還有超級塊信息等。
對於非Unix風格文件系統，如FAT或NTFS，要想能被VFS支持，它們的文件系統代碼必須提供這些概念的虛擬形式。比如，即使一個文件系統不支持索引節點，它也必須在內存中裝配起索引節點結構體——如同本身固有一樣。或者，如果一個文件系統將目錄看作是一種特殊對象，那麼要想使用VFS，必須將目錄重新表示為文件形式。通常，這種轉換需要在使用現場引入一些特殊處理，使得非Unix文件系統能夠兼容Unix文件系統的使用規則和滿足VFS的需求。通過這些處理，非Unix文件系統便可以和VFS一同工作了，是性能上多少會受一些影響[5]。這點很重要，我們實現自己文件系統時必須提供（模擬）Unix風格文件系統的抽象概念。

Linux文件系統中使用的對象
Linux文件系統的對象就是指一些數據結構體，之所以稱它們是對象，是因為這些數據結構體不但包含了相關屬性而且還包含了操作自身結構的函數指針，這種將數據和方法進行封裝的思想和面向對象中對象概念一致，所以這里我們就稱它們是對象。
Linux文件系統使用大量對象，我們簡要分析以下VFS相關的對象，和除此還有和進程相關的一些其它對象。
VFS相關對象
這里我們不展開討論每個對象，僅僅是為了內容完整性，做作簡要說明。
VFS中包含有四個主要的對象類型，它們分別是：
超級塊對象，它代表特定的已安裝文件系統。
索引節點對象，它代表特定文件。
目錄項對象，它代表特定的目錄項。
文件對象，它代表和進程打開的文件。
每個主要對象中都包含一個操作對象，這些操作對象描述了內核針對主要對象可以使用的方法。最主要的幾種操作對象如下：
super_operations對象，其中包括內核針對特定文件系統所能調用的方法，比如read_inode()和sync_fs()方法等。
inode_operations對象，其中包括內核針對特定文件所能調用的方法，比如create()和link()方法等。
dentry_operations對象，其中包括內核針對特定目錄所能調用的方法，比如d_compare()和d_delete()方法等。
file對象，其中包括，進程針對已打開文件所能調用的方法，比如read()和write()方法等。
除了上述的四個主要對象外,VFS還包含了許多對象，比如每個注冊文件系統都是由file_system_type對象表示——描述了文件系統及其能力（如比如ext3或XFS）；另外每一個安裝點也都利用vfsmount對象表示——包含了關於安裝點的信息，如位置和安裝標志等。

其它VFS對象
系統上的每一進程都有自己的打開文件，根文件系統，當前工作目錄，安裝點等等。另外還有幾個數據結構體將VFS層和文件的進程緊密聯系，它們分別是：file_struct 和fs_struct
file_struct結構體由進程描述符中的files項指向。所有包含進程的信息和它的文件描述符都包含在其中。第二個和進程相關的結構體是fs_struct。該結構由進程描述符的fs項指向。它包含文件系統和進程相關的信息。每種結構體的詳細信息不在這里說明了。

緩存對象
除了上述一些結構外，為了縮短文件操作響應時間，提高系統性能，Linux系統採用了許多緩存對象，例如目錄緩存、頁面緩存和緩沖緩存（已經歸入了頁面緩存），這里我們對緩存做簡單介紹。
頁高速緩存（cache）是 Linux內核實現的一種主要磁碟緩存。其目的是減少磁碟的I/O操作，具體的講是通過把磁碟中的數據緩存到物理內存中去，把對磁碟的I/O操作變為對物理內存的I/O操作。頁高速緩存是由RAM中的物理頁組成的，緩存中每一頁都對應著磁碟中的多個塊。每當內核開始執行一個頁I/O操作時（通常是對普通文件中頁大小的塊進行磁碟操作），首先會檢查需要的數據是否在高速緩存中，如果在，那麼內核就直接使用高速緩存中的數據，從而避免了訪問磁碟。
但我們知道文件系統只能以每次訪問數個塊的形式進行操作。內核執行所有磁碟操作都必須根據塊進行，一個塊包含一個或多個磁碟扇區。為此，內核提供了一個專門結構來管理緩沖buffer_head。緩沖頭[6]的目的是描述磁碟扇區和物理緩沖之間的映射關系和做I/O操作的容器。但是緩沖結構並非獨立存在，而是被包含在頁高速緩存中，而且一個頁高速緩存可以包含多個緩沖。我們將在文件後面的文件讀寫部分看到數據如何被從磁碟扇區讀入頁高速緩存中的緩沖中的。

文件系統的注冊和安裝
使用文件系統前必須對文件系統進行注冊和安裝，下面分別對這兩種行為做簡要介紹。
文件系統的注冊
VFS要想能將自己定義的介面映射到實際文件系統的專用方法上，必須能夠讓內核識別實際的文件系統，實際文件系統通過將代表自身屬性的文件類型對象(file_system_type)注冊(通過register_filesystem()函數)到內核，也就是掛到內核中的文件系統類型鏈表上，來達到使文件系統能被內核識別的目的。反過來內核也正是通過這條鏈表來跟蹤系統所支持的各種文件系統的。
我們簡要分析一下注冊步驟：
struct file_system_type {
const char *name; /*文件系統的名字*/
int fs_flags; /*文件系統類型標志*/
/*下面的函數用來從磁碟中讀取超級塊*/
struct super_block * (*read_super) (struct file_system_type *, int,
const char *, void *);
struct file_system_type * next; /*鏈表中下一個文件系統類型*/
struct list_head fs_supers; /*超級塊對象鏈表*/
};
其中最重要的一項是read_super()函數，它用來從磁碟上讀取超級塊，並且當文件系統被裝載時，在內存中組裝超級塊對象。要實現一個文件系統首先需要實現的結構體便是file_system_type結構體。
注冊文件系統只能保證文件系統能被系統識別，但此刻文件系統尚不能使用，因為它還沒有被安裝到特定的安裝點上。所以在使用文件系統前必須將文件系統安裝到安裝點上。
文件系統被實際安裝時，將在安裝點創建一個vfsmount結構體。該結構體用代表文件系統的實例——換句話說，代表一個安裝點。
vfsmount結構被定義在<linux/mount.h>中，下面是具體結構
―――――――――――――――――――――――――――――――――――――――
struct vfsmount
{
struct list_head mnt_hash; /*哈希表*/
struct vfsmount *mnt_parent; /*父文件系統*/
struct dentry *mnt_mountpoint; /*安裝點的目錄項對象*/
struct dentry *mnt_root; /*該文件系統的根目錄項對象*/
struct super_block *mnt_sb; /*該文件系統的超級塊*/
struct list_head mnt_mounts; /*子文件系統鏈表*/
struct list_head mnt_child; /*和父文件系統相關的子文件系統*/
atomic_t mnt_count; /*使用計數*/
int mnt_flags; /*安裝標志*/
char *mnt_devname; /*設備文件名字*/
struct list_head mnt_list; /*描述符鏈表*/
};
――――――――――――――――――――――――――――――――――――――
文件系統如果僅僅注冊，那麼還不能被用戶使用。要想使用它還必須將文件系統安裝到特定的安裝點後才能工作。下面我們接著介紹文件系統的安裝[7]過程。
安裝過程

用戶在用戶空間調用mount()命令——指定安裝點、安裝的設備、安裝類型等——安裝指定文件系統到指定目錄。mount()系統調用在內核中的實現函數為sys_mount(),該函數調用的主要常式是do_mount()，它會取得安裝點的目錄項對象，然後調用do_add_mount()常式。
do_add_mount()函數主要做的是首先使用do_kern_mount()函數創建一個安裝點，再使用graft_tree（）將安裝點作為葉子與根目錄樹掛接起來。
整個安裝過程中最核心的函數就是do_kern_mount()了，為了創建一個新安裝點（vfsmount）,該函數需要做一下幾件事情：
l 1 檢查安裝設備的權利，只有root許可權才有能力執行該操作。
l 2 Get_fs_type()在文件鏈表中取得相應文件系統類型（注冊時被填加到練表中）。
l 3 Alloc_vfsmnt()調用slab分配器為vfsmount結構體分配存儲空間，並把它的地址存放在mnt局部變數中。
l 4 初始化mnt->mnt_devname域
l 5 分配新的超級塊並初始化它。do_kern_mount( )檢查file_system_type描述符中的標志以決定如何進行如下操作：根據文件系統的標志位，選擇相應的方法讀取超級塊(比如對Ext2,romfs這類文件系統調用get_sb_dev()；對於這種沒有實際設備的虛擬文件系統如 ramfs調用get_sb_nodev())——讀取超級塊最終要使用文件系統類型中的read_super方法。
安裝過程做的最主要工作是創建安裝點對象，掛接給定文件系統到根文件系統的指定接點下，然後初始化超級快對象，從而獲得文件系統基本信息和相關操作方法(比如讀取系統中某個inode的方法)。

總而言之，注冊過程是告之內核給定文件系統存在於系統內；而安裝是請求內核對給定文件系統進行支持，使文件系統真正可用。

轉載

⑵ 數據結構的一些小問題

5.4 文件系統的實現
5.4.1 存儲空間的分配與回收
在計算機系統中，存儲空間是一種寶貴的資源。外存儲設備中的空間容量雖然比較大，但也不是無限的，故對文件刪除之後而不再使用的空間，必須加以回收，然後在建立文件等操作中重新利用。

對於制度的存儲設備，無所謂回收，也無所謂動態分配，這種存儲設備在物理上就是不可重用的。

為了進行存儲空間的分配與回收，在外存儲設備上設置有空閑空間登記表，該表動態跟蹤該外存儲設備上所有還沒有分配給任何文件的空閑塊的數目和塊號。

該空閑空間登記表雖然稱為表，但不一定以一個二維表格的形式實現。從方便、高效和安全的角度考慮，通常把空閑空間登記表放在存儲介質上。

對空閑空間表的訪問與修改工作是經常發生的。在進行文件刪除、文件建立、寫文件等操作中都會訪問和修改空閑空間表。

在設計空閑空間登記表的數據結構時，一般有四種不同的方案可以考慮，下面分別介紹。

1、 位示圖

位示圖的基本思想是，利用一串二進制位（BIT）的值來反映磁碟空間的分配使用情況。在位示圖中，沒一個磁碟中物理塊用一個二進制位對應，如果某個物理塊為空閑，則相應的二進制位為0；如果該物理塊已分配了，則相應的二進位為，如圖5-15所示。

位示圖對空間分配情況的描述能力強。一個二進位就描述一個物理塊的狀態。另外，位示圖佔用空間較小，因此可以復制到內存，使查找既方便又快速。位示圖適用於各種文件物理結構的文件系統。使用位示圖能夠簡單有效地在盤上找到N個連續的空閑塊。

2、 空閑塊表

空閑塊表是專門為空閑塊建立的一張表，該表記錄外存儲器全部空閑的物理塊：包括每個空閑塊的第一個空閑物理塊號和該空閑塊只能感空閑物理塊的個數。如圖5-16所示。空閑塊表方式特別適合於文件物理結構為順序結構的文件系統。

在建立新文件時，應該尋找一組連續的空閑物理塊，其空閑塊個數恰好等於所申請值，或接近於所申請值。系統首先查找空閑塊表，主要查看該空閑塊表項中是否有符合上述申請值的對應表項，如果有，就將該表項從空閑塊表中刪去，並且把所對應的一組連續的空閑物理塊分配給申請者。

當刪除文件時，系統收回它所佔用的物理塊，並且考慮所收回的物理塊是否可以與原有空閑塊相鄰接，以便合並成更大的空閑區域，最後修改有關空閑塊表項。

3、 空閑塊鏈表

將外存儲器中所有的空閑物理塊連成一個鏈表，用一個空閑塊首指針指向第一個空閑塊，隨後的每個空閑塊中都含有指向下一個空閑塊的指針，最後一塊的指針為空，表示鏈尾，這樣就構成了一個空閑塊鏈表，如圖5-17所示。

在圖45-17中，一個空閑塊鏈表的首指針維持一個指向物理塊12的指針，該塊是第一個空閑物理塊。物理塊12包含一個指向物理塊13的指針，物理塊13指向物理塊14，如此等等。

空閑塊鏈表模式效率低。要遍歷整張空閑塊鏈表，必須讀每一個物理塊，這就需要大量的I/O時間。

在空閑塊鏈表模式中對空間的申請和釋放是以塊為單位的。申請空間時從鏈首取空閑塊。空間釋放時將物理塊接入鏈尾。

空閑塊鏈表法節省內存，但申請空間和回收空間的速度較慢，實現效率較低。

4、 成組鏈接

對鏈接表的一個改進方案是將N個空閑盤塊的地址存放在第一個空閑塊中，如圖5-18所示。期於N-1個空閑盤塊是實際空閑的。假設每100個空閑塊為一組。第一組的100個空閑塊塊號放在第二組的頭一塊中，而第二組的其餘99塊是完全空閑的。第二組的100個塊號又放在第三組的頭一塊中，依次類推，組與組之間形成鏈接關系。在最後一組的塊號中第2個單元填「0」，表示該塊中指出的塊號是最後一組的塊號，空閑塊鏈到此結束。在這個空閑塊鏈中，不組100塊的一個組的塊號，通常放在內存的一個專用塊中。這種方式稱為成組鏈接。

系統在初始化時先把專用塊內容讀到內存中，當需分配空閑塊時，就直接在內存中找到哪些塊是空閑的，每分配一塊後把空閑塊數減1。但在把一組中的第一個空閑塊分配出去之前，應把登記在該塊中的下一組的塊號及塊數保存到專用塊中（此時原專用塊中的信息已經無用，因為它指出的一組空閑塊都已被分配了）。當一組空閑塊被分配完後，則再把專用塊的內容讀到內存中，指出另一組可供分配的空閑塊。

假設初始化時系統已把專用塊讀入主存儲器L單元開始的區域中，分配和回收的演算法如下：

⑴分配一個空閑塊

查L單元內容（空閑塊數）：

當空閑塊數>1，I：=L+空閑塊數；

從I單元得到一空閑塊號；

把該塊分配給申請者；

空閑塊數減1。

當空閑塊數=1，取出L+1單元內容（一組的第一塊塊號或0）；

取值 =0，無空閑塊，申請者等待；

≠0，把該塊內容復制到專用塊；

把專用塊內容獨到主存L開始的區域。

⑵歸還一塊

查L單元的空閑塊數；

當空閑塊數〈100，空閑塊數加1；

J：=L+空閑塊數；

規劃塊號填入J單元。

當空閑塊數=100，把主存中登記的信息寫入歸還塊中；

把歸還塊號填入L+1單元；

將L單元置成1。

採用成組鏈接後，分配回收空閑塊時均在內存中查找和修改，只有在一組空閑塊分配完或空閑的磁碟塊構成一組時才需要啟動磁碟讀寫。因此，成組鏈接的管理方式比普通的鏈接方式效率高。

成組鏈接這種方案能夠迅速找到大量空閑盤塊地址。有些版本的UNIX操作系統便採用了這種方案。

5.4.2 實現文件系統的表目
當用戶申請打開一個文件時，系統要在內存中為該用戶保存一些必要的信息，這些信息以表格欄目中內容的形式出現，被稱為表目。在實現文件系統時所需要的表目有若干種，其中在內存中所需的重要表目有如下一些：

1、 系統打開文件表

系統打開文件表，專門用於保存已打開文件的文件控制塊。該系統打開文件表放在內存。除了保存已打開文件的文件控制塊之外，在該表格中還保存有已打開的文件號、共享計數、修改標志等等，圖5-19。

2、 用戶打開文件表

在每個進程中，都有一個「用戶打開文件表」。該表的內容有文件描述符、打開方式、讀寫指針、系統打開文件表入口等，圖5-20。另外在進程的進程式控制制塊PCB中，還記錄了「用戶打開文件表」的位置。

3、 系統打開文件表與用戶打開文件表之間的關系

用戶打開文件表指向了系統打開文件表。如果多個進程共享同一個文件，則一定有多個用戶打開文件表目對應著系統打開文件表的同一入口，圖5-21。

5.4.3 記錄的成組與分解
用戶的文件毫無疑問是由用戶按名自己的需要組織的。用戶還可按信息的內在邏輯關系，把文件劃分成若干個邏輯記錄。顯然，邏輯記錄的大小是由文件性質決定的。

另外，存儲介質上的物理分塊與存儲介質的特性有關，尤其是磁碟。磁碟上的塊的大小是在磁碟初始化時預先劃好的。因此，邏輯記錄的大小往往與存儲介質物理分塊的大小不一直。

當用戶文件的邏輯記錄比存儲介質的物理分塊小得多時，把一個邏輯記錄存入一個物理塊中，就會造成存儲空間的浪費。為此，可把多個邏輯記錄存放在一個物理塊中，當用戶需要某個邏輯記錄時再從一物理塊信息中將其分解出來。

1、 記錄的成組

把若干個邏輯記錄合成一組存放一物理塊的工作稱「記錄的成組」，每塊中的邏輯記錄個數稱「塊因子」。

記錄的成組在不同存儲介質上進行信息轉儲是很有用的。

由於信息交換以塊為單位，所以，要進行成組操作時必須使用內存的緩沖區。該緩沖區的長度等於要進行成組的最大邏輯記錄長度乘以成組的塊因子。成組轉儲操作如圖5-22所示。

在進行記錄成組時，還應考慮邏輯記錄的格式。這是因為在記錄式文件中，有「定長記錄格式」和「不定長記錄格式」。對定長記錄格式的文件按記錄成組的方式存儲到存儲介質上，則除最後一塊外，每塊中存放的邏輯記錄個數是相同的。故只要在文件目錄中說明邏輯記錄的長度和塊因子，在需要使用某個記錄時就能方便地將其找出。

如果是一個不定長記錄格式的文件，各個邏輯記錄的長度可能不相等，在進行記錄成組操作時，就應在每個邏輯記錄前附加說明該記錄長度的控制信息。

2、 記錄的分解

對應簽署記錄成組的操作，有必要考慮從一組邏輯記錄中把一個邏輯記錄分離出來的操作，這種操作稱為「記錄的分解」。

顯然，從事記錄的分解操作也要使用內存緩沖區。

當用戶請求讀一個文件中的某個記錄時，文件系統首先找出該記錄所在物理塊的位置，然後把含有該記錄的物理塊全部信息讀入內存緩沖區，由於讀入內存緩沖區的物理塊信息中含有多個邏輯記錄，所以要再從內存緩沖區中分解出指定的記錄，然後傳送到用戶工作區。

對定長記錄格式，只要的邏輯記錄的長度就可容易地進行分解。對不定長記錄格式，要根據說明邏輯記錄長度的控制信息，計算出用戶所指定的記錄在內存緩沖區中的位置，然後把記錄分解出來。圖5-23是記錄的分解操作示例。

在圖5-23中，用戶要求讀出邏輯記錄K4。用戶文件中的記錄是成組存放在磁碟上的，系統找出含有記錄K4的物理塊，從中讀出了6個邏輯記錄K1，K2，K3，K4，K5和K6，並且知道這些邏輯記錄的長度為80，塊因子為6。該塊信息被讀入內存緩沖區後，根據邏輯記錄的長度和塊因子胃，立即就能取出其中的邏輯記錄K4，並把K4傳送到用戶工作區。

從上面的討論可以看到，為了提高存儲空間的利用率和減少啟動設備的次數，採用了記錄的成組和分解技術。但是上述效果的獲得也付出了代價，主要包括：需要設立內存緩沖區，另外操作系統增加了成組和分解的操作的功能。

5.4.4 文件的操作
文件系統是提供給用戶使用的，用戶可以進行按名存取所需要的文件。在文件系統的實現中，為用戶提供使用文件的手段是文件系統的重要任務之一。

1、 建立文件

用戶首先調用文件系統的「建立文件」操作，在請求調用該操作時，提供所要創建的文件的文件名及若干參數：用戶名、文件名、存取方式、存儲設備類型、記錄格式、記錄長度，等等。

系統依據用戶提供的文件名及若干參數，為這一新創建的文件分配一個文件控制塊，填寫文件控制塊中的有關項。

建立文件的實質是建立文件的文件控制塊FCB，並建立必要的存儲空間，分配空的FCB。從而建立起系統與文件的聯系。

建立文件系統調用的一般格式為：CREATE（文件名，訪問許可權，（最大長度））。

建立文件的具體步驟如下：

⑴檢查參數的合法性：

文件名是否符合命名規則，若是，則進行下一步⑵；否則報錯，返回。

⑵檢查同一目錄下有無重名文件：

若沒有，則進行下一步⑶；否則報錯，返回。

⑶在目錄中有無空閑位置；

若有，則進行下一步⑷；否則，不成功返回。

⑷填寫目錄項內容：

包括：文件名、用戶名、存取許可權、長度置零，首地址等等。

⑸返回

2、 打開文件

打開文件，是使用文件的第一步，任何一個文件使用前都要先打開，即把文件控制塊FCB送到內存。

打開文件系統調用的一般格式為：FD=OPEN（文件路徑名，打開方式）。

打開文件時，系統主要完成以下工作：

⑴根據文件路徑名查目錄，找到FCB主部。

⑵根據打開方式、共享說明和用戶身份檢查訪問合法性。

⑶根據文件號查系統打開文件表，看文件是否已被打開。

如果是，共享計數加1；

否則，將外存中的CB主部等信息填入系統打開文件表空表項，共享計數置為1。

⑷在用戶打開文件表中取一空表項，填寫打開方式等，並指向系統打開文件表對應表項。

返回信息：FD：文件描述符，是一個非負整數，用於以後讀寫文件。

3、 讀文件

打開文件後，就可以讀取文件中的信息。

讀文件系統調用的一般格式為：READ（文件名，（文件內位置），要讀的長度，內存目的地址）。

隱含參數：文件主。

讀寫方式可為讀、寫合既讀又寫等。

讀文件時，系統主要完成以下工作：

⑴檢查長度是否為正整數；

若是，則進行下一步；否則，轉向（10）。

⑵根據文件名查找目錄，確定該文件在目錄中的位置。

⑶根據隱含參數中的文件主和目錄中該文件的存儲許可權數據，檢查是否有權讀：

若是，則進行下一步，否則，轉向（10）。

⑷由文件內位置與要讀的長度計算最末位置，將其與目錄中的文件長度比較，超過否？

若是，則轉向（10）；否則，進行下一步（5）。也可將參數中的長度修正為目錄中的文件長度。

⑸根據參數中的位置、長度和目錄中的映射信息，確定物理塊號、需要讀出的塊數等讀盤參數。

⑹根據下一塊號讀塊至內存緩沖區。

⑺取出要讀的內容，也許要進行成組的分解，將取出的內容送至參數中的內存目的地址。

⑻根據塊內長度或起始塊號+塊數，確定還讀下一塊嗎？同時確定下一塊號：

若是，則轉向（5）；否則，進行下一步（9）。

⑼正常返回。

⑽錯誤返回，返回響應錯誤號。

4、 寫文件

寫文件系統調用的一般格式為：WRITE文件名，記錄鍵，內存位置）。

把內存中指定單元的數據作為指定的一個記錄寫入指定文件中，系統還將為其分配物理塊，以便把記錄信息寫到外存上。

5、 關閉文件

若文件暫時不用每則應將它關閉。文件關閉後一般不能存取，若要存取，則必須再次打開

6、 刪除文件

刪除文件文件系統調用的一般格式為：DELETE（文件名）。

7、 指針定位

指針定位的一般格式為：SEEK（FD，新指針的位置）。

指針定位時，系統主要完成以下工作：

⑴由FD檢查用戶打開文件表，找到對應的入口；

⑵將用戶打開文件表中文件讀寫指針位置設為新指針的位置，供後續讀寫命令存取該指針處文件內容。

希望對你有幫助

⑶ 簡述文件系統與資料庫系統的區別與聯系。

1、文件系統於資料庫系統的區別：

文件系統面向某一應用程序，共享性差，冗餘度大，數據獨立性差，記錄內有結構，整體無結構，由應用程序自己控制。

資料庫系統面向現實世界，共享性高，冗餘度小，具有較高的物理獨立性和一定的邏輯獨立性，整體結構化，用數據模型描述，由資料庫系統提供數據安全性，完整性，並發控制和恢復力。

2，文件系統與資料庫系統的聯系：

文件系統於資料庫系統都是計算機系統中管理資料庫的軟體。解析文件系統是操作系統的重要組成部分。

而資料庫系統DBMS是獨立於操作系統的軟體。到時DBMS獅子啊操作系統的基礎上實現的。資料庫系統的組織和存儲是通過操作系統中的文件系統來實現的。

(3)杭電簡單文件系統的實現擴展閱讀：

文件系統存在的意義：

在計算機中，文件系統是命名文件及放置文件的邏輯存儲和恢復的系統。DOS、Windows、OS/2、Macintosh和UNIX-based操作系統都有文件系統，在此系統中文件被放置在分等級的（樹狀）結構中的某一處。

文件系統指定命名文件的規則。這些規則包括文件名的字元數最大量，哪種字元可以使用，以及某些系統中文件名後綴可以有多長。文件系統還包括通過目錄結構找到文件的指定路徑的格式。

文件系統是軟體系統的一部分，它的存在使得應用可以方便的使用抽象命名的數據對象和大小可變的空間。

參考資料來源：網路-資料庫系統

參考資料來源：網路-文件系統

⑷ 文件管理的主要目的是（ ）。

D 實現文件按名存取。

解析:

簡單地說，文件是一段程序或數據的集合，文件系統就是操作系統中與管理文件有關的軟體和數據，它負責為用戶建立文件，撤銷、讀寫、修改和復制文件，還負責文件的按名存取和存取控制。

文件系統具有以下特點：

(1)友好的用戶介面，用戶只對文件進行操作而不用管文件的結構和存放的物理位置。

(2)對文件按名存取，對用戶透明。這也是文件系統的主要目的。

(4)杭電簡單文件系統的實現擴展閱讀：

從系統角度來看，文件系統是對文件存儲器的存儲空間進行組織，分配和回收，負責文件的存儲，檢索，共享和保護。從用戶角度來看，文件系統主要是實現"按名取存"，文件系統的用戶只要知道所需文件的文件名，就可存取文件中的信息，而無需知道這些文件究竟存放在什麼地方。

隨著計算機應用的普及，單純通過制度進行文檔安全管理越來越力不從心，企業開始採用專門的保密設備來管理機密文檔，如安裝專門的涉密計算機、使用認證存儲設備等。

為適應信息化工作及無紙化辦公的要求，同時隨著互聯網路技術的發展，為了應對來自互聯網路的威脅，很多企業採用堵塞的方式，如內網隔離、封USB口、禁止列印等方式管理內部機密文檔。

⑸ 程序員必備知識（操作系統5-文件系統）

本篇與之前的第三篇的內存管理知識點有相似的地方

對於運行的進程來說，內存就像一個紙箱子, 僅僅是一個暫存數據的地方， 而且空間有限。如果我們想要進程結束之後，數據依然能夠保存下來，就不能只保存在內存里，而是應該保存在 外部存儲 中。就像圖書館這種地方，不僅空間大,而且能夠永久保存。

我們最常用的外部存儲就是 硬碟 ，數據是以文件的形式保存在硬碟上的。為了管理這些文件，我們在規劃文件系統的時候，需要考慮到以下幾點。

第一點,文件系統要有嚴格的組織形式，使得文件能夠 以塊為單位進行存儲 。這就像圖書館里，我們會給設置一排排書架，然後再把書架分成一個個小格子，有的項目存放的資料非常多，一個格子放不下，就需要多個格子來進行存放。我們把這個區域稱為存放原始資料的 倉庫區 。

第二點,文件系統中也要有 索引區 ，用來方便查找一個文件分成的多個塊都存放在了什麼位置。這就好比，圖書館的書太多了,為了方便查找,我們需要專門設置一排書架,這裡面會寫清楚整個檔案庫有哪些資料,資料在哪個架子的哪個格子上。這樣找資料的時候就不用跑遍整個檔案庫,在這個書架上找到後，直奔目標書架就可以了。

第三點,如果文件系統中有的文件是熱點文件,近期經常被讀取和寫入，文件系統應該有 緩存層 。這就相當於圖書館裡面的熱門圖書區,這裡面的書都是暢銷書或者是常常被借還的圖書。因為借還的次數比較多,那就沒必要每次有人還了之後，還放回遙遠的貨架，我們可以專門開辟一個區域, 放置這些借還頻次高的圖書。這樣借還的效率就會提高。

第四點,文件應該用 文件夾 的形式組織起來，方便管理和查詢。這就像在圖書館裡面，你可以給這些資料分門別類,比如分成計算機類.文學類.歷史類等等。這樣你也容易管理，項目組借閱的時候只要在某個類別中去找就可以了。

在文件系統中，每個文件都有一個名字,這樣我們訪問一個文件，希望通過它的名字就可以找到。文件名就是一個普通的文本。 當然文件名會經常沖突,不同用戶取相同的名字的情況還是會經常出現的。

要想把很多的文件有序地組織起來,我們就需要把它們成為 目錄 或者文件夾。這樣,一個文件夾里可以包含文件夾,也可以包含文件,這樣就形成了一種 樹形結構 。而我們可以將不同的用戶放在不同的用戶目錄下，就可以一定程度上避免了命名的沖突問題。

第五點，Linux 內核要在自己的內存裡面維護一套數據結構，來保存哪些文件被哪些進程打開和使用 。這就好比，圖書館里會有個圖書管理系統，記錄哪些書被借閱了，被誰借閱了，借閱了多久,什麼時候歸還。

文件系統是操作系統中負責管理持久數據的子系統，說簡單點,就是負責把用戶的文件存到磁碟硬體中,因為即使計算機斷電了，磁碟里的數據並不會丟失,所以可以持久化的保存文件。

文件系統的基本數據單位是 文件 ，它的目的是對磁碟上的文件進行組織管理，那組織的方式不同,就會形成不同的文件系統。

Linux最經典的一句話是:「一切皆文件」,不僅普通的文件和目錄，就連塊設備、管道、socket 等，也都是統一交給文件系統管理的。

Linux文件系統會為每個文件分配兩個數據結構: 索引節點(index node) 和 目錄項(directory entry) ，它們主要用來記錄文件的元信息和目錄層次結構。

●索引節點，也就是inode, 用來記錄文件的元信息，比如inode編號、文件大小訪問許可權、創建時間、修改時間、 數據在磁碟的位置 等等。 索引節點是文件的唯一標識 ,它們之間一一對應, 也同樣都會被 存儲在硬碟 中,所以索引節點同樣佔用磁碟空間。

●目錄項，也就是dentry, 用來記錄文件的名字、索引節點指針以及與其他目錄項的層級關聯關系。多個目錄項關聯起來，就會形成 目錄結構 ，但它與索引節點不同的是,目錄項是由內核維護的一個數據結構,不存放於磁碟，而是 緩存在內存 。

由於索引節點唯一標識一個文件，而目錄項記錄著文件的名，所以目錄項和索引節點的關系是多對一,也就是說，一個文件可以有多個別字。比如，硬鏈接的實現就是多個目錄項中的索引節點指向同一個文件。

注意，目錄也是文件，也是用索引節點唯一標識，和普通文件不同的是，普通文件在磁碟裡面保存的是文件數據，而目錄文件在磁碟裡面保存子目錄或文件。

（PS：目錄項和目錄不是一個東西！你也不是一個東西（^_=）， 雖然名字很相近，但目錄是個文件。持久化存儲在磁碟,而目錄項是內核一個數據結構,緩存在內存。

如果查詢目錄頻繁從磁碟讀，效率會很低，所以內核會把已經讀過的目錄用目錄項這個數據結構緩存在內存，下次再次讀到相同的目錄時，只需從內存讀就可以,大大提高了 文件系統的效率。

目錄項這個數據結構不只是表示目錄，也是可以表示文件的。）

磁碟讀寫的最小單位是 扇區 ，扇區的大小隻有512B大小，很明顯，如果每次讀寫都以這么小為單位，那這讀寫的效率會非常低。

所以，文件系統把多個扇區組成了一個 邏輯塊 ，每次讀寫的最小單位就是邏輯塊(數據塊) , Linux中的邏輯塊大小為4KB,也就是一次性讀寫 8個扇區,這將大大提高了磁碟的讀寫的效率。

以上就是索引節點、目錄項以及文件數據的關系，下面這個圖就很好的展示了它們之間的關系:

索引節點是存儲在硬碟上的數據，那麼為了加速文件的訪問，通常會把索引節點載入到內存中。

另外，磁碟進行格式化的時候，會被分成三個存儲區域，分別是超級塊、索引節點區和數據塊區。

●超級塊,用來存儲文件系統的詳細信息，比如塊個數、塊大小、空閑塊等等。

●索引節點區,用來存儲索引節點;

●數據塊區，用來存儲文件或目錄數據;

我們不可能把超級塊和索引節點區全部載入到內存,這樣內存肯定撐不住，所以只有當需要使用的時候，才將其載入進內存，它們載入進內存的時機是不同的.

●超級塊:當文件系統掛載時進入內存;

●索引節點區:當文件被訪問時進入內存;

文件系統的種類眾多，而操作系統希望 對用戶提供一個統一的介面 ，於是在用戶層與文件系統層引入了中間層，這個中間層就稱為 虛擬文件系統(Virtual File System, VFS) 。

VFS定義了一組所有文件系統都支持的數據結構和標准介面,這樣程序員不需要了解文件系統的工作原理，只需要了解VFS提供的統一介面即可。

在Linux文件系統中，用戶空間、系統調用、虛擬機文件系統、緩存、文件系統以及存儲之間的關系如下圖:

Linux支持的文件系統也不少，根據存儲位置的不同，可以把文件系統分為三類:

●磁碟的文件系統，它是直接把數據存儲在磁碟中,比如Ext 2/3/4. XFS 等都是這類文件系統。

●內存的文件系統，這類文件系統的數據不是存儲在硬碟的,而是佔用內存空間，我們經常用到的/proc 和/sys文件系統都屬於這一類,讀寫這類文件,實際上是讀寫內核中相關的數據。

●網路的文件系統,用來訪問其他計算機主機數據的文件系統，比如NFS. SMB等等。

文件系統首先要先掛載到某個目錄才可以正常使用，比如Linux系統在啟動時,會把文件系統掛載到根目錄。

在操作系統的輔助之下，磁碟中的數據在計算機中都會呈現為易讀的形式，並且我們不需要關心數據到底是如何存放在磁碟中,存放在磁碟的哪個地方等等問題，這些全部都是由操作系統完成的。

那麼，文件數據在磁碟中究竟是怎麼樣的呢?我們來一探究竟!

磁碟中的存儲單元會被劃分為一個個的「 塊 」，也被稱為 扇區 ,扇區的大小一般都為512byte.這說明即使一塊數據不足512byte,那麼它也要佔用512byte的磁碟空間。

而幾乎所有的文件系統都會把文件分割成固定大小的塊來存儲，通常一個塊的大小為4K。如果磁碟中的扇區為512byte,而文件系統的塊大小為4K,那麼文件系統的存儲單元就為8個扇區。這也是前面提到的一個問題，文件大小和佔用空間之間有什麼區別?文件大小是文件實際的大小，而佔用空間則是因為即使它的實際大小沒有達到那麼大,但是這部分空間實際也被佔用，其他文件數據無法使用這部分的空間。所以我們 寫入1byte的數據到文本中,但是它佔用的空間也會是4K。

這里要注意在Windows下的NTFS文件系統中，如果一開始文件數據小於 1K,那麼則不會分配磁碟塊來存儲，而是存在一個文件表中。但是一旦文件數據大於1K,那麼不管以後文件的大小，都會分配以4K為單位的磁碟空間來存儲。

與內存管理一樣,為了方便對磁碟的管理,文件的邏輯地址也被分為一個個的文件塊。於是文件的邏輯地址就是(邏輯塊號，塊內地址)。用戶通過邏輯地址來操作文件,操作系統負責完成邏輯地址與物理地址的映射。

不同的文件系統為文件分配磁碟空間會有不同的方式，這些方式各自都有優缺點。

連續分配要求每個文件在磁碟上有一組連續的塊，該分配方式較為簡單。

通過上圖可以看到，文件的邏輯塊號的順序是與物理塊號相同的,這樣就可以實現隨機存取了，只要知道了第一個邏輯塊的物理地址, 那麼就可以快速訪問到其他邏輯塊的物理地址。那麼操作系統如何完成邏輯塊與物理塊之間的映射呢?實際上,文件都是存放在目錄下的，而目錄是一種有結構文件, 所以在文件目錄的記錄中會存放目錄下所有文件的信息，每一個文件或者目錄都是一個記錄。 而這些信息就包括文件的起始塊號和佔有塊號的數量。

那麼操作系統如何完成邏輯塊與物理塊之間的映射呢? (邏輯塊號, 塊內地址) -> (物理塊號, 塊內地址)，只需要知道邏輯塊號對應的物理塊號即可,塊內地址不變。

用戶訪問一個文件的內容,操作系統通過文件的標識符找到目錄項FCB, 物理塊號=起始塊號+邏輯塊號。 當然，還需要檢查邏輯塊號是否合法,是否超過長度等。因為可以根據邏輯塊號直接算出物理塊號，所以連續分配支持 順序訪問和隨機訪問 。

因為讀/寫文件是需要移動磁頭的，如果訪問兩個相隔很遠的磁碟塊,移動磁頭的時間就會變長。使用連續分配來作為文件的分配方式，會使文件的磁碟塊相鄰，所以文件的讀/寫速度最快。

連續空間存放的方式雖然讀寫效率高，但是有 磁碟空間碎片 和 文件長度不易擴展 的缺陷。

如下圖，如果文件B被刪除，磁碟上就留下一塊空缺，這時，如果新來的文件小於其中的一個空缺，我們就可以將其放在相應空缺里。但如果該文件的大小大於所

有的空缺，但卻小於空缺大小之和，則雖然磁碟上有足夠的空缺，但該文件還是不能存放。當然了，我們可以通過將現有文件進行挪動來騰出空間以容納新的文件,但是這個在磁碟挪動文件是非常耗時，所以這種方式不太現實。

另外一個缺陷是文件長度擴展不方便，例如上圖中的文件A要想擴大一下，需要更多的磁碟空間,唯一的辦法就只能是挪動的方式，前面也說了，這種方式效率是非常低的。

那麼有沒有更好的方式來解決上面的問題呢?答案當然有，既然連續空間存放的方式不太行，那麼我們就改變存放的方式，使用非連續空間存放方式來解決這些缺陷。

非連續空間存放方式分為 鏈表方式 和 索引方式 。

鏈式分配採取離散分配的方式，可以為文件分配離散的磁碟塊。它有兩種分配方式:顯示鏈接和隱式鏈接。

隱式鏈接是只目錄項中只會記錄文件所佔磁碟塊中的第一塊的地址和最後一塊磁碟塊的地址, 然後通過在每一個磁碟塊中存放一個指向下一 磁碟塊的指針， 從而可以根據指針找到下一塊磁碟塊。如果需要分配新的磁碟塊,則使用最後一塊磁碟塊中的指針指向新的磁碟塊,然後修改新的磁碟塊為最後的磁碟塊。

我們來思考一個問題, 採用隱式鏈接如何將實現邏輯塊號轉換為物理塊號呢?

用戶給出需要訪問的邏輯塊號i,操作系統需要找到所需訪問文件的目錄項FCB.從目錄項中可以知道文件的起始塊號，然後將邏輯塊號0的數據讀入內存,由此知道1號邏輯塊的物理塊號，然後再讀入1號邏輯塊的數據進內存，此次類推，最終可以找到用戶所需訪問的邏輯塊號i。訪問邏輯塊號i,總共需要i+ 1次磁碟1/0操作。

得出結論: 隱式鏈接分配只能順序訪問，不支持隨機訪問，查找效率低 。

我們來思考另外一個問題，採用隱式鏈接是否方便文件拓展?

我們知道目錄項中存有結束塊號的物理地址，所以我們如果要拓展文件，只需要將新分配的磁碟塊掛載到結束塊號的後面即可，修改結束塊號的指針指向新分配的磁碟塊，然後修改目錄項。

得出結論: 隱式鏈接分配很方便文件拓展。所有空閑磁碟塊都可以被利用到，無碎片問題，存儲利用率高。

顯示鏈接是把用於鏈接各個物理塊的指針顯式地存放在一張表中，該表稱為文件分配表(FAT, File Allocation Table)。

由於查找記錄的過程是在內存中進行的,因而不僅顯著地 提高了檢索速度 ，而且 大大減少了訪問磁碟的次數 。但也正是整個表都存放在內存中的關系，它的主要的缺點是 不適 用於大磁碟 。

比如，對於200GB的磁碟和1KB大小的塊，這張表需要有2億項，每一項對應於這2億個磁碟塊中的一個塊,每項如果需要4個位元組，那這張表要佔用800MB內存,很顯然FAT方案對於大磁碟而言不太合適。

一直都在，加油！（*゜Д゜）σ凸←自爆按鈕

鏈表的方式解決了連續分配的磁碟碎片和文件動態打展的問題，但是不能有效支持直接訪問(FAT除外) ,索引的方式可以解決這個問題。

索引的實現是為每個文件創建一個 索引數據塊 ，裡面存放的 是指向文件數據塊的指針列表 ,說白了就像書的目錄一樣,要找哪個章節的內容,看目錄查就可以。

另外， 文件頭需要包含指向索引數據塊的指針 ,這樣就可以通過文件頭知道索引數據塊的位置，再通過索弓|數據塊里的索引信息找到對應的數據塊。

創建文件時，索引塊的所有指針都設為空。當首次寫入第i塊時，先從空閑空間中取得一個塊， 再將其地址寫到索引塊的第i個條目。

索引的方式優點在於:

●文件的創建、增大、縮小很方便;

●不會有碎片的問題;

●支持順序讀寫和隨機讀寫;

由於索引數據也是存放在磁碟塊的，如果文件很小，明明只需一塊就可以存放的下，但還是需要額外分配一塊來存放索引數據，所以缺陷之一就是存儲索引帶來的開銷。

如果文件很大，大到一個索引數據塊放不下索引信息，這時又要如何處理大文件的存放呢?我們可以通過組合的方式，來處理大文件的存儲。

先來看看 鏈表+索引 的組合，這種組合稱為 鏈式索引塊 ，它的實現方式是在 索引數據塊留出一個存放下一個索引數據塊的指針 ，於是當一個索引數據塊的索引信息用完了，就可以通過指針的方式，找到下一個索引數據塊的信息。那這種方式也會出現前面提到的鏈表方式的問題，萬一某個指針損壞了，後面的數據也就會無法讀取了。

還有另外一種組合方式是 索引+索引 的方式，這種組合稱為多級索引塊，實現方式是通過一個索引塊來存放多個索引數據塊,一層套一層索引， 像極了俄羅斯套娃是吧๑乛◡乛๑ 

前面說到的文件的存儲是針對已經被佔用的數據塊組織和管理，接下來的問題是，如果我要保存一個數據塊, 我應該放在硬碟上的哪個位置呢?難道需要將所有的塊掃描一遍，找個空的地方隨便放嗎?

那這種方式效率就太低了，所以針對磁碟的空閑空間也是要引入管理的機制，接下來介紹幾種常見的方法:

●空閑表法

●空閑鏈表法

●點陣圖法

空閑表法

空閑表法就是為所有空閑空間建立一張表，表內容包括空閑區的第一個塊號和該空閑區的塊個數，注意，這個方式是連續分配的。如下圖:

當請求分配磁碟空間時，系統依次掃描空閑表裡的內容，直到找到一個合適的空閑區域為止。當用戶撤銷一個文件時，系統回收文件空間。這時，也需順序掃描空閑表,尋找一個空閑表條目並將釋放空間的第一個物理塊號及它佔用的塊數填到這個條目中。

這種方法僅當有少量的空閑區時才有較好的效果。因為，如果存儲空間中有著大量的小的空閑區,則空閑表變得很大,這樣查詢效率會很低。另外，這種分配技術適用於建立連續文件。

空閑鏈表法

我們也可以使用鏈表的方式來管理空閑空間，每一個空閑塊里有一個指針指向下一個空閑塊，這樣也能很方便的找到空閑塊並管理起來。如下圖：

當創建文件需要一塊或幾塊時，就從鏈頭上依次取下一塊或幾塊。反之，當回收空間時，把這些空閑塊依次接到鏈頭上。

這種技術只要在主存中保存一個指針, 令它指向第一個空閑塊。其特點是簡單,但不能隨機訪問，工作效率低，因為每當在鏈上增加或移動空閑塊時需要做很多1/0操作,同時數據塊的指針消耗了一定的存儲空間。

空閑表法和空閑鏈表法都不適合用於大型文件系統，因為這會使空閑表或空閑鏈表太大。

點陣圖法

點陣圖是利用二進制的一位來表示磁碟中一個盤塊的使用情況，磁碟上所有的盤塊都有一個二進制位與之對應。

當值為0時，表示對應的盤塊空閑，值為1時，表示對應的盤塊已分配。它形式如下:

在Linux文件系統就採用了點陣圖的方式來管理空閑空間,不僅用於數據空閑塊的管理,還用於inode空閑塊的管理，因為inode也是存儲在磁碟的，自然也要有對其管理。

前面提到Linux是用點陣圖的方式管理空閑空間，用戶在創建一個新文件時， Linux 內核會通過inode的點陣圖找到空閑可用的inode,並進行分配。要存儲數據時，會通過塊的點陣圖找到空閑的塊，並分配，但仔細計算一下還是有問題的。

數據塊的點陣圖是放在磁碟塊里的，假設是放在一個塊里,一個塊4K,每位表示一個數據塊,共可以表示4 * 1024 * 8 = 2^15個空閑塊,由於1個數據塊是4K大小，那麼最大可以表示的空間為2^15 * 4 * 1024 = 2^27個byte,也就是128M。

也就是說按照上面的結構，如果採用（一個塊的點陣圖+ 一系列的塊），外加一（個塊的inode的點陣圖+一系列的inode）的結構能表示的最大空間也就128M,

這太少了，現在很多文件都比這個大。

在Linux文件系統，把這個結構稱為一個 塊組 ，那麼有N多的塊組,就能夠表示N大的文件。

最終,整個文件系統格式就是下面這個樣子。

最前面的第一個塊是引導塊,在系統啟動時用於啟用引導，接著後面就是一個一個連續的塊組了,塊組的內容如下:

● 超級塊 ,包含的是文件系統的重要信息，比如inode總個數、塊總個數、每個塊組的inode個數、每個塊組的塊個數等等。

● 塊組描述符 ,包含文件系統中各個塊組的狀態,比如塊組中空閑塊和inode的數目等，每個塊組都包含了文件系統中「所有塊組的組描述符信息」。

● 數據點陣圖和inode點陣圖 ，用於表示對應的數據塊或inode是空閑的，還是被使用中。

● inode 列表 ，包含了塊組中所有的inode, inode 用於保存文件系統中與各個文件和目錄相關的所有元數據。

● 數據塊 ，包含文件的有用數據。

你可以會發現每個塊組里有很多重復的信息，比如 超級塊和塊組描述符表，這兩個都是全局信息，而且非常的重要 ，這么做是有兩個原因:

●如果系統崩潰破壞了超級塊或塊組描述符,有關文件系統結構和內容的所有信息都會丟失。如果有冗餘的副本,該信息是可能恢復的。

●通過使文件和管理數據盡可能接近，減少了磁頭尋道和旋轉,這可以提高文件系統的性能。

不過，Ext2 的後續版本採用了稀疏技術。該做法是，超級塊和塊組描述符表不再存儲到文件系統的每個塊組中,而是只寫入到塊組0、塊組1和其他ID可以表示為3、5、7的冪的塊組中。

在前面，我們知道了一個普通文件是如何存儲的，但還有一個特殊的文件,經常用到的目錄，它是如何保存的呢?

基於Linux 一切切皆文件的設計思想，目錄其實也是個文件,你甚至可以通過vim打開它，它也有inode, inode 裡面也是指向一些塊。

和普通文件不同的是， 普通文件的塊裡面保存的是文件數據，而目錄文件的塊裡面保存的是目錄裡面一項一項的文件信息 。

在目錄文件的塊中，最簡單的保存格式就是 列表 ，就是一項一項地將目錄下的文件信息(如文件名、文件inode.文件類型等)列在表裡。

列表中每一項就代表該目錄下的文件的文件名和對應的inode,通過這個inode,就可以找到真正的文件。

通常，第一項是「則」，表示當前目錄,第二項是.，表示上一級目錄, 接下來就是一項一項的文件名和inode。

如果一個目錄有超級多的文件,我們要想在這個目錄下找文件,按照列表一項一項的找,效率就不高了。

於是，保存目錄的格式改成 哈希表 ，對文件名進行哈希計算,把哈希值保存起來,如果我們要查找一個目錄下面的文件名，可以通過名稱取哈希。如果哈希能夠匹配上,就說明這個文件的信息在相應的塊裡面。

Linux系統的ext文件系統就是採用了哈希表，來保存目錄的內容,這種方法的優點是查找非常迅速，插入和刪除也較簡單,不過需要一些預備措施來避免哈希沖突。

目錄查詢是通過在磁碟上反復搜索完成，需要不斷地進行/0操作,開銷較大。所以,為了減少/0操作,把當前使用的文件目錄緩存在內存，以後要使用該文件時只要在內存中操作，從而降低了磁碟操作次數,提高了文件系統的訪問速度。

感謝您的閱讀，希望您能攝取到知識！加油！沖沖沖！（發現光，追隨光，成為光，散發光！）我是程序員耶耶！有緣再見。<－biubiu－⊂(`ω´∩)

⑹ 用C語言設計一個簡單的二級文件系統

簡單嗎，我這有手機的文件系統最簡單功能實現都要上萬行

⑺ 基於多級文件目錄的文件管理系統設計的設計原理是什麼有著什麼樣的背景知識

Flash 存儲器( Flash Memory) 是一種高可靠性、高密度的固態存儲器件。 其存儲方式是完全非易失性的，掉電後可以保存數據；可以在線寫入，並可按頁連續位元組寫入，存取速度快，所以嵌入式系統通常使用Flash 存儲器作為存儲設備。 但Flash存儲器也存在著兩個主要缺陷:一是在重寫之前必須進行擦除，因為Flash 存儲器劃分成很多擦除塊(SectorOErase) ，對任何一位數據進行修改必須先擦除整個塊(Sector) ；二是擦除塊的擦除次數有限，當一個塊提前達到擦除次數上限時， 將導致整個Flash 存儲器無法使用。 所以，目前PC 機上很多成熟的基於磁碟的文件系統在Flash 存儲器上使用都存在著不足。
嵌入式系統應具有的特點: 一是高可靠性，在惡劣環境下系統仍能正常工作；二是低消耗，受成本限制系統設計必須量體裁衣，去除冗餘；三是高效率，在佔用較少資源情況下保證功能需求，這樣就要求演算法簡單，效率高。 而日誌文件系統(Log-St ruct ured File System) 在數據更新時無需將數據寫入原存儲區域，適應Flash 存儲器無法進行重寫這一特點。 目前，針對Flash 存儲器的缺陷而設計的Linux 下的J FFS 文件系統，就是採用簡化的日誌文件系統。 J FFS 文件系統將磨損均衡集成於清除機制之中，在帶來掉電可恢復功能的同時，大大減少了塊擦除的次數，提高了文件系統的存取速度和效率。 但是，J FFS 文件系統無法單獨使用，或者使用於其它實時操作系統中。 對由於受成本和實時性限制而無法使用Linux 的一些嵌入式系統，也就無法使用J FFS 文件系統。基於上述分析，該嵌入式文件系統適合在開源實時操作系統(如μC/OS-II) 和無操作系統的情況下使用。
嵌入式文件系統原理
在日誌文件系統中，一個文件被修改後不是被寫入到原來的存儲空間，而是被加到所有內容的後面，象日誌一樣被更新，這就是日誌文件系統的基本原理。 由於同一個文件在文件系統中會留下不同的版本，所以系統需要設置一張表標注文件的最新與以前的版本。 在內容不斷添加時為不將存儲空間占滿，系統設計了一種回收機制，回收無效內容佔用的空間。
日誌文件系統在文件更新時不用將文件寫回原來的地址，這對Flash 存儲器這種存儲介質最為適合。 文中所設計的嵌入式文件系統採用了日誌文件系統的設計原理，以及J FFS 文件系統將磨損均衡集成於清除機制之中的方法。 該系統將一個可擦寫塊平分為多個簇，文件的讀寫以簇為單位進行。簇的狀態有3 種:臟、干凈和空。 臟表示所存內容已被置為無效；干凈表示所存數據有效；空表示可以寫入數據。 文件和目錄在該系統中被作為節點，一個節點佔用若干個簇，節點中的內容連續存儲，但不能越過塊邊界存儲。 該系統設置一個索引節點，保存整個系統的信息，其中包含保存有各簇狀態的簇狀態表。
每一次文件更新後內容都將被添加至末尾處，索引節點也被更新，總是佔用最末尾的干凈簇。 回收臟簇時，將所要擦除塊中的干凈簇重寫到空簇中，再進行塊擦除。 當內容寫至存儲體末端，則從頭部重新開始循環存儲。 所設計的文件系統的操作過程見圖1。
ic72新聞中心
嵌入式文件系統設計
Flash 存儲器中的存儲結構
Flash 存儲器中的存儲結構見圖2。 該存儲器中每個簇的第一個字作為簇的狀態字，表示此簇是否為一個節點的首簇或空簇。 每個節點的首部存放此節點屬性(文件/目錄/索引節點) 和節點標識號。
ic72新聞中心
索引節點
索引節點存放該文件系統的大部分信息。 包括32 位的索引節點更新號、一張簇狀態表、下一個要被擦除塊的塊號、給下一個新建節點(文件或目錄) 的節點編號、系統根目錄信息表。系統每一次更新都會產生新的索引節點，索引節點更新號加1。 按照Flash 存儲器的使用壽命10 年計算，需要每秒更新136 次以上，才能達到索引節點更新號的上限，所以認為擁有最大更新號的索引節點為最新的索引節點。 簇狀態表中對應每一個簇有兩個Bit 位，表示各個簇的狀態(干凈01 ，臟11 ，空00) 。 根目錄信息表存放根目錄下的各個目錄項，每個目錄項包括:屬性(文件0x1/目錄0x0) 、文件名或目錄名、節點編號、此文件(或目錄) 對應節點的起始簇地址、根目錄表的大小可變。
目錄節點
目錄節點存放的內容有目錄名，目錄項個數，及所有目錄項信息。 文件節點存放文件名，文件大小，文件屬性及文件內容，內存中的目錄結構見圖3。
ic72新聞中心
內存數據結構及基本操作
該文件系統載入(Mount ) 後，會在內存中建立一個系統的映象。 該映象包括:索引節點中的信息、目錄及文件信息、每個可擦寫塊中包含的節點信息、未存檔的節點信息。 簇狀態表、索引節點更新號、新節點編號、下一擦除塊號等索引節點中的內容，在內存中均作為不同的變數。 內存中為每個文件和目錄都建立了映象，數據結構見圖4 和圖5。
ic72新聞中心
ic72新聞中心
內存中的文件節點不包含文件真正的數據，而使用指針。 文件被打開時，在內存中創建一塊新存儲區域存放數據，數據指針便指向此存儲區，未被打開時，此指針指向空。 對於每個目錄有1 個目錄層數，表示此目錄的深度，如根目錄的目錄層數為0 ，根目錄的下一級目錄則為1 ，依此類推。 存儲地址保存文件或目錄在Flash 中的地址。 文件和目錄都被存在上一級目錄下，所屬目錄指針即指向上一級目錄在內存中的數據結構，根目錄的所屬目錄指針即為空。 對於同目錄下的不同節點，在內存中使用鏈表將其串聯，同目錄文件指針即聯成鏈表。 鏈表的首指針保存在上一級目錄中，首目錄項指針即指向鏈表的首項。 為提高塊擦寫的效率，存儲在同一個可擦寫塊中的各個節點在內存中也建立一個鏈表，塊隊列指針即用於連成此鏈表。 為標識被修改的節點，利用一個未保存隊列，未保存隊列指針即用來建立此隊列。
該文件系統載入(mount ) 時，首先順序掃描Flash 中的每個索引節點，查找出最大的索引節點更新號，此更新號對應的索引節點即為最新的索引節點。 查找到最新索引節點後，將簇狀態表等信息映射到內存的數據結構中。 依據索引節點中的根目錄信息，遍歷所有節點，建立內存中的目錄文件結構，並將節點添加到對應的擦寫塊隊列中。 對一個文件編輯並保存的過程見圖6。
ic72新聞中心
文件打開時，先在內存中分配一塊空間作為數據區，將內容寫入，並定位文件節點的數據指針指向該內存中的數據區。 如果文件內容被修改，就將文件節點添加到未存檔隊列，依次寫入Flash 存儲器中，並修改簇狀態表。 保存時將內存中數據區內容寫入F 中，釋放申請的內存空間，修改節點中的數據指針和簇狀態表，再將文件的所有上級目錄重新寫入Flash ，最後將更新後的索引節點內容寫入Flash。 如果文件未被修改，則只需修改數據指針即可。
節點加入未存檔隊列的順序按照目錄層數的大小排列，文件節點排在隊列首，目錄層數最大的排在其後，目錄層數為1 的排在隊列末尾，根目錄不加入未存檔隊列。
嵌入式文件系統特殊處理機制
均衡擦寫機制
為了避免任意一個可擦除塊因擦寫次數過多而過早報廢，文件系統對Flash擦寫時採用了均衡擦寫機制。 考慮到系統的精簡性，擦寫在整片Flash 的各塊中依次進行，一塊擦寫完後，下一個被擦寫的塊即為後一個塊，在系統的索引節點中保存了下一個要擦除的塊號。 當文件系統中的剩餘空間減少到設定值時，系統會擦除此塊，以回收臟簇佔用的空間。 對應每個可擦寫塊都有一個節點隊列，此塊中包含的節點都加入其中。塊擦除的流程見圖7。
ic72新聞中心
首先，將未保存於隊列中的節點保存，清未保存隊列。 然後將塊隊列中的所有文件節點轉移到空簇中，同時將文件路徑上的各級目錄加入到未存檔隊列中。 對於塊隊列中的目錄節點，則將它和其路徑上的各級目錄加入未存檔隊列中，按照未保存隊列的順序，依次將各個目錄寫入Flash 中，最後寫入最新的索引節點。 因為目錄節點加入未存檔隊列時，按照目錄層數的大小排列，所以按照未保存隊列的順序寫入時，可以保證當一個目錄要被寫入Flash 時，它的所有下級目錄已被寫入Flash 中。 所有下級目錄在Flash 中的存儲地址都已確定。當該文件系統的空間將達到存儲上限時，可能會出現特殊情況，即廢簇回收時，空簇的空間不足，無法將所有干凈簇重寫。 文件系統為此建立了應急機制，先將文件節點內容存在內存中，這時新建一個臨時未保存隊列，專門保存文件節點，在塊擦寫完成後，將剩餘的文件節點寫入新的空簇中，其演算法與圖7 所示流程大致相同。 但是，一旦在擦寫時斷電，會導致該塊上的所有數據丟失。
斷電錯誤處理機制
當系統遭遇斷電重新啟動後，索引節點中的信息會與系統中的狀態不符，這時便需要錯誤處理機制。 錯誤一般是索引節點中標注的空簇已被寫入了數據，錯誤處理就是將此簇標志為臟簇，並查找下一個空簇重新寫入。
多任務處理機制
該文件系統允許同時打開多個文件，在多任務操作系統下，為了避免沖突建立了多任務處理機制。 系統允許打開的多個文件在內存中同時被編輯修改，但是對Flash 寫入操作有限制。 處理方法是設立Flash 寫入保護區，在此區中只允許當前正在執行的任務執行Flash 寫入操作。 實現Flash 寫入保護區的方法是建立一個初始值為1 的信號量，當一個節點需要Flash 寫入時，首先申請信號量，完成後再釋放信號量。 Flash 寫入保護區見圖6 、圖7。在圖6 中，空操作語句是用來對多個文件的保存進行同步。 例如，有文件1 和文件2 需要保存，先將文件1 的內容寫入Flash 中，文件1 路徑下的目錄節點被添加到未保存隊列中，再將文件2 的內容寫入Flash 中，文件2 路徑下的目錄節點也被添加到未保存隊列中，最後將未保存隊列中的所有節點都寫入Flash 中。 這樣，如果同一路徑下的兩個文件同時存檔，可避免路徑下的相同目錄節點被寫入兩次，從而提高了效率。 不足之處在於，如果很多文件同時存檔，會導致索引節點在一段時間內都無法寫入Flash 存儲器，有斷電丟失的危險。 但對於一般嵌入式系統來說，很少會碰到這種情況。 當進行Flash存儲器擦寫時，在取塊隊列首節點至索引節點寫入完成這段時間內都不允許進行其他Flash 存儲器的寫入操作，這是為了保證數據的完整性，同時也提高了文件系統的穩定性。
無目錄文件系統的優化
許多嵌入式系統設計中雖沒有目錄管理的要求，但是對執行效率和資源消耗的要求較高。 對於不要求有目錄管理的精簡文件系統，在設計時也進行了優化。 精簡文件系統在Flash 中的存儲格式與上述設計相同，文件系統中的所有文件信息都保存在索引節點的根目錄信息表中。 精簡文件系統在內存中的映象則要簡單很多，只包含索引節點中的信息，包括簇狀態表、下一個擦除塊、下一個新節點的標號和根目錄信息，而不用為每個文件都建立內存中的映象，節省大量的內存空間。 文件的編輯存檔過程簡化為:打開文件、編輯、將文件寫入Flash 存儲器、將修改後的索引節點寫入Flash 存儲器。 擦寫則只需通過查詢根目錄信息表中的各個目錄項，將塊中的所有文件節點寫入空簇即可。在無目錄管理的情況下，精簡文件系統佔用的內存資源可以減少，操作也可便捷，提高了效率。 對於大量只需要按名存取的簡單文件管理的小型嵌入式系統而言，針對Flash 存儲器的簡單文件系統將佔用資源少，執行效率高，有很大的應用價值。
嵌入式文件系統實現及性能分析
該文件系統的實現採用了分層方法，分為3 層4 個部分:應用程序介面、文件系統核心、操作系統調用介面、Flash 存儲器驅動，實現結構見圖8。
ic72新聞中心
實現平台中RTOS 為μC/OSOII 實時操作系統，CPU 使用三星S4510B作為處理器，Flash 存儲器晶元為FUJ ITSU 的29LV160 TE。 針對不同的實時操作系統和Flash 存儲器晶元需要實現不同的操作系統介面和Flash 存儲器驅動。
針對μC/ OSOII 編寫操作系統調用介面，包括5個函數: ①系統調用介面初始化FS_Sys_Interface_Init ( ) ，創建互斥信號量和內存分區； ② Flash 寫入關閉FS_Sys_Write_Lock ( ) ，禁止Flash 寫入操作，調用μC/OS-II 中OSMutePend ( ) ； ③ Flash寫入打開FS_Sys_Write_Unlock ( ) ，重新允許Flash 寫入操作，調用μC/OS-II 中OSMutePost() ； ④內存空間申請FS_Sys_Mem_Alloc( ) 和內存空間添加FS_Sys_Mem_Add ( ) ， 都調用OSMemGet ( ) 來完成； ⑤內存空間釋放FS_Sys_Mem_Free ( ) ，調用OSMemPut ( ) 完成，將申請的內存塊全部釋放。針對29LV160 TE 這款Flash 存儲器晶元，定義一個FlashDef 結構體的全局變數， 用於存儲Flash 器件信息，並且編寫針對此款Flash 的塊擦寫函數FS_Device_Sector_Erase ( ) 和數據寫入函數FJ FS_Device_Write ( ) 。
完成這兩部分的實現後，該系統就可運行調試。 測試應用程序介面(API) 。 應該提供的各部分功能，並在突然斷電情況下，測試文件系統的恢復情況。無目錄管理的精簡文件系統的載入，可在2μs內完成，文件寫入耗時主要為快閃記憶體的等待時間，系統本身只佔用不到200 個位元組的內存，產生的代碼段大小為7 K。 完整的文件系統載入時，需要建立內存中映象，耗時根據文件數量的多少而不同，一般為10μs ，產生的代碼段大小為11 K。 系統寫入效率較高，在無目錄管理的配置下尤其明顯。 試驗中系統在多次斷電的情況下，系統仍能恢復至上次存檔的狀態，雖會導致個別文件未更新，但不會導致文件系統崩潰。
間的關系熟悉嗎？的和（並）。互斥事件（互不相容事件

⑻ 操作系統-文件系統

人們對信息有存儲的需求，早期計算機信息在保存在紙帶上，存和讀都不方便，且容量很低，而存儲信息的需求未能得到滿足，到了磁碟存儲器的出現，對程序和數據等信息的管理的發展才得到質的飛躍。出現文件系統是需要把信息以一種單元，即文件的形式，存儲在磁碟或其它外部存儲介質上，導致了文件系統的出現。

文件系統是操作系統中統一管理信息資源的一種軟體。它管理文件的存儲、檢索、更新、提供安全可靠的共享和保護手段，並且方便用戶使用。從用戶的角度看，文件系統負責為用戶建立文件、讀寫文件、修改文件、復制文件和撤銷文件等，還能對文件按名存取。

文件是一組帶標識的、在邏輯上有完整意義的信息項的序列，這里的標識就是文件名，」信息項「構成了文件的內容。

外存是相對內存而言，主要用來存儲信息，其特點是斷電後仍可保存信息，容量大，速度較慢，成本較低等
外存儲設備通常由驅動部分和存儲介質兩部分組成，存儲介質又常被卷。

存儲介質有：磁帶、磁碟、光碟、快閃記憶體

其中磁帶是順序存儲，只能讀了前面磁帶的內容才能讀後面，存取都一樣，不能跳著讀取，因此磁帶適合存儲不經常變化的內容，比如放歌。

磁碟支持隨機讀取，磁碟由帶有讀寫磁頭的機械臂和磁碟組成，磁碟像光碟，上面有磁性材料。系統對磁碟初始化時，會劃分出一些同心圓，稱為磁軌，信息只能存儲在磁軌上，磁軌分會被分成多個弧段，稱為扇區，每個磁軌有4-32個扇區。使用時，驅動器的馬達帶去磁碟高速勻速旋轉，磁頭一直停留在盤面表面上方並可以在不同磁軌移動，當找到目標磁軌時，碰頭不動，磁碟依然轉動，這時經過磁頭的信息就被讀出來可寫進去。

光碟是激光作用下材料變化的非磁記錄介質。

快閃記憶體是電荷擦除，支持隨機存取，沒有機械運動部件，壽命和可靠性高。

文件可以從不同的維度來進行分類：
按用途的方式分類：

按文件組織形式分類：

文件邏輯結構就是用戶所看到的文件組織形式，文件邏輯結構是經過抽象的結構，所描述的是文件中信息組織形式。按邏輯結構可以把文件劃分成三類：無結構的字元流式文件（由位元組組成）、定長記錄文件和不定長記錄文件（由記錄組成）；

文件的物理結構是指文件存儲在外儲設備上的結構，有三種存儲結構：順序存儲、鏈式存儲、索引存儲；

順序存儲：文件存在連續的空間上，只要知道到起始地址和長度就可以讀取文件。
優點：支持隨機存取、
缺點：不支持動態擴充，容易產生碎片。

鏈式存儲：文件存在不連續的物理塊中，文件控制塊保存第一個物理塊的指針，之後每個物理塊都有一個指針指向下一個物理塊地址，如FAT文件系統
優點：可以動態擴充，提高磁碟利用空間；修改添加快。
缺點：
1.可靠性低。若其中某個物理塊出錯會導致後面全部塊讀取不到。
2.存取速度慢，不適於隨機存取文件，需要從首個物理塊一直讀取到物理塊；

索引存儲：使用一張表來存儲索引，每個索引指向邏輯文件的信息塊。
優點：可以動態擴充，支持隨機存取；
缺點：較多的尋道次數和尋道時間；索引表本身增加了存儲空間的開銷。

文件目錄主要是用途是為了管理和索引文件，其結構簡單說是一張表，表中存儲著文件名、文件控制塊、物理地址，通過文件名可以快速的讀取到對應的文件。

一級目錄是一張線性表，優點是：結構簡單、實現簡單；缺點：無法解決不同用戶的文件名相同；文件多時查找慢。
二級目錄是分為主目錄和用戶目錄，主目錄給出所有用戶目錄所在物理位置； 而用戶目錄則給出所有文件的FCB;優點：不同用戶文件可以重名、查找速度比一級目錄快、能實現文件共享
多級目錄（樹形目錄）除了最低一級物理塊裝有文件信息外，其它每一級的目錄存儲的都是下一級的目錄或文件說明信息，多級目錄存在唯一的概目錄。優點是層次清楚、解決文件重名問題、查找速度快。

目錄是指文件路徑。
目錄項是是文件控制塊以一條記錄的形式存儲在目錄文件中。
目錄文件是多個文件控制塊集中在一起形成的文件。

參考：《操作系統》機械工業出版社 2017年版