操作系統：文件系統的實現

一、文件系統結構

磁盤的邏輯單元爲塊，內存和磁盤之間的 I/O 傳輸以塊爲單位執行。

磁盤的特點

  1. 1 可以原地重寫，可以從磁盤上讀一塊兒，修改該塊，並將它寫回到原來的位置

  2. 可以直接訪問磁盤上的任意一塊。因此，可以方便地按順序或隨機訪問文件

文件系統需要提供高效快捷磁盤訪問，以便輕鬆存儲、定位、提取數據。即存儲文件、訪問文件

文件系統有兩個不同的設計問題

  1. 訪問問題：如何定義文件系統對用戶的接口

  2. 存儲問題：創建數據結構和算法，把邏輯文件系統映射到物理外存設備

文件系統本身通常由許多不同層組成。每層實際利用更低層功能，創建新的功能，以用於更高層的服務。

設備驅動程序可以作爲翻譯器，他的輸入作爲高級指令，輸出由底層的、硬件特定指令組成。

基礎文件系統只需向適當設備驅動程序發送命令。

邏輯文件系統通過文件控制塊維護文件結構。

文件控制塊（FCB）包含有關文件的信息，包括所有者、權限、文件內容的位置等。

大多數操作系統支持多種不同的文件系統，舉例：

二、文件系統實現

1. 概述

在磁盤上，文件系統包括的信息有

  1. 如何啓動存儲在那裏操作系統

  2. 總的塊數

  3. 空閒塊的數目和位置

  4. 目錄結構

  5. 各個具體文件 等

上述許多結構會在之後詳細講述。這裏簡述如下：

內存中的信息用於管理文件系統並通過緩存來提高性能，這些數據在安裝文件裝系統時被加載，在文件系統操作期間被更新，在卸載是被卸載。這些結構類型包括：

  1. 每個進程的打開文件表：包括一個指向系統的打開文件表中合適條目的指針和其他信息

  2. 整個系統的打開文件表：包括每個打開文件的 FCB 副本和其他信息

創建一個新文件

  1. 應用程序調用邏輯文件系統。邏輯文件系統指導目錄結構的格式，它會分配一個新的 FCB

  2. 系統將相應的目錄信息讀入內存

  3. 更新目錄結構和 FCB

  4. 將結果寫回磁盤

一旦文件被創建，就能用於 I/O，不過，首先他要被打開。系統調用 open() 將文件名傳到邏輯文件系統，系統調用 open()：

  1. 首先搜索整個系統的打開文件表，查看是否已經被打開，如果是，則在該進程的打開文件表創建一個條目，並指向現有整個系統的打開文件表。

  2. 否則，根據文件名搜索目錄結構

  3. 找到後，它的 FCB 會複製到內存的整個系統的開放文件表中（該表還存放着打開該文件的進程數量） ，接下來，在該進程的打開文件表創建一個條目，並指向現有整個系統的打開文件表。

Open() 返回值：文件描述符是一個非負整數。它是一進程打開文件表的索引值，指向系統範圍內打開文件表相應條目

2. 虛擬文件系統

操作系統如何才能將多個類型的文件系統集成到目錄結構中？用戶如何在訪問文件系統空間時，可以無縫地在文件系統類型間遷移？大多數操作系統採用面嚮對象的技術來簡化、組織、模塊化實現。

數據結構和程序用於隔離基本的操作系統調用的功能與實現細節。因此，文件系統的實現有三個主要層構成。

第一層爲文件系統接口。

第二層爲虛擬文件系統（VFS），把文件系統的通用操作和具體實現分開，虛擬文件系統提供了在唯一標識一個文件的機制。VFS 基於 vnode 的文件表示結構，它包含了一個數值標識符來唯一表示網絡上的一個文件。

  1. VFS 能區分不同本地文件系統

  2. VFS 能區分本地文件系統和遠程文件系統

三、目錄實現

1. 線性列表

採用文件名稱和數據塊指針的線性列表

2. 哈希表

哈希表根據文件名得到一個值，並返回一個指向線性列表中元素的指針

四、磁盤空間的分配方法

1. 連續分配

每個文件在磁盤上佔有一組連續的塊。 文件的連續分配可以用文件第一塊的磁盤地址和連續塊的數量（即長度）來定義

連續分配支持順序訪問和直接訪問

問題：當文件需要擴展，文件大小變大時會無法擴展

解決：找更大的連續空間，複製過去

基於擴展的連續分配方案 用以下參數來定義文件

  1. 開始地址

  2. 塊兒數

  3. 指向下一個擴展塊兒的指針（擴展塊兒可以是多個）

定義格式：

