【學習筆記】計算機操作系統（七）—

第七章文件管理

文章目錄

第七章文件管理
- 7.1 文件和文件系統
- - 7.1.1 數據項、記錄和文件
  - 7.1.2 文件名和類型
  - 7.1.3 文件系統的層次結構
  - 7.1.4 文件操作
- 7.2 文件的邏輯結構
- - 7.2.1 文件邏輯結構的類型
  - 7.2.2 順序文件(Sequential File)
  - 7.2.3 記錄尋址
  - 7.2.4 索引文件(Index File)
  - 7.2.5 索引順序文件(Index Sequential File)
  - 7.2.6 直接文件和哈希文件
- 7.3 文件目錄
- - 7.3.1 文件控制塊和索引結點
  - 7.3.2 簡單的文件目錄
  - 7.3.3 樹形結構目錄(Tree-Structured Directory)
  - 7.3.4 目錄查詢技術
- 7.4 文件共享
- - 7.4.1 基于有向無循環圖實現文件共享
  - 7.4.2 利用符號鏈接實現文件共享
- 7.5 文件保護
- - 7.5.1 保護域(Protection Domain)
  - 7.5.2 訪問矩陣
  - 7.5.3 訪問矩陣的修改
  - 7.5.4 訪問矩陣的實現
- 7.6 文件存儲空間管理 - 空閑磁盤塊管理
- - 7.6.1 存儲空間的劃分與初始化
  - 7.6.2 存儲空間管理
- 7.7 虛擬文件系統和文件系統掛載

7.1 文件和文件系統

7.1.1 數據項、記錄和文件

1、數據項

📌 數據項（Data Item）：文件系統中最低級的數據組織形式，用于**描述對象的屬性或特征**。可分為兩種類型👇

基本數據項（字段）

🔹 定義：描述對象 單一屬性的最小邏輯單位，不可再分。
🔹 組成：
- 基本數據項的 “型” = 數據名 + 數據類型
  - 數據名（如“學號”、“姓名”）
  - 數據類型（如整數、字符串、布爾值）
- 值（如“30211”、“王有年”）

組合數據項（組項）

🔹 定義：由 多個基本數據項組合 而成的復合屬性。
🔹 特點：
- 可拆分。
- 邏輯上作為一個整體處理。

🔹 例子：

工資 {  基本工資: xxxx,  工齡工資: xxxx,  獎勵工資: xxxx  
}

2、記錄

記錄：一組相關數據項的集合，用于描述對象的某方面屬性。

1?? 記錄的數據項組成

記錄包含哪些數據項，取決于對象的描述需求 👇

📝 示例1：學生作為“班級成員”

數據項	類型	示例值
學號	整數	30211
姓名	字符串	王有年
年齡	整數	20
所在班級	字符串	計算機2023
課程成績	組合數據項	{數學:90, 英語:85}

📝 示例2：學生作為“醫療對象”

數據項	類型	示例值
病歷號	字符串	M20231105
身高	浮點數	175.5
體重	浮點數	65.2
病史	字符串列表	[“過敏性鼻炎”]

同一對象在不同場景下，記錄的數據項可能完全不同！

2?? 關鍵字（Key）

🔹 定義：能 唯一標識一條記錄的數據項（或數據項組合）。
🔹 作用：快速定位、避免重復（類似數據庫的主鍵）。

🔑 關鍵字類型

單字段關鍵字（最常見）例如：學號、病歷號（保證不重復即可）。
復合關鍵字（多字段組合）當單個字段無法唯一標識時使用（如姓名+出生日期）。

?? 關鍵字的選擇原則

唯一性：不能有兩條記錄的關鍵字相同。
穩定性：盡量選擇不常變動的字段（如學號比年齡更適合作關鍵字）。
簡潔性：優先用單個字段，實在不行再用組合。

3、文件

文件的定義與分類

🔹 文件：由 創建者定義 📌、具有 文件名 📁的 一組相關元素 的集合。

📂 文件的兩種結構類型：

類型	特點	應用場景	典型應用
`有結構文件`	由 `若干個相關記錄（Records）` 組成 📊	適用于需要頻繁查詢/修改部分數據的場景	數據庫表、學生檔案
`無結構文件`	視為 `字符流`（連續的字節序列）📜	適合整體讀寫（如照片、視頻）	文本文件、圖像、二進制文件

文件屬性（File Attributes）

屬性	說明	示例
`文件類型` 📝	用途或格式分類（如`.txt`、`.exe`、`.mp4`）	`.py`（Python源碼）
`文件長度` 📏	當前大小（字節/KB/GB）或最大允許長度	`1024 KB`
`物理位置` 📍	存儲的設備和地址（如磁盤C:、扇區編號）	`/dev/sda1, 塊號2048`
`建立/修改時間` ?	創建時間、最后修改時間	`2023-10-05 14:30:00`

? 注意：

這些屬性由 文件系統管理（用戶不可直接修改，如物理位置）。
文件的類型和長度影響其存儲和訪問方式。

4、文件 vs 記錄 vs 數據項的層次關系

7.1.2 文件名和類型

1、文件名和擴展名

文件名：【同一目錄下不允許有重名文件】

📌 1. 文件名長度限制

系統/文件系統	最大長度限制	特點
MS-DOS	8字符（短文件名）	老系統，嚴格限制
舊版 UNIX	14字符	早期標準
NTFS（Win NT+）	255字符（長文件名）?	現代系統支持長文件名

? 2. 禁用字符

常見禁用符號：空格、*/:<>?\|（因用作命令分隔符或路徑符）
現代系統改進：NTFS/Linux 允許空格（需用引號或轉義符包裹，如 "my file.txt"）。

🔠 3. 大小寫敏感性問題

系統類型	是否區分大小寫？	示例（是否相同文件？）
MS-DOS/Win95	? 不區分	`MYFILE` = `myfile`
UNIX/Linux	? 嚴格區分	`MYFILE` ≠ `myfile`

擴展名：

📌 1. 擴展名的作用

標識文件類型🔍：通過擴展名（后綴）快速識別文件的格式和用途。
- 例如：.txt → 文本文件，.jpg → 圖片文件，.exe → 可執行程序。
關聯打開程序 💻：操作系統用它匹配默認打開方式（如雙擊 .pdf 用 Adobe 打開）。

📌 2. 命名規則

規則	示例	說明
分隔符	`文件名.擴展名`	用 `.` 分隔（如 `docx`）
長度	1~4個字符常見	少數擴展名更長（如 `.jpeg`）
大小寫敏感	視操作系統而定	Windows 通常不區分（`.TXT` = `.txt`）

📌 3. 常見擴展名一覽

類型	典型擴展名	用途
文本文件	`.txt`, `.md`	純文本/標記語言
圖片文件	`.jpg`, `.png`	圖像存儲
可執行文件	`.exe`, `.bin`	程序/二進制代碼
文檔文件	`.pdf`, `.docx`	格式化文檔
壓縮文件	`.zip`, `.rar`	打包壓縮數據

2、文件類型

📝 文件按用途分類

📌 1、系統文件（System Files）

🔐 權限特點：

僅供系統使用，多數僅允許調用（執行），禁止讀寫?。
部分文件對用戶完全隱藏（如 Windows 系統 C:\Windows\System32）。

📌 2. 用戶文件（User Files）

🎨 自由度高：

用戶完全控制（可讀、寫、刪、改）?，用戶將這些文件委托給系統保管。
包括源代碼（.c/.py）、文檔（.docx）、媒體（.mp4）等。

📂 分類：

子類型典型擴展名作用
源代碼 .java, .cpp 程序員編寫的原始代碼
可執行文件 .exe, .app 直接運行的程序
數據文件 .xlsx, .db 存儲用戶數據

子類型	典型擴展名	作用
源代碼	`.java`, `.cpp`	程序員編寫的原始代碼
可執行文件	`.exe`, `.app`	直接運行的程序
數據文件	`.xlsx`, `.db`	存儲用戶數據

📌 3. 庫文件（Library Files）

📚 共享但保護：

允許調用（如數學庫、圖形庫），但禁止修改🚫。
提供通用功能，避免重復造輪子。

📂 示例：

靜態庫（.lib/.a）：編譯時綁定。
動態庫（.dll/.so）：運行時調用。

📝 文件按數據形式分類

📌 1. 源文件（Source Files）

💻 定義：

包含原始代碼或數據的文本文件，由程序員/用戶直接編寫👩?💻。
一般為ASCII/Unicode編碼。

📂 特點：

擴展名：.c (C語言)、.py (Python)、.txt (純數據)。

📌 2. 目標文件（Object Files）

🔧 定義：

源文件經編譯生成的中間文件，包含機器碼但未完整鏈接🔗。
不可直接執行，需進一步處理。

📂 特點：

擴展名：.obj (Windows)、.o (Linux/macOS)。
內容：二進制代碼 + 符號表（函數/變量地址）。

📌 3. 可執行文件（Executable Files）

🚀 定義：

完全鏈接后的文件，可直接由操作系統運行?。
包含機器指令 + 庫依賴 + 資源。

📂 特點：

平臺擴展名
Windows .exe
Linux 無擴展名或.bin
macOS .app

平臺	擴展名
Windows	`.exe`
Linux	無擴展名或`.bin`
macOS	`.app`

📝 文件存取控制屬性分類

📌 1. 只執行文件（Execute-only File）

權限：🔒
- 允許：被核準的用戶調用執行（如運行程序）
- 禁止：? 讀內容、? 修改/寫入

📌 2. 只讀文件（Read-only File）

權限：📖
- 允許：文件主及授權用戶讀取內容
- 禁止：? 修改、刪除或寫入

📌 3. 讀寫文件（Read-Write File）

