文件管理

这是一篇关于文件管理的思维导图，主要内容包括：文件逻辑结构，文件目录，文件物理结构，文件存储空间管理，文件操作，文件共享，文件保护，文件系统层次结构，文件在内存中的结构，分区、安装，虚拟文件系统。

文件管理

• 文件逻辑结构
  • 无结构文件
    • 由二进制流或字符流组成，无明显的逻辑结构
  • 有结构文件
    • 由记录组成，分为定长记录、可变长记录
    • 顺序文件
      • 链式存储
        • 无论是定长/可变长记录, 都无法实现随机存取, 每次只能从第一个记录开始依次往后查找
      • 顺序存储
        • 物理存储方面
        • 可实现随机存取。记录长度为L，则第i个记录存放的相对位置是 i*L
        • 采用串结构
          • 各记录之间的顺序与关键字无关, 通常是按照时间先后顺序排列, 因此无法快速找到某关键字对应的记录
          • 增删记录较简单（可直接在末尾操作）
        • 采用顺序结构
          • 所有记录按关键字顺序排列, 对于定长记录的顺序文件, 因此可以快速找到某关键字对应的记录 录（如折半查找）
          • 增删记录较困难（需保持有序性）
        • 一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。
        • 优点
          • 读写效率高
    • 索引文件
      • 建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录
      • 本质: 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
        • 如: 文档的目录就是索引文件
        • 索引地址的确定
          • 编辑时（内存中）​​：您在Word里编辑文档，不断增删内容，章节的页码是不确定的。这时，“目录”这个索引表存在于内存中，其页码是临时的、预估的。
          • ​保存时（写入磁盘）​​：当您点击“保存”，操作系统开始工作：
            • 分配物理块​：系统决定将您的文档内容（包括文字和目录数据）写入磁盘的哪些扇区/块中。这些块可能是连续的，也可能是离散的（这取决于磁盘当时的空闲空间情况，对应不同的物理结构，如连续分配、链接分配等）。
            • ​计算并固定地址​：一旦内容被写入具体的物理块，每个章节最终的、确切的起始位置​（即物理地址，可能是一个块号）就确定了。
            • ​更新索引表​：系统会用这些确定的物理地址，来填充或更新您文档内部的那个“目录”（即索引表）。例如，它知道“第一章”的内容被存放在从第1205号磁盘块开始的位置。
        • 后续访问 = 使用索引进行随机存取
          • 当您再次打开文档，想直接跳到“第三章”时，操作系统不会从文档开头逐字读取。
          • 它会先找到文档的“目录”（索引表），在表中搜索“第三章”这个关键字，找到其对应的物理地址（比如第3050号磁盘块）。
          • 然后，磁头可以直接跳转到第3050号块开始读取，这就是随机存取，速度非常快。
      • 若索引表按关键字顺序排列，则可支持快速检索
      • 解决: 解决了顺序文件不方便增/删记录的问题，同时解决看不定长记录的文件不能随机存取的问题。但索引表可能占用很多空间
      • 缺点
        • 维护成本: 增删操作需要额外维护索引表
        • 空间浪费: 当记录平均8B而索引项32B时，索引表比文件大4倍
      • 多索引: 可以为同一文件建立多个索引表，使用不同字段作为索引号
        • 示例: 学生信息表可同时建立学号索引表和姓名索引表
    • 索引顺序文件
      • 索引表和组内记录均不要求按关键字顺序排列 便于新表项的插入操作 本质是定长记录的串结构顺序文件
      • 将记录分组，每组对应一个索引表项
      • 检索记录时先顺序查索引表，找到分组，再顺序查找分组
      • 当记录过多时，可建立多级索引表
• 文件目录
  • 文件目录的实现
    • 文件控制块(FCB)
      • FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息(如文件的建立时间、修改时间等)。最重要，最基本的还是文件名、文件存放的物理地址。
      • FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”
    • 一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
    • 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
  • 目录结构
    • 单级目录结构
      • 一个系统只有一张目录表 不允许文件重名
    • 两级目录结构
      • 组成结构
        • 主文件目录(MFD)：主文件目录记录用户名及相应用户文件目录存储位置
        • 用户文件目录(UFD)：用户文件目录由该用户所有文件的FCB组成
      • 优点
        • 1. 两级目录结构允许不同用户的文件重名
        • 2. 访问控制：通过验证用户名实现目录访问限制（如User1不能访问User2目录）
      • 缺点
        • 1. 用户不能对自己的文件进行分类(即不能再创建第三级目录)
        • 2. 共享困难：缺乏跨用户文件共享机制
    • 多级(树形)目录结构
      • 不同目录下的文件可以重名，可以对文件进行分类
      • 系统根据“文件路径“找到目标文件
      • 绝对路径 VS 相对路径
        • 从根目录出发的路径是"绝对路径"("/照片/2015-08/自拍。jpg")
        • 从"当前目录"出发的路径是"相对路径”("/照片/2015-08/自拍。jpg"), 提升了访问文件效率
      • 缺点
        • 1. 不方便文件共享
    • 无环图目录结构
      • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
      • 为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
      • 注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
  • 索引结点(对文件控制块(FCB)的优化)
    • 其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率
    • 除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点(inode)
    • 目录项中只包含文件名、索引结点号(指针)，因此每个目录项的长度大幅减小
    • 由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检素文件时磁盘/O的次数就少了很多
      • 如: 假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用640/16 =40 个盘块。因此按照某文件名检索该目录，平均需要查询320个目录项，平均需要启动磁盘20次(每次磁盘I/O读入一块)。
      • 若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入320/64=5个磁盘块。显然，这将大大提升文件检索速度
    • 注意: 存放在外存中的索引结点称为"磁盘索引结点" 当索引结点放人内存后称为"内存索引结点" 相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
