1 文件系统的层次结构
1.1 总览
1.2 例子
2 文件系统的全局结构
2.1 物理格式化（低级格式化）
磁盘在物理格式化后被划分出许多扇区，同时也可能包含坏扇区，磁盘会用备用扇区替代坏扇区，如图。
当操作系统访问到坏扇区时，磁盘会将实际访问的扇区替换成备用扇区，因此坏扇区对于操作系统来说是透明的
2.2 逻辑格式化（高级格式化）
每个分区对应的信息使用分区表来记录
对于UNIX系统来说，磁盘在逻辑格式化后，其内部结构会如图所示
（1）引导块：类似于Windows下的BIOS，负责开机时初始化系统
（2）超级块：操作系统可以通过此块快速找到空闲的磁盘地址
（3）空闲空间管理：里面存储了与空间管理相关的数据结构（比如位视图）
（4）i结点区：里面存储了各文件的索引结点，结点连续存放。索引节点的大小都是相同的，因此可以迅速定位到任何一个索引结点
（5）根目录：任何文件的存储都必须在根目录下
（6）其他文件：在格式化后为空
2.3 文件系统在内存当中的结构
2.3.1 结构示意图
2.3.2 外存
存放文件以及文件目录
2.3.3 内核区
（1）目录缓存
操作系统会将近期访问过的文件目录复制一份放在内核区中，这样当需要再次访问时就不需要再次去外存中寻找了，可以提高访问速度。
（2）系统打开文件表与用户打开文件表
参考之前的笔记
2.3.4 用户区
（1）文件描述符/文件句柄
当我们打开一个文件时，操作系统会放回一个句柄（类似于指针），方便我们对文件进行操控（联想C语言的文件操作）
Fp = file.open(“./test.txt”)
3 文件的逻辑结构
3.1 总览
3.2 无结构文件
3.3 有结构文件
3.3.1 总览
按照各记录项的存储空间是否可以改变分为定长记录和可变长记录两种
3.3.2 顺序文件
（1）定义
（2）分类
第一种分类方法
①逻辑上相邻物理上也相邻
②逻辑上相邻物理上不一定相邻
第二种分类方法
（3）对于以上的几种分类，都需要解决2个问题，比如现在知道一个顺序文件的起始地址，那么
下面给出结论：
总结：
3.4 索引文件
3.4.1 什么是索引文件？
如图，将文件分成很多部分，这些部分可以在外存中离散的存放。建立一张索引表，它的指针项指向文件的各部分。在需要查找文件的第i个内容时，只需查找索引表的第i项，再查找指针的地址就可以。
索引表项都是相同长度的，且属于顺序文件，因此对它的I/O操作就很快。
3.4.2 注意
3.5 索引顺序文件
3.5.1 索引文件的缺点
3.5.2 索引顺序文件的基本实现方式
对于一个文件，先选取一个关键字，比如对于学生信息可以选取姓名作为关键字，将数据按照关键字进行分组，例如：姓名A开头的为一组，姓名B开头的为1组，每个分组的关键字无须排序（方便文件的修改）。而索引顺序文件记录了各分组的第一条数据的关键字、地址。索引顺序文件的键也无须排序（方便新表项的插入），可以看出，该表是一个定长记录的、串结构的顺序文件。
这样，当系统要查找某条记录时，首先根据关键字确定该数据项的组别，根据索引表找到组别的起始地址，并顺序查找具体的文件。
3.5.3 索引顺序文件的实际效果
3.6 多级索引顺序文件
3.6.1 单级索引顺序文件的缺点
可以看到，假如数据项很多，索引顺序文件的查找次数依然较多。
3.6.2 多级索引顺序文件的实现方式
将文件进行分组，各组对应一个低级索引表，而各低级索引表又对应一个顶级索引表。这样可以提高查找效率。
3.6.3 效果分析
次数平均查找次数为50+50+50 = 150次。
3.6.4 注意
3.7 总结
4 文件的物理结构
4.1 总览
4.2 文件块与磁盘块
（1）磁盘块的作用
因为内存、磁盘的最小数据单元就是块，所以当磁盘块的大小与内存块的大小一致时，那么内存与磁盘的数据交换就会很方便。
（2）磁盘分块的基本概念
4.3 文件分配方式——连续分配
4.3.1 连续分配的基本概念
示意图：
4.3.2 如何实现逻辑地址到物理地址的映射
采用连续分配，则文件的目录文件中需存放文件的起始块号及长度
查找过程：
4.3.3 连续分配的优点
（1）连续分配可以实现随机查找（类似于数组，即：查找第2个块不需要先查找第0、1个块）
（2）连续分配的文件在顺序读/写时速度最快
解释：磁盘在读取某个磁盘块时，需要移动磁头（组成原理）。当访问的两个磁盘块距离越远，移动磁头所需的时间就越长。而连续分配方式下不同磁盘块是连续的，所以读取时间最短。
4.3.4 连续分配的缺点
（1）物理上采用连续分配不方便拓展
如图，当黄色块进行拓展时，唯一的方法就是将块迁移到更大的磁盘块中去。而迁移所耗费的资源是很大的。
（2）存储空间利用率低，会产生难以利用的磁盘碎片
如图，虽然此时磁盘内空闲块的个数为5，且此时需要分配的空间只为3，但是因为没有连续的3个空间，所以就没法分配。且这5个块也难以利用起来。
4.3.5 对于连续分配的总结
4.4 文件分配方式——链接分配
4.4.1 链接分配——隐式链接
（1）基本概念
文件的目录文件中存放了文件的起始块号、结束块号。且存放文件内容的每一个块都存放了下一个块的指针。
（2）如何实现逻辑地址到物理地址的映射？
类似于链表的思想
（3）拓展文件
（4）优点
①很方便文件拓展
②所有的空闲文件块都可以被利用，不会有外部碎片，存储空间的利用率高
（5）缺点
①只支持顺序访问，查找效率低
②磁盘块存储的指针也需消耗一定的空间
4.4.2 链式分配——显式链接
（1）基本概念
（注意是物理块不是逻辑块）
假设：
那么，FAT中的内容就应该是：
由FAT内容可知，2号块的下一块是5，5号块的下一块是0，0号块的下一块是1，1号块的下一块是-1，代表没有下一块，所以1号块是文件的末尾。
而目录文件中就只需要存放文件的起始块号就可以了。
（2）注意
①FAT常驻内存
②“物理块号”字段可以隐含
③一个磁盘对应一张FAT表
（3）如何实现逻辑地址与物理地址的映射
（4）优点
①支持顺序访问
若想找到一个文件的第i号块，支持随机访问（只需在FAT中找到对应的块号就可以得到它存放的物理块号），也支持顺序访问（可以在FAT中由起始块号一直顺序查找到目标块号）。
②速度快
操作系统只需访问FAT（常驻内存）就可以找到对应的物理地址。无须对磁盘进行读写，所以速度会更快
③显然，这种方式不会产生外部碎片（链式分配的一般特性）
④便于实现对文件的存储（链式分配的一般特性）
（5）缺点
FAT会占用一定的存储空间
4.5 文件分配方式——索引分配
4.5.1 什么是索引分配？
类似于页表的思想。
一个文件对应一个索引表，文件的目录文件要记录该文件的索引块是几号磁盘块。
4.5.2 例子
假设：
那么文件"aaa"的索引表的内容为：
4.5.3 如何实现逻辑地址到物理地址的转变
4.5.4 注意
（1）索引表中的“物理块号“是可以使用一个固定的长度，因此逻辑块号可以隐藏。
（2）使用索引表查找i号块时，无须查找i-1号块，因此可以实现随机查找。
（3）文件拓展很容易实现：
4.5.5 缺点
（1）索引表需要占用一定的空间，这是缺点
4.5.6 待解决的问题
（1）问题描述
（2）链接方案
①基本介绍
假设一个文件需要i个索引块，那么第 j-1 号索引块中要存储第 j 号索引块的地址。这样，目录文件中就只要记录第1个索引块的地址就可以。
②缺点
如果需要访问第 i 号索引块，那么必须要将前 i-1 个索引块都读入内存，才可以知道索引块的地址。显然，这是很低效的。
（3）多层索引
①基本介绍
②例子
对于上面的那个问题，可以建立两级索引，示意图如图所示。
目录文件只需要存储顶级索引块地址即可。
此时，文件的最大的大小为256*256*KB = 64MB
③如何实现逻辑地址与物理地址的转变
假如系统需要访问1026号逻辑块，首先计算1026/256 = 4，得出这个逻辑块应该在第4个二级索引表中，所以操作系统会先将顶级索引表调入内存，找到第4个二级索引表的物理地址，并将这个二级索引表调入内存；接着，计算1026%256 = 2，得出这个逻辑块应该在第4个二级索引表的第2个表项内，于是访问得到最终的物理地址；再次访问该物理地址可以得到对应的内容。
④缺点
假如一个文件的大小很小，那么也需要访问3次磁盘才可以得到文件内容
（4）混合索引
①基本介绍
既有直接索引，也有多层索引
示意图如图所示
对于一些大小很小的文件内容可以直接存储它的地址（直接地址）。对于可以用一张索引表表示的文件内容可以指向一个单层索引表（一级间接）。对于很大的文件内容可以指向一个多层索引表（二级间接）。
②注意
③优点
4.5.7 关于索引分配的总结
4.6 知识总结
5 文件存储空间管理
5.1 总览
探讨的对象：空闲的存储空间
5.2 存储空间的划分和初始化
5.2.1 文件卷
在系统初始化的过程中，需要将存储空间划分为C盘、D盘。这些就是文件卷（逻辑盘、逻辑卷）。
5.2.2 目录区与文件区
每个文件卷都会被进一步划分为目录区与文件区。其中：
目录区:
文件区：
5.2.3 注意
一个文件卷是可以由多个物理磁盘组成的
5.3 存储空间管理方法——空闲表法
5.3.1 基本概念
使用一张表记录空闲的存储空间。它一般适用于连续分配方式。
5.3.2 例子
那么此时系统内的空闲表的内容为：
5.3.3 分配空间的方法
（1）首次适应
系统从空闲表的初始点开始寻找，找到第一个可以满足要求的空闲表项，分配空间并修改空闲表
（2）最佳适应
找到一个可以满足要求、且空闲盘块数最小的空闲表项。
（3）最坏适应
找到一个可以满足要求、且空闲盘块数最大的空闲表项。
5.3.4 回收空间的方法
总体与内存管理中的动态分配类似。
（1）回收区的前后都没有相邻空闲区
新增空闲表项
（2）回收区的前后都是空闲区
合并空闲表项
（3）回收区前面是空闲区
修改前面的空闲表项
（4）回收区的后面是空闲区
修改后面的空闲表项
5.4 存储空间管理方法——空闲链表法
5.4.1 分类
空闲盘块链：
空闲盘区链：
5.4.2 空闲盘块链
操作系统需要保存盘块链的链头指针和链尾指针
（1）分配存储空间
（2）回收存储空间
（3）注意
在分配的时候要从链头一个一个摘下磁盘块，所以为文件分配盘块可能重复多次操作
5.4.3 空闲盘区链
（1）分配存储空间
（2）回收存储空间
（3）注意
因为它可以一次为文件分配许多空间，不像空闲盘块链一次只可以分配一个块。
5.5 存储空间管理——位示图法
5.5.1 基本概念
使用一个二进制位表示一个盘块，为1时代表有数据，为0时代表空闲。
5.5.2 注意
①一般来说为了方便管理，位视图一般采用连续的字来表示。比如一台主机的字长为16，则16个盘块的位视图被存储在一个字内。如图所示。
②由盘块号推出（字号、位号）
注意起始位置是从0开始还是从1开始
③由（字号、位号）推出盘块号
5.5.3 分配存储空间
回收存储空间
5.6 存储空间管理方法——成组链接法
UNIX系统采用的方法，适合大型系统
5.7 总结
6 虚拟文件系统与文件挂载
6.1 普通的文件系统
不同的文件介质，他们提供的文件调用接口可能不一样，如图所示。所以程序员在对文件进行操作时，还需要考虑文件存储在什么地方，这显然非常不方便。
6.2 虚拟文件系统
6.2.1 什么是虚拟文件系统
为了解决普通文件系统的缺点，操作系统引入虚拟文件系统，如图所示。它提供了标准的接口，程序员在进行文件调用时只需要使用同一个标准函数，而这些函数具体到不同文件系统中的实现就有虚拟文件系统来完成。
6.2.2 虚拟文件系统的特点
（1）提供标准接口
（2）标准函数具体到不同文件系统中的实现是由虚拟文件系统提供的，因此必须确保文件系统有虚拟文件系统提供给的功能。因此：
（3）不同文件系统中对于文件的表示可能也不一样，FAT文件系统、UFS文件系统的表示方式分别如图。
因此，虚拟文件在打开一个文件后，都会创建一个同一的VNode结构，里面存放了各种要求的信息，如图。注意：VNode只在主存中存在。
这是虚拟文件系统的第三个特点：
注意到VNode中有一个函数功能指针，这相当于是C语言文件操作中和fopen(“test.txt”)时放回的文件对象。方便程序员对文件进行各种操作。
6.3 文件系统挂载
6.3.1 解释
6.3.2 文件系统挂载要做的事情
7 总结
本文PDF文件下载链接：提取码：ikun
操作系统，如默默守护的守夜者，无声地管理硬件与软件的交流，为计算机创造和谐秩序。
它是无形的引导者，让复杂的任务变得井然有序，为用户提供无忧体验。
操作系统的巧妙设计，让计算机变得更加智能高效，让人与科技之间的交流更加顺畅。
在每一次启动中，它如信任的伙伴，带领我们进入数字世界的奇妙旅程。
渴望挑战操作系统的学习路径和掌握进阶技术？不妨点击下方链接，一同探讨更多操作系统的奇迹吧。我们推出了引领趋势的💻OS专栏：《OS从基础到进阶》 ，旨在深度探索OS的实际应用和创新。🌐🔍