權限：??
- 允許：文件主及授權用戶讀取 + 修改（如編輯、保存）
- 注意：需謹慎設置權限，防止越權操作！

📝 文件組織形式和處理方式分類

📌 1、普通文件（Regular File）

內容：📄 ASCII碼（文本）或二進制碼（程序/數據）
例子：
用戶創建的：源代碼（.c/.py）、文檔（.txt）
系統自帶的：內核代碼、實用工具（如 ls 命令）

特點：最常見的文件類型，可直接讀寫內容！

📌 2、目錄文件（Directory File）

本質：📂 文件目錄的集合（一種特殊文件）
功能：
記錄**下屬文件的元信息**（名稱、權限等）
支持文件檢索（如 ls）、操作（如 cd）

權限控制：和普通文件類似（需 r 讀目錄、w 增刪文件）
舉個栗子🌰：/home/user/ 是一個目錄文件，存放下屬文件列表。

📌 3、特殊文件（Special File / Device File）

代表對象：🖨? I/O設備（如鍵盤、打印機、磁盤）
設計目的：統一用文件接口管理設備！
訪問方式：
像操作文件一樣 讀/寫設備（如 /dev/sda 代表磁盤）
實際執行由 設備驅動程序完成

權限驗證：與普通文件規則一致（但操作可能受限）

類型細分：
字符設備（如 /dev/tty，按字符流傳輸）
塊設備（如 /dev/sda，按數據塊傳輸）

7.1.3 文件系統的層次結構

文件系統的模型可分為三個層次: 最底層是對象及其屬性，中間層是對對象進行操縱和管理的軟件集合，最高層是文件系統提供給用戶的接口。

在這里插入圖片描述

1、對象及其屬性

1?? 文件（File） 📄

核心對象：文件是文件系統直接管理的實體。
多樣性：包括 文本文件、二進制文件、可執行文件 等不同類型。
管理內容：
- 存儲（占用磁盤空間）
- 讀取/寫入控制（權限管理）
- 元數據維護（文件名、大小、修改時間等）

💡 關鍵作用：用戶和程序操作的基本單位！

2?? 目錄（Directory） 📂

功能：幫助用戶 組織文件、快速檢索。
目錄項包含：
- 文件名（標識文件）
- 文件屬性（如權限、類型、大小）
- 物理地址 / 指針（指向文件在磁盤的實際位置）
優化目標：
- 加快查找速度（索引、哈希等優化方法）
- 層級結構（如樹形目錄，/home/user/docs/）

? 影響：目錄設計直接影響 文件存取效率！

3?? 存儲空間（Disk/Tape Storage） 💿

核心任務：高效管理文件和目錄占用的 物理存儲。
管理方式：
- 空間分配（如連續分配、鏈式分配、索引分配）
- 碎片整理（減少空間浪費）
- 磁盤調度優化（提高讀寫速度）

🔧 重要性：好的存儲管理能 提升系統整體性能！

2、對對象進行操縱和管理的軟件集合

操縱對象

存儲空間管理 💾 - 管理文件在磁盤上的存儲分配【對象：存儲空間】
目錄管理 📁 - 組織文件和目錄結構【對象：目錄】
地址轉換 🔄 - 邏輯地址?物理地址轉換【對象：文件】
讀寫管理 ??📖 - 控制文件讀寫操作【對象：文件】
共享與保護 🔒 - 實現文件共享和安全機制【對象：文件】

與文件系統有關的軟件分為四個層次（自底向上）👇

1?? I/O控制層（設備驅動程序層）

功能：
- 最底層，直接與硬件交互 🖥??
- 通過 磁盤驅動程序 控制物理設備（如讀寫磁盤扇區）。

2?? 基本文件系統層（數據塊交換層）

功能：
- 負責內存 ?磁盤的 數據塊傳輸（如緩存塊加載/寫回）📦?💽
- 不關心內容含義，只處理原始塊操作。

3?? 基本I/O管理程序（磁盤事務層）

核心任務：
- 邏輯塊 → 物理塊映射 🗺?（如文件第3塊對應磁盤的哪個扇區？）
- 空閑盤塊管理（標記哪些塊可用/已占用）🔍
- I/O緩沖區分配（優化讀寫速度）?→🚀

4?? 邏輯文件系統（用戶接口層）

功能：
- 處理 文件和記錄 的高層操作 ?
- 提供 符號文件名訪問（如/home/note.txt）📂
- 實現 文件保護（權限控制）和 元數據管理（創建時間、大小等）🔒
用戶視角：
- “右鍵屬性”都來自這一層 🌳📋

3、文件系統提供給用戶的接口

文件系統通過 標準化的接口 為用戶和應用程序提供 文件和記錄操作 的方法，使其無需關心底層存儲細節。

📋 (1) 命令接口（Command Interface）

🔹 定義：用戶通過 命令行終端（CLI） 輸入指令與文件系統交互。
🔹 特點：

? 直接交互（如 ls、cp、rm 等命令）。
? 適用于管理員、開發者 或 需要手動操作文件的場景。

💻 (2) 程序接口（Program Interface / API）

🔹 定義：應用程序通過 系統調用（System Calls） 訪問文件系統。
🔹 特點：

? 編程方式調用（如 open()、read()、write()）。
? 適合軟件開發

文件系統的層次結構詳細版

7.1.4 文件操作

創建文件 🆕

功能：建立新文件并分配存儲空間。【進行 Create 系統調用】
步驟：
1. 為新文件 分配外存空間（如磁盤）。
2. 在 文件目錄中創建目錄項，記錄文件屬性：
  - ? 文件名
  - ? 外存地址（物理位置）
  - ? 元數據（大小、權限、時間等）。

刪除文件 🗑?

功能：釋放文件占用的資源。【進行 Delete 系統調用，參數文件名和文件路徑】
步驟：
1. 查找目錄項：根據文件名定位到對應條目。
2. 回收空間：釋放文件占用的外存（物理刪除）。
3. 標記為空項：刪除目錄中的記錄（邏輯刪除）

讀文件 📖

功能：從 外存讀取文件內容到內存。【進程使用read系統調用】
步驟：
1. 查找目錄：根據文件名找到目錄項。
2. 獲取位置：從目錄項中讀取文件的 外存地址。
3. 移動指針：通過目錄項中的 讀指針定位讀取位置（默認從文件開頭）。

寫文件 ??

功能：將 內存中的數據寫入外存文件。【進程使用write系統調用】
步驟：
1. 查找目錄：根據文件名找到對應的目錄項。
2. 獲取外存地址：從目錄項中讀取文件的 外存地址。
3. 定位寫指針：根據目錄項中的寫指針（或當前文件偏移量）確定寫入位置：
  - 如果寫指針默認在文件開頭（如新文件或覆蓋寫），則從起始位置寫入。
  - 如果寫指針在文件末尾（追加模式），則從結尾續寫。
4. 執行寫入：將內存中的數據寫入外存，并更新寫指針的位置。
注意：寫入可能覆蓋原有內容！??

設置讀/寫位置 🎯

功能：實現 隨機存取（非順序操作）。
關鍵：通過調整 文件的讀/寫指針，直接跳轉到指定位置。
- 順序存取：每次操作必須從頭開始。
- 隨機存取：靈活定位。

當用戶對文件進行多次操作（讀/寫）時，如果每次都要從目錄檢索開始（根據文件名找外存位置），會導致重復檢索開銷大，效率低下。

引入 open() 系統調用，提前加載文件信息到內存。避免重復目錄檢索，用空間換時間。

“打開文件” - open(文件路徑，文件名，對文件的操作類型：只讀r/讀寫rw) 🚪

判斷權限: 根據文件存放路徑找到相應的目錄文件，從目錄中找到文件名對應的的目錄項，并檢查該用戶是否有指定的操作權限。
建立連接：在用戶和文件之間創建一個 邏輯通道（無需重復檢索目錄）。
內存緩存：將 文件的屬性（如外存地址、權限、大小等） 從目錄項 拷貝 到 內存的打開文件表。
返回索引號：系統為用戶分配一個 文件描述符（File Descriptor）【也稱索引號】，后續操作直接憑此索引訪問文件。

在這里插入圖片描述

“關閉文件” - close() ??

斷開連接：釋放文件描述符（“退票”）。
清理內存：從打開文件表刪除該文件的表目。
同步數據（可選）：如果文件被修改，可能將緩沖區的數據寫回磁盤💾。

在這里插入圖片描述

文件屬性操作 📂??

功能：直接修改/查詢文件的元數據（metadata）。
常用系統調用：
- rename：修改文件名 🔄
- chown：改變文件所有者 👑
- chmod：修改文件權限（讀/寫/執行）🔐
- stat/fstat：獲取文件狀態 ??包括：大小、創建時間、類型、權限等。

目錄操作 📁🔧

功能：管理文件系統的目錄結構。
常用系統調用：
- mkdir：創建目錄 🆕
- rmdir：刪除空目錄 🗑?要求目錄必須為空
- getcwd：獲取當前工作目錄 🗺?
- chdir：切換工作目錄 🔄
注意：
- 刪除非空目錄需遞歸操作（如rm -rf命令💥）

文件共享與系統級操作 🤝💻

功能：實現多進程/用戶共享文件或管理文件系統。
關鍵系統調用：
- link：創建硬鏈接（同一文件的多個入口）??
- symlink：創建軟鏈接（快捷方式）🔗（刪除原文件后失效💨）
- mount/unmount：掛載/卸載文件系統 🏗?

7.2 文件的邏輯結構

檢索速度同時受以下兩種結構影響

文件的邏輯結構（File Logical Structure） 🧠📄

定義：從 用戶視角 看到的文件組織形式【在用戶看來，文件內部的數據應該是如何組織起來的。】

核心特點：