文件【開始地址，塊兒數，指向下一個擴展塊的指針】

2. 鏈接分配

每個文件是磁盤塊兒的鏈表，磁盤塊分佈在磁盤的任何地方，文件有起始塊和結束塊來定義

定義格式：【起始塊，結束塊】

同時，每個磁盤塊都有指向下一個磁盤塊的地址。

優點：沒有磁盤空間浪費

缺點：

  1. 不支持文件的直接訪問

  2. 需要更多的磁盤空間（來記錄指針）

鏈接分配的一個重要變種是文件分配表

每個卷的開始部分用於存儲文件分配表 (File Allocation Table)，表中每個磁盤塊都有一個 FAT 條目，並可通過塊號索引。（未使用的塊爲 0，使用的塊包含下一個塊兒號）

目錄條目含有文件首塊號碼，通過這個塊號索引的 FAT 條目包含文件下一塊的號碼，這個鏈會繼續下去，直到最後一塊，最後一塊的表條目值爲文件結束值。

3. 索引分配

通過將所有指針放在一起，即索引塊

文件用索引塊來定義， 每個文件有其索引塊。

這裏有一個問題，索引塊應爲多大？

每個文件必須有一個索引塊，因此索引塊應儘可能小，然而不能太小，否則放不下足夠多的指針，爲處理這個問題，有如下一些機制：

  1. 鏈接方案：爲了處理大文件，可以將多個索引塊鏈接起來

  2. 多層次索引：用第一層索引塊指向一組第二層的索引塊，第二層索引塊再指向文件塊

  3. 組合方案：用於基於 UNIX 的文件系統，將索引塊的前 15 個指針存儲在文件的 i-node 中。其中，前 12 個指針指向直接塊，剩下 3 個指針指向間接塊

五、磁盤空閒空間的管理

1. 位向量

空閒空間表實現爲位圖, 或位向量，每塊用一位（bit）表示。1 表示塊空閒；0 表示塊已分配

2. 鏈表

所有空閒塊用鏈表鏈接起來，並將指向第一個空閒塊兒的指針保存在特殊位置，同時緩存在內存。

每個塊兒含有下一個塊兒的指針

3. 組

將 n 個空閒塊的地址保存在第一個空閒塊中。

這些空閒塊中的前 n－1 個爲空，而最後一塊包含另外 n 個空閒塊的地址。

比鏈表好的是空閒塊的地址可以很快找到，而且可以明確一段連續空閒塊空間

例：n=3

4. 計數

基於以下事實：

通常有多個連續塊需要同時分配或釋放，尤其是在使用連續分配時。因此記錄

例：

六、文件系統的性能和效率

磁盤空間的有效使用（效率），取決於

改善性能的方法：緩存

  1. 緩衝區緩存：一塊獨立內存，位於其中的塊是馬上需要使用的

  2. 頁面緩存：將文件數據作爲頁而不是塊來緩存。頁面緩存使用虛擬內存技術，將文件數據作爲頁來緩存，比採用物理磁盤塊來緩存更高效

  3. 板載高速緩存

如果沒有統一緩存，則會由下圖情況發生：

系統調用 read() 和 write() 會通過緩衝區緩存，然而，內存映射調用需要使用兩個緩存，即頁面緩存和緩衝區緩存。內存映射先從文件系統中讀入磁盤塊, 並放入緩衝區緩存，由於虛擬內存系統沒有緩衝區緩存接口，緩衝緩存內的文件必須複製到頁面緩存中。

採用統一緩衝緩存

統一緩衝緩存：統一使用緩衝器緩存來緩存進程頁和文件數據。

無論是緩存塊還是頁面都有置換問題，

文件的讀入或寫出一般是按順序進行。所以，不適合採用 LRU 算法，因爲最近使用的頁面最後纔會用甚至根本不會再用。

順序訪問可以通過馬上釋放和預先讀取來加以優化

  1. 馬上釋放（free-behind）：請求下一頁時，馬上釋放上一頁

  2. 預先讀取（read-ahead）：請求頁之後的下一個頁也一起讀入

七、文件系統的恢復

目錄信息一般事先保存在內存中以加快訪問，有時會導致目錄結構中的數據和磁盤塊中的數據不一致。

解決：

  1. 一致性檢查：比較目錄結構中的數據和磁盤塊中的數據，嘗試着去修正不一致

  2. 備份 & 恢復：I. 備份（backup）：利用系統程序來備份數據到其他的存儲設備。軟盤，磁帶 II. 恢復（recovery）：通過從備份來恢復丟失的文件或磁盤

基於日誌結構的文件系統

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lzyYPdqfbXjWQqtV-u5Plw

猜你喜歡