目錄

前言

文件管理：基礎(chǔ)

基本概念

文件

文件系統(tǒng)

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

文件的組成

文件名

文件分類

文件結(jié)構(gòu)

邏輯結(jié)構(gòu)

物理結(jié)構(gòu)

練習(xí)題?

文件管理：目錄

文件控制塊FCB

FCB：File Control Block

FCB信息

目錄

基本概念

目錄功能

目錄基本操作

?FCB組織方法

?改進(jìn)的FCB組織方法

目錄的組織

路徑

無環(huán)圖目錄

鏈接

通用圖目錄

文件管理：磁盤管理

空閑分區(qū)表

概念

特點(diǎn)?

空閑分區(qū)鏈表

概念

特點(diǎn)

位示圖

成組塊鏈接法

分配方法

釋放方法

例題

文件一致性：盤塊

鏈接數(shù)一致性檢查

文件執(zhí)行

數(shù)據(jù)結(jié)構(gòu)

文件共享

文件操作

執(zhí)行過程

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

---

前言

設(shè)備管理模塊已經(jīng)更新，傳送門：電子科技大學(xué)操作系統(tǒng)期末復(fù)習(xí)筆記（四）：設(shè)備管理

本復(fù)習(xí)筆記基于電子科技大學(xué)計(jì)算機(jī)操作系統(tǒng)-教學(xué)大綱（2022）中的課程模塊部分，分為五大章節(jié)，分別是：

• CM1：操作系統(tǒng)概念。操作系統(tǒng)基本功能、操作系統(tǒng)發(fā)展歷史及趨勢(shì)、操作系統(tǒng)主流架構(gòu)、常見操作系統(tǒng)特點(diǎn)、操作系統(tǒng)安全機(jī)制。
• CM2：進(jìn)程管理。進(jìn)程概念、線程概念、進(jìn)程生命周期、進(jìn)程調(diào)度算法、進(jìn)程同步互斥、進(jìn)程間通信和死鎖。
• CM3：內(nèi)存管理。內(nèi)存空間的概念、連續(xù)分配、離散分配（分頁(yè)管理、分段管理、段頁(yè)式管理）、虛擬存儲(chǔ)管理和頁(yè)面置換算法。
• CM4：設(shè)備管理。I/O?系統(tǒng)結(jié)構(gòu)、緩沖管理、磁盤結(jié)構(gòu)和磁盤調(diào)度算法。
• CM5：文件管理。文件系統(tǒng)的作用、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、目錄、文件共享和文件系統(tǒng)的一致性。

本節(jié)是最后一部分，要點(diǎn)在CM5，大致內(nèi)容如下：

第五章 文件管理（6 學(xué)時(shí)，多媒體課件結(jié)合板書面授）CM5

1、主要內(nèi)容

文件和文件系統(tǒng)的概念，文件邏輯結(jié)構(gòu)（堆文件、順序文件、索引順序文件、索引文件、HASH 文件），外存分配方法（連續(xù)分配、鏈接分配、索引分配），目錄管理（一級(jí)目錄、二級(jí)目錄、多 級(jí)目錄），文件存儲(chǔ)空間的管理技術(shù)（位示圖、空閑鏈表、索引）。文件系統(tǒng)性能的改善、數(shù)據(jù)一致性控制。

2、應(yīng)達(dá)到的要求記憶：文件系統(tǒng)性能的改善、數(shù)據(jù)一致性控制。

理解：文件系統(tǒng)的基本概念、目錄管理、文件共享、文件保護(hù)的方法。

分析：文件邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)、文件目錄、外存空間的管理。

一共3個(gè)PPT，就分三大塊：文件管理：基礎(chǔ)、文件管理：目錄、文件管理：磁盤管理。

---

文件管理：基礎(chǔ)

---

基本概念

• 文件

  • 一種具有符號(hào)名的、相關(guān)聯(lián)元素的有序集合。
  • 用戶按照信息的邏輯功能將關(guān)聯(lián)存儲(chǔ)單元組織成文件。
  • 文件是信息在磁盤上存儲(chǔ)的基本邏輯單位。
  • 文件名：對(duì)相關(guān)聯(lián)元素的Naming

• 文件系統(tǒng)

