第12章：文件系統(tǒng)

• 文件系統(tǒng)概念

  • 文件系統(tǒng)和文件
  • 文件描述符
  • 目錄
  • 文件別名
  • 文件系統(tǒng)種類

• 虛擬文件系統(tǒng)

• 文件緩存和打開文件

• 文件分配

• 空閑空間管理

• 冗余磁盤陣列RAID

12.1 文件系統(tǒng)概念

（一）文件系統(tǒng)和文件

• 文件系統(tǒng)是操作系統(tǒng)中管理持久性數(shù)據(jù)的子系統(tǒng)掠河，提供數(shù)據(jù)存儲(chǔ)和訪問功能

  • 組織、檢索、讀寫訪問數(shù)據(jù)
  • 大多數(shù)計(jì)算機(jī)系統(tǒng)都有文件系統(tǒng)
  • Google也是一個(gè)文件系統(tǒng)

• 文件是具有符號(hào)名肩刃、由字節(jié)序列構(gòu)成的數(shù)據(jù)項(xiàng)集合

  • 文件系統(tǒng)的基本數(shù)據(jù)單位
  • 文件名是文件的標(biāo)識(shí)符號(hào)

文件系統(tǒng)的功能

• 分配文件的磁盤空間

  • 管理文件塊（位置和順序）
  • 管理空閑空間（位置）
  • 分配算法（策略）

• 管理文件集合

  • 定位：文件及其內(nèi)容
  • 命名：通過名字找到文件
  • 文件系統(tǒng)結(jié)構(gòu)：文件組織方式

• 數(shù)據(jù)可靠和安全

  • 安全：多層次保護(hù)數(shù)據(jù)安全

  • 可靠：

    • 持久保存文件
    • 避免系統(tǒng)崩潰、媒體錯(cuò)誤凌那、攻擊等

• 文件屬性

  • 名稱、類型、位置辈灼、大小、保護(hù)也榄、創(chuàng)建者巡莹、創(chuàng)建時(shí)間、最近訪問時(shí)間…

• 文件頭：文件系統(tǒng)元數(shù)據(jù)中的文件信息

  • 文件屬性
  • 文件存儲(chǔ)位置和順序

（二）文件描述符

• 文件描述符是指打開的文件它在內(nèi)存當(dāng)中所維護(hù)的相關(guān)信息

打開文件和文件描述符

• 文件訪問模式

  • 進(jìn)程訪問文件數(shù)據(jù)前必須先“打開”文件

• 內(nèi)核跟蹤進(jìn)程打開的所有文件

  • 操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一個(gè)打開文件表
  • 文件描述符是打開文件的標(biāo)識(shí)

文件描述符

• 操作系統(tǒng)在打開文件表中維護(hù)的打開文件狀態(tài)和信息

  • 文件指針

    • 最近一次讀寫位置
    • 每個(gè)進(jìn)程分別維護(hù)自己的打開文件指針

  • 文件打開次數(shù)

    • 當(dāng)前打開文件的次數(shù)
    • 最后一個(gè)進(jìn)程關(guān)閉文件時(shí)甜紫，將其從文件表中移除

  • 文件的磁盤位置

    • 緩存數(shù)據(jù)訪問信息

  • 訪問權(quán)限

    • 每個(gè)進(jìn)程的文件訪問模式信息

文件的用戶視圖和系統(tǒng)視圖

• 文件的用戶視圖

  • 持久的數(shù)據(jù)結(jié)構(gòu)

• 系統(tǒng)訪問接口

  • 字節(jié)序列的集合（UNIX）
  • 系統(tǒng)不關(guān)心存儲(chǔ)在磁盤上的數(shù)據(jù)結(jié)構(gòu)

• 操作系統(tǒng)的文件視圖

  • 數(shù)據(jù)塊的集合
  • 數(shù)據(jù)塊是邏輯存儲(chǔ)單元降宅，而扇區(qū)還是物理存儲(chǔ)單元
  • 塊大小和扇區(qū)大小可能不一樣

