一、檔案系統結構

磁盤的邏輯單元為塊，記憶體和磁盤之間的I/O傳輸以塊為單位執行，

磁盤的特點

1. 可以原地重寫，可以從磁盤上讀一塊兒，修改該塊，并將它寫回到原來的位置
2. 可以直接訪問磁盤上的任意一塊，因此，可以方便地按順序或隨機訪問檔案

檔案系統需要提供高效快捷磁盤訪問，以便輕松存盤、定位、提取資料，即存盤檔案、訪問檔案

檔案系統有兩個不同的設計問題

1. 訪問問題：如何定義檔案系統對用戶的介面
2. 存盤問題：創建資料結構和演算法，把邏輯檔案系統映射到物理外存設備

檔案系統本身通常由許多不同層組成，每層實際利用更低層功能，創建新的功能，以用于更高層的服務，

設備驅動程式可以作為翻譯器，他的輸入作為高級指令，輸出由底層的、硬體特定指令組成，
基礎檔案系統只需向適當設備驅動程式發送命令，
邏輯檔案系統通過檔案控制塊維護檔案結構，
檔案控制塊（FCB）包含有關檔案的資訊，包括所有者、權限、檔案內容的位置等，

大多數作業系統支持多種不同的檔案系統，舉例：

• CD-ROM ISO9660 檔案格式
• Unix 檔案系統（Unix File System）
• Windows檔案系統：FAT（File Allocation Table），FAT32, FAT64,NTFS（Windows NT File System）
• Linux 檔案系統：可擴展檔案系統（Extended file system），分布式檔案系統（Distributed File System）

二、檔案系統實作

1.概述

在磁盤上，檔案系統包括的資訊有

1. 如何啟動存盤在那里作業系統
2. 總的塊數
3. 空閑塊的數目和位置
4. 目錄結構
5. 各個具體檔案 等

上述許多結構會在之后詳細講述，這里簡述如下：

• 引導控制塊（每個卷）：可以包含從該卷引導作業系統的所需資訊，如果磁盤不包括作業系統，則這塊的內容為空，UFS稱為引導塊（boot block），NFS稱為磁區引導扇區（partition boot sector）
• 卷控制塊（每個卷）：包括卷的詳細資訊（磁區的塊數、塊的大小、空閑塊的數量和指標、空閑
  FCB 的數量和指標等），UFS稱為超級塊兒（super block）,NTFS主控檔案表（master boot sector）
• 每個檔案的FCB包含該檔案的許多詳細資訊，他有一個唯一的標識號，以便與目錄條目相關聯
• 每個檔案系統的目錄結構用于組織檔案

記憶體中的資訊用于管理檔案系統并通過快取來提高性能，這些資料在安裝檔案裝系統時被加載，在檔案系統操作期間被更新，在卸載是被卸載，這些結構型別包括：

1. 每個行程的打開檔案表：包括一個指向系統的打開檔案表中合適條目的指標和其他資訊
2. 整個系統的打開檔案表：包括每個打開檔案的FCB副本和其他資訊

創建一個新檔案
3. 應用程式呼叫邏輯檔案系統，邏輯檔案系統指導目錄結構的格式，它會分配一個新的FCB
4. 系統將相應的目錄資訊讀入記憶體
5. 更新目錄結構和FCB
6. 將結果寫回磁盤

一旦檔案被創建，就能用于I/O，不過，首先他要被打開，系統呼叫open()將檔案名傳到邏輯檔案系統，系統呼叫open()：

1. 首先搜索整個系統的打開檔案表，查看是否已經被打開，如果是，則在該行程的打開檔案表創建一個條目，并指向現有整個系統的打開檔案表，
2. 否則，根據檔案名搜索目錄結構
3. 找到后，它的FCB會復制到記憶體的整個系統的開放檔案表中（該表還存放著打開該檔案的行程數量） ，接下來，在該行程的打開檔案表創建一個條目，并指向現有整個系統的打開檔案表，

Open() 回傳值：檔案描述符是一個非負整數，它是一行程打開檔案表的索引值，指向系統范圍內打開檔案表相應條目

2.虛擬檔案系統

作業系統如何才能將多個型別的檔案系統集成到目錄結構中？用戶如何在訪問檔案系統空間時，可以無縫地在檔案系統型別間遷移？大多數作業系統采用面向物件的技術來簡化、組織、模塊化實作，

資料結構和程式用于隔離基本的作業系統呼叫的功能與實作細節，因此，檔案系統的實作有三個主要層構成，
第一層為檔案系統介面，
第二層為虛擬檔案系統（VFS），把檔案系統的通用操作和具體實作分開，虛擬檔案系統提供了在唯一標識一個檔案的機制，VFS基于vnode 的檔案表示結構，它包含了一個數值識別符號來唯一表示網路上的一個檔案，

1. VFS能區分不同本地檔案系統
2. VFS能區分本地檔案系統和遠程檔案系統

三、目錄實作

1.線性串列

采用檔案名稱和資料塊指標的線性串列

• 優點：編程簡單
• 缺點：因為需要搜索，運行較為費時

2.哈希表

哈希表根據檔案名得到一個值，并回傳一個指向線性串列中元素的指標

• 優點：減少目錄搜索時間
• 缺點：兩個檔案名哈希到相同的位置時可能發生沖突；因哈希表固定大小，創建檔案需要哈希表重建時，比較麻煩，

四、磁盤空間的分配方法

1.連續分配

每個檔案在磁盤上占有一組連續的塊， 檔案的連續分配可以用檔案第一塊的磁盤地址和連續塊的數量（即長度）來定義

