UNIX傳統(tǒng)文件系統(tǒng)s5fs的實現(xiàn)

xzh2002

文件系統(tǒng)實現(xiàn)—重點講述s5fs

兩種在現(xiàn)代UNIX 系統(tǒng)中常見的、用于通用目的的本地文件系統(tǒng)是System V 文件系統(tǒng)
(s5fs)和伯克利快速文件系統(tǒng)(FFS)。s5fs 是UNIX 最初的文件系統(tǒng)，System V 的所有版本和一些商業(yè)UNIX 系統(tǒng)都支持s5fs 。由伯克利UNIX 4.2BSD 版引進的FFS 比sSfs 性能更好，更可靠且功能更強大。它在商業(yè)界贏得了廣泛的接受，融入SVR4 系統(tǒng)是FFS 文件系統(tǒng)的頂峰(SVR4 支持三種用于通用目的文件系統(tǒng)：s5fs，F(xiàn)FS 和VxFS，Veritas 的日志文件系統(tǒng))。
當FFS 第一次被提出時，UNIX 文件系統(tǒng)框架還只能支持一種類型的文件系統(tǒng)。這就迫使
廠商們必須在s5fs 和FFS 之間作出選擇。由Sun[ Kiel 86] 提出來的vnode/vfs 接口可以允許多種類型的文件系統(tǒng)共存于同一臺機器上。這樣，原先的文件系統(tǒng)實現(xiàn)必須要修改，以便能同vnode/vfs 集成起來。FFS 集成vnode/vfs 之后成為現(xiàn)在的UNIX 文件系統(tǒng)(ufs)。在[ Bach 86] 中對s5fs 做了詳細的介紹[ Leff 89] 則對FFS 做了詳細的分析。本章主要總結和比較了兩種不同的實現(xiàn)，既是為了完整性，同時也為理解以后幾章描述的高級文件系統(tǒng)打下基礎。
在UNIX 中，文件包括各種I/O 對象，比如通過套接字和STREAMS 建立的網(wǎng)絡連接，像管道和FIFO 之類的進程間通信機制，以及塊設備和字符設備等等。vnode/vfs 體系結構將文件和文件系統(tǒng)抽象為一種概念，并向內(nèi)核的其他部分提供模塊化接口。這一結構促成了幾種專用文件系統(tǒng)的產(chǎn)生。這些文件系統(tǒng)跟文件和I/O 關系很小，而僅僅利用該接口的抽象特征來實現(xiàn)特殊的功能。本章將介紹幾種有趣的實現(xiàn)。
最后，本章描述了UNIX 的磁盤高速緩存。在早期的像SVR3 和4.3BSD 中的UNIX 版本中，
所有的文件I/O 都使用這個高速緩存。像SVR4 之類的現(xiàn)代版本將文件I/O 與內(nèi)存管理集成在一起，通過將文件映射到內(nèi)核的地址空間中來訪問它們。盡管本章介紹了這種方法的一些細節(jié)，大多數(shù)的討論將放在14 章中介紹(14 章主要討論SVR4 中的虛存管理)。傳統(tǒng)的磁盤高速緩存機制仍用在元數(shù)據(jù)塊中。這里，元數(shù)據(jù)指的是一個文件或文件系統(tǒng)的屬性和輔助信息。高速緩存是一種全局資源，可以被所有的文件系統(tǒng)所共享，而不僅僅用于某—種特定的文件系統(tǒng)。 我們首先討論s5fs，并描述其在磁盤仁的排列方式和在內(nèi)核中的組織。盡管FFS 和s5fs在很多重要的方面相差很大，但它們還是有一些共同點的，其基本操作的實現(xiàn)方式相同。我們關于FFS 的討論將主要集中在它們的區(qū)別上面，除了特別指明，所有在9.3 節(jié)中描述的s5fs的一般算法也適用于FFS 。