用戶視圖到系統(tǒng)視圖的轉(zhuǎn)換

• 進(jìn)程讀文件

  • 獲取字節(jié)所在的數(shù)據(jù)塊
  • 返回?cái)?shù)據(jù)塊內(nèi)對(duì)應(yīng)部分

• 進(jìn)程寫文件

  • 獲取數(shù)據(jù)塊
  • 修改數(shù)據(jù)塊中對(duì)應(yīng)部分
  • 寫回?cái)?shù)據(jù)塊

• 文件系統(tǒng)中的基本操作單位是數(shù)據(jù)塊

訪問模式

• 操作系統(tǒng)需要了解進(jìn)程如何訪問文件

• 順序訪問：按字節(jié)依次讀取

  • 大多數(shù)的文件訪問都是順序訪問

• 隨機(jī)訪問：從中間讀寫

  • 不常用，但仍然重要囚霸。對(duì)系統(tǒng)性能有影響腰根。
  • 例如，虛擬內(nèi)存中把內(nèi)存頁存儲(chǔ)在文件

• 索引訪問：依據(jù)數(shù)據(jù)特征索引

  • 通常操作系統(tǒng)不完整提供索引訪問
  • 數(shù)據(jù)庫是建立在索引內(nèi)容的磁盤訪問上

文件內(nèi)部結(jié)構(gòu)

• 無結(jié)構(gòu)

  • 單詞邮辽、字節(jié)序列

• 簡(jiǎn)單記錄結(jié)構(gòu)

  • 分列
  • 固定長(zhǎng)度
  • 可變長(zhǎng)度

• 復(fù)雜結(jié)構(gòu)

  • 格式化的文檔（如MS Word唠雕，PDF）
  • 可執(zhí)行文件

文件共享和訪問控制

• 多用戶系統(tǒng)中的文件共享是很必要的

• 訪問控制

  • 每個(gè)用戶能夠獲得哪些文件的哪些訪問權(quán)限
  • 訪問模式：讀、寫吨述、執(zhí)行岩睁、刪除、列表等

• 文件訪問控制列表（ACL）

  • <文件實(shí)體揣云，權(quán)限>

  • 用戶|組|所有人|：讀|寫|可執(zhí)行|

  • 用戶標(biāo)識(shí)ID

    • 識(shí)別用戶捕儒，表明每個(gè)用戶所允許的權(quán)限及保護(hù)模式

  • 組標(biāo)識(shí)ID

    • 允許用戶組成組，并指定了組訪問權(quán)限

語義一致性

• 規(guī)定多進(jìn)程如何同時(shí)訪問共享文件

  • 與同步算法相似
  • 因磁盤I/O和網(wǎng)絡(luò)延遲而設(shè)計(jì)簡(jiǎn)單

• UNIX文件系統(tǒng)（UFS）語義

  • 對(duì)打開文件的寫入內(nèi)容立即對(duì)其他打開同一文件的其他用戶可見
  • 共享文件指針允許用戶同時(shí)讀取和寫入文件

• 會(huì)話語義

  • 寫入內(nèi)容只有當(dāng)文件關(guān)閉時(shí)可見

• 讀寫鎖

  • 一些操作系統(tǒng)和文件系統(tǒng)提供該功能

（三）目錄邓夕、文件別名和文件系統(tǒng)種類

分層文件系統(tǒng)

• 文件以目錄方式組織起來

• 目錄是一列特殊的文件

  • 目錄的內(nèi)容是文件索引表<文件名刘莹，指向文件的指針>

• 目錄和文件的樹型結(jié)構(gòu)

  • 早期的文件系統(tǒng)是扁平的（只有一層目錄）

目錄操作

• 典型目錄操作

  • 搜索、創(chuàng)建焚刚、刪除点弯、重命名文件
  • 列目錄
  • 遍歷路徑

