簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

眼見為實(shí)

單級(jí)文件目錄

早期操作系統(tǒng)不支持多級(jí)目錄，整個(gè)系統(tǒng)只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)。
因?yàn)檫@個(gè)特性，文件是不允許重名的。

二級(jí)文件目錄

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

兩級(jí)目錄允許不同用戶的文件重名，但依舊缺乏靈活性。因?yàn)椴荒軐?duì)自己的文件進(jìn)行分類

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

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

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

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

眼見為實(shí)

linux下，絕對(duì)路徑與相對(duì)路徑:

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

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

眼見為實(shí)

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

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

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

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

眼見為實(shí)

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

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

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

在很多操作系統(tǒng)中，磁盤塊與內(nèi)存頁框保持大小一致，目的是為了數(shù)據(jù)交換時(shí)，因?yàn)榇笮。灾恍枰淮蜪/O操作

文件分配方式

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

1. 連續(xù)分配(Contiguous Allocation)
   原理：將文件在磁盤上分配為一組連續(xù)的物理塊，文件的邏輯塊號(hào)(Logical Block Number,LBN)，對(duì)應(yīng)磁盤上連續(xù)的物理塊號(hào)(Physical Block Number,PBN)。
   優(yōu)點(diǎn)：訪問速度快，支持隨機(jī)訪問。比如PBN=起始?jí)K號(hào)+LBN
   缺點(diǎn)：磁盤碎片，動(dòng)態(tài)擴(kuò)容復(fù)雜。

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

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

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

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

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

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

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

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

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

磁盤基本劃分

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

空閑存儲(chǔ)空間管理

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

1. 空閑表法
   與內(nèi)存分配的動(dòng)態(tài)分配算法如出一轍，因此不再贅述。
   反正來來去去就是首次適應(yīng)，最佳適應(yīng)等策略，回收時(shí)注意合并壓縮。

2. 空閑鏈表法
   原理：將所有空閑塊通過指針或索引鏈接成一個(gè)鏈表，記錄起始?jí)K和塊數(shù)。
   優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，適合動(dòng)態(tài)分配。
   缺點(diǎn)：鏈表操作（遍歷、拆分、合并）效率低，不適合大規(guī)模存儲(chǔ)。

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

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

4. 成組鏈接法
   原理:將空閑塊分組，每組記錄下一組的快號(hào)，最后一組指向NULL或-1。
   優(yōu)點(diǎn)：結(jié)合位圖和鏈表的優(yōu)勢(shì)，兼顧空間效率和分配速度，常用于高效文件系統(tǒng)。
   缺點(diǎn)：實(shí)現(xiàn)復(fù)雜。

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

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

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

文件的基本操作

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

系統(tǒng)索引號(hào)，也被稱為文件描述符(fd)

轉(zhuǎn)自https://www.cnblogs.com/lmy5215006/p/18824802
?