• 概念：
• 對(duì)文件實(shí)施管理、控制與操作的一組軟件。
  • 用戶或應(yīng)用程序訪問文件的唯一方式
• 目標(biāo)與功能：
  • 保證文件中的數(shù)據(jù)有效
  • 減少或消除丟失或破壞數(shù)據(jù)的可能性
  • 從系統(tǒng)角度優(yōu)化總吞吐量，從用戶角度優(yōu)化響應(yīng)時(shí)間
  • 為各種類型的存儲(chǔ)設(shè)備提供I/O支持，并提供統(tǒng)一接口
  • 統(tǒng)一管理文件的存儲(chǔ)空間，實(shí)施存儲(chǔ)空間的分配與回收
  • 實(shí)現(xiàn)文件的按名存取：文件名字空間? 存儲(chǔ)空間
  • 實(shí)現(xiàn)文件信息共享，提供文件保護(hù)和保密措施
• 用戶觀點(diǎn)
  • 實(shí)現(xiàn)“按名存取”功能
• 操作系統(tǒng)觀點(diǎn)
  • 文件目錄怎樣實(shí)現(xiàn)、管理存儲(chǔ)空間、文件存儲(chǔ)位置、磁盤實(shí)際運(yùn)作方式(與設(shè)備管理的接口)

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

  • 文件系統(tǒng)接口：命令、系統(tǒng)調(diào)用和圖形窗口的文件系統(tǒng)訪問功能。?
  • 邏輯功能層：根據(jù)接口層所發(fā)下的文件訪問需求，通過相關(guān)的文件控制塊、文件目錄、文件分配表等，獲取訪問存儲(chǔ)介質(zhì)的物理參數(shù)。 ?
  • 物理驅(qū)動(dòng)層 ：將邏輯功能層所發(fā)下的命令轉(zhuǎn)化為相應(yīng)的驅(qū)動(dòng)程序的動(dòng)作，完成對(duì)文件物理存儲(chǔ)設(shè)備的處理。
  • 

• 文件的組成

  • 文件=元數(shù)據(jù)+文件內(nèi)容
  • 元數(shù)據(jù)：文件名、內(nèi)部標(biāo)識(shí)(如unix的inode)、擁有者、訪問時(shí)間/權(quán)限、文件大小 ……

• 文件名

  • 格式：A.B
  • A: 文件名稱? ?B: 文件類型/文件格式/文件擴(kuò)展名

• 文件分類

  • 對(duì)不同文件進(jìn)行管理，提高系統(tǒng)效率
  • 提高用戶界面友好性
  • 
  • 設(shè)備文件：統(tǒng)一的抽象接口（了解即可）

---

文件結(jié)構(gòu)

邏輯結(jié)構(gòu)

從用戶角度研究文件的組織形式，獨(dú)立于物理存儲(chǔ)結(jié)構(gòu)

• 無結(jié)構(gòu)文件：流式文件
  • 構(gòu)成文件的基本單位是字節(jié)，文件是有邏輯意義的、無結(jié)構(gòu)的一串字節(jié)的集合。
  • 自身不提供任何數(shù)據(jù)結(jié)構(gòu) 提供很大的靈活性
  • 用戶自定義文件內(nèi)容含義
• 有結(jié)構(gòu)文件：記錄文件
  • 文件是由若干個(gè)記錄組成，每個(gè)記錄有一個(gè)鍵，可按鍵進(jìn)行查找。
  • 記錄(record)、字段(field)、鍵(key)
  • 