1、 System V 文件系統(tǒng)(s5fs)
文件系統(tǒng)駐留在某個的邏輯盤或分區(qū)內(nèi)，每個邏輯磁盤可能最多只能有一個文件系統(tǒng)。每一個文件系統(tǒng)是自包含的，有自己的根目錄、子目錄、文件和所有相關的數(shù)據(jù)和元數(shù)據(jù)。用戶可見的文件樹是由一個或多個這樣的文件系統(tǒng)連接而成的。一個分區(qū)在邏輯上可以被視為塊的線性數(shù)組。一個塊的大小為512 字節(jié)乘以2 的n 次冪(不同的版本可能為512，1024 或2048 個字節(jié))。它代表了文件空間分配和文件I/O 操作的粒度。物理塊號(簡稱塊號)是這個線性數(shù)組的索引，它唯一地標識了某個指定磁盤分區(qū)上的一個塊。這個號必須由磁盤驅(qū)動程序轉(zhuǎn)換成柱面號、磁道和扇區(qū)號。這種轉(zhuǎn)換依賴于磁盤的物理特性(柱面和磁道、每個磁道中的扇面?zhèn)�數(shù))以及分區(qū)在磁盤上的位置。

在分區(qū)的開始部分是包含有操作系統(tǒng)自舉(加載和初始)代碼的啟動區(qū)(boot area)。雖然只有一個分區(qū)需要包含啟動信息，但每一分區(qū)都包含一個空的啟動區(qū)。緊接著啟動區(qū)的是超級塊，其中包含著文件系統(tǒng)屬性和元數(shù)據(jù)。在超級塊后面是i 節(jié)點表，這是i 節(jié)點的一個線性數(shù)組。每一個文件都有一個i 節(jié)點。
i 節(jié)點由i 節(jié)點號(inode number)唯一地標識，這個號跟該i 節(jié)點在i 節(jié)點表中的索引相同。每個i 節(jié)點有64 個字節(jié)。幾個i 節(jié)點放在一個磁盤塊中。超級塊和i 節(jié)點表的起始偏移在系統(tǒng)的每個分區(qū)中都是不變的。因此i 節(jié)點號就可以很容易地轉(zhuǎn)換為一個磁盤塊號和從該塊起始位置開始的偏移。i 節(jié)點表長度固定(其長度是在該分區(qū)中創(chuàng)建文件系統(tǒng)時設定)，它限制了一個分區(qū)中最多含有的文件數(shù)。在i 節(jié)點表之
后的空間是數(shù)據(jù)區(qū)。其中有文件和目錄的數(shù)據(jù)塊以及間接塊，間接塊中包含有指向文件數(shù)據(jù)
塊的指針.

2、目錄
s5fs 的目錄是包含有文件和子目錄列表的特殊文件。它包含有一些固定長度的記錄，其中每個記錄16 字節(jié)。前兩個字節(jié)包含的內(nèi)容是i 節(jié)點號，下面14 個字節(jié)是文件名。這就限制了一個磁盤分區(qū)中最多有65535 個文件(因為0 不是一個合法的i 節(jié)點號)，并且每個文件名占14 個字符的長度。如果文件名少于14 個字符，則會以空(NULL)字符填補。因為目錄也是文件，所以它也有一個i 節(jié)點，只是在i 節(jié)點中有一個域?qū)⑵錁俗R為目錄。目錄的頭兩項第一個是“.”，代表了目錄本身，第二個是“..”，表示父目錄。如果一個表項的i 節(jié)點號為零，則表示對應的文件不存在。一個分區(qū)的根目錄和它的“.”表項的i 節(jié)點號都是2 。這也是文件系統(tǒng)能夠識別其為根目錄的方法。

3、i 節(jié)點
每一個文件都有一個與之相聯(lián)系的i 節(jié)點。i 節(jié)點中包含有文件的管理信息或者稱為元
數(shù)據(jù)。它存儲在i 節(jié)點表的磁盤空間內(nèi)。當一個文件被打開，或者一個目錄變?yōu)榛顒幽夸洉r，
內(nèi)核將磁盤i 節(jié)點中的內(nèi)容復制到內(nèi)存中的一個也稱為i 節(jié)點的一個數(shù)據(jù)結構中。但這個結
構中包含有許多磁盤i 節(jié)點中所不包含的信息。為了不產(chǎn)生二義性，我們將在磁盤上的數(shù)據(jù)
結構(struct dinode)稱為磁盤i 節(jié)點，而將在內(nèi)存中的結構(struct inode)稱為內(nèi)存i 節(jié)點。