連續分配支持順序訪問和直接訪問
問題：當檔案需要擴展，檔案大小變大時會無法擴
展
解決：找更大的連續空間，復制過去

基于擴展的連續分配方案
用以下引數來定義檔案

1. 開始地址
2. 塊兒數
3. 指向下一個擴展塊兒的指標（擴展塊兒可以是多個）

定義格式：
檔案【開始地址，塊兒數，指向下一個擴展塊的指標】

2.連接分配

每個檔案是磁盤塊兒的鏈表，磁盤塊分布在磁盤的任何地方，檔案有起始塊和結束塊來定義

定義格式：【起始塊，結束塊】

同時，每個磁盤塊都有指向下一個磁盤塊的地址，

優點：沒有磁盤空間浪費
缺點：

1. 不支持檔案的直接訪問
2. 需要更多的磁盤空間（來記錄指標）

鏈接分配的一個重要變種是檔案分配表
每個卷的開始部分用于存盤檔案分配表(File Allocation Table)，表中每個磁盤塊都有一個FAT條目，并可通過塊號索引，（未使用的塊為0，使用的塊包含下一個塊兒號）

目錄條目含有檔案首塊號碼，通過這個塊號索引的FAT條目包含檔案下一塊的號碼，這個鏈會繼續下去，直到最后一塊，最后一塊的表條目值為檔案結束值，

3.索引分配

通過將所有指標放在一起，即索引塊
檔案用索引塊來定義， 每個檔案有其索引塊，

這里有一個問題，索引塊應為多大？
每個檔案必須有一個索引塊，因此索引塊應盡可能小，然而必能太小，否則放不下足夠多的指標，為處理這個問題，有如下一些機制：

1. 鏈接方案：為了處理大檔案，可以將多個索引塊鏈接起來
2. 多層次索引：用第一層索引塊指向一組第二層的索引塊，第二層索引塊再指向檔案塊
3. 組合方案：用于基于UNIX的檔案系統，將索引塊的前15個指標存盤在檔案的i-node中，其中，前12個指標指向直接塊，剩下3個指標指向間接塊
   

五、磁盤空閑空間的管理

1.位向量

空閑空間表實作為位圖, 或位向量，每塊用一位（bit）表示，1表示塊空閑；0表示塊已分配

2.鏈表

所有空閑塊用鏈表鏈接起來，并將指向第一個空閑塊兒的指標保存在特殊位置，同時快取在記憶體，
每個塊兒含有下一個塊兒的指標

3.組

將n個空閑塊的地址保存在第一個空閑塊中，
這些空閑塊中的前n－1個為空，而最后一塊包含另外n個空閑塊的地址，
比鏈表好的是空閑塊的地址可以很快找到，而且可以明確一段連續空閑塊空間

例：n=3

4.計數

基于以下事實：
通常有多個連續塊需要同時分配或釋放，尤其是在使用連續分配時，因此記錄

• 記錄第一塊的地址和緊跟第一塊的連續的空閑塊的數量，
• 空閑空間表的每個條目包括磁盤地址和數量

例：

六、檔案系統的性能和效率

磁盤空間的有效使用（效率），取決于

• 磁盤分配和目錄管理演算法
• 保留在檔案目錄條目中的資料型別

改善性能的方法：快取

1. 緩沖區快取：一塊獨立記憶體，位于其中的塊是馬上需要使用的
2. 頁面快取：將檔案資料作為頁而不是塊來快取，頁面快取使用虛擬記憶體技術，將檔案資料作為頁來快取，比采用物理磁盤塊來快取更高效
3. 板載高速快取
   
   如果沒有統一快取，則會由下圖情況發生：
   
   系統呼叫read()和write()會通過緩沖區快取，然而，記憶體映射呼叫需要使用兩個快取，即頁面快取和緩沖區快取，記憶體映射先從檔案系統中讀入磁盤塊,并放入緩沖區快取，由于虛擬記憶體系統沒有緩沖區快取介面，緩沖快取內的檔案必須復制到頁面快取中，

采用統一緩沖快取
統一緩沖快取：統一使用緩沖器快取來快取行程頁和檔案資料，

無論是快取塊還是頁面都有置換問題，
檔案的讀入或寫出一般是按順序進行，所以，不適
合采用LRU演算法，因為最近使用的頁面最后才會用甚至根本不會再用，

順序訪問可以通過馬上釋放和預先讀取來加以優化

1. 馬上釋放（free-behind）：請求下一頁時，馬上釋放上一頁
2. 預先讀取（read-ahead）：請求頁之后的下一個頁也一起讀入

七、檔案系統的恢復

目錄資訊一般事先保存在記憶體中以加快訪問，有時會導致目錄結構中的資料和磁盤塊中的資料不一致，
解決：

1. 一致性檢查：比較目錄結構中的資料和磁盤塊中的資料，嘗試著去修正不一致
2. 備份&恢復：
   I. 備份（backup）：利用系統程式來備份資料到其他的存盤設備，軟盤，磁帶
   II. 恢復（recovery）：通過從備份來恢復丟失的檔案或磁盤

基于日志結構的檔案系統

• 檔案創建涉及到目錄結構修改，FCB分配，資料塊分配等
• 所有元資料（meta data）的變化寫入日志上，一旦這些修改寫到日志，就認為已經提交了，
• 提交了的事務，并不一定馬上完成操作
• 當整個提交的事務已經完成時，就從日志中洗掉事務條目
• 如果系統崩潰，日志檔案可能還存在事務，它包含的任何事務雖然已經由作業系統提交了，但還沒有完成到檔案系統，必須重新執行，