• 文件組織與訪問
  • 原則：
    • 原則可能互相矛盾（如索引 vs. 空間）
    • 優(yōu)先級(jí)取決于使用文件的應(yīng)用程序
  • 堆文件：數(shù)據(jù)按到達(dá)時(shí)間順序存放；每個(gè)記錄長(zhǎng)度、字段數(shù)量不確定；隨機(jī)訪問效率極低，對(duì)大多數(shù)應(yīng)用都不可用；例：log（日志文件）
  • 順序文件：所有記錄有序排列（主字段）；字段定義、記錄長(zhǎng)度固定；批處理，順序訪問最佳；查詢或更新記錄的交互式應(yīng)用，性能差；（隨機(jī)）訪問大型順序文件時(shí)性能差（包含某個(gè)key的記錄）
  • 索引順序文件：是一個(gè)順序文件；將順序文件中的記錄進(jìn)行分組(block)；索引表僅記錄每組中第一個(gè)記錄的信息；組與組之間記錄的關(guān)鍵字必須有序排列；搜索非key字段困難
    • 
  • 索引文件：每個(gè)索引項(xiàng)指向一個(gè)記錄，索引項(xiàng)按照記錄中的某個(gè)關(guān)鍵字排序；記錄大小不必相同，不必排序，存放在主文件中。 可以對(duì)不同的關(guān)鍵字域建立多個(gè)索引；主文件中增/減/變更記錄時(shí)，索引文件須相應(yīng)更新
  • 直接，散列/哈希文件：記錄的存儲(chǔ)位置由以關(guān)鍵字為參數(shù)的哈希函數(shù)計(jì)算得到。 記錄大小一般相同；檢索時(shí)給出記錄的關(guān)鍵字值，通過哈希函數(shù)計(jì)算出該記錄在文件中的位置；訪問速度快， 一次只需訪問一條記錄時(shí)使用。例：目錄、價(jià)格表、調(diào)度和名字列表等。
• 有結(jié)構(gòu)文件和無結(jié)構(gòu)文件的區(qū)別：
  • 

物理結(jié)構(gòu)

文件的邏輯地址和物理地址 文件在物理介質(zhì)上的存放方式

• 文件訪問方法
  • 用戶在使用文件時(shí)按何種次序存取文件
    • 順序存取：按照文件信息的邏輯順序(記錄的排列順序)依次存取。
    • 隨機(jī)存取(直接存取）：按任意的次序?qū)ξ募M(jìn)行讀寫操作
  • 與文件使用方式有關(guān)
    • 源程序文件用順序存取
    • 數(shù)據(jù)庫(kù)文件用隨機(jī)存取
  • 與存儲(chǔ)介質(zhì)的特性有關(guān)
    • 磁帶
    • 磁盤
• ?文件分配表
  • 為了有效地管理文件存儲(chǔ)器，通常把文件存儲(chǔ)空間劃分成若干個(gè)大小相等的物理塊。
  • 物理塊是分配及傳輸信息的基本單位。
  • 塊的大小通常是扇區(qū)的倍數(shù)，如512B、1KB、2KB或者4KB。
  • 文件分配表：描述文件所獲得物理塊的詳細(xì)信息，不同的操作系統(tǒng)賦予了該結(jié)構(gòu)不同的名字
    • DOS：FAT / Windows NTFS: MFT (master file table)
    • UNIX類操作系統(tǒng)：inode
  • 分配方式
    • 靜態(tài)分配：文件創(chuàng)建時(shí)申明需要的最大空間
      • 預(yù)分配，實(shí)現(xiàn)簡(jiǎn)單，易于維護(hù)，但靈活性差
    • 動(dòng)態(tài)分配：文件存儲(chǔ)空間按需分配
      • 實(shí)現(xiàn)較復(fù)雜，需要維護(hù)較多的數(shù)據(jù)結(jié)構(gòu)，實(shí)用性高

連續(xù)結(jié)構(gòu)（順序）

• 文件信息存放在若干連續(xù)的物理塊中
• 優(yōu)點(diǎn)：簡(jiǎn)單；支持順序存取和隨機(jī)存取；順序存取速度快：磁盤尋道次數(shù)（尋道時(shí)間）最少
• 缺點(diǎn)：不利于文件尺寸的動(dòng)態(tài)增長(zhǎng)（插入、刪除）；可能會(huì)導(dǎo)致磁盤碎片，降低外存空間的利用率（可以采用緊湊技術(shù)處理，從而改善）。

鏈接結(jié)構(gòu)

• 文件信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接。
  • 隱式鏈接
    • 每個(gè)物理塊都設(shè)有一個(gè)指針字段，指向下一個(gè)物理塊的位置。
    • 隨機(jī)訪問性能差
  • 顯式鏈接
    • 用于鏈接文件各物理塊的指針，顯示地存放在一張內(nèi)存鏈表中，該表在整個(gè)磁盤中僅一張。
    • 隨機(jī)性能優(yōu)于隱式鏈接