域 大小(字節(jié))說明
di_mode 2 文件類型，權限等
di_nlinks 2 對文件的硬鏈接數(shù)
di_uid 2 屬主UID
di_gid 2 屬主GID
di_size 4 字節(jié)大小
di_addr 39 塊地址數(shù)組
di_gen 1 總數(shù)(每次i 節(jié)點重用于一個新文件時都遞增)
di_atlme 4 上次訪問的時間
di_mtime 4 上次修改的時間文件
di_ctime 4 上次改動的時間i 節(jié)點(除了di_atime 或di_mtime 的改變)
di_mode 域被分為幾個位元(圖9-3)，前四位指定了文件的類型，既可能是IFREG(常規(guī)
文件)，也可能是IFDIR(目錄文件)，還有可能是IFBLK(塊設備)，IFCHR(字符設備)等等。9
個低位分別指定廠文件所有者，用戶組以及其他人對該文件的讀、寫、執(zhí)行權限。

關于di_addr 需要詳細地闡述一下。UNIX 文件在磁盤上并不是連續(xù)的。當文件長度增加時，內(nèi)核從磁盤上任何方便的地方分配一個新的塊。這樣就可以很方便地增大或縮小文件，
同時又沒有連續(xù)分配策略固有的磁盤碎片問題。很顯然，這種分配策略仍然沒有完全消除磁
盤碎片，因為每個文件的最后一個塊可能包含有未用的空間。平均下來每個文件浪費了半個
磁盤塊的空間。
這種方法要求文件系統(tǒng)對文件的每一個磁盤塊的位置都維持一個映射。這可以用一個物
理塊地址數(shù)組來實現(xiàn)。每個文件中的邏輯塊號便是這個數(shù)組的索引。這個數(shù)組的大小依賴于
文件的大小。大文件可能要用幾個磁盤塊來存儲該數(shù)組。然而大多數(shù)文件都很小[ Saly 81] ，
如果使用大的數(shù)組會浪費很多空間。而且如果將磁盤塊數(shù)組存放在分離的塊中訪問文件需要
多次讀操作，會降低系統(tǒng)性能。
UNIX 的解決方法是在i 節(jié)點中用一個很小的表存儲i 節(jié)點，如果文件是夠大，則使用附加的結構存儲i 節(jié)點。這種方法對小文件來說效率很高，同時也能足夠靈活地處理大文件。
29 個字節(jié)的di_attr 域由13 個元素表項組成，每個表項用三個字節(jié)來存放物理塊號。數(shù)組元素0 到9 包含著文件的從0 到9 的數(shù)據(jù)塊的i 節(jié)點號。因此，如果一個文件的數(shù)據(jù)塊個數(shù)少于等于10 個，則這些數(shù)據(jù)塊的地址都在i 節(jié)點表中找到。元素10 是間接塊的i 節(jié)點號，即塊中包含塊號數(shù)組。表項11 指向一個二級間接塊，在二級間接塊中有其他間接塊的塊號。最后表項12 指向一個三級間接塊，其中包含有二級間接塊的i節(jié)點號。

