changed 4 years ago  
Published Linked with GitHub

OS筆記-Chapter 11: File System Implementation

tags: OS

目錄

檔案系統結構(File-System Structure)

  • 檔案系統藉由允許資料能方便的儲存、找到及重新取出，以提供有效且方便的存取磁碟方法

    • 主記憶體與磁碟間以區段(block)為單位

  • 檔案系統本身由不同層次所組成

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

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