• 優(yōu)點(diǎn)：提高了磁盤空間利用率，不存在外部碎片問題；有利于文件插入和刪除
• 缺點(diǎn)：更多的尋道次數(shù)和尋道時(shí)間；隨機(jī)訪問性能差；可靠性問題，如指針出錯(cuò)
• 改進(jìn)方法：擴(kuò)大文件塊分配單位。若干個(gè)連續(xù)的數(shù)據(jù)塊，稱之為簇(Cluster)。
  • 簇（Cluster）
    • 一組連續(xù)的扇區(qū)→虛擬扇區(qū)
    • 分配單位 Cluster=2^n Sectors

索引結(jié)構(gòu)

文件信息存放在若干不連續(xù)物理塊中，每個(gè)文件關(guān)聯(lián)一個(gè)索引表，記錄塊號(hào)

索引表就是磁盤塊地址數(shù)組，第i個(gè)條目指向文件的第i塊

優(yōu)點(diǎn)：支持隨機(jī)存取（優(yōu)于鏈接結(jié)構(gòu)，找第i塊更快）；滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除要求；利用多級(jí)索引，可以支持大型文件的存取

缺點(diǎn)：較多的尋道次數(shù)和尋道時(shí)間（對(duì)比頁(yè)表）

一個(gè)數(shù)據(jù)塊容納不了一個(gè)文件的所有分區(qū)時(shí)，需要若干個(gè)索引結(jié)點(diǎn)進(jìn)行存儲(chǔ)

多級(jí)索引

• 盤塊大小：1 KB，每個(gè)盤塊號(hào)：4B
  • 一個(gè)索引塊中可存放1K/4B=256個(gè)盤塊號(hào)
  • 兩級(jí)索引時(shí)， 最多可包含的存放文件的盤塊總數(shù)N = 256 × 256 = 64 K個(gè)盤塊號(hào)。
  • 最大文件長(zhǎng)度：64MB
• 計(jì)算：盤塊大小：4KB，盤塊號(hào)：4B，一級(jí)、兩級(jí)索引時(shí)最大文件分別為？
  • 4KB/4B=2^10;? 1_file=2^10*4KB=4MB; 2_file=2^10*2^10*4KB=4GB

?綜合/混合模式

將多種索引分配方式相結(jié)合而形成的一種分配方式。

例如，系統(tǒng)既采用了直接地址，又采用了一級(jí)索引分配方式，或兩級(jí)索引分配方式，甚至還采用了三級(jí)索引分配方式。

Unix iNode

13個(gè)索引項(xiàng)，每項(xiàng)2個(gè)字節(jié) 前10項(xiàng)為直接塊

第11項(xiàng)指向一個(gè)物理塊，該塊中最多可放256個(gè)文件物理塊的塊號(hào)（一次間接尋址）。

第12和第13項(xiàng)作為二次和三次間接尋址

單個(gè)文件最大長(zhǎng)度：（10+256+256*256）*block-storage

練習(xí)題?

設(shè)文件索引節(jié)點(diǎn)中有7個(gè)地址項(xiàng) 4個(gè)直接地址索引 2個(gè)一級(jí)間接地址索引 1個(gè)二級(jí)間接地址索引 每個(gè)地址項(xiàng)大小為4B 磁盤索引塊和磁盤數(shù)據(jù)塊均為256B

問：單個(gè)文件的最大長(zhǎng)度是多少？

答：每個(gè)索引塊中的項(xiàng)目數(shù)為：256/4=64個(gè)

4個(gè)直接地址索引塊，可索引塊數(shù)：4

2個(gè)一級(jí)間接地址索引塊，可索引塊數(shù)：2×64=128

1個(gè)二級(jí)間接地址索引塊，可索引塊數(shù)：1×64×64=4096

單個(gè)文件的最大長(zhǎng)度為：（4+128+4096)*256B=1057KB

假定UNIX磁盤塊的大小為1KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，文件索引節(jié)點(diǎn)中的磁盤地址明細(xì)表如圖所示，請(qǐng)將下列文件的字節(jié)偏移量轉(zhuǎn)換為物理地址？

1． 9000 ? ? ? ? ?2． 14000 ? ? ? ? ? ? 3． 350000?

答：字節(jié)偏移量為9000時(shí)