• 文件物理结构
  • 物理地址
    • 磁盘存储单元被划分为大小相等的"块/磁盘块/物理块"，每个块都有唯一编号（如0号块、1号块等）
    • 地址结构：采用（逻辑块号，块内地址）的二元组形式，类似于内存的（页号，页内地址）
    • 分配原则：操作系统以块为单位分配存储空间，用户无需知晓物理存储位置
    • 分配方式和存储介质有关,不同的存储介质有不同的存储特性，如磁带只能顺序存取，磁盘可以随机存取
  • 连续分配
    • 地址映射
      • 转换规则：仅需转换块号（物理块号=起始块号+逻辑块号），块内地址保持不变
      • 目录项信息：FCB中记录起始块号和长度（如aaa文件：起始块号4，长度3）
      • 合法性验证：需检查逻辑块号是否小于文件长度（避免越界访问）
    • 优点
      • 支持顺序访问和直接访问（随机访问）, 顺序访问时速度最快（磁头移动距离最短）
    • 缺点
      • 拓展困难：文件扩容时可能需要整体迁移
      • 空间利用率：产生磁盘碎片（类似内存外部碎片），紧凑处理代价高
      • 分配失败：虽有5个空闲块但无连续3块空间时，无法创建新文件
  • 链接分配
    • 隐式链接
      • 目录结构：文件目录项(FCB)中记录起始块号(如9)和结束块号(如16)
      • 地址映射
        • 1. 用户给出逻辑块号I
        • 2. 系统根据文件名找到FCB中的起始块号
        • 3. 依次读入0号到I-1号逻辑块才能定位I号块
      • IO操作：访问I号逻辑块需要I+1次磁盘IO
      • 优点
        • 1. 文件拓展方便
        • 2. 无碎片问题, 外存利用率高
      • 缺点
        • 1. 仅支持顺序访问
        • 2. 查找效率低
        • 3. 指针占用少量存储空间
    • 显式链接
      • FAT表
        • -1 表示文件的最后一块
        • -2 表示空闲磁盘块, 因此FAT可以用于文件系统管理空闲磁盘块
        • FAT表会存储数据区域所有磁盘块的分配情况
        • FAT文件系统
          • 簇是文件分配的基本单位
      • 目录项
      • 计算机启动时
        • 会自动把FAT和根目录导入内存，并常驻内存, 提高了检索速度
      • 优点：
        • 很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。
        • 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
      • 缺点
        • 每次启动时都会把FAT读入内存, 若FAT很大, 则会占有大量的内存空间
      • 问题1: FAT表中，每个表项的大小nbit对文件系统有什么影响？
        • 对文件系统支持的最大磁盘块数有影响, n bit 允许FAT最多拥有2^n个表项,即查询范围最多支持2^n个磁盘块
  • 索引分配
    • 原理：
      • 【每个文件对应有一个索引表】，内存中的文件目录表存的是每个文件对应的索引表块号，当要访问一个文件的时候，首先把该文件【的索引表从外存读入内存】
    • 目录表：
      • <文件名、索引表块号>
    • 索引表：
      • 索引指针指向的是文件数据占用的簇，而不是单个磁盘块。
      • 簇: 文件系统的逻辑分配单位, 大小可调（如4KB、32KB）
        • 1簇 = N个连续的磁盘块（N≥1）
      • 磁盘块: 物理存储的最小读写单位,固定（如4KB）
    • 优缺点：
      • 优点：
        • 支持随机、顺序存取
        • 文件拓展很方便
        • 比起显示链接，不需要把索引表同时存入到内存中
      • 缺点：
        • 如果程序很大的话，一个块大小的索引表不够用
    • 缺点优化：
      • 链接方案：
        • 如果一个块大小的索引表存不够，那么索引表最后就指向下一个索引表的块
        • 缺点
          • 若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/0次数过多，查找效率低下。
      • 多层索引：
        • 和多级页表一样，首先访问一级索引表，然后再访问二级索引表,采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。
        • 缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
      • 混合索引
        • 多种索引分配方式的结合。
          • • 一个索引表中，存在
            • 1. 直接地址（直接指向一个块）
              • i.addr(0) ~ i.addr(9)
            • 2. 一级间接（指向一个索引表）
              • i.addr(10)
            • 3. 二级间接（指向一个二级索引表）
        • 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。
      • 超级超级超级重要考点
        • 1||| 要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）
        • 2||| 要能自已分析访问某个数据块所需要的读磁盘次数（Key:FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件一一顶级索引块是否已调入内存）
  • 如果访问一个文件中第n块中的记录：
    • 连续分配
      • 只需访问一次磁盘
    • 链接分配
      • 隐性
        • 需要访问n次磁盘
      • 显性
        • 需要访问1次磁盘
    • 索引分配
      • 访问两次磁盘（一次读索引表，一次读文件）
      • 可能存在超过两次访问（如果索引表一块磁盘装不下）
  • 若需要在文件中间增加一块，则连续分配就要将后面的所有盘块都向后移动一块，这样就会产生很多的磁盘I/O操作。而其他三种分配方式都不需要移动盘块，只需修改一些指针或者索引。因此，连续分配是操作磁盘I/O次数最多的。
