# 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)為單位

* 檔案系統本身由不同層次所組成
* I/O控制:包括裝置驅動程式、主記憶體與磁碟傳遞資料時的中斷控制程式等等
* 基本檔案系統:發出命令給裝置驅動程式、管理持有不同檔案系統的記憶體緩衝區和快取
* 檔案組織模組:知道邏輯與實體區段、轉換邏輯與實體區段
* 邏輯檔案系統:管理中介資料(metadata)、經由檔案控制區塊(FCB,file-control block)維護檔案
* 中介資料:包含所有檔案系統結構，但不含真正的資料
* 檔案控制區塊:包括檔案的資訊、所有權、所在位置

* 不同作業系統的檔案系統結構
* 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被拷貝到全系統的開啟檔案表格，此表格也包含開啟此檔的行程個數

* 分割和掛載
* 分割區可以是
* 原始磁碟(raw disk):用在沒有檔案系統適合的情況
* 編制好的(cookd)
* 根分割區(root partition):包含作業系統核心和其他系統檔案，在啟動時被掛載
* 其他分割區可在啟動時自動掛載或稍後手動掛載

* 虛擬檔案系統(VFS,virtual file system)
* 藉由定義VFS介面，可將檔案系統的一般操作和製作方式分開
* 對整個網路提供一個獨一無二表示檔案的機制

### 目錄製作(Directory Implementation)
* 線性串列(Linear list)
* 以指標指向資料區段
* 要找到指定的檔案，很浪費時間(需搜尋整個串列)

* 雜湊表格(Hash Table)
* 從檔名計算出一個數值
* 主要的困難是雜湊表格大小通常固定
* 使用鏈結串列，解決碰撞問題

### 配置方法(Allocation Methods)
* 分配磁碟的三種方法
* 連續(contiguous)
* 鏈結(linked)
* 索引(index)

* 連續分配(Contiguous allocation)
* 檔案占用磁碟上的連續區段
* 磁碟搜尋時間最短
* 如何分配空間
* 最先配合、最佳配合
* 有外部斷裂問題
* 使用聚集解決
* 若檔案大小是緩慢增加的，將會有配置問題
* 原先配置固定大小
* 配置額外的連續部分，與原位置鍊結

* 鏈結分配(Linked allocation)
* 每個檔案都是磁碟上區段的鏈結串列
* 不易找到檔案的第N段位置，必須從頭開始搜尋
* 指標占掉實際能儲存的空間
* 使用叢集(cluster)，將多個區段設為一個叢，所有操作都以叢為單位
* 叢集會使內部斷裂增加
* 可靠度問題
* 指標可能指錯
* 使用雙重鍊結(浪費更多空間)
* 檔案配置表格(FAT,file-allocation table)
* 類似鏈結配置
* 表格為每個磁碟區段保有一份紀錄
* 造成大量磁頭尋找(FAT一次、實際位置一次)

* 索引分配(Indexed allocation)
* 將指標全部放在索引區段(index block)
* 索引區段太大會浪費空間，太小對大型檔案會不夠
* 鏈結方式:索引區段鍊結，提供更多空間
* 多層索引:第一層索引再指向第二層索引
* 組合方式:分為直接區段與單一界間區段等等

### 可用空間管理(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...
* 搜尋可用區段有效率
* 需要較多空間給位元映像來記錄

* 鏈結串列
* 將所有可用連結區鍊結在一起

* 組群(Grouping)
* 將前n個可用區段的位址存放在第一個區段中
* 最後一個存放另外n個可用區段位址

* 計數(Counting)
* 利用一般情況下許多連續區段同時被分配或同時被釋放的事實
* 只需記住第一個的位址與後面n個連續區段的數量

* 空間地圖(Space Maps)
* 是一個按照時間順序和計數格式去紀錄所有區塊活動的日誌
* ZFS(Oracle)使用計數演算法來儲存可用區段
* 當ZFS要配置或釋放時，將關聯的空間地圖讀入平衡樹架構的記憶體中

### 效率和性能(Efficiency and Performance)
* 效率取決於
* 磁碟配置
* 目錄演算法
* 檔案目錄進入點的資料型態
* 資料結構的固定長度或可變長度
* 中介資料預先配置

* 性能取決於
* 讓資料與中介資料相近
* 緩衝區快取(buffer cache)
* 一塊獨立的主記憶體
* 分頁快取(page cache)
* 將檔案資料以分頁的方式快取
* 使用虛擬位址快取
* 一致性的緩衝區快取
* 非一致性的緩衝區快取/雙重快取
* 同步寫入(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天為一個循環，從完全備份開始
* 但可能過很久才發現檔案毀損，完全備份應另外儲存，使用不同的儲存媒體