邏輯塊號(hào)為：9000/1024＝8 塊內(nèi)偏移量為：9000 % 1024＝808 邏輯塊號(hào)小于10→該塊為直接塊。邏輯塊號(hào)8對(duì)應(yīng)的物理盤塊號(hào)為367，該塊中的第808字節(jié)即為文件的第9000字節(jié)。?

字節(jié)偏移量為14000時(shí)

邏輯塊號(hào)為：14000/1024＝13 塊內(nèi)偏移量為：14000 % 1024＝688 邏輯塊號(hào)9<13<266→該塊為一次間接塊。 一次間接的盤塊號(hào)為428，從一次間接塊中讀出盤塊號(hào)表，查得邏輯塊號(hào)13的物理塊號(hào)為952，該塊中的第688字節(jié)即為文件的第14000字節(jié)。

字節(jié)偏移量為350000時(shí)

邏輯塊號(hào)為：350000/1024＝341 塊內(nèi)偏移量為：350000 %1024＝816 因邏輯塊號(hào)265<341<65802(256*256+256+10)→該塊為二次間接塊。 由圖可知，二次間接塊的盤塊號(hào)為9156。一個(gè)一次間接塊中可容納256個(gè)塊號(hào)，341-10-256＝75 75/256=0，故字節(jié)偏移量350000在二次間接塊的第0個(gè)一次間接塊的第75個(gè)表項(xiàng)中，其盤塊號(hào)為333，該塊中的第816字節(jié)即為文件的第350000字節(jié)。

---

文件管理：目錄

文件控制塊FCB

FCB：File Control Block

描述和控制文件的數(shù)據(jù)結(jié)構(gòu) 與文件一一對(duì)應(yīng)

文件存在的標(biāo)志

文件控制塊的組成——與操作系統(tǒng)相關(guān)

FCB信息

文件名：用戶利用該名字進(jìn)行存取。

文件物理位置：在外存的存儲(chǔ)位置（設(shè)備名、起始盤塊號(hào)、占用的盤塊等）

使用信息：創(chuàng)建時(shí)間：create time ；最后一次讀訪問的時(shí)間：access time ；最后一次寫訪問的時(shí)間：modify time

---

目錄

基本概念

文件目錄：一組文件的集合

目錄：文件元數(shù)據(jù)（控制塊）的集合

目錄文件：目錄項(xiàng)構(gòu)成的文件

遞歸效果：目錄也用FCB表示

目錄即文件?

目錄文件具有固定格式 由系統(tǒng)進(jìn)行管理，用戶不能直接訪問目錄文件

目錄功能

• 按名存取
• 提高檢索速度
  • 合理地組織目錄結(jié)構(gòu)，可以加快對(duì)目錄的檢索速度，從而提高對(duì)文件的存取速度。
• 文件共享
  • 允許共享文件，節(jié)省存儲(chǔ)空間，方便用戶。
• 允許文件重名
  • 方便用戶按照自己的習(xí)慣來命名和使用文件。

目錄基本操作

• 羅列文件
• 搜索文件
  • 通過查找目錄結(jié)構(gòu)，實(shí)現(xiàn)特定文件的按名查找
• 創(chuàng)建文件
  • 建立新文件，將相應(yīng)控制塊加到目錄中去
• 刪除文件
  • 當(dāng)一個(gè)文件不再需要時(shí)，從目錄中刪除
• 重命名文件

?FCB組織方法

計(jì)算: 一個(gè)FCB有48字節(jié)，假設(shè)物理塊512字節(jié)，某目錄有128個(gè)文件。 計(jì)算查找一個(gè)文件平均訪盤次數(shù)。

• 每塊存儲(chǔ)的FCB數(shù)量：512/48=10
• 128個(gè)文件的目錄文件需要磁盤塊：128/10=13
• 平均訪盤次數(shù)：(1+13)/2=7(最少一次找到，最多13次，取均值)

?改進(jìn)的FCB組織方法

采用目錄項(xiàng)分解法，把FCB分成兩部分

一個(gè)FCB有48字節(jié)，符號(hào)目錄項(xiàng)占 8字節(jié)（文件名6字節(jié)，文件號(hào)2字節(jié)），假設(shè)物理塊512字節(jié)，某目錄有128個(gè)文件。 采用改進(jìn)的FCB組織方法，查找一個(gè)文件平均訪盤次數(shù)。