• 文件存储空间管理
  • 存储空间的划分与初始化
    • 文件卷（逻辑卷），目录区、文件区的概念
    • 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
  • 空闲表法
    • 空闲表中记录每个连续空闲区的起始盘块号、盘块数
    • 分配算法：
      • 最佳、首次、最坏、临近
    • 存储回收：
      • 和动态分区分配内存回收算法一致
      • 动态分区分配在内存管理的【连续分配】是高效的办法，比较低效是固定大小分区、直接分配
  • 空闲链表法
    • 空闲盘块链：
      • 分配模式：
        • 离散分配
      • 数据结构：
        • 每一个盘块都有指针、一个链头、一个链尾
      • 分配算法：
        • 从链头拿k个块，分配给进程
      • 回收算法：
        • 把回收的盘块，放到链尾
      • 优点: 分配和回收一个盘块的过程简单
      • 缺点:
        • 1. 分配盘块时可能会重复多次, 效率低
        • 2. 盘块链较长
    • 空闲盘区链：
      • 分配模式：
        • 离散分配+连续分配
      • 数据结构：
        • 每一个盘区由相邻的盘块组成，每个盘区有一个链头、一个链尾、本盘区大小
      • 分配算法：
        • 和内存的动态分区分配一样，通常采用首次适应算法
      • 回收算法：
        • 将回收区和相邻的空闲盘区合并
      • 优点: 分配和回收效率高
      • 缺点: 分配和回收过程较为复杂
  • 位示图法
    • • 字号、位号和盘块号进行转化
    • 分配算法：
      • 如何分配：
        • 需要M个，就顺序扫描位示图，找到M个0就行（无所谓连续与否）
      • 如何找k个连续的
        • 在二进制数组中找到k个相邻的空闲块（k个连续0）
        • 然后把这个k个二进制位改为1
    • 回收算法：
      • 首先获得盘块号，然后推出位示图的行号和列号
      • 修改位示图，把对应的二进制位改为0
  • 成组链接法
    • 上述算法的缺点：
      • 无法适用于大型文件系统，因为会导致空闲表和空闲链表太大
    • 超级块
      • 成组链接法的第一块
    • 图示：
      • • 超级块保存在内存的专用栈中, 称为空闲盘块号栈,一般存储在每卷的超级块中, 在对文件操作前会将其预先读入内存
    • 分配算法：
      • 需要小于当前空闲块号：
        • 分配块出去，修改超级块的 1. 空闲块数 2. 空闲块号信息
      • 需要超过当前空闲块号：
        • 把下一个分组的块号表复制到这个超级快中，分配出去当前所有的空闲块号，如果还不够继续复制+分配
    • 回收算法：
      • 如果有位置就填入到超级块当中
      • 若超级块已满，则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中，然后将盘块数1和回收块号记入超级块中
  • 不同文件系统采用不同的管理方法
• 文件操作
  • 创建
    • 从外存中找到文件对应大小的【磁盘空间】
    • 创建该文件对应的【目录项】
  • 删除文件
    • 如果存在其他硬链接：
      • 修改FCB的文件链接数
    • 不存在硬链接：
      • 根据文件存放路径找到相应的目录文件，从录中找到文件名对应的目录项。
      • 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。
      • 从目录表中删除文件对应的目录项。
      • 释放与此文件相关的内存缓冲区
  • 打开(目录)文件
    • 主要工作：
      • 1. 找到文件对应的目录项
      • 2. 把目录项复制到内存中的打开文件表中
      • 3. 随后用户就可以使用打开文件表中的编号来指明要操作的文件
    • 指令：
      • open(char* path, char* fname, int access) -> int
        • path：文件路径
        • fname：文件名
        • access：指明了是只读、只写、读和写
        • 返回的int：文件唯一标识符fd
  • 关闭
    • 将进程的打开文件表相应表项删除
    • 将文件当前的控制信息从内存写回磁盘
      • 文件大小、创建/修改时间、权限（如读/写/执行）。
    • 回收分配给该文件的内存空间等资源
    • 系统打开文件表的打开计数器count 减1，若count =0,则删除对应表项。
  • 读文件
    • 路径解析与文件查找:
      • 目录遍历​：从根目录开始逐级解析路径 /home/user/data.txt
      • ​目录项查找​：在各级目录中查找对应的目录项（directory entry）
      • ​获取文件控制块​：从目录项中获取文件的inode号和元数据信息(inode结构)
      • 逻辑地址 = (inode号=2567, 逻辑块号=2, 偏移量=0)
        • 假设inode 2567的块映射为： i_block[0]→ 物理块 1001 i_block[1]→ 物理块 1002 i_block[2]→ 物理块 1003 ← 我们要找的 i_block[3]→ 物理块 1004
        • ​物理地址​：(物理块号=1003, 偏移量=0)
    • 内存状态检查
      • 内存映射表查询​：检查文件的逻辑地址是否已映射到物理内存
      • ​缓存检查​：查看文件数据是否在系统缓冲区或页缓存中
      • ​状态判断​：
        • 命中​：数据在内存中，直接进行内存访问
        • ​未命中​：数据不在内存中，则进程进入到阻塞态，请求调页, 从外存加载
    • 指令：
      • read(int fd, int* buf, int n)
        • fd：文件唯一标识符
        • buf：缓冲区始址
        • n：读入的字节数
  • 写
    • 找到文件、打开文件、读取文件（记事本需要显示已记录的内容）
    • 在内存区域中修改了文件数据后，使用write系统调用写入到磁盘中
  • 复制
    • 文件在同一个OS中复制时，应保证逻辑结构不变，但物理结构可变
  • 重定位
    • 按某条件搜索目录，将当前文件位置设为给定值，并且不会读、 写文件。
  • 截断
    • 允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。
  • 提高文件访问速度
    • 下列优化方法中，可以提高文件访问速度的
    • 提前读
      • 提前读是指在读当前盘块时，将下一个可能要 访问的盘块数据读入缓冲区，以便需要时直接从缓冲区中读取，提高了文件的访问速度
    • 为文件分配连续的簇
    • 延迟写
      • 延迟写是指先将数据写入缓冲区，并置上“延迟写"标志，以备不久之后访问，当缓冲区需要再次 被分配出去时，才将缓冲区数据写入磁盘，减少了访问磁盘的次数，提高了文件的访问速度
    • 采用磁盘高速缓存
    • 采用页缓存机制
