文件系统
概述
文件是大多数应用程序的核心要素，文件系统是操作系统对用户来说最重要的部分之一。
本章的主要内容见下图：
文件，大家耳熟能详的就是的docx、pdf、jpg、MP4等各种后缀文件，根据任务需要文件又分成了文本、图片、表格、视频等类型。那么文件该如何定义呢？
说白了，文件就是一组有意义的信息集合。我们新建一个文件，核心目的就是为了存储一些有用的信息，比如各种申请表、证件照、产品说明等等，一般不会无故创建文件。
文件自身有很多的属性，比如文件名、标识符、类型、位置（路径）、大小、保护信息等。
OS一般都会封装一些常见的文件操作作为系统调用，比如create、delete、open、close等，在Linux中我们可以编写C代码，通过#include <fcntl.h>来引入。
接下来我们来了解一些文件的组织形式。
文件的组织和访问
- 无结构文件：流式文件，文件体为字节流，不划分记录（常见的.txt文件）
- 有结构文件：记录式文件，每条记录由若干数据项组成。
- 累积文件（Pile，文件体为无结构的记录序列，通过特定分隔符来划分记录，各记录大小和组成可变；最简单文件组织，例如数据库的log）
- 索引文件（Indexed file，记录大小不必相同，不必排序。比如词典A/B/C/D……，溢出的新词一般放在最后）
- 顺序文件（Sequential file，主文件和临时文件构成，记录格式固定，大小相同；不过在磁盘中即使排列有序也无法通过算法进行快速查找）
- 索引顺序文件（在顺序文件的基础上根据区间建立索引，甚至可以建立多级索引）
- 哈希文件（Direct/Hash file，主文件和溢出文件组成，通过哈希函数计算出记录在文件中的相对位置）
其中，有结构文件根据记录长度是否相等又分为定长记录和可变长记录。
索引文件在文件记录中快速查找，同时可以对非关键字建立索引（比如姓名），但是一旦修改之后维护成本高。哈希查找速度更快，同时会有溢出文件。现在的通用计算机不会插入一条记录到文件系统，只有数据库管理系统才会有类似的记录。
在记录数量较大时，索引顺序比顺序文件大大缩短检索时间。
顺序文件是N/2，而索引顺序文件（一级索引）是
i
2
+
(
N
/
i
)
2
=
(
i
+
N
/
i
)
2
\frac{i}{2} + \frac{(N/i)}{2} = \frac{(i + N/i)}{2}
2i+2(N/i)=2(i+N/i)，其中i为索引长度，N/i是每个索引映射的文件范围。
举个🌰，1,000,000条记录的文件，顺序文件的平均检索长度为500,000，有1,000条索引项的索引文件，平均检索长度为(1,000+1,000,000/1,000)/2 = 1000。
索引还可以是多级的，二级索引的平均索引长度更短，查询速度更快。
同理，假设i1 = i2 = 100，那么结果作为N‘ =
i
1
2
+
i
2
2
+
N
/
(
i
1
×
i
2
)
2
\frac{i_1}{2}+\frac{i_2}{2}+\frac{N/(i_1 \times i_2)}{2}
2i1+2i2+2N/(i1×i2) = 50+50+50 = 150
管理层次
从下之上，依次是设备驱动程序→基本文件系统→基本 I/O 管理程序→逻辑 I/O 层→实际文件→用户程序（了解即可）
- 磁盘和磁带驱动，统称为设备驱动程序。它们直接与外围设备通信，负责启动一个设备上的I/O 操作，并继续处理I/O 请求的完成。
- 基本文件系统，即物理I/O层，处理与磁盘等系统交换的数据块，关注数据块在辅存中的放置，关注在主存中缓冲的数据块
- 基本I/O管理程序，负责文件I/O 的开始和终止，维护控制结构，辅助磁盘/磁带调度，负责缓冲区的指定和辅存的分配
- 逻辑I/O，使得用户和应用程序可以访问到记录，提供通用的记录I/O 操作的能力，维护有关文件的基本数据
这张图展示了文件管理系统的关键组成部分及其相互关系，包括文件结构、目录管理、访问方法、文件操作功能，以及用户访问控制。系统还涉及物理存储管理，如内存中的物理块、磁盘调度、I/O处理、文件分配与空闲存储管理。每个部分都是文件系统性能和效率的关键，需要良好的协调和优化以确保整个系统的高效运作。
文件目录
目录是由文件说明组成的用于文件检索的特殊文件。文件目录的内容主要是文件访问的控制信息（不包括文件内容），主要作用如下：
- 实现按名存取
- 提高目录检索速度
- 文件共享
- 解决文件重名问题
- 文件控制块（FCB）
文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的有关信息（文件属性），类似进程控制块PCB。
- 文件控制块是文件存在的标志
- 文件控制块构成文件目录项
FCB有多条信息供给系统，包括文件属性、位置（路径）、属主等。而文件属性包括了文件的基本信息、存取控制信息、使用信息等等。
- 文件目录：
把所有的FCB组织在一起，就构成了目录文件，即文件控制块的有序集合，其中一个FCB就称作一个目录项。
文件名在特定的目录里面必须是唯一的，不能重名。
不同系统有不同的命名规则，比如有些系统不支持某些特殊符号，有的支持修改有的不支持。
- 文件目录也是一个文件
- 提供文件名与文件自身的映射（双击进入）
- 一级目录
- 线性结构，一个文件一个表项
- 以文件名为关键字的顺序文件
- 无法管理和组织文件
- 没有解决重名问题
- 二级目录
在主目录下每个用户目录对应一个目录项，解决了不同用户之间的文件重名问题，没有解决用户自身文件重名问题，或者说不能进行文件分类。 - 多级目录
每个用户目录下可以有子目录和文件，彻底解决了文件重名问题
- 文件命名
按名存取，同一路径下不能重名，查找的时候名字是最关键的 - 工作目录
除了绝对路径，我们常常会基于当前目录/工作目录使用相对路径，比如.表示当前目录，..表示父目录。在Linux类OS中，使用pwd指令就可以知道当前的工作目录了。
- 改进的多级文件目录
首先说一下索引节点inode (index node）是指在许多“类Unix文件系统”中的一种数据结构，用于描述文件系统对象（包括文件、目录、设备文件、socket、管道等）。每个inode保存了文件系统对象数据的属性和磁盘块位置。文件系统对象属性包含了各种元数据（如：最后修改时间） ，也包含用户组（owner）和权限数据。
基于iNode改进的多级目录：
- 符号文件目录：只有文件名和内部标识iNode组成树状结构，可以按文件名排序
- 基本文件目录：一张大表，包含iNode和对应文件的全部详细信息。
举个🌰，
分解前，遍历读取才能知道文件在哪个盘块，平均需要13/2 = 6.5，也就是7次
而分解后，先查找符号目录，两个盘块平均就是一次，然后由于iNode大小确定，通过符号目录编号iNode计算出偏移量，然后根据基址变址寻址找到文件的基本目录项，再查看文件权限和数据等，也就是说总共平均是两次。这样确实能有效减少访问硬盘的次数，提高检索速度
到此总结一下，常见的三种文件目录查询技术：
- 目录查询：用户给出文件名，按名寻找目录项（FCB，或索引节点）。
- 线性检索：
- 全路径名：从根开始
- 相对路径：从当前目录开始
- Hash检索：hashed structure，通过键值对进行查询