每塊存儲(chǔ)的符號(hào)目錄項(xiàng)：512/8=64

每塊存儲(chǔ)的基本目錄項(xiàng)：512/42=12

128個(gè)文件，符號(hào)文件、基本文件分別需要：128/64=2, 128/12=11

平均訪盤次數(shù)：(1+2)/2+1=2.5(最少一次查找符號(hào)目錄，最多兩次，取均值，再加上一次精準(zhǔn)查找的基本目錄項(xiàng))

目錄的組織

• 組織文件目錄是文件系統(tǒng)的主要內(nèi)容之一
• 有效性：快速定位一個(gè)文件
• 命名：用戶使用方便
  • 兩個(gè)用戶對(duì)不同的文件可以使用同一個(gè)文件名
  • 同一個(gè)文件可能有不同的文件名
    • 文件數(shù)據(jù)，元數(shù)據(jù)
• 空目錄≠文件數(shù)為0的目錄：不存在文件數(shù)為0的目錄！
• 單級(jí)目錄結(jié)構(gòu)
  • 所有文件都包含在同一目錄中
  • 缺點(diǎn)：查找速度慢；不允許重名；不便于共享；不能分組
• 兩級(jí)目錄結(jié)構(gòu)
  • 為每個(gè)用戶創(chuàng)建單獨(dú)的目錄
  • 用戶文件目錄UFD 主文件目錄MFD
  • 
  • 優(yōu)點(diǎn)：不同用戶可以有相同的文件名；提高了檢索速度；將一個(gè)用戶與另一個(gè)用戶有效隔開 ?
  • 缺點(diǎn)：不利于文件的共享
• 樹狀目錄結(jié)構(gòu)
  • 
  • 每一級(jí)目錄可以包含文件，也可以包含下一級(jí)目錄。
  • 只有一個(gè)根目錄，除根目錄外，其余每個(gè)目錄或者文件都有唯一的一個(gè)上級(jí)目錄。（父目錄、子目錄）
  • 優(yōu)點(diǎn)：文件的層次和隸屬關(guān)系清晰；便于實(shí)現(xiàn)不同級(jí)別的存取保護(hù)和文件系統(tǒng)的動(dòng)態(tài)裝卸
  • 缺點(diǎn)：
    • 不便于共享（相比較而言）

路徑

從樹根(namespace)到節(jié)點(diǎn)的唯一表達(dá)

不同文件→文件可以同名，但路徑名不同。（路徑名不同 ≠ 文件不同）

文件可按照相對(duì)于工作目錄的方式訪問：

絕對(duì)路徑(absolute)：從根目錄開始指定

相對(duì)路徑(relative)：從當(dāng)前工作目錄開始（./當(dāng)前目錄）（../上一級(jí)目錄）

練習(xí)：當(dāng)前目錄/spell/mail/copy 請(qǐng)用絕對(duì)和相對(duì)路徑表達(dá)紅色箭頭文件

prog: ./prog ; /spell/mail/prog

find:? .../programs/p/find ; /programs/p/find

all: /all ; /spell/mail/copy/all

first: ./prt/first ; /spell/mail/prt/first

無環(huán)圖目錄

在樹型目錄的基礎(chǔ)上，允許多個(gè)目錄項(xiàng)指向同一個(gè)數(shù)據(jù)文件或者目錄文件，實(shí)現(xiàn)了目錄或者數(shù)據(jù)文件的共享

一個(gè)文件或者目錄在多個(gè)父目錄中占有項(xiàng)目

目錄結(jié)構(gòu)不再是一顆樹，而是一個(gè)無環(huán)圖

實(shí)現(xiàn)共享文件：多個(gè)用戶同時(shí)訪問一個(gè)文件，可節(jié)約存儲(chǔ)空間

數(shù)據(jù)復(fù)制：數(shù)據(jù)不一致

通過路徑名共享：不靈活

鏈接：在多個(gè)目錄中對(duì)要共享的文件建立相應(yīng)的表項(xiàng)，一個(gè)文件或目錄在目錄樹中多處出現(xiàn)（引用） 在外存上只有一份物理存儲(chǔ)。