• 操作系統(tǒng)應(yīng)該只允許內(nèi)核修改目錄

  • 確保映射的完整性
  • 應(yīng)用程序通過系統(tǒng)調(diào)用訪問目錄

目錄實(shí)現(xiàn)

• 文件名的線性列表，包涵了指向數(shù)據(jù)塊的指針

  • 編程簡(jiǎn)單
  • 執(zhí)行耗時(shí)

• 哈希表 - 哈希數(shù)據(jù)結(jié)構(gòu)的線性表

  • 減少目錄搜索時(shí)間
  • 沖突 - 兩個(gè)文件名的哈希值相同
  • 固定大小

文件別名

• 兩個(gè)或多個(gè)文件名關(guān)聯(lián)同一個(gè)文件

  • 硬鏈接：多個(gè)文件項(xiàng)指向一個(gè)文件

  • 軟鏈接：以“快捷方式”指向其他文件

    • 通過存儲(chǔ)真實(shí)文件的邏輯名稱實(shí)現(xiàn)

文件目錄中的循環(huán)

• 如何保證沒有循環(huán)矿咕？

  • 只允許到文件的鏈接抢肛，不允許在子目錄的鏈接
  • 增加鏈接時(shí)，用循環(huán)檢測(cè)算法確定是否合理

• 更多實(shí)踐

  • 限制路徑可遍歷文件目錄的數(shù)量

名字解析（路徑遍歷）

• 名字解析：把邏輯名字轉(zhuǎn)換成物理資源（如文件）

  • 依據(jù)路徑名碳柱，在文件系統(tǒng)中找到實(shí)際文件位置
  • 遍歷文件目錄直到找到目標(biāo)文件

• 當(dāng)前工作目錄（PWD）

  • 每個(gè)進(jìn)程都會(huì)指向一個(gè)文件目錄用于解析文件名

    • 即給每個(gè)進(jìn)程設(shè)定一個(gè)缺省的目錄捡絮，它的名字解析就從這個(gè)目錄開始解析

  • 允許用戶指定相對(duì)路徑來代替絕對(duì)路徑

文件系統(tǒng)掛載

• 文件系統(tǒng)需要先掛載才能被訪問
• 未掛載的文件系統(tǒng)被掛載在掛載點(diǎn)上

文件系統(tǒng)種類

• 磁盤文件系統(tǒng)

  • 文件存儲(chǔ)在數(shù)據(jù)存儲(chǔ)設(shè)備上，如磁盤
  • 例如莲镣，F(xiàn)AT, NTFS, ext 2/3/4, ISO 9660等
  • 不同文件系統(tǒng)安全級(jí)別要求不同福稳，安全級(jí)別要求越高，訪問效率下降

• 數(shù)據(jù)庫文件系統(tǒng)

  • 文件特征是可被尋址（辨識(shí)）的
  • 例如瑞侮，WinFS

• 日志文件系統(tǒng)

  • 記錄文件系統(tǒng)的修改/事件

• 網(wǎng)絡(luò)/分布式文件系統(tǒng)

  • 例如的圆，NFS, SMB, AFS, GFS

• 特殊/虛擬文件系統(tǒng)

網(wǎng)絡(luò)/分布式文件系統(tǒng)

• 文件可以通過網(wǎng)絡(luò)共享

• 文件位于遠(yuǎn)程服務(wù)器

• 客戶端遠(yuǎn)程掛載服務(wù)器文件系統(tǒng)

• 標(biāo)準(zhǔn)文件系統(tǒng)訪問被轉(zhuǎn)換成遠(yuǎn)程訪問

• 標(biāo)準(zhǔn)文件共享協(xié)議

  • NFS for Unix鼓拧， CIFS for Windows