對于有1024 個字節(jié)的塊來說，這種策略使用直接索引可以尋址10 個塊，使用一次間接
塊可以尋址256 多塊，使用二級間接塊可以尋址65536 多塊，使用三級間接塊可以尋址16，
777，216 多塊。
UNIX 文件中可以包含有空洞(holes)。如果一個用戶創(chuàng)建了一個文件，然后將文件指針
調(diào)整到一個很大的偏移(通過調(diào)用lseek 可在打開文件對象中設置偏移指針，詳見8.2.4 小
節(jié))，再往里寫入數(shù)據(jù)。這樣，該偏移前的空間中就沒有數(shù)據(jù)因此使形成了一個“空洞”。如果一個進程試圖從文件“空洞”處讀取數(shù)據(jù)，它將得到全零字節(jié)。
文件“空洞”有時候會很大，甚至整個磁盤塊都是“空洞”。為這樣的磁盤塊分配空間，
無疑是很浪費的。解決方法是內(nèi)核將di_addr 數(shù)組的相應表項(既可能是直接塊，也可能是間接塊)置為零。當用戶試圖讀這樣一個塊時，內(nèi)核將充滿0 的塊返回給用戶。只有當有人試圖往這個塊里寫數(shù)據(jù)時內(nèi)核才分配磁盤空間。
拒絕為空洞分配空間有很重要的意義。一個進程在試圖往空洞里寫數(shù)據(jù)時可能意外地超
出了磁盤空間。如果復制一個包含空洞的文件，新文件在磁盤上可能會有充滿零的頁，而不
是預期的空洞。這是因為復制文件要先從源文件中讀出內(nèi)容，然后寫到目的文件中。當內(nèi)核
讀取一個空洞時，它創(chuàng)建了一個充滿零的頁，然后該頁會被原樣復制到目的文件中去。這樣，
一些像tar 或cpio 之類的在文件級而非原始磁盤級上操作的備份和歸檔工具便會出現(xiàn)問題。系統(tǒng)管理員可能要為一個文件系統(tǒng)作備份，可是他會發(fā)現(xiàn)復制的數(shù)據(jù)在相同磁盤上卻沒有足夠的空間來恢復。

4、超級塊
超級塊中包含有文件系統(tǒng)本身的元數(shù)據(jù)。每一個文件系統(tǒng)都有一個超級塊，它在磁盤文
件系統(tǒng)的開始處。當內(nèi)核安裝一個文件系統(tǒng)時讀取超級塊，將其放在內(nèi)存中，直到該文件系
統(tǒng)被卸載。超級塊包含有如下的信息：
·文件系統(tǒng)中塊的大小
·i 節(jié)點表中塊大小
·空閑塊和空閑i 節(jié)點的數(shù)目
·空閑塊表
·空閑i 節(jié)點表
因為文件系統(tǒng)可能有很多空閑i 節(jié)點或空閑磁盤塊，因此無論是將空閑塊表還是將空閑
i 節(jié)點表完全放在超級塊中都是不現(xiàn)實的。對于i 節(jié)點，超級塊維持一個局部表。當空閑i
節(jié)點表為空時，內(nèi)核掃描磁盤尋找空閑i 節(jié)點(di_mode==0)，將其充實到表中。
這種方法對于空閑塊表是不可能的，因為不可能通過檢查一個塊的內(nèi)容而判別它是否空
閑。因此無論在任何時候，文件系統(tǒng)都必須維持一個在磁盤上的所有空閑塊的完整列表。超級塊包含了表的第一部分并且在表的尾部增加或刪除數(shù)據(jù)。表的第一個元素指向包含該表下一部分的磁盤塊等等。

有時候，磁盤塊分配程序會發(fā)現(xiàn)超級塊中的空閑塊表僅包含一個元素。存儲在該元素中
的值是包含空閑表下一部分的塊號(圖9-5 中的塊a)。內(nèi)核將表從那個塊中復制到超級塊，
這樣那個塊便成為空閑的了。這樣的好處是存儲空閑塊表占用的空間直接依賴于分區(qū)上的空
閑空間大小。對于一個幾乎全滿的磁盤來說，根本不需要浪費任何空間去存儲空閑塊表。

5、s5fs 內(nèi)核組織
i 節(jié)點是s5fs 中的基本的文件系統(tǒng)相關對象。它是與一個s5fs v 節(jié)點相關的私有數(shù)據(jù)
結構，正如前面所說，內(nèi)存i 節(jié)點同磁盤i 節(jié)點是不同的。本節(jié)主要講述內(nèi)存i 節(jié)點，我們
將會看到s5fs 是如何操縱它們來實現(xiàn)各種文件系統(tǒng)操作的。

