i-node 和 data block。
圖片來源：Professor Eggert, UCLA CS 111
2015.1.15 初版
2017.9.15 二版
一、File System Structure
Directory Implementation overview
Linear list of file names with pointer to the data blocks.
- simple to program
- time-consuming to execute
- ex : FAT and ext 2,3
Linear list with hash data structure.
- decreases directory search time
- collisions – situations where two file names hash to the same location
- fixed size
B-trees
- XFS, NTFS, ext4
- Scaling to terabyte/petabyte filesystems
二、Free Space Management
Disk allocation/free space 單位是以 block 為主。
1. Bit Vector：用一組 bits 來代表 blocks 配置與否，一個 bit 對應一個Block。
- 優點：Simple，且易於找到連續可用空間 (即找到連續的 0)
- 缺點：bit vector 儲存佔用 memory 空間，所以此法不適用於大型 disk
2. Link List：用 link list 將 free block 串接，形成一個 AV List。
- 優點：加入/刪除 block 容易
- 缺點：效率不佳。因為在找尋可用區塊時，需從頭檢視此串列，I/O time 過長 (檢視一個 block 就須做一次 I/O) 。
3. Combination (組合法，Grouping) ：向量加上 link list。取某個可用區塊記錄其它可用區塊之編號。若此區塊不足以容納所有的 free block 編號，則再以其它區塊記錄並用 link 串連。
- 優點：加入/刪除 block 容易，可迅速取得大量可用區塊。
- 缺點：效率不佳，I/O time 過長。
4. Counting：適用於連續區塊較多之情況。在一個 free block 中，記錄其後的連續可用區塊數目 (含自已)。
- 如果連續區塊數目夠多，則 link list 長度可大幅縮短。
三、Allocation Methods
1. 連續性配置 (Contiguous allocation)
若檔案大小為 n 個 blocks，則 OS 必須在 disk 上找到 >= n 個連續 free blocks 才能配置。
記錄方式 :
- File Name, Size, Starting Block #
優點：
- 可支援 sequential access 及 random access
- seek time 通常較短 (檔案所佔的連續區塊大都會落在同一個 track 上)
缺點：
- external fragmentation
- 檔案大小無法任意增/刪
- 建檔時須事先宣告大小
2. 連結配置 (Link allocation)
若檔案大小為 n 個區塊，則 OS 必須在 disk 上找到 >= n 個可用區塊即可配置 (不一定要連續)。各配置區塊之間以 link list 做串連。
記錄方式 :
- File Name, Start Block #, End Block #
優點：
- 沒有 external fragmentation
- 檔案可任意增/刪空間建檔時無需事先宣告大小
缺點：
- 不支援 random access ：要讀某個檔案的某個區塊時需從頭找起，只支援 sequential access。
- seek time比 contiguous 配置方式長，非連續性 blocks 可能散落在不同的 track。
- Reliability 差，若連結斷裂則會資料丟失。
3. 索引式配置 (Index Allocation)
每個檔案皆會多配置一些額外的 blocks 作為 index blocks，內含各配置的 data block 編號。採非連續性配置方式。
記錄方式 :
- File Name, Index Block #
優點 :
- 沒有 external fragmentation：linked list 的優點
- 支援 random access 及 sequential access：contiguous 的優點
- 可任意增/刪空間
- 建檔時無需事先宣告大小
缺點 :
- index blocks 佔用額外空間：索引區塊佔用 free block 的空間。
- index block 太小不夠存放一個檔案的所有 block 編號，太大又形成浪費。
解決 index block 不夠大的三個方法：
- 利用多個 index blocks 儲存，且其之間以 link 方式串連。
- 缺點是資料區塊 IO 隨大小線性成長，無法 random access。
- Multilevel index
- 僅適用大檔案，小檔案不適合 (似 2-level cache table)，當存到小檔案時，有可能 index 的大小會大於檔案。
- Unix i-Node Structure
[用心去感覺] Unix i-Node Structure
有 15 個Pointer，可逐級累加使用。
- 1~12 號指標 : 儲存 data block # (檔案的Block需求 ≤12 個時適用)
- 13 號指標 : 指向 Single-level index
- 14 號指標 : 指向 Two-level index
- 15 號指標 : 指向 Three-level index
[實例1] FAT (File Allocation Table)
為 link allocation 的變形。將所有配置區塊之間的 link 及 free block 資訊全部記錄在一個Table(FAT)。FAT集中在磁碟某一個固定位置，或可以將它載入主記憶體內，因此雖然在找尋指標時是循序找尋，但速度相對快很多。若 disk 有 n 個 blocks，則 FAT 有 n 個項目 (不論是Free的還是使用中的Block皆需記錄)。
FAT中的項目資訊：
- 空白 : 表示 free block。
- block # : 有 link 指向此 block，即使用中的 block。
概覽：
- MS-DOS 及 OS/2 採用
- Physical directory 的記錄方式 : [file name, FAT Index]
- block 可完全都存放 data，不像 link Allocation 會有幾個 byte 用來存放連結。
- 優缺點和 link allocation 差不多。
[實例2] Extent-Based Systems - ext4
現代檔案系統使用改良式的 contiguous allocation，例如 ext4。
ext4基本資料：
- 發布時間：2006年10月10日 (Linux 2.6.28, 2.6.19)
- 目錄內容：連結串列, hashed B-tree
- 檔案分配：Extents/Bitmap
Extents-based : Extent 指的是一連串的連續實體 block，這種方式可以增加大型檔案的效率並減少分裂檔案。
- Extents 大小不用一樣。
- Extents 間採用 sequential access
ext4 引進了 Extent 檔案儲存方式，以取代 ext2/3 使用的 block mapping 方式。ext4 支援的單一 Extent，在單一block為4KB的系統中最高可達128MB。單一 i-node 中可儲存 4 筆 Extent；超過四筆的 Extent 會以 Htree 方式被索引。
四、Review
- Plain table : FAT, ext.
- B-tree : XFS, NTFS.
Allocation methods
- Linked list : FAT
- Indexed allocation : ext (using I-Node, extent : ext4)
Free space management
- Linked list : FAT
- Bitmap : ext
References
Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
聯合大學陳士杰教授課程教材
洪逸 - 作業系統金寶典
發表文章
