OS筆記-Chapter 11: File System Implementation

# OS筆記-Chapter 11: File System Implementation ###### tags: `OS` --- #### 目錄 * 總論 [Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA) [Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A) * 行程管理 [Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ) [Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw) [Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw) [Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q) [Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g) * 記憶體管理 [Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog) [Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw) * 儲存裝置 [Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg) <font color="red">Chapter 11: File System Implementation</font> [Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q) [Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg) * 保護和安全 [Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw) [Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg) --- ### 檔案系統結構(File-System Structure) * 檔案系統藉由允許資料能方便的儲存、找到及重新取出，以提供有效且方便的存取磁碟方法 * 主記憶體與磁碟間以區段(block)為單位 * 檔案系統本身由不同層次所組成 ![](https://i.imgur.com/yY4HGlR.png) * I/O控制:包括裝置驅動程式、主記憶體與磁碟傳遞資料時的中斷控制程式等等 * 基本檔案系統:發出命令給裝置驅動程式、管理持有不同檔案系統的記憶體緩衝區和快取 * 檔案組織模組:知道邏輯與實體區段、轉換邏輯與實體區段 * 邏輯檔案系統:管理中介資料(metadata)、經由檔案控制區塊(FCB,file-control block)維護檔案 * 中介資料:包含所有檔案系統結構，但不含真正的資料 * 檔案控制區塊:包括檔案的資訊、所有權、所在位置 ![](https://i.imgur.com/meIZ2Jb.png) * 不同作業系統的檔案系統結構 * UNIX:UFS(UNIX file system) * Windows:NTFS(Windows NT file System) ### 檔案系統製作(File-System Implementation) * 檔案系統可能包括 * 啟動控制區段(boot control block):包含作業系統需要的資訊，以便將作業系統從該分割區啟動 * 卷區控制區段(volume control block):包含卷的詳細資料 * 卷:每個包含一個檔案系統的實體 * 目錄結構 * 每個檔案都有的FCB包含檔案細節 * 記憶體中的資訊經由快取被用在檔案系統管理和性能改善上，包括一些型態的結構 * 掛載表格(mount table):包括每個已掛載分割區的資訊 * 保存最近存取目錄的資訊 * 全系統的開啟檔案表格(system-wide open-file table):包含每一個開啟檔案之FCB的拷貝以及其他資訊 * 每個行程的開啟檔案表格(per-process open-file table) * 持有檔案系統區塊的緩衝區 * 當產生一個新檔案時，會呼叫邏輯檔案系統，作業系統會配置一個新的FCB * 當檔案被開啟，FCB被拷貝到全系統的開啟檔案表格，此表格也包含開啟此檔的行程個數 ![](https://i.imgur.com/HyJKCcE.png) * 分割和掛載 * 分割區可以是 * 原始磁碟(raw disk):用在沒有檔案系統適合的情況 * 編制好的(cookd) * 根分割區(root partition):包含作業系統核心和其他系統檔案，在啟動時被掛載 * 其他分割區可在啟動時自動掛載或稍後手動掛載 * 虛擬檔案系統(VFS,virtual file system) * 藉由定義VFS介面，可將檔案系統的一般操作和製作方式分開 * 對整個網路提供一個獨一無二表示檔案的機制 ![](https://i.imgur.com/iroVt8o.png) ### 目錄製作(Directory Implementation) * 線性串列(Linear list) * 以指標指向資料區段 * 要找到指定的檔案，很浪費時間(需搜尋整個串列) * 雜湊表格(Hash Table) * 從檔名計算出一個數值 * 主要的困難是雜湊表格大小通常固定 * 使用鏈結串列，解決碰撞問題 ### 配置方法(Allocation Methods) * 分配磁碟的三種方法 * 連續(contiguous) * 鏈結(linked) * 索引(index) * 連續分配(Contiguous allocation) * 檔案占用磁碟上的連續區段 ![](https://i.imgur.com/dt8quHd.png) * 磁碟搜尋時間最短 * 如何分配空間 * 最先配合、最佳配合 * 有外部斷裂問題 * 使用聚集解決 * 若檔案大小是緩慢增加的，將會有配置問題 * 原先配置固定大小 * 配置額外的連續部分，與原位置鍊結 * 鏈結分配(Linked allocation) * 每個檔案都是磁碟上區段的鏈結串列 ![](https://i.imgur.com/cQxiikU.png) * 不易找到檔案的第N段位置，必須從頭開始搜尋 * 指標占掉實際能儲存的空間 * 使用叢集(cluster)，將多個區段設為一個叢，所有操作都以叢為單位 * 叢集會使內部斷裂增加 * 可靠度問題 * 指標可能指錯 * 使用雙重鍊結(浪費更多空間) * 檔案配置表格(FAT,file-allocation table) * 類似鏈結配置 * 表格為每個磁碟區段保有一份紀錄 * 造成大量磁頭尋找(FAT一次、實際位置一次) ![](https://i.imgur.com/CKnb3cz.png) * 索引分配(Indexed allocation) * 將指標全部放在索引區段(index block) ![](https://i.imgur.com/kidnwka.png) * 索引區段太大會浪費空間，太小對大型檔案會不夠 * 鏈結方式:索引區段鍊結，提供更多空間 * 多層索引:第一層索引再指向第二層索引 * 組合方式:分為直接區段與單一界間區段等等 ![](https://i.imgur.com/zXChngh.png) ### 可用空間管理(Free-Space Management) * 可用空間串列(free-space list):紀錄可用磁碟空間 * 位元映像(bit map)/位元向量(bit vector) * 磁碟的2、3、4、5、8、9、10、11、12、13、17、18、25、26、27為可用 * 位元映像為001111001111110001100000011100000... * 搜尋可用區段有效率 * 需要較多空間給位元映像來記錄 * 鏈結串列 * 將所有可用連結區鍊結在一起 ![](https://i.imgur.com/lH27P4p.png) * 組群(Grouping) * 將前n個可用區段的位址存放在第一個區段中 * 最後一個存放另外n個可用區段位址 * 計數(Counting) * 利用一般情況下許多連續區段同時被分配或同時被釋放的事實 * 只需記住第一個的位址與後面n個連續區段的數量 * 空間地圖(Space Maps) * 是一個按照時間順序和計數格式去紀錄所有區塊活動的日誌 * ZFS(Oracle)使用計數演算法來儲存可用區段 * 當ZFS要配置或釋放時，將關聯的空間地圖讀入平衡樹架構的記憶體中 ### 效率和性能(Efficiency and Performance) * 效率取決於 * 磁碟配置 * 目錄演算法 * 檔案目錄進入點的資料型態 * 資料結構的固定長度或可變長度 * 中介資料預先配置 * 性能取決於 * 讓資料與中介資料相近 * 緩衝區快取(buffer cache) * 一塊獨立的主記憶體 * 分頁快取(page cache) * 將檔案資料以分頁的方式快取 * 使用虛擬位址快取 * 一致性的緩衝區快取 ![](https://i.imgur.com/jUm05xY.png) * 非一致性的緩衝區快取/雙重快取 ![](https://i.imgur.com/aj2LVc7.png) * 同步寫入(Synchronous write) * 寫入時不做緩衝 * 非同步寫入(asynchronous write) * 資料先存入快取 * 後釋放(Free-behind)和先讀取(read-ahead) * 後釋放:下一個被要求後才從緩衝池釋放 * 先讀取:一個要求到的分頁，緊接其後的分頁也會先載入快取(等等可能會用到) ### 復原(Recovery) * 一致性檢查(Consistency checking) * 一致性檢查器(consistency checker):是一個系統程式 * 比較目錄結構的資料和磁碟上的資料，並試著修正 * 登入結構的檔案系統(log-based transaction-oriented/journaling) * 中介資料的改變是以循序的方式寫入登錄中 * 交易(transaction):執行特定任務的每一組操作 * 一旦改變被寫入登入中，它們就被視為交付 * 當一整筆交付的交易完成後，從登入檔中清除 * 若檔案系統毀損，登入檔中剩餘的交易仍須執行 * 其他解決辦法 * 一次交易將所有資料和中介資料的改變寫入新的區塊 * 將所有指向就區塊的指標改為指向新區塊，並移除舊區塊 * 快照(snapshot):上次更新前，檔案系統的外觀，也就是未被移除的舊區塊 * 備份(backup)或復原(restore) * 如果知道上一次的改變的時間 * 只需增加備份(inctemental backup) * 否則須完全備份(full backup) * 使用N天為一個循環，從完全備份開始 * 但可能過很久才發現檔案毀損，完全備份應另外儲存，使用不同的儲存媒體

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.