用戶可見 👀：用戶直接操作。
獨立于物理存儲 💾：與磁盤如何存放無關。
組成單位：由 邏輯記錄（Logical Record）構成，用戶可以直接處理的數據及其結構
又稱為 文件組織(File Organization)

文件的物理結構（File Physical Structure）- 非空閑磁盤塊管理 🖥?📦

定義：文件在 外存（磁盤）上的實際存儲方式，對用戶透明。【在操作系統看來，文件的數據是如何存放在外存中的。】

核心特點：

用戶不可見 🙈：由操作系統管理。
依賴存儲介質 💽：與磁盤塊大小、分配策略相關。

在外存管理中，為了方便對文件數據的管理，文件的邏輯地址空間也被分為了一個一個的文件“塊” 。文件的邏輯地址表示為(邏輯塊號，塊內地址) 的形式，操作系統 為文件分配存儲空間都是以塊為單位 的。用戶通過邏輯地址來操作自己的文件，操作系統要負責實現從邏緝地址到物理地址的映射

在這里插入圖片描述

類型	描述	目錄項內容	優點	缺點
連續分配	文件占用的磁盤塊物理相鄰 📏	起始塊號、文件長度	`支持順序訪問和直接訪問`(即隨機訪問) 連續分配的文件在順序訪問時速度最快	`不方便文件拓展`; 存儲空間利用率低，`會產生磁盤碎片`（外部碎片）
鏈式分配	`隱式鏈接`：除文件的最后一個盤塊之外，每個盤塊中都存有指向下一個盤塊的指針 `顯式鏈接` ：建立一張文件分配表(FAT)顯式記錄盤塊的先后關系(開機后FAT常駐內存)	隱式鏈接：起始塊號、結束塊號顯式鏈接：起始塊號	隱式鏈接：很 `方便文件拓展，不會有碎片問題` ，外存利用率高。顯式鏈接：很 `方便文件拓展，不會有碎片問題`，外存利用率高，并且 `支持隨機訪問`。相比于隱式鏈接來說，`地址轉換時不需要訪問磁盤（文件分配表常駐內存）`，因此文件的訪問效率更高。	隱式鏈接：`只支持順序訪問，不支持隨機訪問`，查找效率低，`指向下一個盤塊的指針也需要耗費少量的存儲空間`。顯式鏈接：`文件分配表的需要占用一定的存儲空間`。
索引分配	為文件數據塊建立索引表若文件太大，可采用鏈接方案、多層索引、混合索引📇	鏈接方案記錄的是雪，全層準合案引記錄的是頂級索引塊的塊號	`支持隨機訪問`，易于實現 `文件的拓展`	`索引表需占用一定的存儲空間`。`訪問數據塊前需要先讀入索引塊`。若采用 `鏈接方案`，查找索引塊時可能需要 `很多次讀磁盤操作`

連續分配：連續分配方式要求每個文件在磁盤上占有一組連續的塊

可以直接算出邏輯塊號對應的物理塊號，因此 連續分配支持順序訪問和直接訪問(即隨機訪問)
鏈式分配 ：考試題目中遇到未指明隱式/顯式的“鏈接分配”，默認指的是隱式鏈接的鏈接分配
- 隱式鏈接：
- 顯式鏈接：把用于鏈接文件各物理塊的指針顯式地存放在一張表中，即 文件分配表(FAT, File Allocation Table )
索引分配：索引分配允許文件離散地分配在各個磁盤塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊。索引表存放的磁盤塊稱為索引塊。文件數據存放的磁盤塊稱為數據塊。

超級超級超級重要考點:

①要會根據多層索引、混合索引的結構計算出 文件的最大長度(Key:各級索引表最大不能超過一個塊);

②要能自己分析 訪問某個數據塊所需要的讀磁盤次數(Key: FCB中會存有指向頂級索引塊的指針，因此可以根據FCB讀入頂級索引塊。每次讀入下一級的索引塊都需要一次讀磁盤操作。另外，要注意題目條件--頂級索引塊是否已調入內存)

邏輯結構 vs 物理結構

文件內部各條記錄鏈式存儲:由創建文件的用戶自己設計的

文件整體用鏈接分配:由操作系統決定

在這里插入圖片描述

索引文件的索引表：用戶自己建立的，映射:關鍵字→記錄存放的邏輯地址

索引分配的索引表：操作系統建立的，映射:邏輯塊號→物理塊號

7.2.1 文件邏輯結構的類型

1、按文件是否有結構分類

有結構文件（記錄式文件）📊

定義：像Excel表格一樣按記錄存儲數據，每條記錄描述一個實體（如學生信息表）。一般來說，每條記錄有一個數據項可作為關鍵字(作為識別不同記錄的ID)

1. 定長記錄 🔢

特點：
? 所有記錄長度相同（如身份證號固定18位）
? 數據項位置固定（類似表格列對齊）
? 高速訪問：直接計算偏移量定位（秒級跳轉?）

2. 變長記錄 🐍

特點：
🌟 記錄長度可變，但每個記錄的長度都是可知的（如病歷摘要📝、商品評論💬）
?? 需額外存儲長度信息（如開頭2字節記錄長度）
🐢 訪問速度較慢（需順序遍歷）

無結構文件（流式文件）🌊

定義：字節流 形式存儲（如MP3/EXE文件）

特點：
? 極致簡單：僅按字節編號，以字節為單位的。
? 靈活通用：任何數據都可存儲
? 訪問方式：讀寫指針控制

應用場景：源程序、可執行文件、庫函數等，所采用的就是無結構的文件形式

2、按有結構文件的組織方式分類

一、順序文件（Sequential File）??📉

定義：指由一系列記錄 按某種順序排列 所形成的文件。【文件中的記錄一個接一個地順序排列(邏輯上)。】

核心特點：

存儲方式：
- 定長記錄：直接物理連續存儲（如數組🗃?）
- 變長記錄：需用分隔符/長度前綴標記（如CSV📝）
物理上存儲：
- 順序存儲 ：邏輯上相鄰的記錄物理上也相鄰(類似于順序表)
- 鏈式存儲 ：邏輯上相鄰的記錄物理上不一定相鄰(類似于鏈表)
結構：
- 串結構：記錄之間的順序與關鍵字無關。通常 按照記錄存入的時間決定記錄的順序
- 順序結構：記錄之間的順序 按關鍵字順序排列。
訪問特性：
- ? 順序訪問極快（適合磁帶等順序存儲介質🎞?）
- ? 隨機訪問極慢（平均需遍歷n/2條記錄🐢）

二、索引文件（Indexed File）🔍📇

定義：為可變長記錄文件建立 一張索引表，為 每個記錄設置一個表項

核心特點：

結構組成：
- 數據區：原始變長記錄
- 索引區：固定格式的〈key, 物理地址〉映射表（像字典📖）
訪問特性：
? 隨機訪問極快（O(1)時間復雜度?）
? 空間開銷大（需額外存儲索引表）

三、索引順序文件（Indexed Sequential File）🔄🚀

定義：分組建立索引 —— 為每個文件建立一張索引表時，并不是為每一個記錄建立一個索引表項，而是為一組記錄中的第一個記錄建立一個索引表項。

核心特點：

分層結構：
- 數據分塊（如每100條記錄為一組）
- 只索引每組的第一個記錄（空間省50%+?）
訪問特性：
? 折中了順序和索引的優點
? 適合 超大規模文件

7.2.2 順序文件(Sequential File)

1、順序文件的排列方式

1. 串結構 ?（時間序列式）

特點：

無腦追加：按存入時間的先后進行排序 的，各記錄之間的順序與關鍵字無關。
零排序：記錄之間沒有邏輯關聯 → 純線性結構 ?
檢索代價：
🐢 必須從頭遍歷，直到找到指定的記錄或查完所有的記錄為止。（平均查找次數 = n/2）
😫 最壞情況查完全部記錄

應用場景：系統日志文件🖥?、區塊鏈交易記錄（按時間戳追加??）

2. 順序結構 🔢（關鍵字排序式）

特點：

強制排序：用戶指定 唯一關鍵字（如學號/身份證號🆔）, 可以是 任意類型的變量，每個記錄的關鍵字值 在文件中具有唯一性。
有序：記錄 按關鍵字嚴格排序（像字典拼音排序📖）
檢索加速：支持高效算法 → 如折半查找法、插值查找法、跳步查找法等方法提高檢索效率。

應用場景：學生信息表（按學號排序🎓）

鏈式存儲：無論是定長/可變長記錄，都無法實現隨機存取，每次只能從第一個記錄開始依次往后查找
順序存儲：
可變長記錄：無法實現隨機存取。每次只能從第一個記錄開始依次往后查找
定長記錄：可實現隨機存取。記錄長度為L，則第i個記錄存放的相對位置是i*L
若采用串結構，無法快速找到某關鍵字對應的記錄
若采用順序結構，可以快速找到某關鍵字對應的記錄(如折半查找 - 快速檢索)

一般來說，考試題目中所說的“順序文件”指的是物理上順序存儲的順序文件。

2、順序文件的優缺點

? 順序文件的優點

1. 批量存取效率極高 🚀

最佳場景：需要大批量連續讀寫（如日志備份、數據導出）

2. 存儲結構簡單 📏

定長記錄：物理存儲連續，類似數組（訪問簡單高效🔢）
變長記錄：利用分隔符（CSV、JSON等）管理

3. 適合順序存儲設備（磁帶）🎞?

磁帶只能順序訪問 → 順序文件是唯一可行方案

? 順序文件的缺點

1. 隨機訪問性能差?

查找復雜度：平均O(n/2)，最差O(n)（遍歷全表😵）
變長記錄更慢：額外解析記錄邊界（加劇I/O開銷📉）

2. 修改（增/刪/改）困難 ??