6、內(nèi)存i 節(jié)點
struct inode 代表一個內(nèi)存i 節(jié)點。其中包含所有磁盤i 節(jié)點的內(nèi)容，另外，它還有其
他一些數(shù)據(jù)，如：
·v 節(jié)點——i 節(jié)點的i_vnode 數(shù)據(jù)域包含有文件的v 節(jié)點。
·文件所在分區(qū)的設備號
·文件的i 節(jié)點號
·用于同步和高速緩存管理的標志位
·i 節(jié)點在空閑i 節(jié)點表的指針(指向其前后節(jié)點的指針)
·i 節(jié)點在哈希隊列中的指針(指向其在哈希隊列中的前后節(jié)點的指針)。內(nèi)核根據(jù)i 節(jié)
點的i 節(jié)點號由哈希函數(shù)求得索引值，從而在需要時可快速得到數(shù)據(jù)。
·上一次讀取塊的塊號。

7、i 節(jié)點查找
文件系統(tǒng)無關層中的lookuppn()函數(shù)用于路徑名解析。它調(diào)用VOP_LOOKUP 操作，每次解析一個分量。當解析到一個s5fs 目錄的時候，則要調(diào)用s5lookup()函數(shù)。s5lookup 首先檢查日錄名查詢高速緩存。如果找不到，它每次讀取目錄中的一個塊，查找指定的文件名表項。
如果目錄中包含有該文件的—個合法表項，s5lookup()得到該表項的i 節(jié)點號。接著它
調(diào)用iget()函數(shù)去定位i 節(jié)點。iget()使用哈希函數(shù)處理i 節(jié)點號，然后到相應的哈希隊列
中查找i 節(jié)點。如果i 節(jié)點不在這個哈希隊列中，iget()分配一個i 節(jié)點，并且從磁盤i 節(jié)點中讀取數(shù)據(jù)將其初始化。當將磁盤i 節(jié)點復制到內(nèi)核i 節(jié)點中去時，iget()將di_addr[ ] 中的每個元素擴展到四個字節(jié)。接著將該新i 節(jié)點加入到相應的哈希隊列中。它同時也初始化v 節(jié)點，將其v_op 域指向s5vnodeops 向量，v_data 指向其本身，v_vfsp指向它所屬的文件系統(tǒng)。最后它向s5lookup()返回一個指向i 節(jié)點的指針。s5lookup()將該指針返回給lookuppn()。
注意，iget()是s5fs 中唯一用來分配和初始化i 節(jié)點和v 節(jié)點的函數(shù)。例如，當創(chuàng)建一個新文件時，s5create()分配一個未使用的i 節(jié)點號(從超級塊的空閑i 節(jié)點表中得到)并且調(diào)用iget()將其調(diào)入到內(nèi)存中。