• 分布式文件系統(tǒng)的挑戰(zhàn)

  • 客戶端和客戶端上的用戶辨別起來很復(fù)雜
  • 例如，NFS 是不安全的
  • 一致性問題
  • 錯(cuò)誤處理模式

12.2 虛擬（邏輯）文件系統(tǒng)（VFS, Virtual File System）

文件系統(tǒng)的實(shí)現(xiàn)

• 分層結(jié)構(gòu)

虛擬文件系統(tǒng)

• 目的

  • 對(duì)所有不同的文件系統(tǒng)的抽象

• 功能

  • 提供相同的文件和文件系統(tǒng)接口
  • 管理所有文件和文件系統(tǒng)關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)
  • 高效查詢例程越妈，遍歷文件系統(tǒng)
  • 與特定文件系統(tǒng)模塊的交互

文件系統(tǒng)基本數(shù)據(jù)結(jié)構(gòu)

• 文件卷控制塊（Unix: “Superblock”）

  • 每個(gè)文件系統(tǒng)一個(gè)
  • 文件系統(tǒng)詳細(xì)信息
  • 塊毁枯、塊大小、空余塊叮称、計(jì)數(shù)/指針等

• 文件控制塊（Unix: “vnode” or “inode”）

  • 每個(gè)文件系統(tǒng)一個(gè)
  • 文件系統(tǒng)詳細(xì)信息
  • 訪問權(quán)限种玛、擁有者、大小瓤檐、數(shù)據(jù)塊位置等

• 目錄項(xiàng)（Linux: “dentry”）

  • 每個(gè)目錄項(xiàng)一個(gè)（目錄和文件）
  • 將目錄項(xiàng)數(shù)據(jù)結(jié)構(gòu)及樹型布局編碼成樹型數(shù)據(jù)結(jié)構(gòu)
  • 指向文件控制塊赂韵、子目錄等

文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)

• 文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)

  • 卷控制塊（每個(gè)文件系統(tǒng)一個(gè)）
  • 文件控制塊（每個(gè)文件一個(gè)）
  • 目錄節(jié)點(diǎn)（每個(gè)目錄項(xiàng)一個(gè)）

• 持久存儲(chǔ)在外存中

  • 存儲(chǔ)設(shè)備的數(shù)據(jù)塊中

• 當(dāng)需要時(shí)加載進(jìn)內(nèi)存

  • 卷控制模塊：當(dāng)文件系統(tǒng)掛載時(shí)進(jìn)入內(nèi)存
  • 文件控制塊：當(dāng)文件被訪問時(shí)進(jìn)入內(nèi)存
  • 目錄節(jié)點(diǎn)：在遍歷一個(gè)文件路徑時(shí)進(jìn)入內(nèi)存

12.3 文件緩存和打開文件

數(shù)據(jù)塊緩存

• 數(shù)據(jù)塊按需讀入內(nèi)存

  • 提供read()操作
  • 預(yù)讀：預(yù)先讀取后面的數(shù)據(jù)塊

• 數(shù)據(jù)塊使用后被緩存

  • 假設(shè)數(shù)據(jù)將會(huì)再次用到
  • 寫操作可能被緩存和延遲寫入

• 兩種數(shù)據(jù)塊緩存方式

  • 數(shù)據(jù)塊緩存
  • 頁緩存：統(tǒng)一緩存數(shù)據(jù)塊和內(nèi)存頁

頁緩存

• 虛擬頁式存儲(chǔ)

  • 在虛擬地址空間中虛擬頁面可映射到本地外存文件中

• 文件數(shù)據(jù)塊的頁緩存

  • 在虛擬內(nèi)存中文件數(shù)據(jù)塊被映射成頁
  • 文件的讀/寫操作被轉(zhuǎn)換成對(duì)內(nèi)存的訪問
  • 可能導(dǎo)致缺頁和/或設(shè)置為臟頁
  • 問題：頁面置換算法需要協(xié)調(diào)虛擬存儲(chǔ)和頁緩存間的頁面數(shù)

