Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 14: File System Implementation (Allocation Methods(配置方法)…
Chapter 14:
File System Implementation
File-System Structure
File system
:star: : 常駐於disk，負責控制資料儲存與檢索(包括提供介面、邏輯到實體位置的對應)
File System Layers(圖p.14.4 :fire::fire::fire:)
檔案存取的步驟
1.應用程式：process發出read需求並提供路徑
2.邏輯檔案系統：檢查儲存權限
3.檔案組織模組：將logical address轉換成physical address
4.基本檔案系統：讀取physical address 要求
5.I/O控制：實際的I/O控制
6.裝置：從儲存裝置讀取資料
名詞解釋
Logical file system
:star: : 管理metadata，將檔案名稱翻譯成檔案編號，location by maintain file control blocks (
inodes
:star: in UNIX)
File organization module
:star: : Translates logical block # to physical block #、管理可用空間及磁碟配置
Basic file system
:star: : 管理記憶體buffer、快取
Device drivers
:star: : 負責啟動該設備上的I/O操作，處理I/O請求的完成
Layer的分析
優點 : 降低複雜度、redundancy
缺點 : 降低效能
File-System Operations
名詞解釋
Boot control block
:star: : a atorage block，包含系統boot from volume 所需的資訊
Volume control block (superblock, master file table)
:star: : A per-volume storage block，包含描述volume的data(block總數、free block數、block大小、free block指標)
File Control Block (FCB)
:star: : 包含許多檔案的細節，包括inode number, 允許權、大小、資料
In-Memory File System Structures
Mount table
:star: : 儲存檔案系統mounts, mount points, 檔案系統型別
system-wide open-file table
:star: : contain 每個文件的FCB copy與其他資訊
per-process open-file table
:star: : contain指向system-wide open-file中entry的合適指標
Directory Implementation(目錄實作)
Linear list
說明 : 將檔案名稱串起來，再用pointer指到data block
評估 : 實作簡單，但搜尋花時間(可用B Tree改善)
Hash Table
說明 : 用hash data架構串列起來
評估 : 減少目錄搜尋時間，且有固定的大小，但可能發生碰撞問題，因為hash後可能會有相同的位置。
Allocation Methods(配置方法)
Contiguous allocation
(連續性配置)
說明 : 每個檔案都會占掉一組連續的blocks，大多數情況下效能最佳
分析
優點 : 實作容易(只要知道起始位置、長度)
缺點 : 需替檔案查找空間、了解檔案大小、外部碎裂 => 每過一段時間就需要做
compaction
改版 :
Extent-Based system
說明 : 將配置單位從block變成一個extent(連續的block)
問題 : extent太大->內部碎裂; extent大小不同->外部碎裂
Linked allocation
(連結配置)
說明 : 若file的大小=n個blocks，則os只要在disk中找到n個free block即可(不用連續)，且allocated blocks之間以link方式串聯(適合循序存取，不適合隨機存取)
分析
優點 : 無外部碎裂
缺點 : 存指標佔空間、可靠度低(list斷裂，資料就遺失了)、I\O次數多(block散落)
變形 :
FAT (File Allocation Table)
:star:
說明 : 與Linked allocation的差異在於，Allocated blocks之間的linking info存於os memory area中的一個表格叫FAT，並非存在disk中
優點 : 加速random access
圖p.13 :fire::fire::fire:
Indexed allocation
(索引式配置)
說明
若file大小=n個blocks，則除了配置n個blocks(無須連續)存放data，另需額外配置
Index block
，儲存所有data blocks之No.(address)。且OS在實體目錄紀錄<檔案名稱, Index Block No.>
分析
優點 : 無外部碎裂、可隨機存取
缺點 : 需額外空間記index block
Supporting Unbounded Size (3種方法; 解決單一個Index Block不夠放所有Data Blocks No.之問題)
Linked scheme
說明 : 使用多個index blocks，且彼此以link方式串聯
缺點 : rabdom access時，平均I/O次數大幅增加
Multilevel index
說明 : 使用階層式的index structure
優點 : random access之 I/O次數是固定值
缺點 : 不適合用於小型檔案(Idex block太佔空間，甚至多餘data block數)
Combined scheme
:star::star::star:
說明 : 即UNIX的I-Node結構
其中
(1)第1~12格 : 直接記Data Block No.
(2)第13格 : 指向single-level index
(3)第14格 : 指向double-level index
(4)第15格 : 指向triple-level index
優點 : 小型、大型的檔案都適合
Free-Space Management
說明 : 檔案系統maintain一個free-space list來管理可用空間
方法(3種)
Bit vector (bit map)
:star:
說明 : 透過一組bit來代表block有沒有被用到，一個bit對應一個block。
分析 : 這個方法比較容易找到連續的檔案，但是bit vector會佔用memory的空間，不適用在大型硬碟上
Linked list (free list)
:star:
說明 : 將所有可用空間用指標串連起來
分析 : 比較不會浪費空間、找可用空間較快速，但這個方法不容易找到連續空間來存放檔案。
加強版
Grouping
: 把所有的free block的位址找出來，存放在first free blocks中，滿了再放到一個block
Counting
: 紀錄從幾號開始有幾塊連續的，每個entry裡面都存放disk address、count
Space map
Efficiency and Performance
影響檔案系統效率的原因有
硬碟如何分配
目錄的演算法
存放在檔案內資料的型態
增加效能的方法
Disk cache
：將常用的block放到記憶體內
Free-behind
and
read-ahead
:star:：讓要做的事有最好的安排順序，需要讀的檔案就先做，執行完後需要釋放空間的動作，在空間足夠下，就晚一點再執行
將部分的記憶體當硬碟使用，像是virtual disk
Recovery
Recovery
Consistency checking
(一致性檢查):star: : 比較目錄結構中、disk上的data，並嘗試修復不一致的問題
back up
: 使用系統程式將資料備份到其他儲存裝置
restoring
: 通過備份資料來還原失去的檔案或是硬碟
Log Structured(or journaling) File System(LFS)
:star: : LFS紀錄著每一次檔案的更新動作，檔案不管做什麼動作都要寫入
log
內，而且一旦寫進去皆會被commit。但檔案系統可能不會這麼快就更新，因為log內的動作是非同步的寫入。意思是當檔案被修改後，log的動作會被移除。但如果檔案系統crashes的話，log內的動作還是會繼續執行。