• 文件共享
  • 硬链接
    • 文件指向同一个inode
      • 索引节点的两大功能
        • 文件链接数
          • 在采用索引节点存储方式的OS中，文件目录可以指向同一个索引节点，文件链接数就保存这个值
          • inode索引结点中需要有链接计数 count
            • ​内存中的变化​：当一个文件被打开时，系统会将磁盘inode的信息（包括这个链接计数）读入内存，形成一个内存inode。如果此时有进程创建或删除指向该inode的硬链接，系统会首先更新内存中的这个计数，以便后续操作能立即看到正确的结果。
          • 某用户想删除文件时，只是删除该用户的目录项，且count--
          • count!=0，不能删除文件,否则会导致指针悬空
        • 访问计数
          • 在内存中运行时的访问计数
  • 软链接 （符号链接）
    • 使用符号链，创建一个LINK类新文件
      • 新文件：
        • 创建一个LINK类型的新文件(Windows 快捷方式)
          • 拥有自己的inode和数据块
        • LINK中只存储符号链
      • 软链接特点：
        • 软链接文件只存储路径
          • 操作系统根据路径一层层 查找目录，最终找到共享文件
          • 因此用软链接访问共享文件的速度要比硬链接更慢
        • 不知道文件是否被删除
          • 一访问就知道
        • Link文件的inode引用计数从它被创建的那一刻起就永远是1​（因为只有一个目录项指向F3这个符号链接文件本身）
• 文件保护
  • 口令保护
    • 为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确
    • 实现开销小，但"口令"一般存放在FCB或索引结点中（也就是存放在系统中）因此不太安全
  • 加密保护
    • 用一个“密码"对文件加密，用户想要访问文件时，需要提供相同的“密码才能正确的解密
    • 安全性高，但加密/解密需要耗费一定的时间(Eg：异或加密)
  • 访问控制
    • 用一个访问控制表(ACL)记录各个用户（或各组用户）对文件的访问权限
    • 对文件的访问类型可以分为：读/写/执行/删除等
    • 实现灵活，可以实现复杂的文件保护功能
    • 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制
    • • 描述文件权限的位数 = 用户数量*权限数量
• 文件系统层次结构
  • • 1. 用户接口层
      • 功能：负责接收并解析应用程序发出的系统调用请求，如 open, read, write, close 等。
      • 工作示例：当应用程序执行 open(‘/home/user/project.pdf’) 时。
    • 2. 文件目录系统
      • 功能：路径解析。根据用户给出的文件路径，逐级查找目录，最终找到目标文件对应的控制块（如 inode）。
      • 工作示例：从根目录 / 开始，依次在 home、user 目录中查找，利用目录项（或B+树）找到 project.pdf 对应的 inode 号码。它管理着打开文件表等数据结构。
    • 3. 存取控制模块
      • 功能：安全验证，确保当前用户有足够的权限对文件执行所请求的操作（读、写、执行等）。
      • 工作示例：当文件目录系统层返回 project.pdf 的 inode 号后，此层会介入。它读取 inode 中的权限信息（所有者、组、权限位），并与当前进程的凭据进行比对。如果权限不足，访问在此被拒绝。
    • 4. 逻辑文件系统与文件信息缓冲区
      • 功能：文件的“翻译官”与“高速缓存”。
      • 逻辑文件系统：将应用程序视角的记录号或字节偏移，转换为文件系统内部的逻辑块号。
      • 文件信息缓冲区：这是性能加速的关键！它在内存中缓存：
        • Inode缓存：最近访问过的文件的 inode。
        • 目录项缓存：最近解析过的路径。
        • 页缓存：最近读写过的文件数据块。
      • 工作示例：
        • 翻译：将 read 请求的“读取8192字节”转换为“需要读取该文件的逻辑块0和1”。
    • 5. 物理文件系统
      • 功能：地址转换的“核心引擎”。负责将逻辑块号转换为文件系统内部的物理块号。
      • 工作示例：此层接收到的请求是“读取 project.pdf 的逻辑块0”。它会查阅内存中该文件的 inode，并解析其中的混合索引结构（直接指针、间接指针等），从而将“逻辑块0”映射为具体的“物理块号2048”。
      • 缓存：如果 project.pdf 的 inode 已在缓存中，则路径解析和地址转换速度极快，可能完全避免磁盘I/O。
• 文件在内存中的结构
  • 概念：
    • 目录缓存：
      • 把最近读入过的目录文件的数据保存在内存中
    • inode缓存: 一个全局哈希表，用于缓存最近被访问过的文件的inode信息。
    • 页缓存
      • 内存中的缓存区域
        • 用于临时存储文件数据
      • 提高读写效率
        • 减少对硬盘的直接访问次数
    • 系统打开文件表：
      • 保存一个系统中现在打开的文件，已经打开过多少次
    • 进程打开文件表：
      • 保存一个进程打开了哪些文件，记录在进程的PCB中
  • 图示：
    • • ① 使用open调用把文件目录调入内存
      • ② 根据open中的文件名参数，在内存的目录缓存中找到对应的文件，记录其FCB等信息
      • ③ 打开这个文件的进程同样需要把这个文件信息写入到自己的打开文件表中
      • 如果用户要读一个文件
        • 用户使用read(fd, xx, xx)来 1. 找进程打开文件表 2. 系统打开文件表 3. 访问外存