文件I/O系統(tǒng)調(diào)用read()和write()都接受一個文件描述符(open 返回的索引)、數(shù)據(jù)源或目的用戶緩沖區(qū)地址，以及要傳送的字節(jié)數(shù)作為參數(shù)。文件中的偏移是從與描述符相聯(lián)系的打開文件對象中獲得的。在I/O 操作的最后，將此次讀寫操作傳輸?shù)淖止?jié)數(shù)加到偏移量上去，這意味著下一次讀寫操作要從本次讀寫操作結束的地方開始。如果想進行隨機I/O，用戶必須首先調(diào)用lseek 函數(shù)將文件指針移到希望的偏移處。
文件系統(tǒng)無關代碼利用文件描述符從描述符表中索引得到指向打開文件對象(struct file)的指針，然后驗證文件是否按所需要的方式被打開。如果是，內(nèi)核從file 結構中得到v 節(jié)點指針。在每次I/O 前內(nèi)核調(diào)用VOP_RWLOCK 操作將對文件的訪問串行化。在s5fs 中，這是通過給i 節(jié)點加上排斥性鎖來實現(xiàn)的②。這保證了在一次系統(tǒng)調(diào)用中讀寫的數(shù)據(jù)是一致的，并且對文件的所有寫是單線程的。內(nèi)核接著便可以調(diào)用VOP_READ 或VOP_WRITE操作，這將分別導致對s5read()和s5write()的調(diào)用。在早期的實現(xiàn)中，文件I/O 例程使用了磁盤塊高速緩存(block buffer cache)，它是一塊專為文件系統(tǒng)塊預留的內(nèi)存區(qū)域。SVR4 把文件I/O 和虛擬內(nèi)存結合了起來，它僅為元數(shù)據(jù)塊使用磁盤塊高速緩存。9.12 節(jié)中將描述原有的高速緩存，本節(jié)只是總結SVR4 的操作.
我們使用read 操作作為例子詳細地講述一下I/O 過程。s5read()將文件I/O 操作的起始偏移轉(zhuǎn)換成邏輯塊號以及塊內(nèi)偏移量。接著它每次讀取一頁數(shù)據(jù)③，方法是將塊映射到內(nèi)核虛地址空間并且調(diào)用uiomove()將數(shù)據(jù)復制到用戶空間，uiomove()調(diào)用copyout()例程來進行實際數(shù)據(jù)傳輸。如果頁沒有在物理內(nèi)存中，或者內(nèi)核沒有將其合理地進行地址轉(zhuǎn)換，
eopyout()將產(chǎn)生一個頁面失效。失效處理函數(shù)將標識出該頁所屬的文件，然后在文件v 節(jié)點上進行VOP_GETPAGE 操作。
在s5fs 中，該操作是由s5getpage()實現(xiàn)的。s5getpage()首先調(diào)用bmap()函數(shù)將邏輯
塊號轉(zhuǎn)換成磁盤上的物理塊號。接著它搜索v 節(jié)點的頁表(由v_page 所指的)查看該頁是否已經(jīng)在內(nèi)存中了，如果不是，s5getpage()分配一空閑頁，調(diào)用磁盤驅(qū)動程序從磁盤上讀取數(shù)據(jù)。
在I/O 操作進行過程中調(diào)用進程一直處于睡眠狀態(tài)。當塊讀取完畢之后，磁盤驅(qū)動程序
喚醒調(diào)用進程，恢復copyout()中的數(shù)據(jù)復制過程。在將數(shù)據(jù)復制到用戶空間之前copyout()
首先要確認一下用戶是否對其所指定的要將數(shù)據(jù)復制于其中的緩沖區(qū)有寫權限。否則，用戶
可能無意或有意地指定錯誤的地址，導致很多問題。例如，如果用戶指定一內(nèi)核地址，內(nèi)核
將會錯誤地重寫內(nèi)核的正文或數(shù)據(jù)結構。
當所有的數(shù)據(jù)都已讀完或者發(fā)生錯誤時s5read()返回，系統(tǒng)無關代碼將v 節(jié)點解鎖(使
用VOP_RWUNLOCK)，將file 結構中的指針偏移加上讀取的字節(jié)數(shù)，然后返回用戶。read 的返
回值是讀取字節(jié)總數(shù)。一般來說它等于要求的字節(jié)數(shù)，除非到達了文件尾或者發(fā)生了其他的
錯誤。
write 系統(tǒng)調(diào)用過程類似，但有一些差別。write 修改過的數(shù)據(jù)并不立即寫回磁盤，而是
留在內(nèi)存中，根據(jù)高速緩存替換算法在以后的某一時刻寫回磁盤。除此外，write 可能會增
加文件尺寸因而需要分配數(shù)據(jù)塊，也有可能是間接塊。最后，如果只有磁盤塊的一部分數(shù)據(jù)
被修改，內(nèi)核必須要從磁盤上將整個數(shù)據(jù)塊讀入內(nèi)存，修改相關的部分，再寫回磁盤。