鏈接

硬鏈接：多個(gè)文件名鏈接到同一個(gè)索引結(jié)點(diǎn)，鏈接文件和被鏈接文件必須位于同一個(gè)文件系統(tǒng)中。

軟鏈接：符號(hào)鏈接(symbolic link, shortcut) 特殊類型的文件，其內(nèi)容是另一個(gè)目錄或文件的路徑。 無硬鏈接的限制，可跨盤，跨目錄，甚至跨機(jī)器。建立符號(hào)鏈接文件，并不影響原文件→它們是獨(dú)立的文件。?

缺點(diǎn)： 空間和時(shí)間開銷更大；如果設(shè)置不當(dāng)，上下級(jí)目錄關(guān)系可能會(huì)形成環(huán)狀

硬鏈接和軟鏈接的比較

硬鏈接

只允許文件鏈接，不允許目錄鏈接；

只能在同一個(gè)文件系統(tǒng)范圍內(nèi)進(jìn)行，不允許跨文件系統(tǒng)。

刪除文件時(shí)，如果還有其他鏈接鏈至該文件，則該文件不能被刪除。

軟鏈接

訪問速度相對(duì)慢一些，但適用范圍和靈活性要大一些。

允許目錄鏈接，允許在不同的文件系統(tǒng)間進(jìn)行鏈接，這兩個(gè)文件系統(tǒng)可以在同一個(gè)計(jì)算機(jī)上，也可以在不同的計(jì)算機(jī)上。

被鏈接文件的刪除和符號(hào)鏈接的刪除是完全獨(dú)立的

通用圖目錄

無環(huán)圖目錄結(jié)構(gòu)中，加上允許子目錄對(duì)上層目錄的引用的條件

允許環(huán)存在：搜索子目錄時(shí)要避免無窮地循環(huán)搜索——限制訪問目錄的次數(shù)來確定；釋放孤立環(huán)（orphan cycle）——垃圾回收（garbage collection）?。

---

文件管理：磁盤管理

磁盤存儲(chǔ)器

文件存儲(chǔ)空間的分配單位是磁盤塊而非字節(jié)；

文件系統(tǒng)必須記錄存儲(chǔ)空間的使用情況；

文件系統(tǒng)對(duì)存儲(chǔ)空間進(jìn)行分配和回收；

常用的磁盤空間的管理方式有：

---

空閑分區(qū)表

概念

將空閑分區(qū)登記在一張表中，一個(gè)分區(qū)對(duì)應(yīng)一個(gè)表項(xiàng)，每個(gè)表項(xiàng)包含有空閑分區(qū)號(hào)、分區(qū)起始?jí)K號(hào)、分區(qū)長(zhǎng)度等主要信息，按起始?jí)K序號(hào)排序

特點(diǎn)?

• 實(shí)現(xiàn)簡(jiǎn)單
• 將各空閑分區(qū)按照長(zhǎng)度有序進(jìn)行排列，能很快找到需要大小的空閑分區(qū)。 (排序規(guī)則不固定）
• 當(dāng)空閑分區(qū)分布較分散且數(shù)量較多時(shí)，空閑分區(qū)表將會(huì)很大。??

---

空閑分區(qū)鏈表

概念

利用空閑分區(qū)空間通過指針將各個(gè)空閑分區(qū)連接起來，并記載各空閑分區(qū)大小。

無空閑分區(qū)表的額外空間開銷。

特點(diǎn)

回收由許多離散小分區(qū)組成的文件時(shí)，小分區(qū)鏈接到空閑分區(qū)鏈表中需要很長(zhǎng)時(shí)間（按照某種規(guī)則，大小或者位置）。

類比可變分區(qū)管理

---

位示圖

• 一個(gè)向量，每位(bit)對(duì)應(yīng)于磁盤中的一個(gè)塊(block)
  • 空閑塊：0，已使用塊：1
• 方便地查找一個(gè)或一組連續(xù)的空閑分區(qū)。
• 位示圖需要占用的存儲(chǔ)空間大小
  • 磁盤容量（字節(jié)數(shù)）/ （8×數(shù)據(jù)塊大小） Byte
• 大位示圖搜索將會(huì)降低文件系統(tǒng)的性能?

---

成組塊鏈接法

• 將所有空閑塊每n塊劃分為一組，用索引表表示
• 每組的第一塊用來存放后一組中各塊的塊號(hào)和總塊數(shù)
  • 各組間自然構(gòu)成鏈表
• 第一組的塊號(hào)與總塊數(shù)放在一個(gè)專用棧中：空閑盤塊號(hào)棧
  • 棧計(jì)數(shù)count：棧中的空閑塊數(shù)目
  • 棧中的元素是空閑塊編號(hào)
• 對(duì)塊的分配和釋放在棧中進(jìn)行

分配方法

• 查看棧中是否count==1，若不是，那么就彈出棧頂元素N（表示可用磁盤塊號(hào)），分配出去，--count；若是，彈出棧頂元素N，把空閑塊N中的內(nèi)容讀入到棧中；返回空閑塊編號(hào)N。因?yàn)樗峙涞拇疟P塊號(hào)是棧中最后一個(gè)可用盤塊號(hào)，由于在該盤塊中存放了下一組的所有盤塊號(hào)，于是要先將該塊的內(nèi)容讀入棧中，然后才能將該塊分配出去