• 分区、安装
  • 分区：
    • 一个磁盘可以划分为多个分区，每个分区可以创建单独的文件系统，也可以有不同的操作系统
      • （例：装双系统）
    • 主引导扇区MBR(512B) = 引导代码(440字节) + ​磁盘签名(4B) + 分区表(64字节) + ​结束标志(2B)(固定为0x55AA)
    • 引导块：
      • 存储引导信息，存储一系列连续的代码，负责启动该分区的才操作系统
    • 超级块：
      • 存储和文件系统有关信息，例如文件系统类型、i结点的个数、数据块个数, 空闲FCB数量和FCB指针等。
    • i 结点区：
      • inode，有多个，每个文件对应一个
        • ​inode 1​ 可能是某个系统文件的档案。
        • ​inode 2​ 是根目录 /的档案​（这是一个约定俗成的规定）。
        • ​inode 1314​ 可能是您家目录 /home/yourname的档案。
        • ​inode 7410​ 可能是您的一个文档 project.pdf的档案。
      • B+树用于在路径查找中定位inode编号，而inode区则存储该编号对应的文件元数据(inode)。
    • 数据块：
      • 存文件数据
  • 安装：
    • 安装 ↔ 挂载
      • 例如：插入U盘
    • WINDOWS/MAC自动发现设备，安装找到的文件系统
    • UNIX需要自行挂载文件系统：
      • mount -t ex2 /dev/fd0 /flp
        • umount进行解除
  • 计算机启动流程
• 虚拟文件系统
  • 虚拟文件系统采用了面向对象的思想，它抽象出一个通用的文件系统模型，定义了通用文件系统都支持的接口。新的文件系统只要支持并实现这些接口，即可安装和使用。
  • • ① 向上给进程提供一个统一的read、open调用
    • ② 向下规定所有文件系统提供统一的打开、读、写、格式化等操作
    • ③ VFS维护自己的在内存中的vnode，来表示文件，无论文件存储在哪一个文件系统中
    • • 当文件读入内存后，文件的各种信息会被复制+转化为vnode对应的数据结构（构造）
      • 函数功能指针指向的是对应文件系统中的函数
        • UFS：
        • FAT：
    • write()
      • 用户空间
      • sys_write()
        • VFS
        • 文件系统的写方法
          • 具体某个文件系统
          • 物理介质
  • Linux抽象的四种对象类型
    • • 超级块对象
        • 表示一个已安装（挂载）的特定文件系统
        • 对应磁盘中扇区的文件系统超级块，存储已安装文件系统的元信息
        • 有对超级块进行更改的操作函数，例如分配、销毁、读写inode等
      • 索引结点对象
        • struct inode是磁盘 inode 的内存缓存，包含文件元数据和扩展运行时状态。
        • 操作例如创建索引节点、硬链接、新目录等
      • 目录项对象
        • 表示一个特定的进程
        • 由于VFS经常执行切换到某个目录这种操作，为了提高效率，便引入了目录项的概念
        • 目录文件（如/home）存储文件名和 inode 编号，但 dentry 是内核动态构建的缓存。
      • 文件对象
        • 表示一个与进程相关的已打开文件,跟踪文件的打开模式、读写位置等进程级状态
        • 文件对象代表进程打开的一个文件，open()调用打开，close()调用关闭
    • 四个核心对象均为内存中的数据结构

B+树在管理文件目录的应用

• 1. 核心基础概念
  • FCB：文件控制块，存储文件的元数据
  • 文件目录：本质是"文件名"到"FCB/inode"的映射表
  • 核心问题：如何高效存储和检索目录中的大量映射记录
• 2. 传统线性列表方式的缺点
  • 数据结构：简单线性列表<文件名, inode号>
  • 搜索操作：顺序遍历，时间复杂度O(n)
  • 缺点：目录文件数量大时，性能急剧下降
• 3. B+树解决方案
  • 核心思想：将目录内容组织成一棵B+树
  • 键：文件名
    • key = 文件名（或文件名的哈希值）
  • 值：inode号
  • 节点：对应磁盘块
• 4. B+树目录的存储结构
  • 4.1 磁盘块的角色
    • 根节点/内部节点：存储导航信息（键和指针）
      • key = 文件名（或文件名的哈希值）
    • 叶子节点：存储实际目录项<文件名, inode号>
  • 4.2 目录inode的作用
    • 指向目录内容所在的第一个磁盘块
    • 该磁盘块即为B+树的根节点
