一、文件系統基礎

1.文件邏輯結構

無結構文件

無結構文件：文件內部的數據就是一系列二進制流或字符流組成。又稱“流式文件”。如：Windows 操作系統中的 .txt 文件。

有結構文件

有結構文件：由一組相似的記錄組成，又稱“記錄式文件”。每條記錄又若干個數據項組成。如：數據庫表文件。一般來說，每條記錄有一個數據項可作為關鍵字（作為識別不同記錄的ID）

有結構文件分為順序文件、索引文件、索引順序文件和直接文件或散列文件

順序文件：

定長記錄的順序文件，若物理上采用順序存儲，則可實現隨機存取；若能再保證記錄的順序結構，則可實現快速檢索（即根據關鍵字快速找到對應記錄）

索引文件：

索引表本身是定長記錄的順序文件。因此可以快速找到第 i 個記錄對應的索引項。可將關鍵字作為索引號內容，若按關鍵字順序排列，則還可以支持按照關鍵字折半查找。每當要增加/刪除一個記錄時，需要對索引表進行修改。由于索引文件有很快的檢索速度，因此主要用于對信息處理的及時性要求比較高的場合

索引順序文件：

索引順序文件是索引文件和順序文件思想的結合。索引順序文件中，同樣會為文件建立一張索引表，但不同的是：并不是每個記錄對應一個索引表項，而是一組記錄對應一個索引表項。

多級索引順序文件：

2.文件目錄

文件控制塊（FCB）

FCB 的有序集合稱為“文件目錄”，一個FCB就是一個文件目錄項。FCB 中包含了文件的基本信息（文件名、物理地址、邏輯結構、物理結構等），存取控制信息（是否可讀/可寫、禁止訪問的用戶名單等），使用信息（如文件的建立時間、修改時間等）。最重要，最基本的還是文件名、文件存放的物理地址。

目錄結構

單級目錄

單級目錄實現了“按名存取”，但是不允許文件重名。在創建一個文件時，需要先檢查目錄表中有沒有重名文件，確定不重名后才能允許建立文件，并將新文件對應的目錄項插入目錄表中

兩級目錄結構

多級目錄結構

無環圖目錄結構

可以用不同的文件名指向同一個文件，甚至可以指向同一個目錄（共享同一目錄下的所有內容）。需要為每個共享結點設置一個共享計數器，用于記錄此時有多少個地方在共享該結點。用戶提出刪除結點的請求時，只是刪除該用戶的FCB、并使共享計數器減1，并不會直接刪除共享結點。只有共享計數器減為0時，才刪除結點。

注意：共享文件不同于復制文件。在共享文件中，由于各用戶指向的是同一個文件，因此只要其中一個用戶修改了文件數據，那么所有用戶都可以看到文件數據的變化。

3.文件保護

口令保護

為文件設置一個“口令”（如：abc112233），用戶請求訪問該文件時必須提供“口令”。口令一般存放在文件對應的 FCB 或索引結點中。用戶訪問文件前需要先輸入“口令”，操作系統會將用戶提供的口令與FCB中存儲的口令進行對比，如果正確，則允許該用戶訪問文件

優點：保存口令的空間開銷不多，驗證口令的時間開銷也很小。
缺點：正確的“口令”存放在系統內部，不夠安全。

加密保護

用某個“密碼”對文件進行加密，在訪問文件時需要提供正確的“密碼”才能對文件進行正確的解密。
例如：一個最簡單的加密算法——異或加密
假設用于加密/解密的“密碼”為“01001”

優點：保密性強，不需要在系統中存儲“密碼”
缺點：編碼/譯碼，或者說加密/解密要花費一定時間。

訪問控制

在每個文件的FCB（或索引結點）中增加一個訪問控制列表（Access-Control List, ACL），該表中記錄了各個用戶可以對該文件執行哪些操作。

4.文件共享

硬鏈接

索引結點中設置一個鏈接計數變量 count，用于表示鏈接到本索引結點上的用戶目錄項數。

若 count = 2，說明此時有兩個用戶目錄項鏈接到該索引結點上，或者說是有兩個用戶在共享此文件。
若某個用戶決定“刪除”該文件，則只是要把用戶目錄中與該文件對應的目錄項刪除，且索引結點的count值減 1。
若 count>0，說明還有別的用戶要使用該文件，暫時不能把文件數據刪除，否則會導致指針懸空。
當 count = 0 時系統負責刪除文件。

軟鏈接

當 User3 訪問“ccc”時，操作系統判斷文件“ccc”屬于 Link 類型文件，于是會根據其中記錄的路徑層層查找目錄，最終找到 User1 的目錄表中的“aaa”表項，于是就找到了文件1的索引結點。

5.文件系統實現

文件物理結構

磁盤塊：

連續分配

鏈接分配

隱式鏈接

用戶給出要訪問的邏輯塊號 i，操作系統找到該文件對應的目錄項（FCB），從目錄項中找到起始塊號（即0號塊），將0號邏輯塊讀入內存，由此知道1號邏輯塊存放的物理塊號，于是讀入1號邏輯塊，再找到2號邏輯塊的存放位置……以此類推。因此，讀入i號邏輯塊，總共需要 i+1 次磁盤I/O。

結論：采用鏈式分配（隱式鏈接）方式的文件，只支持順序訪問，不支持隨機訪問，查
找效率低。另外，指向下一個盤塊的指針也需要耗費少量的存儲空間。

顯式鏈接

索引分配

6.文件存儲空間管理

文件空間劃分：

文件空間管理：

1. 空閑表法
   
2. 空閑鏈表
   

1. 位式圖法
   
2. 成組鏈接法

空閑表法、空閑鏈表法不適用于大型文件系統，因為空閑表或空閑鏈表可能過大。UNIX系統中采用了成組鏈接法對磁盤空閑塊進行管理。
文件卷的目錄區中專門用一個磁盤塊作為“超級塊”，當系統啟動時需要將超級塊讀入內存。并且要保證內存與外存中的“超級塊”數據一致。

7.文件系統的層次結構

8.磁盤結構

9.磁盤調度算法

先來先服務算法（FCFS）

最短尋找時間優先（SSTF）

掃描算法（SCAN）

LOOK 調度算法

循環掃描算法（C-SCAN）

C-LOOK 調度算法