插入/刪除：必須移動后續記錄（類似數組操作，時間復雜度O(n)）【如果是串結構則相對簡單】
擴容受限：變長記錄易導致存儲碎片化

🔧 解決方案：日志文件（Log / Transaction File）

核心思想：避免實時修改主文件，采用批處理合并方式

實現方式：

主文件（Main File） 保持順序結構（只讀📖）
操作日志（Log File） 記錄增刪改請求📝
定期合并（如4小時/每日）生成新主文件🔄

🚀 用順序文件的場景：批量處理 + 順序設備（如日志備份、ETL數據流）
🚫 避免使用的場景：高頻隨機讀寫 + 低延遲要求（如在線交易系統）

7.2.3 記錄尋址

1、隱式尋址方式

隱式尋址（Implicit Addressing）是順序文件訪問記錄的方式，通過讀/寫指針自動定位記錄地址，適用于定長/變長記錄的順序文件。

在這里插入圖片描述

定長記錄

存儲結構：所有記錄固定長度（L），物理連續存儲（類似數組）

指針操作

讀指針（Rptr）：指向 下一個待讀取記錄的首地址
```
// 每當讀完一個記錄時，便執行
Rptr = Rptr + L  
```
示例：若 L=100B，當前 Rptr=0x1000，讀完后 Rptr=0x1064（0x1000 + 100）

寫指針（Wptr）：指向 下一個待寫入位置

// 在每寫完一個記錄時，便執行
Wptr = Wptr + L

變長記錄

存儲結構：每個記錄包含長度字段（Li），存儲不連續：

指針操作: 設置讀或寫指針，在每次讀或寫完個記錄后，須將讀或寫指針加上L_i，L_i是剛讀或剛寫完的記錄的長度。

Rptr = Rptr + Li + sizeof(Li)

關鍵問題

性能損失：每次需解析長度字段 → 額外I/O開銷📉
隨機訪問低效：必須順序掃描前 i-1 個記錄才能找到第 i 個（時間復雜度O(n)😵）

2、顯式尋址方式

通過文件中記錄的位置

定長記錄文件

獲得第i個記錄相對于第一個記錄首址的地址:
$A_i = i × L （首地址為 0）。$

由于獲得任何記錄地址的時間都非常短，故可利用這種方法對定長記錄實現隨機訪問。
變長記錄文件

記錄長度不固定（L1, L2, ...），必須順序解析前 i-1 個記錄才能定位第 i 個，檢索時間長很低效
$Ai=∑i=0i?1Li+1A_i = \sum_{i=0}^{i-1}L_i + 1$

利用關鍵字

定長記錄文件 + 變長記錄文件：用戶必須指定一個字段作為關鍵字，系統將利用該關鍵字順序地從第一個記錄開始，與每一個記錄的關鍵字進行比較，直到找到匹配的記錄。

? 隱式尋址 vs 顯式尋址

特性	隱式尋址	顯式尋址
訪問方式	指針自動移動📍	直接跳轉（通過索引）🎯
適用記錄	定長/變長	通常定長
隨機訪問	? 慢（O(n)）	? 快（O(1)~O(log n)）
存儲開銷	低	高

7.2.4 索引文件(Index File)

1、按關鍵字建立索引

📌 問題背景

定長記錄文件：可通過計算直接定位記錄，支持高效 隨機訪問。🔢
變長記錄文件：必須 順序查找，效率低（O(n)時間）。?

💡 解決方案：索引表

索引表結構
- 每個表項包含：
  - 指針：記錄在邏輯地址空間的首地址。📍
  - 長度：記錄的長度（L）。📏
- 索引表按 關鍵字排序，本身是 定長記錄的順序文件。
檢索流程
1. 折半查找：在索引表中 用關鍵字快速定位 記錄（O(log n)時間）。🔍
2. 直接訪問：根據 指針和長度定位 主文件中的記錄。🚀
更新操作
- 新增記錄：需同步 更新索引表（維護排序）。🔄
- 刪除/修改：類似處理，可能 需調整索引表。??

2、具有多個索引表的索引文件

🔍 背景問題

單索引表限制：只能按 一個關鍵字 檢索。🔢
實際需求：不同用戶希望按不同屬性快速查找。🎯

💡 解決方案：多索引表

索引表結構
- 每個檢索屬性一個索引表，例如：
  - 📖 圖書編號索引（主鍵）
  - 📚書名索引
  - ?? 作者索引
  - 📅 出版時間索引
- 🗂? 所有索引表按各自關鍵字排序，仍是 定長記錄文件。
檢索流程
- 🔎用戶選擇檢索條件（如作者="魯迅"）→ 在對應索引表中折半查找→ 通過指針定位主文件記錄。
更新操作
- ?? 增/刪/改記錄：需 同步更新所有相關索引表，維護排序性。

🎯 核心優勢

多維度檢索：支持按任意關鍵字（屬性）高效查詢，適應不同需求。🌈
高效隨機訪問：索引表將O(n)順序查找優化為O(log n)隨機訪問。?
動態維護便捷：記錄增刪僅需調整索引表，無需重組主文件。🔄

?? 缺點

存儲開銷大：每個記錄需在多個索引表中保留條目，占用額外空間。💾
更新代價高：修改主文件需同步更新多個索引表。??

7.2.5 索引順序文件(Index Sequential File)

1、索引順序文件的特征

📚 基本概念：索引順序文件是 順序文件的改進版，在保留順序文件核心特性的基礎上，通過 引入索引表 和 溢出文件，顯著提升了文件操作的靈活性。

💡 核心特點

📌 記錄按關鍵字順序存儲（保留順序文件的特性）
🔍 支持隨機訪問（通過索引表實現）
🛠 增刪改更高效（利用溢出文件管理動態變更）

🎯 核心組件

文件索引表：
- 提供 隨機訪問能力（通過折半查找快速定位記錄）。🔍?
- 將O(n)順序檢索優化為O(log n)。🎯
溢出區（Overflow File）：
- 存儲新增、刪除或修改的記錄，避免頻繁重組主文件。🔄
- 類似數據庫的“臨時緩沖區”，定期合并到主文件。?

? 優勢

隨機+順序雙模式：既可快速訪問單條記錄，又支持高效順序掃描。🔀
動態維護便捷：溢出區減少插入/刪除時的數據遷移開銷。?
低成本升級：在順序文件基礎上僅增加索引和溢出區，存儲開銷可控。💾

?? 局限性

溢出區膨脹：長期不合并可能導致檢索性能下降（需定期維護）。??
不適合高頻更新：大量修改時溢出區管理復雜度增加。??

2、一級索引順序文件

📚 基本原理

首先將變長記錄順序文件中的 所有記錄分為若干個組，如50個記錄為一個組。
然后為順序文件 建立一張索引表，并為 每組中的第一個記錄在索引表中建立一個索引項，其中 含有該記錄的關鍵字和指向該記錄的指針。

🔍 檢索流程詳解（兩步法）

1?? 第一步：索引表查找（定位記錄組）

輸入：用戶/程序提供的 目標關鍵字 🔑
查找算法：
- 二分查找（索引表有序時） ?
- 順序查找（簡單但略慢） 🐢
輸出：
- 找到 目標記錄所在分組 的首記錄表項
- 提取該組的 起始位置指針（指向主文件） 📌

2?? 第二步：主文件順序查找（定位目標記錄）

輸入：索引表返回的 組起始位置
查找方法：
- 從起始位置開始，順序掃描 該組記錄 📖
- 逐個比對關鍵字，直至命中目標（或失敗） 🎯
平均查找次數：
- 每組 k 條記錄 → 平均需查 k/2 次

🎯 索引順序文件的平均查找次數是√N

總記錄數 = N
每組記錄數 ≈ √N
組數 ≈ √N（組數 × 每組記錄數 ≈ N）

1?? 查索引表（定位組）：

對√N個索引項進行二分查找 → 平均比較次數≈log?(√N)
當N較大時，可近似為O(√N)（例如順序查找索引表時）。

2?? 查主文件（組內順序查找）：

每組√N條記錄 → 平均查找√N/2次

總查找次數 ≈ √N（索引） + √N/2（組內） ≈ √N

3、兩級索引順序文件

為順序文件建立多級索引，即為索引文件再建立一張索引表，從而形成兩級索引表。

在這里插入圖片描述

7.2.6 直接文件和哈希文件

1、直接文件

🎯 核心特點 ：關鍵字（Key） → 物理地址（Address）的直接轉換！

無需中間查找：跳過索引、鏈表或順序掃描，一步到位！🚀
空間換時間：通過特定算法將鍵值轉換為地址，實現 O(1) 訪問（理想情況下）。

2、哈希文件

🎯 核心概念 ：鍵值→地址的間接映射：哈希文件是直接文件的經典實現，利用 哈希函數（Hash Function） 快速定位記錄。但與純直接文件不同，它采用 「間接尋址」：🔹 關鍵字（Key） → Hash值 → 目錄表指針 → 物理塊地址

🔍 哈希文件流程詳解

1?? Hash函數（H）: 作為標準函數存于系統中，供存取文件時調用。

輸入：記錄的關鍵字 K
輸出：目錄表索引 A = H(K)
🌰 示例：H("ID101") = 5 → 指向目錄表的第5項

2?? 目錄表（指針表）：每個表項存儲 物理塊指針（如磁盤塊地址）

3?? 物理存儲塊：實際存放記錄的數據塊

7.3 文件目錄

文件目錄是文件系統的“導航地圖🗺?”，目錄管理的核心要求如下：

1?? 按名存取（Name-Based Access）

用戶視角：只需輸入 文件名（如 report.docx），系統自動找到文件位置。
底層實現：目錄中記錄 文件名 → 物理地址 的映射。

2?? 提高檢索速度（Fast Lookup）

