深度解析操作系統(tǒng)的文件管理

當前位置：點晴教程→知識管理交流 →『技術(shù)文檔交流』

freeflydom

2025年4月16日 15:19 本文熱度 295

簡介

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

高效存儲
減少I/O開銷，提升讀寫速度
數(shù)據(jù)完整
確保文件不被非法破壞
用戶透明
隱藏底層細節(jié)，比如磁盤的物理指針，提供統(tǒng)一的API。
多用戶支持
支持并發(fā)訪問，權(quán)限控制和資源共享。

文件的邏輯結(jié)構(gòu)

所謂文件邏輯結(jié)構(gòu)，就是對用戶或者GUI而言，文件內(nèi)部的數(shù)據(jù)是如何呈現(xiàn)的。

無結(jié)構(gòu)文件
文件內(nèi)部數(shù)據(jù)就是一系列二進制流或字符流組成。比如txt文件，只是簡單的文字表達，并無特殊結(jié)構(gòu)。

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

有結(jié)構(gòu)文件
有一組組相似結(jié)構(gòu)的數(shù)據(jù)組成，比如excel的統(tǒng)計表，比如數(shù)據(jù)庫
根據(jù)每一組數(shù)據(jù)的長度不等，又分為定長記錄和不定長記錄

從其特性出發(fā)，定長記錄=數(shù)組，可以實現(xiàn)隨機訪問，偏移量 = i × 記錄長度
不定長記錄=鏈表，無法隨機訪問。

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

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

眼見為實

單級文件目錄

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

二級文件目錄

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

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

多級目錄結(jié)構(gòu)

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

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

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

眼見為實

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

無環(huán)圖目錄結(jié)構(gòu)

為了解決文件共享的問題，又衍生出了無環(huán)圖目錄結(jié)構(gòu)。本質(zhì)上是一個單向但不形成環(huán)的圖。

眼見為實

關(guān)于圖的數(shù)據(jù)結(jié)構(gòu)，可以參考https://www.cnblogs.com/lmy5215006/p/18757481

用索引節(jié)點強化無環(huán)圖目錄結(jié)構(gòu)

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

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

眼見為實

文件的物理結(jié)構(gòu)

文件的物理結(jié)構(gòu)，指的是在系統(tǒng)看來，文件的數(shù)據(jù)是如何存儲在外存當中的。

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

在很多操作系統(tǒng)中，磁盤塊與內(nèi)存頁框保持大小一致，目的是為了數(shù)據(jù)交換時，因為大小，所以只需要一次I/O操作

文件分配方式

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

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

數(shù)組的優(yōu)/缺點就是它的優(yōu)/缺點。
早期文件系統(tǒng)或?qū)υL問速度要求高且文件大小固定的場景（如可執(zhí)行文件）

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

鏈表的優(yōu)/缺點就是它的優(yōu)/缺點
早期 Unix 文件系統(tǒng)（如 UFS）的非索引節(jié)點分配方式

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

Windows 的 FAT 文件系統(tǒng)、早期數(shù)碼相機存儲卡。

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

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

特性	連續(xù)分配	鏈接分配（隱式）	索引分配（單級）
空間連續(xù)性	連續(xù)	不連續(xù)	不連續(xù)
隨機訪問支持	高效（O(1)）	低效（O(n)）	高效（O(1)）
碎片問題	外部碎片嚴重	無外部碎片	無外部碎片
動態(tài)擴展能力	差（需整塊搬遷）	好（追加塊）	好（修改索引）
元數(shù)據(jù)開銷	低（僅起始塊+長度）	中（每個塊含指針）	高（索引塊）
典型應用	早期 FAT、固定文件	早期 Unix 非索引節(jié)點	Linux ext2/ext3、NTFS

邏輯結(jié)構(gòu)vs物理結(jié)構(gòu)

特征	邏輯結(jié)構(gòu)	物理結(jié)構(gòu)
視角	在用戶看來，占用連續(xù)的邏輯地址	在系統(tǒng)看來，系統(tǒng)決定連續(xù)結(jié)構(gòu) or 離散結(jié)構(gòu)
關(guān)注點	數(shù)據(jù)的排列，訪問方式	存儲設備的物理布局，塊分配策略
與存儲介質(zhì)	無關(guān)，它是抽象結(jié)構(gòu)	有關(guān)，它依賴磁盤扇區(qū)，塊大小
目標	方便用戶操作	高效利用I/O設備

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

磁盤基本劃分

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

空閑存儲空間管理

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

空閑表法
與內(nèi)存分配的動態(tài)分配算法如出一轍，因此不再贅述。
反正來來去去就是首次適應，最佳適應等策略，回收時注意合并壓縮。
空閑鏈表法
原理：將所有空閑塊通過指針或索引鏈接成一個鏈表，記錄起始塊和塊數(shù)。
優(yōu)點：實現(xiàn)簡單，適合動態(tài)分配。
缺點：鏈表操作（遍歷、拆分、合并）效率低，不適合大規(guī)模存儲。

鏈表結(jié)構(gòu)為0=>4=5=>6=>7=>......=>12=>14=>17=>......

位圖法（Bit Map）
原理：用一個二進制位（Bit）對應磁盤上的一個物理塊，0表示空閑，1表示已占用。
優(yōu)點：空間占用小，查詢和分配速度塊(位運算)，適合大容量，比如ext4文件系統(tǒng)。
缺點：分配連續(xù)空間時需掃描多個位，可能效率較低。
成組鏈接法
原理:將空閑塊分組，每組記錄下一組的快號，最后一組指向NULL或-1。
優(yōu)點：結(jié)合位圖和鏈表的優(yōu)勢，兼顧空間效率和分配速度，常用于高效文件系統(tǒng)。
缺點：實現(xiàn)復雜。

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

典型文件系統(tǒng)實現(xiàn)

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

文件的基本操作

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