• 5. 文件查找过程详解
  • （以路径 /home/user/project.pdf 为例）
  • 1. 路径解析
    • 目标：将路径字符串分解为可逐步查找的组件。
    • 过程：
      • 分割路径：/ -> home -> user -> project.pdf
      • 起始：从根目录 / 开始查找过程。
  • 2. 定位根节点 (/)
    • 目标：获取根目录的Inode及其数据块。
    • 过程：
      • 根目录的Inode号通常固定（如inode 2）。
      • 通过磁盘上的超级块信息定位根目录的Inode。
      • 读取根目录的Inode，获取指向其数据块的指针。
  • 3. B+树搜索（在目录数据中查找）
    • 前提：目录文件的数据块以B+树结构组织，而非简单列表。
    • B+树结构：
      • 根节点/中间节点：存储键（文件名范围）和指向子节点的指针。
      • 叶子节点：存储实际的目录项 <文件名, Inode号>。
    • 搜索过程（以在根目录中查找home为例）：
      • 加载根节点：将根目录数据块（B+树的根节点）加载到内存。
      • 二分查找：在当前节点键值中进行二分查找，确定home所属的范围。
      • 定位子节点：根据查找结果，找到并加载下一个子节点（可能是中间节点或叶子节点）。
      • 递归查找：重复“二分查找->定位子节点”的过程，直到最终到达叶子节点。
  • 4. 获取下一级目录的Inode号
    • 目标：在叶子节点中找到目标文件名对应的Inode号。
    • 过程：
      • 在到达的叶子节点中，搜索目录项 <home, Inode号>。
      • 成功匹配后，即获得 home 目录的Inode号（例如 1314）。
  • 5. 迭代过程（进入下一级目录）
    • 将新获取的Inode号（home的inode 1314）作为当前目录的Inode。
    • 重复步骤 2 -> 3 -> 4：
      • 定位home节点：读取inode 1314，找到home目录的数据块。
      • B+树搜索：在home目录的B+树中查找 user。
      • 获取Inode：在叶子节点中找到 <user, Inode号>，获得inode号（例如 2520）。
  • 6. 定位目标文件
    • 重复迭代过程，将当前目录设置为 user（inode 2520）。
    • 重复步骤 2 -> 3 -> 4：
      • 定位user节点：读取inode 2520，找到user目录的数据块。
      • B+树搜索：在user目录的B+树中查找 project.pdf。
      • 获取目标Inode：在叶子节点中找到 <project.pdf, Inode号>，获得目标文件的inode号（例如 7410）。
  • 7. 最终访问文件
    • 目标：使用获取到的Inode号访问文件内容和元数据。
    • 过程：
      • 读取Inode：将inode 7410读入内存。
      • 访问元数据：从Inode中获取文件权限、大小、时间戳等信息，进行权限校验。
      • 访问数据块：通过Inode中的数据块指针（混合索引结构）：
        • 直接指针：直接指向文件数据块。
        • 间接指针：指向包含更多数据块指针的索引块。
      • 读取数据：根据指针将相应的磁盘数据块读入内存，供应用程序使用。
  • 关键概念
    • Inode：索引节点，文件的元数据集合（不含文件名）和数据指针。
    • 目录项：目录文件内容的基本单元，存储了<文件名, Inode号>的映射关系。
    • B+树：一种高效平衡查找树，用于在大型目录中快速定位文件名。
    • 数据块：磁盘上存储文件实际内容的最小单位。
• 6. B+树的优势
  • 高扇出：树矮胖，查找速度快
  • 少量I/O：通常仅需1-3次磁盘I/O
  • 高效查找：节点内二分查找，时间复杂度O(log n)
  • 适合磁盘：节点与磁盘块大小对应，充分利用预读
• 7. 实际应用
  • Linux ext4：使用HTree（B+树变体）
  • XFS/Btrfs：全面使用B+树管理元数据

磁盘逻辑地址到物理块号转换流程

• 1. 接收读取请求
  • • 系统调用：read(文件路径, 缓冲区, 大小, 偏移量)
  • • 输入：文件偏移量（逻辑地址）
  • • 示例：读取偏移量8192字节处
• 2. 计算逻辑块号
  • 逻辑块号 = 文件偏移量 / 磁盘块大小 8192 ÷ 4096 = 第2个逻辑块
• 3. 文件系统转换（核心步骤）
  • 3.1 定位文件元数据
    • • 根据文件路径找到inode
    • • 加载磁盘inode到内存inode
  • 3.2 查询映射关系
    • • 访问inode中的索引结构
    • • 直接索引：直接块指针表
    • • 间接索引：单重/双重/三重间接指针
  • 3.3 完成地址转换
    • 逻辑块号 2 → 物理块号 200 （通过查inode索引表得到）
• 4. 驱动层处理
  • 4.1 转换物理地址格式
    • • 物理块号 → 三维磁盘地址(CHS)
    • • C：柱面号 (Cylinder)
    • • H：磁头号 (Head)
    • • S：扇区号 (Sector)
  • 4.2 发出硬件指令
    • • 向磁盘控制器发送读写命令
    • • 包含目标CHS地址信息
• 5. 硬件执行
  • 5.1 磁盘定位
    • • 磁臂移动到指定柱面
    • • 选择对应磁头
    • • 等待目标扇区旋转到位
  • 5.2 数据传输
    • • 通过DMA直接内存访问
    • • 数据从磁盘→内存缓冲区
    • • 完成后产生中断信号

文件访问流程说明

• 载入inode（打开文件时）
  • 进程首次调用open("文件A")
    • 系统通过目录项找到文件A的inode编号
  • 内核检查inode缓存
    • 如果未命中则从硬盘inode区读取inode信息到内存
  • inode包含文件的元数据
    • 权限、大小等
  • inode包含数据块位置信息
    • 最重要的数据块位置信息
• 查找FCB（文件控制块）
  • 进程通过文件描述符
    • 在进程打开文件表中找到对应的系统打开文件表项
  • 实现从用户空间文件描述符到内核文件对象的转换
• 获取inode
  • 系统打开文件表项指向内存中的inode缓存
  • 多个进程打开同一文件时
    • 会指向同一个inode
    • 实现文件共享
• 数据块映射
  • inode中包含文件数据块在硬盘上的位置信息
  • 通过inode建立文件逻辑偏移到物理磁盘块的映射关系
• 读写数据
  • 数据在页缓存和硬盘数据区之间传输
  • 读操作
    • 数据从硬盘→页缓存→用户缓冲区
  • 写操作
    • 数据从用户缓冲区→页缓存→硬盘（延迟写入）