優化手段：
- 哈希目錄：用哈希表加速文件名查找。
- 樹形結構：層級目錄減少單層文件數。
關鍵目標：減少磁盤I/O，尤其在大中型文件系統中！

3?? 文件共享（File Sharing）

多用戶場景：多個用戶訪問同一文件。
實現方式：
- 硬鏈接：多個目錄項指向同一文件。
- 符號鏈接：快捷方式（記錄目標文件路徑）。
優勢：節省存儲空間 + 保證數據一致性！ 💾

4?? 允許重名（Name Reuse）

用戶自由：不同用戶可對不同文件使用相同名字。
實現原理：
- 目錄隔離：用戶私有目錄（如 /home/user1/ vs /home/user2/）。
- 命名空間：通過路徑全稱區分（如 /home/user1/notes.txt ≠ /home/user2/notes.txt）。

7.3.1 文件控制塊和索引結點

文件控制塊（File Control Block, FCB） 是操作系統中用于 描述和控制文件 的數據結構，文件與文件控制塊一一對應。

文件目錄：文件控制塊的有序集合，即 一個文件控制塊就是一個文件目錄項。

目錄文件：一個文件目錄也被看做是一個文件

1、文件控制塊 FCB(File Control Block)

在文件控制塊中，通常應含有三類信息，即基本信息、存取控制信息及使用信息。

基本信息類
- 文件名，指用于標識一個文件的符號名，在每個系統中，每一個文件都必須有唯一的名字，用戶利用該名字進行存取。
- 文件物理位置，指 文件在外存上的存儲位置，它包括:
  - 存放文件的設備名
  - 文件在外存上的起始盤塊號
  - 指示文件所占用的盤塊數，或字節數的文件長度。
- 文件邏輯結構，指示 文件是流式文件還是記錄式文件、記錄數，文件是定長記錄還是變長記錄 等。
- 文件的物理結構，指示 文件是順序文件，還是鏈接式文件或索引文件。
存取控制信息類
- 文件主的存取權限
- 核準用戶的存取權限
- 一般用戶的存取權限
使用信息類
- 文件的建立日期和時間
- 文件上一次修改的日期和時間
- 當前使用信息。
  - 當前已打開該文件的進程數
  - 是否被其它進程鎖住
  - 文件在內存中是否已被修改但尚未拷貝到盤上等。

2、索引結點

1?? 問題背景：傳統目錄檢索的瓶頸

🔍 傳統FCB目錄結構（如FAT）：

每個FCB完整存儲（文件名+文件描述信息），占用空間大。
例：FCB=64B，盤塊=1KB → 每塊僅存16個FCB。
檢索時需逐塊調入內存，依次比對文件名。?存在性能問題：若目錄占用N個盤塊，平均需 (N+1)/2次磁盤I/O。
例：640個FCB → 40塊 → 平均20次磁盤訪問！🐢

2?? 優化方案：UNIX的i-node設計

核心思想：分離文件名與文件元數據，減少目錄檢索時的磁盤I/O！

📂 i-node（索引結點）結構

組成部分 作用 節省點
文件名 文件標識（短字符串）僅存14B（UNIX為例）
i-node指針 指向文件元數據（物理地址/權限等） 2B指針 → 取代完整FCB！?
文件元數據 存儲在獨立的i-node中（磁盤另存） 檢索時不加載，按需讀取

組成部分	作用	節省點
`文件名`	文件標識（短字符串）	僅存14B（UNIX為例）
`i-node指針`	`指向文件元數據`（物理地址/權限等）	2B指針 → 取代完整FCB！?
`文件元數據`	存儲在獨立的i-node中（磁盤另存）	檢索時不加載，按需讀取

3?? 磁盤索引結點

存放在磁盤上的索引結點。每個文件有唯一的一個磁盤索引結點

💾 磁盤i-node的七大核心字段

字段	作用	🌟 特別說明
`文件主標識符`	記錄文件所有者（用戶/組）	`ls -l`看到的`user:group`就是它！
`文件類型`	標明是普通文件、目錄、設備文件等	`-`普通文件，`d`目錄，`c`字符設備…
`文件存取權限`	控制用戶/組/其他用戶的讀（r）、寫（w）、執行（x）權限	`chmod 755`修改的就是它 🔒
`文件物理地址`	13個地址項（`iaddr(0)~iaddr(12)`）以直接或間接方式給出數據文件所在盤塊的編號	混合索引結構 → ?? 支持大文件+高效訪問
`文件長度`	文件實際大小（字節為單位）	`du`和`ls -l`顯示的數據源 📏
`文件連接計數`	硬鏈接數量（多少目錄項指向本i-node）	為0時文件真正刪除！ ??
`文件存取時間`	記錄最后訪問、修改、i-node變更時間	`touch`命令會更新這些時間 ?

4?? 內存索引結點

🏃 為什么需要內存i-node？

🐌 磁盤i-node存儲在硬盤，每次訪問都要讀盤 → 慢！
🚀 內存i-node加載到RAM，減少磁盤I/O → 快！

💡 核心思想：高頻訪問的元數據 緩存在內存，避免重復讀盤 ?

🔍 內存i-node五大新增字段

字段	用途	🌟 場景舉例
1. i-node編號	唯一標識內存中的i-node	內核通過編號快速查找緩存 🔎
2. 狀態標志	標記是否被鎖定（locked）或修改（dirty）	寫文件時加鎖，防止并發沖突 🚧
3. 訪問計數	記錄多少進程正在使用此i-node（Open計數）	計數=0時可安全釋放緩存 ??
4. 設備號	指向文件所屬的文件系統（如`/dev/sda1`）	跨設備文件操作時定位磁盤位置 💾
5. 鏈接指針	維護空閑鏈表和哈希隊列（加速i-node查找）	內核通過哈希表快速定位內存i-node ?

🧠 內存i-node vs. 磁盤i-node

特性	磁盤i-node	內存i-node（新增字段）
存儲位置	磁盤	內存（進程打開文件時加載）
核心作用	持久化存儲元數據	加速訪問 + 動態管理文件狀態
生命周期	文件存在即存在	文件打開時創建，關閉后可能釋放

在這里插入圖片描述

7.3.2 簡單的文件目錄

1、單級文件目錄

🧩 基本概念

單級文件目錄（Single-Level Directory） 是最簡單的文件目錄結構，整個系統只有一張目錄表，每個文件占一個目錄項，包含：

📝 文件名（如：report.txt）
🏷? 文件擴展名（如：.txt、.exe）
📏 文件長度（大小）
🏗? 文件類型（文本、二進制、目錄等）
🗺? 文件物理地址（存儲在磁盤的哪個位置）
🔒 其他屬性（如只讀、隱藏等）
? 狀態位（1=已占用，0=空閑）

📌 特點：

每個文件 唯一對應一個目錄項
文件名必須唯一（按名存取 - 不能有重名）
查找方式：線性掃描 全部目錄項

? 工作流程

創建文件（Create）📂
- 1?? 檢索全部目錄項 → 檢查文件名是否已存在（避免重名）
- 2?? 找空白目錄項（狀態位=0）
- 3?? 填入文件名、屬性，并置狀態位=1
刪除文件（Delete）🗑?
- 1?? 查找目標目錄項
- 2?? 釋放文件占用的存儲空間（如磁盤塊）
- 3?? 清空目錄項，狀態位=0

? 優點

簡單易實現 🛠?
滿足最基本功能：按名存取（open("a.txt") 能定位到文件）

? 缺點

查找速度慢 🐌：平均需掃描 N/2 個目錄項（N=文件總數）
不允許重名 🔥：在多用戶/多任務環境下難以避免沖突
無法共享文件 🤝：所有用戶必須用相同文件名訪問同一文件，不能個性化命名

🚀 適用場景

單用戶環境（如早期DOS系統） 🖥?
文件數量極少 📉

2、兩級文件目錄

🧩 基本概念

兩級文件目錄（Two-Level Directory） 是為了解決單級目錄的缺點而設計的。它在 主目錄（MFD）下為每個用戶單獨建立用戶文件目錄（UFD），形成兩級結構：

主文件目錄（MFD）：記錄所有用戶信息（用戶名 + 指向UFD的指針） 📁
用戶文件目錄（UFD）：用戶自己的文件列表（類似單級目錄，但只屬于該用戶） 🗂?

在這里插入圖片描述

? 核心思想：用戶隔離 → 每個用戶有自己的“私人文件夾”，互不干擾！

? 工作流程

創建文件（Create）📂
- 1?? 查MFD → 找到對應用戶的UFD指針
- 2?? 在UFD中檢查文件名是否沖突（只需檢查自己的文件，不用管其他用戶）
- 3?? 分配空白目錄項，填入文件信息，狀態位=1 ?
刪除文件（Delete）🗑?
- 1?? 查MFD → 定位到UFD
- 2?? 在UFD中找到目標文件，釋放存儲空間
- 3?? 清除目錄項，狀態位=0
訪問文件（Open）🔍
- 路徑形式：/用戶名/文件名

? 優點（對比單級目錄）

改進點	兩級目錄解決方案	實際效果
`查找速度快`	只需查 n（MFD） + m（UFD）次	從單級的 `N=n×m` → 降到 `n+m`
`允許用戶重名`	不同用戶的UFD可含同名文件（如 `A/test`和`B/test`）	用戶A和B的 `temp.txt` 共存！
`支持基礎共享`	可通過系統鏈接【讓不同用戶的不同文件名指向同一個物理文件】讓不同用戶訪問同一物理文件	用戶A的 `data.txt` → 用戶B的 `backup.txt`

? 缺點

用戶隔離太強 🚧：合作開發時，跨用戶訪問文件需手動配置權限或鏈接，不夠靈活。
共享仍有限 🔗：需顯式設置共享文件表或符號鏈接，天然不支持多級協作。