8、i 節(jié)點的分配與回收
一個i 節(jié)點只要它的v 節(jié)點的引用計數(shù)不為零，它就會一直保持活躍，當引用計數(shù)降至
零時，文件系統(tǒng)無關代碼便會調(diào)用VOP_INACTIVE 操作釋放i 節(jié)點。在SVR2 中，空閑i 節(jié)點
被標明是無效的，因此在需要的時候還要從磁盤重新讀取。這會導致效率低下，因此新的UNIX
系統(tǒng)將i 節(jié)點盡可能地放在高速緩存中。當i 節(jié)點變?yōu)椴换钴S時，內(nèi)核將其放到空閑表中，
但并不使之無效。iget()函數(shù)可以在需要的時候找到它，因為它在被重用之前一直被放在某
一哈希隊列中。
每一個文件系統(tǒng)都有一個長度固定的i 節(jié)點表，這樣就限制了內(nèi)核中同時活動的i 節(jié)點
數(shù)。在SVR3 中，i 節(jié)點高速緩存機制使用一種最近最少使用的替換算法。內(nèi)核釋放i 節(jié)點時將其放到該表的尾部，當分配i 節(jié)點時則從其頭部獲得。盡管這是一種很通用的啟發(fā)式高速緩存替換算法，但把它用到i 節(jié)點的高速緩存中卻并不是很合適。這是因為有些不活動的i節(jié)點大概要比別的不活動i 節(jié)點更有用。
如果一個文件當前正被使用，其i 節(jié)點便被釘(pinned)在i 節(jié)點表中，當文件被訪問時，
它的頁被放到高速緩存中。當文件變?yōu)椴换顒訒r，它的一些頁可能仍在內(nèi)存中。這些頁可以
通過訪問v 節(jié)點的頁表的v_page 域而被找到。分頁系統(tǒng)(paging system)也按照v 節(jié)點指針和頁面在文件中的偏移將它們放到哈希隊列中，如果內(nèi)核重用i 節(jié)點(以及v 節(jié)點)，這些頁
便丟掉了其標識。如果進程需要某一頁，盡管該頁已經(jīng)在內(nèi)存中，內(nèi)核也必須重新到磁盤上
讀取。 注意：如果一個對象既不能被釋放也不能被刪除，我們便說該對象被釘在內(nèi)存中。有
引用計數(shù)的對象會被釘在內(nèi)存中，直到其最后一個引用被釋放。另一個例子是，一個進程可
以用mlock 系統(tǒng)調(diào)用將其地址空間的一部分釘在內(nèi)存中。因此，重用那些沒有內(nèi)存緩沖頁的
i 節(jié)點比較好。當v 節(jié)點引用計數(shù)到達零后，內(nèi)核調(diào)用VOP_INACTIVE 操作釋放v 節(jié)點以及其私有數(shù)據(jù)(在這里便是i 節(jié)點)，當釋放i 節(jié)點時，內(nèi)核檢查v 節(jié)點的頁表。如果頁表為空，
內(nèi)核便將i 節(jié)點放到空閑表的頭部。如果頁表不為空，內(nèi)核則將i 節(jié)點放到空閑表的尾部。
如果i 節(jié)點保持不活躍，分頁系統(tǒng)便及時地將它的頁釋放掉。[ Bark 90] 討論了一種新的i 節(jié)點分配和回收方法，該方法根據(jù)系統(tǒng)的負載調(diào)整內(nèi)存i節(jié)點的數(shù)目。文件系統(tǒng)使用內(nèi)核內(nèi)存分配程序動態(tài)地分配i 節(jié)點，而不使用固定長度的i 節(jié)點表。這樣，內(nèi)存中的i 節(jié)點數(shù)便可以根據(jù)需要增力喊減少。系統(tǒng)管理員也沒有必要在預先配置系統(tǒng)時猜測系統(tǒng)中該有多少個i 節(jié)點。當iget()在i 節(jié)點哈希隊列中找不到某一i 節(jié)點時，它從空閑表中刪除第一個節(jié)點。如果這個i 節(jié)點在內(nèi)存中仍然有頁面，iget()將它放回到空閑表的尾部，然后調(diào)用內(nèi)核內(nèi)存分配程序分配一個新的內(nèi)存i 節(jié)點結構。當然，也可以檢索整個空閑表找到一個在內(nèi)存中沒有頁面的i 節(jié)點，但是我們上面描述的算法更簡單有效。它唯一的缺點是有可能分配的i 節(jié)點數(shù)目比需要的多。
在一個多用戶分時系統(tǒng)上的負載基準測試[ Gaed 82] 實驗顯示新算法對系統(tǒng)時間(內(nèi)核態(tài)所占的CPU 的時間)的占有減少了12％到16％。這種方法最初是在s5fs 中實現(xiàn)的，但是也可用在其他的文件系統(tǒng)中，比如說FFS 。