• 文件访问流程详解
  • 打开文件
    • 调用系统调用open
      • 指定文件名
      • 指定访问模式（读、写、追加等）
    • 系统查找文件名对应的目录项
      • 获取文件的inode编号
    • 检查inode缓存
      • 如果缓存中没有
        • 从硬盘读取inode信息到内存
    • inode缓存命中
      • 直接使用缓存中的inode信息
  • 文件控制块（FCB）
    • 每个打开的文件在系统中有一个FCB
      • 包含文件状态信息
        • 文件指针位置
        • 文件打开模式
        • 文件访问权限
    • 进程打开文件表
      • 与系统打开文件表关联
        • 通过文件描述符索引
  • inode信息
    • 文件元数据
      • 包括文件类型、权限、大小、创建时间等
    • 数据块位置信息
      • 指向文件实际数据存储位置
  • 数据块映射
    • 确定数据块位置
      • 根据inode中的信息
    • 逻辑偏移量转换为物理块地址
      • 通过文件系统算法
  • 读写操作
    • 读操作流程
      • 系统检查页缓存
        • 如果缓存中有数据
          • 直接从缓存读取
        • 如果缓存中没有数据
          • 从硬盘读取数据到页缓存
          • 再从页缓存读取到用户缓冲区
    • 写操作流程
      • 数据首先写入页缓存
        • 系统稍后将页缓存数据写入硬盘
          • 这种机制称为延迟写入或回写
  • 文件共享
    • 多个进程共享同一inode
      • 通过相同的inode编号访问文件
    • 共享文件数据块
      • 所有进程看到的文件内容是一致的
  • 文件系统缓存
    • 利用内存缓存数据块
      • 提高文件访问速度
    • 缓存管理
      • 系统自动管理缓存的替换策略
  • 文件系统结构
    • 硬盘上的组织方式
      • 包括inode区、数据块区等
    • 文件系统类型
      • 如ext4、NTFS、FAT32等
  • 文件描述符
    • 每个打开的文件分配一个唯一的描述符
      • 用于标识和管理文件
    • 文件描述符表
      • 进程级别的文件打开状态表
  • 系统打开文件表
    • 内核级别的文件管理表
      • 包含所有打开文件的状态信息
    • 与进程打开文件表关联
      • 通过文件描述符索引
  • 页缓存
    • 内存中的缓存区域
      • 用于临时存储文件数据
    • 提高读写效率
      • 减少对硬盘的直接访问次数
  • 硬盘数据区
    • 实际存储文件数据的硬盘区域
      • 包括数据块和inode信息
    • 硬盘I/O操作
      • 直接与硬盘硬件交互
  • 延迟写入机制
    • 提高系统性能
      • 减少频繁的硬盘写操作
    • 数据一致性保证
      • 系统定期同步缓存数据到硬盘
  • 文件访问权限
    • 根据inode中的权限信息
      • 确定进程对文件的访问权限
    • 权限检查
      • 在每次文件操作前进行
  • 文件系统调用
    • open、read、write、close等
      • 用户空间通过系统调用与内核通信
    • 系统调用接口
      • 提供文件操作的接口函数
  • 文件系统的一致性
    • 系统崩溃后的恢复
      • 利用inode和日志文件保证数据一致性
    • 文件系统检查工具
      • 如fsck工具检查和修复文件系统错误
  • 文件系统的安全性
    • 访问控制列表（ACL）
      • 提供更细粒度的访问控制
    • 加密文件系统
      • 保护存储在硬盘上的文件数据安全
  • 文件系统的性能优化
    • 预读取机制
      • 预先读取可能需要的数据块到缓存
    • 写缓存策略
      • 优化写入操作以提高性能
  • 文件系统的维护
    • 定期检查和维护
      • 确保文件系统的健康和性能
    • 文件系统碎片整理
      • 优化硬盘空间使用和访问速度

文件系统操作全流程解析： 从小明创建 hello.c 到与小红共享

• 第一阶段：规划与“土地划分” - 对应“分区、安装”
  • 背景：小明的计算机有一块硬盘。在安装操作系统时，这块硬盘被分区（Partition）成了两个主要部分：/dev/sda1 (挂载为根目录 /) 和 /dev/sda2 (挂载为 /home)。
  • 动作：操作系统启动时，会将这两个分区安装（Mount）到文件系统树中。这意味着，/dev/sda2 这个物理存储空间，被逻辑地“挂”在了 /home 这个目录节点上。
  • 知识点覆盖：分区、安装。这确定了文件系统的物理边界和逻辑入口。
• 第二阶段：文件的“诞生” - 对应“文件操作”、“逻辑/物理结构”、“存储空间管理”
  • 动作：小明在终端输入 vim /home/xiaoming/projectA/hello.c 并回车。
  • 文件系统层次结构开始工作：
    • 用户接口层：接收 vim 程序的 create 系统调用。
    • 文件目录系统层：解析路径 /home/xiaoming/projectA/。这个过程需要：
      • 目录查询：从根目录 / 开始，依次查找 home、xiaoming、projectA 目录。这里运用了 目录的优化：目录项只存储了文件名和inode号，使得目录表“瘦身”，查询更快（比如使用B+树索引）。
    • 存取控制模块：在路径解析的每一步，都检查小明是否有进入目录和创建文件的权限。
    • 在 projectA 目录中，为新文件 hello.c 分配一个空闲的 inode（假设是 #1314）。inode 是文件物理结构的核心，它将来会记录文件的数据块指针。
  • 文件创建：
    • 在 projectA 目录的数据块中，增加一条记录：<hello.c, 1314>。
    • 在内存中创建 hello.c 的 文件打开表项，并返回一个文件描述符给 vim 进程。
  • 知识点覆盖：文件操作（创建）、文件目录、文件目录的实现（瘦身优化）、索引结点（inode）、文件系统层次结构、文件保护（权限检查）。