7.3.3 樹形結構目錄(Tree-Structured Directory)

1、樹形目錄

🧩 基本概念

樹形目錄（Tree-Structured Directory） 是現代OS最常用的文件組織方式，將文件系統組織為一棵倒置的樹：

根目錄（/） 🏠：最頂層的唯一目錄（如Linux的/、Windows的C:\）
節點（子目錄） 📂：樹的中間層（文件夾），可無限嵌套
葉節點（文件） 📄：樹的末端（實際數據文件）

在這里插入圖片描述

? 核心特性

單根唯一性 🎯
- 全系統 只有一個根目錄，所有文件和目錄都從根派生。
- 例如：Linux中絕對路徑/home/user/file.txt必須從/開始。
單父依賴 👨
- 每個文件/目錄 只能有一個父目錄，避免環路（類似單繼承）。
- 例外：通過鏈接（硬鏈/軟鏈）實現多路徑訪問。
混合存儲能力 🔄
- 目錄項可以是：
  - 子目錄的FCB（📂 如/home/user/Documents/）
  - 數據文件的FCB（📄 如/home/user/report.txt）
- 用 標志位 區分類型（如d代表目錄，-代表文件）。

/  (根目錄)  
├── home/  （用戶主目錄）  
│   ├── alice/  （子目錄）  
│   │   ├── Documents/  （子目錄）  
│   │   │   └── project.docx  （數據文件）  
│   │   └── notes.txt   （數據文件）  
│   └── bob/  （子目錄）  
│       └── Downloads/  （子目錄）  
└── etc/  （配置文件目錄）  └── passwd

2、路徑名和當前目錄

🚩 路徑名（Path Name）

在樹形目錄中，每個文件的絕對路徑是從根目錄（/）出發的唯一訪問路徑，所有目錄和文件名用 / 連接。

📌 當前目錄/工作目錄（Current Directory）
解決方案：為每個進程設置工作目錄（Working Directory），默認從此目錄出發解析路徑。

路徑類型	定義	示例（當前目錄=`/home/alice`）	特點
`絕對路徑` 🔵	從根目錄 `/` 開始的完整路徑	`/home/alice/Documents/notes.txt`	唯一但冗長
`相對路徑` 🟢	從當前目錄開始的縮寫路徑	`Documents/notes.txt` 或 `../bob/file`	簡潔需上下文

特殊符號：

. ：當前目錄（如 ./file = 當前目錄下的 file）
.. ：父目錄（如 ../file = 上級目錄中的 file）

?? 樹形目錄的優缺點

🌟 優勢：

清晰層次🗂?：不同用戶/項目分屬不同子樹（如 /home/user1/ vs /var/log/）。
權限隔離🔐：可為每層目錄設置不同訪問權限（如 chmod 750 /home/secret/）。

?? 缺點：

逐級訪問開銷?
- 查找 /a/b/c/file 需讀3次目錄（a→b→c），增加磁盤I/O。
- 解決方案：通過符號鏈接（ln -s）縮短訪問路徑。
相對路徑陷阱🌀：若當前目錄變化（如 cd ..），相同相對路徑可能指向不同文件！
樹形結構不便于實現文件的共享