文件系統(tǒng)中打開文件的數(shù)據(jù)結(jié)構(gòu)

• 文件描述符

  • 每個(gè)被打開的文件都有一個(gè)文件描述符

  • 文件狀態(tài)信息

    • 目錄頁、當(dāng)前文件指針挠蛉、文件操作設(shè)置等

• 打開文件表

  • 每個(gè)進(jìn)程一個(gè)進(jìn)程打開文件表
  • 一個(gè)系統(tǒng)級(jí)打開文件表
  • 有文件被打開時(shí)祭示，文件卷就不能被卸載

• 打開文件鎖

  • 一些文件系統(tǒng)提供文件鎖，用于協(xié)調(diào)多進(jìn)程的文件訪問
  • 強(qiáng)制 - 根據(jù)鎖保持情況和訪問需求確定是否拒絕訪問
  • 勸告 - 進(jìn)程可以查找鎖的狀態(tài)來決定怎么做

12.4 文件分配

文件大小

• 大多數(shù)文件都很小

  • 需要對(duì)小文件提供很好的支持
  • 塊空間不能太大

• 一些文件非常大

  • 必須支持大文件（64位文件偏移）
  • 大文件訪問需要高效

文件分配

• 如何表示分配給一個(gè)文件數(shù)據(jù)塊的位置和順序

• 分配方式

  • 連續(xù)分配
  • 鏈?zhǔn)椒峙?/li>
  • 索引分配

• 指標(biāo)

  • 存儲(chǔ)效率：外部碎片等
  • 讀寫性能：訪問速度

連續(xù)分配

• 文件頭指定起始?jí)K和長(zhǎng)度

• 分配策略

  • 最先匹配谴古、最佳匹配……

• 優(yōu)點(diǎn)

  • 文件讀取表現(xiàn)好
  • 高效的順序和隨機(jī)訪問

• 缺點(diǎn)

  • 碎片

  • 文件增長(zhǎng)問題

    • 按需分配质涛？
    • 預(yù)分配？

鏈?zhǔn)椒峙?/h4>

• 文件以數(shù)據(jù)塊鏈表方式存儲(chǔ)

• 文件頭包含了到第一塊和最后一塊的指針

• 優(yōu)點(diǎn)

  • 創(chuàng)建掰担、增大汇陆、縮小很容易
  • 沒有碎片

• 缺點(diǎn)

  • 無法實(shí)現(xiàn)真正的隨機(jī)訪問

  • 可靠性差

    • 破壞一個(gè)鏈，后面的數(shù)據(jù)塊就丟了

索引分配

• 為每個(gè)文件創(chuàng)建一個(gè)索引數(shù)據(jù)塊

  • 指向文件數(shù)據(jù)塊的指針列表

• 文件頭包含了索引數(shù)據(jù)塊指針

• 優(yōu)點(diǎn)

  • 創(chuàng)建带饱、增大毡代、縮小很容易
  • 沒有碎片
  • 支持直接訪問

• 缺點(diǎn)

  • 當(dāng)文件很小時(shí)，存儲(chǔ)索引的開銷
  • 如何處理大文件勺疼？

大文件的索引分配

• 鏈?zhǔn)剿饕龎K（IB+IB+…）
• 多級(jí)索引塊（IB+IB+…）

UFS多級(jí)索引分配

• 文件頭包含13個(gè)指針

• 10個(gè)指針指向數(shù)據(jù)塊

• 第11個(gè)指針指向索引塊

• 第12個(gè)指針指向二級(jí)索引塊

• 第13個(gè)指針指向三級(jí)索引塊

• 效果

  • 提高了文件大小限制閾值
  • 動(dòng)態(tài)分配數(shù)據(jù)塊教寂，文件擴(kuò)展很容易
  • 小文件開銷小
  • 只為大文件分配間接數(shù)據(jù)塊。大文件在訪問數(shù)據(jù)塊時(shí)需要大量查詢

