簡介

操作系統的文件管理負責都計算機中的數據(文件和目錄)進行組織，存儲，檢索，保護，共享。
其核心目標為：

1. 高效存儲
   減少I/O開銷，提升讀寫速度
2. 數據完整
   確保文件不被非法破壞
3. 用戶透明
   隱藏底層細節，比如磁盤的物理指針，提供統一的API。
4. 多用戶支持
   支持并發訪問，權限控制和資源共享。

文件的邏輯結構

所謂文件邏輯結構，就是對用戶或者GUI而言，文件內部的數據是如何呈現的。

1. 無結構文件
   文件內部數據就是一系列二進制流或字符流組成。比如txt文件，只是簡單的文字表達，并無特殊結構。

int main()
{
    FILE *fp=fopen("test.txt","r");
    if(fp==NULL){
        printf("文件打開報錯");
        return 0;
    }
    fseek(fp,10,SEEK_SET);//移動指針到制定位置
    char c=fgetc(fp);//從指定位置讀取信息，底層使用read系統調用，實現了邏輯塊號到物理塊號的轉換
    printf("value=%c",c);
    fclose(fp);
    return 0;
}

2. 有結構文件
   有一組組相似結構的數據組成，比如excel的統計表，比如數據庫
   根據每一組數據的長度不等，又分為定長記錄和不定長記錄

從其特性出發，定長記錄=數組，可以實現隨機訪問，偏移量 = i × 記錄長度
不定長記錄=鏈表，無法隨機訪問。

文件目錄，從文件名到 inode 的映射

目錄本身就是一種有結構的文件，由一條一條記錄組成。這個記錄叫做File Control Block,FCB。
FCB中包含了文件的基本信息，權限信息，使用信息等。

眼見為實

單級文件目錄

早期操作系統不支持多級目錄，整個系統只建立一張目錄表，每個文件占一個目錄項。
因為這個特性，文件是不允許重名的。

二級文件目錄

為了解決文件不允許重名的問題，又優化出了二級文件目錄。
分為主文件目錄(Master File directory,MFD)和(User File Directory)

兩級目錄允許不同用戶的文件重名，但依舊缺乏靈活性。因為不能對自己的文件進行分類

多級目錄結構

為了解決多用戶，文件分類的問題。又優化出多級目錄結構。
系統根據文件路徑一級一級的向下查找，先從root開始，再找到照片目錄，再找到2025/4/15目錄。這個過程需要3次I/O操作。比較低效，因此可以設置一個"當前目錄"，來減少I/O操作。

這就是絕對路徑與相對路徑的由來，與產生原因。，可以理解為一個鏈表，如果持有了上一個節點，就能很快找到當前節點，否則就要從表頭開始遍歷。

到目前為止，樹形目錄結構可以很方便的對文件分配，也支持多用戶，結構也很清晰。但依舊存在一個缺點，樹形結構不便于實現文件共享。

眼見為實

linux下，絕對路徑與相對路徑:

無環圖目錄結構

為了解決文件共享的問題，又衍生出了無環圖目錄結構。本質上是一個單向但不形成環的圖。

眼見為實

關于圖的數據結構，可以參考https://www.cnblogs.com/lmy5215006/p/18757481

用索引節點強化無環圖目錄結構

在FCB的結構中，往往包含了大量信息。但在查找各級目錄的過程中，只需要用到"文件名"來做匹配。
因此，可以考慮讓目錄表"瘦身"來提高效率。

加入一個FCB占用64B，一個磁盤block是1kb，那么就只能放16個FCB，。如果一個目錄下有640個FCB，那么就占用40個磁盤block ，時間復雜度為O(n/2) 也就是I/O平均下來要20次讀寫。
而使用索引節點，文件名占14B，節點指針占2B，那每個磁盤block就可存儲1024/(14+2)=64，640個FCB，只占用10個磁盤block，I/O讀寫降低為5.

眼見為實

文件的物理結構

文件的物理結構，指的是在系統看來，文件的數據是如何存儲在外存當中的。

外存管理與內存管理師出同門，與內存分頁類似，磁盤的存儲單元也會被分為一個個的block。

在很多操作系統中，磁盤塊與內存頁框保持大小一致，目的是為了數據交換時，因為大小，所以只需要一次I/O操作

文件分配方式

萬物皆套路，本身上與內存分配方式思想并無區別。故只簡單描述

1. 連續分配(Contiguous Allocation)
   原理：將文件在磁盤上分配為一組連續的物理塊，文件的邏輯塊號(Logical Block Number,LBN)，對應磁盤上連續的物理塊號(Physical Block Number,PBN)。
   優點：訪問速度快，支持隨機訪問。比如PBN=起始塊號+LBN
   缺點：磁盤碎片，動態擴容復雜。

數組的優/缺點就是它的優/缺點。
早期文件系統或對訪問速度要求高且文件大小固定的場景（如可執行文件）