系統	根目錄	用戶目錄范例	關鍵命令
Linux	`/`	`/home/username/`	`pwd`（顯示當前目錄）
Windows	`C:\`	`C:\Users\Username\`	`cd`（切換目錄）

3、目錄操作

📌 創建目錄

作用：在用戶目錄（UFD）或其子目錄中新建目錄或文件。
規則：
- 檢查當前目錄下是否有同名文件/目錄，避免沖突（? mkdir 或 touch 重名會報錯）。
- 示例：
```
mkdir new_folder       # 創建目錄
touch new_file.txt     # 創建文件
```

🗑? **刪除目錄 **

情況	處理方法	示例命令
空目錄	直接刪除（無風險?）	`rmdir empty_dir`
非空目錄	兩種方式： ① 遞歸刪除所有子文件和目錄（`rm -r`） ② 禁止刪除非空目錄，如要刪除必須采取遞歸調用方式來將其刪除（如早期 MS-DOS）	`rm -r non_empty_dir` (??`rm -rf /`危險！)

🔄 改變當前目錄

常用命令：

cd /home/user/Documents   # 絕對路徑切換
cd ../Downloads           # 相對路徑（返回上級再進入Downloads）
cd ~                      # 回到用戶主目錄（如 /home/username）

查看當前目錄：
```
pwd    # 輸出：/home/user/Documents
```

?? 移動目錄/文件

命令：

mv old_dir new_location/   # 移動目錄（路徑變化）
mv file.txt ../new_name.txt # 移動并重命名

風險：移動系統關鍵目錄（如 /usr/bin）可能破壞依賴關系💥！

🔗 鏈接操作（文件共享）

鏈接類型	特點	命令示例
硬鏈接	共享 i-node，刪除原文件不影響硬鏈接（?? 不可跨文件系統）	`ln source.txt hard_link`
軟鏈接	類似快捷方式，存儲目標路徑（? 可跨文件系統，原文件刪除后失效）	`ln -s source.txt soft_link`

🔍 查找文件

精確匹配（指定完整文件名）：

find /home -name "report.pdf"    # 在 /home 下搜索 report.pdf

模糊匹配（通配符 * 或 ?）：

find . -name "*.log"             # 當前目錄及其子目錄中所有 .log 文件

按類型查找（目錄/文件/鏈接）：

find /var -type d                # 查找 /var 下所有目錄

7.3.4 目錄查詢技術

當用戶請求訪問文件時（如cat report.txt），系統執行以下流程：

1?? 文件名解析
- 用戶提供文件名 → 系統在目錄結構中搜索該文件。
- 查找方式：
  - 絕對路徑：從根目錄 / 逐級匹配（如/home/user/report.txt）。
  - 相對路徑：基于當前目錄檢索（如./docs/report.txt）。
- 🚦 關鍵目標：找到文件的控制塊（FCB）或索引結點（i-node）。
2?? 獲取文件元數據
- 通過FCB/i-node獲取文件關鍵信息：📏 大小 | 🔒 權限 | 📅 時間戳 | 🧩 物理地址（磁盤塊號）
3?? 定位磁盤數據
- 系統根據 FCB/i-node 中的物理地址，計算出文件在磁盤上的具體位置（柱面/扇區）。
4?? 讀取文件到內存
- 磁盤驅動程序執行 I/O 操作：
  - 🚀 尋道：磁頭移動到目標位置（機械硬盤有延遲）。
  - ? 傳輸：數據從磁盤讀入內存緩沖區。
- 用戶態交付：最終將文件內容返回給用戶程序（如 cat 顯示內容）。

1、線性檢索法

🔍 核心概念

線性檢索法（順序檢索法）是最基礎的目錄搜索策略，通過逐級比較文件名在目錄中查找目標文件，適用于單級目錄和樹形目錄結構。

單級目錄檢索（簡單但低效）

📌 流程：

輸入：用戶提供文件名（如 report.txt）。
檢索：系統依次遍歷目錄項，逐一比對文件名。
結果：
- ? 找到 → 返回文件控制塊（FCB）或 i-node。
- ? 未找到 → 報錯“文件不存在”。

📌 缺點：效率低：目錄項多時耗時（O(n) 時間復雜度）。

🌳 樹形目錄檢索（多級路徑解析）

📌 示例路徑：/usr/ast/mbox

1?? 解析根目錄 /
- 讀入分量名 usr → 與根目錄項順序比較。
- 匹配結果：找到 usr 目錄項 → 獲取其 i-node 號（如 6）。
- 定位數據：根據 i-node 6 讀取 usr 目錄的物理盤塊（如 132號）。
2?? 解析第二級 /usr/ast
- 讀入分量名 ast → 與 132 號盤塊中的目錄項順序比較。
- 匹配結果：找到 ast → 獲取其 i-node 號（如 26）。
- 定位數據：根據 i-node 26 讀取 /usr/ast 的盤塊（如 496號）。
3?? 解析最終文件 /usr/ast/mbox
- 讀入分量名 mbox → 與 496 號盤塊中的目錄項順序比較。
- 匹配結果：找到 mbox → 獲取其 i-node 號（如 60）。
- 成功：i-node 60 中存儲了文件物理地址，檢索完成！

?? 中斷條件：
任意一級匹配失敗（如 ast 不存在） → 立即終止并返回 “文件未找到”。

在這里插入圖片描述

2、Hash 方法

🔍 核心思想

Hash 方法通過 文件名 → Hash值 → 快速定位目錄項，顯著提升檢索效率（理想情況下O(1)），適用于大目錄場景。但需處理Hash沖突和通配符兼容性問題。

Hash 檢索流程

📌 無沖突場景（理想情況）

輸入文件名：如 report.txt。
計算Hash值：通過Hash函數（如MD5、CRC32）轉換為索引值。
```
hash("report.txt") % 100 → 索引值=42
```
定位目錄項：直接訪問目錄表的第42項。
- ? 匹配成功 → 獲取文件物理地址。
- ? 目錄項為空 → 文件不存在。

? 優勢：只需一次計算和訪問，速度極快！

📌 沖突處理（關鍵難點）

當不同文件名計算出相同Hash值時，系統按以下規則解決：

檢查目錄項：若已存文件名 ≠ 目標名 → 發生沖突！
重新Hash：
- 新索引 = (原Hash值 + 常數) % 目錄長度（該 常數應與目錄的長度值互質）。
- 重復步驟1，直到找到匹配或空項。

🌰 舉例：report.txt和 data.log的Hash值均為42：

第一輪查42 → 存的是 data.log（不匹配）。
第二輪查 (42+1)%100=43 → 找到 report.txt（成功）！

限制與兼容性

場景	處理方法	原因
文件名含通配符（如`*.txt`）	退化為線性檢索 🔄	Hash無法處理模糊匹配
目錄動態擴容	需Rehash所有文件 🚧	Hash值依賴目錄長度

?? 注意：Hash函數選擇：應盡量均勻分布（如SHA-1），減少沖突概率。

性能對比

方法	時間復雜度	適用場景
線性檢索	O(n)	小目錄/含通配符
Hash檢索	O(1)*	大目錄/精確文件名匹配

*注：O(1)為平均情況，沖突頻繁時可能退化。

7.4 文件共享

7.4.1 基于有向無循環圖實現文件共享

1、有向無循環圖 DAG(Directed Acyclic Graph)

🔍 核心概念

有向無環圖（DAG） 是一種允許文件/子目錄被多個父目錄引用的目錄結構。

問題背景：樹形目錄中，文件共享必須通過屬主目錄（非對稱共享?）。
DAG解決方案：文件可被多個目錄直接鏈接

📌 如何建立共享鏈接？

硬鏈接（物理地址拷貝）
- 操作：將文件的物理盤塊號復制到父目錄項中。
- 風險：
  - 若某個用戶對文件 追加內容僅對操作者可見，其他用戶無法共享更新部分！
  - 數據不一致：多個父目錄可能指向不同版本的文件內容。
- 適用場景：適合 只讀文件
💣 致命缺陷：硬鏈接破壞了共享文件的統一性！
符號鏈接（軟鏈接）
- 操作：父目錄中存儲文件的路徑名而非物理地址。
- 優勢：所有父目錄訪問同一文件，追加內容對所有用戶可見。
- 代價：需要額外解析路徑，性能略低。
- 適用場景：適合 協作文件

2、利用索引結點 - 硬鏈接

📂 傳統目錄 vs 索引結點方案

	傳統目錄	索引結點
存儲內容	直接把文件地址、屬性存目錄里🗂?	目錄只存文件名+i-node指針👉📍
共享問題	硬鏈接導致更新不同步🔀	所有人通過i-node訪問同一文件🔗

🔑 核心結構

count計數器：記錄有多少目錄指向該文件

如何解決共享問題

多用戶的文件目錄中都設置有指向共享文件的索引結點指針。此時，由任何用戶對共享文件所進行的操作，都將引起其相應結點內容的改變
刪除文件：通過count確保安全刪除🔒，如何系統收費始終由創建者（count=1時）負責💰。【count=2時，創建者不能刪除該文件，因為若刪除了該文件，也必然刪除了該文件的索引結點，這樣便會使另一個使用者的指針懸空】

在這里插入圖片描述

7.4.2 利用符號鏈接實現文件共享

1、利用符號鏈接(Symbolic Linking)的基本思想

符號鏈接允許 一個文件有多個“父目錄”，但 只有一個主父目錄，其他都是快捷方式

符號鏈接 = 創建“文件快捷方式”📎，存儲目標文件路徑，訪問時自動跳轉！

傳統樹結構	符號鏈接結構
父目錄類型	所有連接都是實線（真實父目錄） 🏗?	1個實線（主父目錄）+ N個虛線（符號鏈接） 🪢

在這里插入圖片描述

2、如何利用符號鏈實現共享

📂 示例：讓 D5 共享 D6 的文件 F8（實現符號鏈接）

創建符號鏈接文件 💻
- 系統在目錄 D5 下創建 LINK 類型 文件，名稱與原文件相同（F8）。
- 該文件**內容僅為真實文件路徑**（如 /D6/F8）。
```
# Linux命令行示例：ln -s
ln -s /D6/F8 D5/F8  # 創建符號鏈接
```
文件結構變化 📝

目錄/文件 類型 存儲內容
/D6/F8 真實文件文件數據🔢
/D5/F8 符號鏈接路徑 /D6/F8🛣?
用戶訪問流程 🔄
- 用戶 B 打開 /D5/F8 → 系統發現是符號鏈接（不是真實文件）。
- 操作系統自動解析路徑 /D6/F8，并訪問真實文件。
- 最終讀寫操作 作用在 /D6/F8 上，實現共享！

目錄/文件	類型	存儲內容
`/D6/F8`	真實文件	文件數據🔢
`/D5/F8`	符號鏈接	路徑 `/D6/F8`🛣?

即使軟鏈接指向的共享文件已被刪除，Link型文件依然存在，只是通過 Link 型文件中的路徑去查找共享文件會失敗(找不到對應目錄項)

3、利用符號鏈實現共享的優點

1?? 文件主（Owner）絕對掌控 👑

索引結點（i-node）指針 僅有**文件主**持有，而 共享用戶只能通過路徑訪問 📌。
文件主刪除文件后🗑?：【無耦合，安全刪除 🔒】
- 其他用戶的符號鏈接自動失效 ?（不會出現“懸空指針”問題）。
- 系統檢測到文件不存在，自動刪除無效符號鏈，避免累積垃圾。

2?? 支持跨系統/網絡共享 🌐

符號鏈可指向任何有效路徑，包括：
- 同一磁盤不同目錄 📂
- 不同磁盤/分區 💾
- 網絡文件（如 Web 鏈接🌍）

3?? 靈活權限管理 🛡?

用戶只需 路徑訪問權限，無需持有原文件的 i-node。
適合多用戶環境 👥（如服務器共享文件）。

4、利用符號鏈的共享方式存在的問題

性能略低🐢：每次訪問需 解析路徑（比硬鏈接多一次 I/O）。
死鏈（Dangling Link）：若原文件被刪，需手動或定期清理無效符號鏈（可用 find -xtype l 查找）。
存儲開銷💾：每個符號鏈占用 1 i-node + 少量空間（存路徑字符串）。

7.5 文件保護

威脅類型	典型案例	防護措施	具體實現技術/工具
1. 人為因素 👤	- 誤刪文件 - 惡意篡改 - 越權訪問	存取控制機制 🚪	- 權限分檔（`rwx`） - ACL訪問控制列表 - 多因素認證
2. 系統因素 💻	- 磁盤故障 - 系統崩潰 - 軟件漏洞	系統容錯技術 ??	- RAID磁盤陣列 - 事務日志（Journaling） - 熱備組件
3. 自然因素 🌌	- 磁盤老化 - 磁場干擾 - 物理損壞	后備系統 🗄?	- 定期備份（全量/增量） - 異地容災 - 數據校驗

口令保護

口令一般存放在文件對應的 FCB 或索引結點中。
用戶訪問文件前需要先輸入“口令”，操作系統會將用戶提供的口令與FCB中存儲的口令進行對比，如果正確，則允許該用戶訪問文件。
優點: 保存口令的空間開銷不多，驗證口令的時間開銷也很小。
缺點: 正確的“口令”存放在系統內部，不夠安全。

密碼保護

使用某個“密碼”對文件進行加密，在訪問文件時需要提供正確的“密碼”才能對文件進行正確的解密。
優點: 保密性強，不需要在系統中存儲“密碼”
缺點: 編碼/譯碼，或者說加密/解密要花費一定時間

7.5.1 保護域(Protection Domain)

1、訪問權

1?? 基本概念

定義：進程對某個對象（Object） 執行特定操作的權限。【由**系統控制**進程對對象的訪問】
對象類型：
- 硬件對象 💻：磁盤、打印機、內存等。
- 軟件對象 📂：文件、程序、數據庫等。
權限示例：文件 → 讀（R）、寫（W）、執行（X）。

2?? 訪問權的表示方法

🧮 例子：進程對文件 report.txt 有 讀寫權限 → (report.txt, {R, W}) 📄??

2、保護域

1?? 基本概念

定義：保護域（Domain）是 進程對一組對象訪問權的集合，規定了進程能訪問的對象和操作范圍。
核心規則：🔐 進程只能在指定的域內操作，不能跨域越權！

2?? 保護域的特性

特性	說明	例子 🖼?
對象集合 📦	一個域包含一組可訪問的對象（文件、打印機等）。	域1：文件F、打印機PR1
權限綁定 🔗	每個對象在域中有明確的權限（如讀、寫、執行）。	域1中：文件F₁可讀，文件F₂可讀寫
跨域共享 🤝	同一對象可出現在多個域中（權限可能不同）。	打印機PR1同時屬于域2和域3

3?? 保護域的作用

最小權限原則 🎯：限制進程僅擁有必要權限，避免過度授權。
隔離性 🧊：防止錯誤/惡意進程破壞其他域的資源。
靈活共享 ??：通過跨域分配對象，實現安全共享。

3、進程和域間的靜態聯系

靜態域：進程 整個生命周期僅綁定一個固定保護域，權限 無法動態調整。
問題：🚨 權限過度分配！進程可能獲得實際不需要的訪問權（如同時擁有磁帶機和打印機權限）。
特性：
- 權限固定：進程啟動時就擁有域內所有對象的權限，無法中途釋放/變更。
- 資源浪費：域需包含進程全程可能用到的所有對象（即使某階段不需要, 存在閑置權限）。

4、進程和域間的動態聯系方式

動態域：進程在不同的 運行階段 可以關聯 不同的保護域（一對多聯系）。
核心優勢：🎯 按需分配權限！進程只在當前階段擁有必要的最小權限。
特性：
- 階段化權限：進程生命周期被劃分為多個階段，每個階段綁定一個域。
- 最小權限：域僅包含當前階段所需的對象。

7.5.2 訪問矩陣

1、基本的訪問矩陣

🔹 基本概念

訪問矩陣（Access Matrix） 是表示 保護域（Domain） 和 對象（Object） 之間權限關系的數據結構。
行（Row） = 域（Domain）：代表進程執行的權限環境（如 D?, D?）。
列（Column） = 對象（Object）：代表系統中的資源（如文件 F?、打印機 Printer 1）。
矩陣項（Cell） = 訪問權（Access Rights）：access(i, j) 表示域 D? 對對象 O? 的操作權限（如 R-讀，W-寫，E-執行）。

訪問矩陣示例

域\對象	F?	F?	F?	F?	F?	F?	Printer 1	Plotter 2
D?	R	R, W
D?			R	R,W,E	R, W		W
D?						R,W,E	W	W

是由 三個域 和 8個對象 所組成的:

進程在域D₁中運行時，它能讀文件F₁、讀和寫文件F₂。
進程在域D₂中運行時，它能讀文件 F₃、F₄和F₅，以及寫文件F₄、F₅和執行文件F₄，此外還可以使用打印機 1。
進程在域D₃中運行時，才可使用繪圖儀 2。

2、具有域切換權的訪問矩陣

Switch 權限（S）：在訪問矩陣中新增一項，表示域間的切換權。

僅當 switch_access(i, j) = S 時，進程才能從 域 D? 切換到 D?。
切換權**由系統或管理員授予**，避免進程隨意越權。

具有域切換權的訪問矩陣示例

域\對象	F?	F?	F?	F?	F?	F?	Printer 1	Plotter 2	域 D₂	域 D₃
D?	R	R, W							S
D?			R	R,W,E	R, W		W			S
D?						R,W,E	W	W

允許在域D₁中的進程切換到域D₂中；允許在域D₂中的進程切換到域D₃中。

7.5.3 訪問矩陣的修改

1、拷貝權(Copy Right)

拷貝權（Copy Right） 是一種 動態權限擴展機制，允許進程將 某個域中對某對象的訪問權復制到其他域 中，但會對權限的傳播進行限制，以防止無限擴散風險。

關鍵點：

拷貝標記（*）：在訪問權（如 R*、W*）中，* 表示該權限可被拷貝至其他域。
限制拷貝：拷貝后生成的權限不帶 *（如 R* → R），阻止進一步擴散。
目的：實現權限的 可控共享，避免權限濫用。

域\對象 F? F? F?
D? E W^*
D? E R^* E
D? E
運行在D₂域中的進程可以將其對文件F₂的讀訪問權擴展到域 D₃中去，使在域D₃中運行的進程也具有對文件F₂的讀訪問權。

運行在域D₁中的進程可以將其對文件F₃的寫訪問權擴展到域 D₃中去，使在域D₃中運行的進程也具有對文件F₃的寫訪問權。

域\對象 F? F? F?
D? E W^*
D? E R^* E
D? E R W

域\對象	F?	F?	F?
D?	E		W^*
D?	E	R^*	E
D?	E

域\對象	F?	F?	F?
D?	E		W^*
D?	E	R^*	E
D?	E	R	W

2、所有權(Owner Right)

所有權（Owner Right） 賦予進程對某對象 完整的控制權，包括：

增刪權限：可以修改其他域對該對象的訪問權。
動態權限管理：無需管理員介入，擁有者可自主調整權限。

所有權用 O 標記在訪問矩陣中（如 access(i,j) = O），表示域 D? 對對象 F? 擁有所有權。

域\對象 F? F? F?
D? O,E W
D? R^*,O R^*,O,W
D? E
在域 D₁中運行的進程(用戶)是文件F₁的所有者，它能增加或刪除在其它域中的運行進程對文件F₁的訪問權。

如下表：在域 D₁中運行的進程刪除了在域D₃中運行的進程對文件F₁的執行權;

在域 D₂中運行的進程(用戶)是文件F₂和文件F₃的擁有者, 該進程可以增加或刪除在其它域中運行的進程對這兩個文件的訪問權。

如下表：在域 D₂中運行的進程增加了在域D₃中運行的進程對文件F₂和F₃的寫訪問權。

域\對象 F? F? F?
D? O,E
D? R^*,O R^*,O,W
D? W W

域\對象	F?	F?	F?
D?	O,E		W
D?		R^*,O	R^*,O,W
D?	E

域\對象	F?	F?	F?
D?	O,E
D?		R^*,O	R^*,O,W
D?		W	W

3、控制權(Control Right)

拷貝權和所有權都是用于改變矩陣內同一列的各項訪問權的，或者說，是用于改變在不同域中運行的進程對同一對象的訪問權的。

控制權（Control Right） 可用于改變矩陣內同一行中(域中)的各項訪問權，亦即，用于改變在某個域中運行的進程對不同對象或域的訪問權的。

權限標記：access(i,j) = Control，表示域 D? 可以控制域 D? 的權限。

域\對象	F?	F?	F?	F?	F?	F?	Printer 1	Plotter 2	域 D₃
D?	R	R, W
D?			R	R,W,E	R, W		W		Control
D?						R,W,E	W	W

在 access(D?,D₃)中包括了控制權，則一個在域 D₂中運行的進程能夠改變對域D₃內各項的訪問權。

7.5.4 訪問矩陣的實現

1、訪問控制表(Access Control List)

ACL：對 訪問矩陣按列(對象)劃分，為 每一列建立一張訪問控制表 ACL。在該表中，已把矩陣中屬于該列的 所有空項刪除，此時的訪問控制表是由一 有序對(域，權集)所組成的。

ACL(F?) = {    (D?, {R, W}),    (D?, {R}),     (D?, {W}) }

域的兩種實現方式

域類型	說明	示例場景
`用戶`作為域	每個用戶是一個域，權限綁定用戶身份	用戶A可讀文件F，用戶B可寫文件F。
`進程`作為域	每個進程是一個域，權限綁定進程身份	進程P?可執行程序，進程P?不可。

ACL的存儲與查詢

存儲位置

文件系統：ACL 常存放在文件的控制塊（FCB）或 i-node中。
數據庫：作為對象的元數據。

權限查詢流程

缺省 ACL（Default ACL） 是一種 預先定義的權限模板，用于在新建子對象（文件/目錄）時自動繼承權限。

核心功能：當在目錄下創建新文件或子目錄時，系統會 自動將缺省 ACL 的權限賦予新對象，無需手動設置。

2、訪問權限(Capabilities)表

訪問權限表：訪問矩陣按行(即域)劃分，便可由 每一行構成一張訪問權限表。換言之，這是由一個域對每一個對象可以執行的一組操作所構成的表。表中的每一項即為該域對某對象的訪問權限。

當域為用戶(進程)、對象為文件時，訪問權限表便可用來描述一個用戶(進程) 對每一個文件所能執行的一組操作。

訪問權限表的組成（三字段）

字段	說明
類型	對象類型（如文件、打印機、目錄）。
權力	域對該對象的操作權限（如 `讀`、`寫`、`執行`）。
對象	指向對象的指針（如 UNIX 的 i-node 編號）。

🛡? 安全性實現

禁止用戶直接訪問權限表
- 權限表存儲在內核或受保護的 系統專用區，用戶進程無法直接修改。
- 只有通過 合法性檢查的系統調用 才能查詢或更新權限。
動態權限綁定流程

🚀 對比ACL與權限表（Capabilities）

特性	訪問控制表（ACL）	訪問權限表（Capabilities）
視角	對象為中心（文件→用戶權限）	域為中心（進程→可訪問對象）
查詢效率	對象被訪問時需遍歷ACL	進程直接持有權限表，無需重復檢查

7.6 文件存儲空間管理 - 空閑磁盤塊管理

7.6.1 存儲空間的劃分與初始化

在這里插入圖片描述

7.6.2 存儲空間管理

空閑表法

在這里插入圖片描述

空閑鏈表法

在這里插入圖片描述

位示圖法

在這里插入圖片描述

成組鏈接法

空閑表法、空閑鏈表法不適用于大型文件系統，因為空閑表或空閑鏈表可能過大。UNIX系統中采用了成組鏈接法對磁盤空閑塊進行管理。

基本原理

空閑塊根據大小劃分成若干個組。【UNIX默認采用每組100個空閑塊的配置】
每個組的空閑塊通過鏈表進行連接，鏈表中的每個節點表示一個空閑塊。
當系統需要分配存儲空間時，首先根據請求的大小選擇合適的鏈表，然后從鏈表中分配空閑塊。
當塊被釋放時，它會被返回到相應大小的鏈表中。

組的劃分：通常，有幾種不同的劃分策略：

按固定大小劃分：每個組管理固定大小的塊。例如，組1管理1KB的塊，組2管理2KB的塊，組3管理4KB的塊，以此類推。
按塊大小范圍劃分：根據一定的大小范圍進行劃分，每個組管理一個大小范圍內的塊。例如，組1管理1KB到2KB的塊，組2管理2KB到4KB的塊等。
按指數劃分：將空閑塊的大小按照指數級別劃分，比如2的倍數的塊（2KB, 4KB, 8KB等）

在這里插入圖片描述

7.7 虛擬文件系統和文件系統掛載

普通文件系統 vs 虛擬文件系統

在這里插入圖片描述

文件系統掛載

文件系統掛載(mounting)，即文件系統安裝/裝載–如何將一個文件系統掛載到操作系統中?

① 在VFS中注冊新掛載的文件系統。內存中的掛載表(mount table)包含每個文件系統的相關信息，包括文件系統類型、容量大小等。
② 新掛載的文件系統，要向VFS提供一個函數地址列表
③ 將新文件系統加到掛載點(mountpoint)，也就是將新文件系統掛載在某個父目錄下【windows 和C、D盤平級；Mac 在根目錄下的Volumes文件夾下】

參考：

教材：

計算機操作系統（第四版） (湯小丹) (Z-Library).pdf

操作系統 (羅宇（清華大學出版社 2023年）) (Z-Library).pdf

視頻：

王道計算機考研操作系統

【天勤考研】成組鏈接法