简介

操作系统的文件管理负责都计算机中的数据(文件和目录)进行组织，存储，检索，保护，共享。
其核心目标为：

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
​