9、對s5fs 的分析
s5fs 以其設計簡單而著名，可是設計的簡單性卻給它的可靠性、性能、功能等帶來很多
問題。本節(jié)我們便討論一下這些問題，正是這些問題才導致了BSD 快速文件系統(tǒng)的出現(xiàn)。
最主要的可靠性考慮是超級塊。超級塊中有很多關于整個文件系統(tǒng)的重要信息，比如空
閑塊表和空閑i 節(jié)點表等。每個文件系統(tǒng)僅包含超級塊的—個副本，如果副本崩潰，整個文
件系統(tǒng)便不再可用。有幾個原因?qū)е滦阅艿牟患�。s5fs 把所有的i 節(jié)點組織到文件系統(tǒng)的開始位置，而用剩余的磁盤空間容納文件數(shù)據(jù)塊。訪問—個文件需要首先讀取i 節(jié)點，然后再讀取文件數(shù)據(jù).這種分隔導致在兩次操作間有一段很長的搜索時間，這使得I/O 時間大增，i 節(jié)點是隨機組織的，而沒有將相關文件的i 節(jié)點分組，比如將同一個目錄下的文件組織起來。這樣對一個目錄底下所有文件的訪問操作(比如，ls -l)就會導致磁盤的隨機訪問。
磁盤塊分配方案也不是最佳的。當文件系統(tǒng)第一次被創(chuàng)建時(使用mkfs 程序)，s5fs 以
最佳方式組織空閑塊表，這樣磁盤塊分配就會以旋轉(zhuǎn)連續(xù)的方法進行了。然而，隨著文件的
創(chuàng)建和刪除，返回空閑表的磁盤塊的順序被完全打亂。這樣文件的順序訪問就會變慢，這是
因為邏輯上連續(xù)的磁盤塊在物理磁盤上可能相距非常遠。
磁盤塊大小也是影響性能的一個因素，SVR2 的磁盤塊大小512 字節(jié)，SVR3 則使用了1024字節(jié)。提高磁盤塊大小之后，一次磁盤訪問可以讀取更多的數(shù)據(jù)，從而提高了性能。然而，這會浪費更多的磁盤空間，因為平均每個文件就要浪費半個磁盤塊的空間。這就需要有更加靈活的磁盤中間分配方案。最后，該文件系統(tǒng)在功能上仍然有很多限制。將文件名字長度限制在14 個字符之內(nèi)可能在早期UNIX 使用的環(huán)境中不會有很多麻煩，然而對一個功能強大的商用大系統(tǒng)來說，這和限制是不能接受的。有些程序往往通過在已有文件名上加上一些擴展來自動產(chǎn)生文件名，可是有了這個限制，他們不得不小心翼翼地避免使得文件名長度超過14 個字符。另外，每個文件系統(tǒng)只允許有65535 個i 節(jié)點也是很大的限制。
所有上述這些問題促使伯克利UNIX 開發(fā)一種新的文件系統(tǒng)，這就是快速文件系統(tǒng)
(FFS)，它首次出現(xiàn)于4.2BSD 中。下面一節(jié)討論其主要特征。