---
# System prepended metadata

title: 'OS筆記-Chapter 11: File System Implementation'
tags: [OS]

---

# 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天為一個循環，從完全備份開始
        * 但可能過很久才發現檔案毀損，完全備份應另外儲存，使用不同的儲存媒體