釋放方法

• 被釋放空閑塊為編號(hào)N。查看是否棧已滿，若不是，則N入棧，++count； 若是，則將棧（包括棧計(jì)數(shù)）寫入到空閑塊N，然后把N放入棧頂并置count為1。說明棧已滿，須先將棧中所有盤塊號(hào)復(fù)制到新回收的盤塊中，再將新回收盤塊的編號(hào)放到棧中，成為棧中第一個(gè)盤塊

例題

解：92=41+50+1，所以是#400最下面的一個(gè)，也就是401。?

---

文件一致性：盤塊

鏈接數(shù)一致性檢查

每個(gè)目錄項(xiàng)都含有一個(gè)索引結(jié)點(diǎn)號(hào)

共享文件的索引結(jié)點(diǎn)號(hào)會(huì)在目錄中出現(xiàn)多次

若某文件被共享（硬鏈接）N次，其索引結(jié)點(diǎn)號(hào)會(huì)在目錄中出現(xiàn)N次；

另一方面，該共享文件索引結(jié)點(diǎn)中的鏈接計(jì)數(shù)count，用來指出共享本文件的引用數(shù)。

正常情況下這兩個(gè)數(shù)據(jù)應(yīng)該一致

數(shù)據(jù)塊使用數(shù)組和空閑數(shù)組互補(bǔ)

---

文件執(zhí)行

數(shù)據(jù)結(jié)構(gòu)

用戶打開文件表：每個(gè)進(jìn)程一個(gè)，記錄用戶打開文件?

系統(tǒng)文件打開表：整個(gè)系統(tǒng)一張：放在內(nèi)存，用于保存已打開文件的FCB文件號(hào)、共享計(jì)數(shù)（打開共享）、讀寫位置、打開模式、修改標(biāo)志等；指向內(nèi)存inode（也有共享計(jì)數(shù)）

內(nèi)存inode表：操作文件時(shí)要將磁盤inode加載到內(nèi)存中；訪問速度；共享控制（計(jì)數(shù)）

三張表之間的關(guān)系

文件共享

不同進(jìn)程獨(dú)立訪問

同進(jìn)程復(fù)制fd：dup() / dup2() / fcntl()

跨進(jìn)程復(fù)制fd：fork()?

fork()可以共享文件，但是fork()以后打開文件則不共享?

文件操作

執(zhí)行過程

create：實(shí)質(zhì)是建立FCB，返回一個(gè)文件描述符

open：把FCB送到內(nèi)存，創(chuàng)建用戶、系統(tǒng)打開文件表項(xiàng)，建立與內(nèi)存inode三者關(guān)聯(lián)，返回文件描述符

close：緩存數(shù)據(jù)寫回磁盤；清理用戶文件打開表；清理系統(tǒng)文件打開表；清理內(nèi)存inode表

---

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

支持面向?qū)ο笫降奈募到y(tǒng)實(shí)現(xiàn)——多態(tài)

用戶程序：統(tǒng)一接口

底層支持：不同文件系統(tǒng)

VFS接口：API，而非具體的文件系統(tǒng)實(shí)現(xiàn)