12.5 空閑空間管理

• 跟蹤記錄文件卷中未分配的數(shù)據(jù)塊

空閑空間組織：位圖

• 用位圖表示空閑數(shù)據(jù)塊列表

  • 0100101110110…
  • Di=0 表明數(shù)據(jù)塊i是空閑执庐，否則酪耕，表示已分配

• 使用簡(jiǎn)單但是可能會(huì)是一個(gè)很大的向量表

  • 160GB磁盤 -> 40M數(shù)據(jù)塊 -> 5MB位圖

  • 假定空閑空間在磁盤中均勻分布，則找到“0”之前要掃描 n/r

    • n = 磁盤上數(shù)據(jù)塊的總數(shù)
    • r = 空閑塊的數(shù)目

其他空閑組織方式

• 鏈表
• 鏈?zhǔn)剿饕?/li>

12.6 冗余磁盤陣列RAID

磁盤分區(qū)

• 通常磁盤通過分區(qū)來最大限度減小尋址時(shí)間

  • 分區(qū)是一組柱面的集合
  • 每個(gè)分區(qū)都可視為邏輯上獨(dú)立的磁盤

一個(gè)典型的磁盤文件系統(tǒng)組織

• 文件卷：一個(gè)擁有完整文件系統(tǒng)實(shí)例的外存空間轨淌，通常常駐在磁盤的單個(gè)分區(qū)上

多磁盤管理

• 使用多磁盤可改善

  • 吞吐量（通過并行）
  • 可靠性和可用性（通過冗余）

• 冗余磁盤陣列（RAID, Redundant Array of Inexpensive Disks）

  • 多種磁盤管理技術(shù)
  • RAID分類
  • 如迂烁，RAID-0，RAID-1猿诸，RAID-5

• 冗余磁盤陣列的實(shí)現(xiàn)

  • 軟件：操作系統(tǒng)內(nèi)核的文件卷管理
  • 硬件：RAID硬件控制器（I/O）

RAID-0：磁盤條帶化

• 把數(shù)據(jù)塊分成多個(gè)子塊婚被，存儲(chǔ)在獨(dú)立的磁盤中

  • 通過獨(dú)立磁盤上并行數(shù)據(jù)塊訪問提供更大的磁盤帶寬

RAID-1：磁盤鏡像

• 向兩個(gè)磁盤寫入狡忙，從任何一個(gè)讀取

  • 可靠性成倍增長(zhǎng)
  • 讀取性能線性增加

RAID-4：帶校驗(yàn)的磁盤條帶化

• 數(shù)據(jù)塊級(jí)的磁盤條帶化加專用奇偶校驗(yàn)磁盤

  • 允許從任意一個(gè)故障磁盤中恢復(fù)

RAID-5：帶分布式校驗(yàn)的磁盤條帶化

• 將校驗(yàn)和存放位置做了一個(gè)分部梳虽，不是把校驗(yàn)和固定存在校驗(yàn)磁盤上
• 可以把校驗(yàn)磁盤瓶頸分?jǐn)傞_，從而提高性能

基于位和基于塊的磁盤條帶化

• 條帶化和奇偶校驗(yàn)按“字節(jié)”或者“位”

  • RAID-0/4/5：基于數(shù)據(jù)塊
  • RAID-3：基于位

可糾正多個(gè)磁盤錯(cuò)誤的冗余陣列

• RAID-5：每組條帶塊有一個(gè)奇偶校驗(yàn)塊

  • 允許一個(gè)磁盤錯(cuò)誤

• RAID-6：每組條帶塊有兩個(gè)冗余塊

  • 允許兩個(gè)磁盤錯(cuò)誤

RAID嵌套

• RAID 0+1

• RAID 1+0

參考鏈接：https://mp.weixin.qq.com/s/h0s-paBLA_9Vp75bS1871Q