• 第三阶段：文件的“成长” - 对应“文件操作”、“物理结构”、“存储空间管理”
  • 动作：小明在 vim 中键入代码 #include <stdio.h>... 并保存。
  • 写操作：vim 发起 write 系统调用。
  • 逻辑 vs 物理：
    • 逻辑文件系统：将小明要写入的字节流（逻辑结构），按4KB大小划分为逻辑块（比如需要2个块）。
    • 物理文件系统：为这些逻辑块分配实际的磁盘空间。这涉及到文件物理结构的分配方式：
      • 连续分配？（不适合会增长的文件，会产生碎片）
      • 链接分配？（可以，但随机访问慢）
      • 索引分配（现代文件系统如ext4的选择）：使用inode中的混合索引结构。因为hello.c还很小，数据块的地址可以直接存放在inode的直接指针中。
  • 分配空间：
    • 辅助分配模块 被调用，它使用位示图法 查询空闲磁盘块，发现块 #2048 和 #2049 是空闲的，将其标记为已用。
    • 物理文件系统将块地址 #2048 和 #2049 填入 inode #1314 的直接指针中。
  • 数据写入：设备管理模块将数据写入磁盘块 #2048 和 #2049。
  • 知识点覆盖：文件操作（写）、文件逻辑结构（流式文件）、文件物理结构（索引分配）、文件存储空间管理（位示图法）。
• 第四阶段：文件的“使用”与“共享” - 对应“文件操作”、“共享”、“保护”
  • 动作：小明需要和小红协作。他不想复制文件，只想共享。
  • 文件共享：
    • 硬链接：小明在 /home/xiaohong/ 目录下为 hello.c 创建一个硬链接：ln /home/xiaoming/projectA/hello.c /home/xiaohong/hello_link.c。
    • 发生了什么：操作系统在 /home/xiaohong 目录中添加一条新记录 <hello_link.c, 1314>，指向同一个inode #1314。inode 的链接计数 从1变为2。
    • 与软链接的区别：如果使用软链接 ln -s，则会创建一个新的、类型为“链接”的小文件，其内容只是原始文件的路径字符串。
  • 文件保护：
    • 小红尝试编译这个文件：gcc hello_link.c -o hello。这会触发 read 操作。
    • 存取控制模块 再次介入：它检查 inode #1314 的权限位。假设权限是 -rw-r--r--（所有者可读可写，其他人只读）。
    • 小红属于“其他人”组，拥有r--（只读）权限，因此 read 操作被允许，但后续的 write 操作会被拒绝。
    • 其他保护方式：如果这是高度机密文件，还可以采用加密保护，或在访问控制列表中精细控制。
  • 知识点覆盖：文件共享（硬链接、软链接）、文件保护（口令保护、加密保护、访问控制）、文件操作（读、写）。
• 第五阶段：文件的“内存映像” - 对应“文件在内存中的结构”
  • 动作：小红执行编译好的程序 ./hello。
  • 文件在内存中的结构：
    • 操作系统需要将可执行文件 hello 加载到内存才能运行。
    • 它不会一次性读入整个文件，而是使用内存映射文件 机制。
    • 系统调用 mmap 将文件 hello 的虚拟地址空间映射到进程的虚拟地址空间。
    • 当CPU执行到代码的某一部分时，如果发现该部分不在物理内存中，会触发缺页异常。
    • 操作系统处理异常，根据映射关系，找到需要的数据在文件中的哪个逻辑块，然后通过文件系统层（物理文件系统->设备管理）将该页从磁盘调入物理内存。
  • 为什么快：这个过程利用了文件信息缓冲区（页缓存）。如果小明之前运行过这个程序，数据可能还在缓存中，速度极快。
  • 知识点覆盖：文件在内存中的结构（内存映射、页缓存）、文件系统层次结构（底层支持）。
• 第六阶段：文件的“消亡”与空间回收
  • 动作：项目结束，小明决定删除 hello.c：rm hello.c。
  • 删除操作：
    • 这实际上是删除目录项。系统将 projectA 目录中 <hello.c, 1314> 这条记录标记为删除。
    • inode #1314 的链接计数 从2减为1（因为小红那里还有一个硬链接）。
    • 只要链接计数不为0，文件数据就不会被真正清除。这就是硬链接共享的语义。
  • 空间回收：
    • 当小红也删除了她的硬链接后，链接计数降为0。
    • 操作系统此时才会
      • a. 将 inode #1314 标记为空闲。
      • b. 将数据块 #2048 和 #2049 在位示图中标记为空闲（存储空间管理）。
      • c. 这些块可以被后续新创建的文件复用。

inode分配方式(了解)

• 1. inode分配方式
  • 静态预分配(ext2/3/4)
    • 创建时机: 文件系统格式化时
    • 特点
      • 固定数量和大小的inode预分配
      • 存储在inode table中
      • 数量不可动态调整
    • 优缺点
      • 访问速度快
      • 可能耗尽inode
  • 动态按需分配(XFS/Btrfs/ZFS)
    • 创建时机: 创建文件时动态分配
    • 特点
      • 无固定数量上限
      • 分散存储大小可变的inode
      • 随文件创建而分配
    • 优缺点
      • 无inode耗尽问题
      • 元数据管理复杂
• 2. inode磁盘存储
  • 存储结构
    • 多个inode打包存储在磁盘块中
    • inode大小通常<块大小
    • 采用inode table集中管理(ext系列)
  • 空间占用计算
    • inode数量 × inode大小 = 总占用空间
    • 默认占用磁盘空间1-5%
    • 可格式化时调整密度参数