2. 隱式鏈接分配（Linked Allocation）
   將文件分散存儲在非連續的物理塊中，通過指針（鏈接）記錄塊間順序。
   原理：為每個文件記錄起始塊號與結束塊號，并在每個數據塊末尾記錄下一個塊的指針。熟悉鏈表的朋友不會陌生，它就是一個擁有頭/尾節點的單鏈表
   優點：無外部碎片，動態擴展容易
   缺點：無法隨機訪問，只能順序訪問。效率低O(n)

鏈表的優/缺點就是它的優/缺點
早期 Unix 文件系統（如 UFS）的非索引節點分配方式

3. 顯式鏈接（Explicit Linking）
   原理：將所以塊的鏈接指針集中存儲在一張文件分配表中(File Allocation Tab,FAT)中，磁盤的每個塊對應一個item，并記錄它的下一個塊號。
   優點：通過 FAT 表直接查找塊號，無需遍歷。可以常駐內存提交搜索效率，不再需要I/O操作。
   缺點：FAT表占用空間，有兼容性問題(FAT16,FAT32)
   

Windows 的 FAT 文件系統、早期數碼相機存儲卡。

4. 索引分配（Indexed Allocation）
   原理：索引塊是一個物理塊，其中每個表項對應一個數據塊的物理地址。文件的邏輯塊號對應索引塊中的表項索引。
   優點：直接通過索引查找，時間復雜度O(1)，無碎片，新增數據庫不需要移動數據。
   缺點：維護索引塊本身就有開銷
   

當文件過大時，單級索引塊可能不足。又衍生出了多級索引，混合索引。比如linux的inode結構

邏輯結構vs物理結構

Linux 的 ext4 文件系統使用索引分配（inode 記錄直接 / 間接塊）
Windows 的 NTFS 使用混合索引（MFT 表記錄文件屬性和索引）
FAT 文件系統使用顯式鏈接分配（FAT 表記錄塊鏈接）

磁盤基本劃分

目錄區包含文件目錄，空閑表，位示圖，超級塊等用于文件管理的信息

空閑存儲空間管理

操作系統需要跟蹤磁盤上的可用空間，確保高效分配和回收操作系統需要跟蹤磁盤上的可用空間，確保高效分配和回收。常用方法如下：

1. 空閑表法
   與內存分配的動態分配算法如出一轍，因此不再贅述。
   反正來來去去就是首次適應，最佳適應等策略，回收時注意合并壓縮。

2. 空閑鏈表法
   原理：將所有空閑塊通過指針或索引鏈接成一個鏈表，記錄起始塊和塊數。
   優點：實現簡單，適合動態分配。
   缺點：鏈表操作（遍歷、拆分、合并）效率低，不適合大規模存儲。

鏈表結構為0=>4=5=>6=>7=>......=>12=>14=>17=>......

3. 位圖法（Bit Map）
   原理：用一個二進制位（Bit）對應磁盤上的一個物理塊，0表示空閑，1表示已占用。
   優點：空間占用小，查詢和分配速度塊(位運算)，適合大容量，比如ext4文件系統。
   缺點：分配連續空間時需掃描多個位，可能效率較低。
   

4. 成組鏈接法
   原理:將空閑塊分組，每組記錄下一組的快號，最后一組指向NULL或-1。
   優點：結合位圖和鏈表的優勢，兼顧空間效率和分配速度，常用于高效文件系統。
   缺點：實現復雜。

空閑法，空閑鏈表，位視圖法，成組鏈接法本質上是數據結構的翻來覆去。數組=>鏈表=>位圖=>混合使用。
注意一點，這一節講的是操作系統如何跟蹤磁盤可用空間(空閑管理)，上一節的物理結構分配是操作系統如何占用物理空間(分配策略)。兩者不要搞混了。

典型文件系統實現

1. Linux ext4
   采用成組鏈接法管理空閑塊，inode 索引分配（支持三級索引），位圖記錄塊狀態。
2. Windows NTFS
   使用 B + 樹管理元數據，主文件表（MFT）記錄文件屬性和索引，空閑空間通過位圖和鏈表結合管理。
3. FAT32
   顯式鏈接分配，通過 FAT 表記錄塊鏈接，適合簡單存儲設備（如 U 盤）。

文件的基本操作

1. 創建文件（created系統調用）
2. 刪除文件(delete系統調用)
   在windows系統中，我們刪除某個文件。會提示“暫時無法刪除文件”。就是因為計數器還未歸零
3. 讀文件(read系統調用)
   根據讀指針，讀入數據量，內存位置，講文件從外存寫入內存
4. 寫文件(write系統調用)
   根據寫指針，寫入數據量，內存位置，講文件從內存寫入外存
5. 打開文件(open系統調用)
   將FCB信息負責到系統的打開文件表中，再復制給需要打開的進程。
   進程的打開文件表特有的屬性：讀寫指針，訪問權限。
   系統的打開文件表特有的屬性：打開計數器
6. 關閉文件(close系統調用)
   將進程的打開文件表中刪除相應的表項
   回收分配給該文件的內存空間
   系統打開文件表，計數器-1。若count為0，則刪除相應表項。

系統索引號，也被稱為文件描述符(fd)

轉自https://www.cnblogs.com/lmy5215006/p/18824802
?