type
status
date
slug
summary
tags
category
icon
password
能力模型
能力分类
省赛
全球总决赛
学习进度
中国总决赛
文件的基本概念
文件是以硬盘为载体的存储在计算机上的信息集合。
在系统运行时，九三级以进程为基本单位进行资源的调度和分配；而在用户进行的输入、输出中，则以文件为基本单位。
1 文件的定义
1.1 数据项
数据项是文件系统中最低级的数据组织形式，分为基本数据项和组合数据项。
- 基本数据项：用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。
- 由若干个基本数据项组成，简称组项。
1.2 记录
记录是一组相关数据项的集合，用于描述一个对象在某方面的属性、
为了能够唯一的标识记录，在一个记录的各个数据项中，确定一些数据项，将它们集合称为关键字。关键字是唯一能标识一个记录的数据项。
1.3 文件
文件是指由创建者所定义的，具有文件名的一组组相关元素的集合，可以分为有结构文件和无结构文件。
- 有结构文件：文件由若干个相关记录组成
- 无结构文件：被看成一个字符流
文件是文件系统中最大的数据单位，描述了一个字符流。
1.4 文件、记录、数据项间的层次关系
2 文件的属性
1.文件名：由创建文件的用户决定文件名，主要为了方便用户找到文件，同一目录下不允许有重名文件。
2.标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
3.类型：指明文件的类型。
4.位置：文件存放的路径(让用户使用)、在外存中的地址(操作系统使用，对用户不可见)。
5.大小：指明文件大小。
6.保护信息：对文件进行保护的访问控制信息。
3 文件的分类
（1）按用途分：系统文件、用户文件、库文件；
（2）按文件中的数据形式分：源文件、目标文件、可执行文件；
（3）按存储控制属性分类：只执行文件、只读文件、读写文件；
（4）按组织形式和处理方式分类：普通文件、目录文件、特殊文件。
4 了解文件
（1）文件结构
文件结构包括逻辑结构和物理结构。
- 逻辑结构是用户组织数据的结构形式，数据组织形式来自需求。逻辑结构的组织形式取决于用户。
- 物理结构是操作系统组织物理存储块的结构形式。物理结构的选择取决于文件系统设计者针对硬件结构所采取的策略。
(2)文件系统的访问
- 对于一个文件的访问，常由用户访问权限和文件属性共同限制。
- 在树形目录结构中，文件已被打开后，对文件的访问采用文件描述符。（注意：不是文件名）
文件的逻辑结构
逻辑结构：指在用户看来，文件内部的数据应该如何组织。
1 无结构文件
无结构文件是最简单的文件组织形式，它是由字符流构成的文件，所以又称流式文件，其长度以字节为单位。
源程序、可执行文件、库函数等，采用的就是无结构的文件形式，即流式文件。
对流式文件的访问，采用读/写指针来指出下一个要访问的字符。
2 有结构文件
有结构文件是指由一个以上的记录构成的文件，又称记录式文件。每条记录又有若干个数据项组成。
一般来说，每条记录有一个数据项可作为关键字、
根据每天记录是否等长，又可分为定长记录和可变长记录。
- 定长记录：文件中所有记录的长度都相同，所有记录中的歌数据项都处在记录中相同的位置，具有相同的顺序和长度。
- 可变长记录：文件中各记录的长度不同。
有结构文件按记录的组织形式可分为顺序文件、索引文件、索引顺序文件。
- 顺序文件:一系列记录按某种顺序排列所形成的文件，定长记录。
- 索引文件:记录为可变长度时，建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。
- 索引顺序文件:为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。
2.1 顺序文件
文件是记录的集合，可按照不同的顺序进行排列，可归纳为两种：
- 串结构：各记录之间的顺序与关键字无关，通常是按照存入的先后时间进行排列，检索时必须从头开始顺序依次查找，比较费时。
- 顺序结构：文件中的所有记录按关键字排列，对于定长记录的顺序文件，检索时可采用折半查找，效率较高。
顺序文件的优缺点：
- 适用于对记录进行批量存取，其存取效率是所有逻辑文件中最高的。
- 对于顺序存取设备（如磁带），只有顺序文件才能被存储并能有效地工作。
- 查找、修改、删除单个记录的性能差。
2.2 索引文件
索引文件主要就是解决可变长记录无法随机存取的问题
对于变长记录文件，记录一张索引表，对主文件中的每个记录在索引表中分别设置一个索引表项，其中包含指向记录的指针和记录长度。
索引表是按记录键排序，索引表本身是一个定长记录的顺序文件，方便实现直接存取。
索引文件的组织形式：
对索引文件检索时，根据用户提供的关键字，利用折半查找法去检索索引表，从中找到相应的表项。（增加了存储开销）
2.3 索引顺序文件
索引顺序文件，是顺序文件和索引文件的产物，将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录键值和指向该记录的指针。
在索引顺序文件中，假设N条记录分为，索引表中有个表项，每组有条记录，在查找某关键字的记录时，先顺序查找索引表，需要查找次，然后在主文件对应的组中顺序查找，也需要查找次，因此共需要查找次。
2.4 直接文件或散列文件（Hash File）
给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。
散列文件具有很高的存储速度，但是会引起冲突，即不同关键字的散列函数值可能相同。
文件的物理结构
- 物理结构：文件的数据是如何存放在外存中的
- 文件块：文件的逻辑地址空间也被分为一个一个的文件块【逻辑块号，块内地址】
- 磁盘块：磁盘的存储单元也会被分为一个个 块/磁盘块/物理块
文件分配外存空间时所要考虑的主要问题是：怎样才能有效地利用外存空间和如何提高对文件的访问速度。外存分配方式有连续分配、链接分配和索引分配。文件的物理结构直接与外存分配方式有关，采用不同的分配方式时，将形成不同的文件物理结构。
1 连续分配
连续分配要求为每一个文件分配一组相邻接的盘块，一组盘块的地址定义了磁盘上的一段线性地址。
盘块位于一条磁道上，进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续的读/写多个盘块。
连续分配方式时，把逻辑文件中的记录顺序的存储到邻接的各物理盘块中，形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。
连续分配保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。
系统可通过目录项的"文件物理地址"字段，记录该文件第一个记录所在的盘块号和文件长度。
文件目录中记录存放该文件在外存中的起始块和长度
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）
- 物理块号 = 起始块号 + 逻辑块号
优点：
- 连续分配的文件在顺序读写时速度最快。
- 连续分配可以支持顺序访问 & 随机访问。
缺点：
- 不方便扩展。如果需要新增一个磁盘块，但连续的地方没有位置了，就需要把所有磁盘块一起移动到空间满足的位置。
- 存储空间利用率低，会产生难以利用的磁盘碎片（可用紧凑技术处理碎片，但是时间代价大）。
- 需事先知道文件的长度，根据其大小，在存储空间中找出一块大小足够的存储区，将文件装入。
2 链接分配
链接分配：通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，形成的纹理文件称为链接文件。
链接分配采用离散分配的方式，可以为文件分配离散的磁盘块（消除了外部碎片），分为隐式链接 & 显示链接。
2.1 隐式链接
隐式链接分配方式问题在于：只适合顺序访问，对随机访问的效率低下。
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）
- 从目录项中找到起始块号（即 0 号块），将 0 号逻辑地址读入内存，由此知道 1 号逻辑块存放的物理地址，于是读入 1 号逻辑块，再找到 2 号逻辑块，以此类推...
- 因此，读入 i 号逻辑块，总共需要 i + 1 次磁盘 I/O
扩展文件：随便找到一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的 FCB
优点：方便文件扩展，不会有碎片问题，外存利用率高
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个磁盘块的指针也需要消耗一定的存储空间
2.2 显式链接
显示链接用于连接文件个物理块的指针，显示的存放在内存的一张链接表中，该表在整个磁盘仅设置一张。
在该表中，每一条链的链首指针所对应的盘块号，均作为文件地址被填入响应文件的 FCB 的物理地址字段中，
由于分配给文件的所有盘块都放在该表中，该表称为文件分配表（FAT File Allocation Table）。
注意：一个磁盘仅设置一张 FAT。开机时，将 FAT 读入内存，并常驻内存。FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此，物理块号可以隐含
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）
- 从目录项中找到起始块号，若 i > 0，则查询内存中的文件分配表 FAT，往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
缺点：文件分配表的需要占用一定的存储空间
3 索引分配
3.1 单级索引分配方式
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块。
注：在显式链接的链式分配方式中，文件分配表FAT 是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）
- 从目录项中可知索引表存放位置，将索引表 从外存读入内存，并查找索引表即可只 i 号逻辑块在外存中的存放位置
可见，索引分配方式可以支持随机访问。 文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间。
3.2 多级索引分配方式
建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据 文件大小的要求再建立第三层、第四层索引块。
假设磁盘块大小为 1KB，一个索引表项占 4B，则一个磁盘块只能存放 256 个索引
若某文件采用两层索引，则该文件最大长度可以到 256 * 256 * 1KB = 65536KB = 64MB
可以根据逻辑块号计算出应该查询索引表中的表项：
- 如：要访问 1026 号逻辑块，则 1026 / 256 = 4，1026 % 256 = 2
- 一级索引的 4 号块，二级索引的 2 号块
采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读写操作
3.3 混合索引分配方式
多种索引方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引块），还包含两级间接索引（指向两层索引表）
3.4 总结
早期 Unix 文件系统是组合了前面的文件存放方式的优点，如下图：
4 文件系统相关计算
（1）文件占用的磁盘块数目
- 采用类似于Linux的inode存储结构
一个文件占用的块数=直接指针数=直接指针+一级间接指针*（磁盘块/地址位数）
一个间接指针可以存放的直接指针数 = 磁盘块/地址位数
（2）文件系统支持的最大文件尺寸
- 索引分配
n+1级索引块可以指向n级索引块的数目 = 磁盘块大小 / 索引号大小
最大文件尺寸 = 最大可以指向的磁盘块数 * 磁盘块的大小
（3）创建文件数量上限
创建文件数量上限 = 索引节点数量上限 = 2^{索引节点位数}
文件的目录结构
OS通过文件目录实现对文件的管理，文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。
文件系统实现按名存取主要是靠查找文件目录实现的。
1 文件控制块
1.1 概念
- 文件控制块(FCB)：描述和控制文件的数据结构，使得文件能进行正确的存取。
- 文件目录：文件控制块的有序集合，一个文件控制块就是一个文件目录项。一个文件目录可被当作一个文件，称为目录文件。
1.2 PCB包含的内容
文件控制块包含三类信息，分别是基本信息、存取控制信息和使用信息。
- 基本信息
- 文件名：标识文件的符号名；
- 文件物理位置：文件在外存上的存储位置，包括存放文件的设备名，文件在外存上的起始盘块号、文件占用的盘块数、字节数的文件长度；
- 文件逻辑结构：指示文件是流式文件还是记录式文件、记录数；文件是定长记录还是变长记录。
- 文件的物理结构：指示文件是顺序文件，还是链接式文件或索引文件。
- 存取控制信息
- 文件主的存取权限，核准用户的存取权限及一般用户的存取权限。
- 使用信息
- 文件的日期及当前使用信息，包括已打开文件进程数，是否被其它进程锁住，文件在内存中是否已被修改但尚未拷贝到盘上。
2 索引节点
2.1 索引节点的引入
文件目录存放在磁盘，文件很多时，文件目录要占用大量的盘块。
- 查找目录的过程：先将存放目录文件的第一个盘块中的目录调入内存，再把用户给定的文件名和目录项中的文件逐一比较。未找到指定文件，将下一盘块中的目录项调入内存。
- 检索目录的过程：只用到文件名，仅当找到一个目录项时，才需要从该目录项中读出该文件的物理地址，其它对描述文件的信息，检索目录时不许用。
文件名和文件描述符分开，使文件描述信息单独形成一个称为索引节点的数据结构，简称i节点。
文件目录中，每个目录项紧由文件名和指向该文件所对应的i节点的指针所构成。
2.2、磁盘索引节点
存放在磁盘上的索引节点，每个文件唯一的一个磁盘索引节点，包含以下内容：
- 文件主标识符
- 文件类型
- 文件存取权限
- 文件物理地址:每一个索引节点汇总含有13个地址项，iaddr(0) ~ iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号。
- 文件长度:以字节为单位的文件长度。
- 文件连接计数:本文件系统中所有指向该文件名的指针计数。
- 文件存储时间
2.3、内存索引节点
存放在内存中的索引节点，文件被打开时，要将磁盘索引节点拷贝到内存索引节点中，便于后续使用。包含以下内容：
- 索引节点编号：表示内存索引节点
- 状态：指示i节点是否上锁或被修改
- 访问计数：当有一进城要访问此i节点时，将该访问计数加1，访问完再减1
- 文件所属文件系统的设备号
- 连链接指针，设置有分别指向空闲链表和散列队列的指针。
3 目录结构
3.1 单级目录结构
整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项包含文件名、文件拓展名、文件长度、文件类型、文件物理地址以及其他文件属性、为表明每个目录项是否空闲，设置一状态位。
- 单级目录实现了按名存取，但是查找速度慢，不允许文件重名，不便于实现文件共享。
- 在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中
- 删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间，清除该目录项。
3.2 两级目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User File Directory）。
- 主文件目录MFD：在主文件目录中，每个用户目录文件都占有一个目录项，目录项中包括用户名和指向该用户目录文件的指针。
- 用户文件目录UFD：UFD由用户所有文件的文件控制块组成，用于解决单级目录的问题。
当有了UFD后，创建新文件时，OS只需检查该用户UFD，判定该UFD中是否已有同名的另一个文件。若有，为新文件重新命名，若无，在UFD中建立一个新目录项，将文件名及相关属性填入目录项中，并置状态位为1。
优点：
- 提高了检索目录的速度；
- 在不同的用户目录中，可使用相同的文件名；
- 不同用户可以使用不同的文件名来访问系统中的同一个共享文件。
缺点：
- 对于某一个用户来说，不能对自己的文件进行分类管理
3.3 树形目录结构
多级目录，也被称为树型目录结构，主目录被称为根目录，把数据文件称为树叶，其他的目录均作为树的结点。
多级目录结构如下：
方框表示目录文件，圆圈标识数据文件。
优点：
- 以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
缺点：
- 树形结构不便于实现文件的共享
3.4 无环图目录结构
在树形目录结构的基础上，增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更加方便的实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的 FCB、并使共享计数器减 1，并不会直接删除共享结点。只有共享计数器减为 0 时，才删除结点
注意：共享和复制是不同的。
空闲分区管理
划分：将物理磁盘划分为一个个的文件卷（逻辑卷、逻辑盘），如 C 盘、D 盘等
初始化：把每个文件卷划分为目录区、文件区
- 目录区：存放文件目录信息（FCB）、用于磁盘存储空间管理的信息
- 文件区：用于存放文件数据
1 空闲表法
系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等。空闲盘块表如下：
- 分配：空闲盘区的分配与内存的动态分配类似，采用首次适应、最佳适应、最坏适应算法等。
- 回收：系统对用户释放的存储空间做回收时，采取类似于内存回收的方法即合并。
2 空闲链表法
空闲链表法：将所有空闲盘区拉成一条空闲链，根据构成的链所用基本元素的不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链。（难以得到连续的空间）
- 空闲盘块链：将磁盘上所有空闲空间，以盘块为单位拉成一条链。
- 分配：若某文件申请 K 个盘块，则从链头依次摘下 K 个盘块分配，并修改空闲链的链头指针
- 回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针（适用于离散分配的物理结构）
- 空闲盘区链：将磁盘上所有的空闲盘区(每个盘区包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应能有指明本盘区大小信息(盘块数)。
- 分配：若某文件申请K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据
- 回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾（离散分配、连续分配都适用）
3 位示图法
位示图：利用二进制的以为来表示磁盘中一个盘块的使用情况，当值为0时，表示对应盘块空闲；为1时，表示已分配。
所有盘块所对应的位构成一个集合，称为位示图。
位示图可描述为一个二维数组。
（字号，位号）= （i，j）的二进制对应的 盘块号 b = n * i + j
- 分配
- 顺序扫描位示图，找到 K 个相邻或不相邻的 “0”。
- 根据字号、位号算出对应的盘块号，将相应盘块分配给文件将相应位设置为 “1”。
- 找到之前要扫描n/r，其中n为总项数，r为空闲为0的项数
- 回收
- 根据回收的盘块号计算出对应的字号、位号。
- 将相应二进制位设为 “0”。
优点：容易找到空闲盘块，占用空间少，可保存在内存中，每次进行盘区分配时，无需把盘区分配表读入内存，节省很多磁盘启动操作。
4 成组链接法
空闲表与空闲链表法不适用大型文件系统，会使表太长。
成组链表法适用于大型文件系统。
4.1、空闲盘块的组织
空闲盘块号栈：存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号数N。
栈是临界资源，每次仅允许一个进程访问，系统为栈设置了锁。
文件区中的所有空闲盘块被分成若干个组；
每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的中S.free(0) ~ S.free(99)。如此，各组的第一个盘块可链成一条链。
将第一组含有的盘块总数N和所有的盘块号记入空闲盘块栈中，作为当前可供分配的空闲盘块号。
3.2、空闲盘块的分配与回收
分配：先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已栈底，即S.free(0)，表示这是当前栈中最后一个可分配的盘块号。由于该盘块号所对应的盘块中记有下一组可用的盘块号，因此需要调用个磁盘读过程，将占地盘块号对应的盘块内存读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后在分配一相应的缓冲区(作为盘块的缓冲区)，最后把栈中的空闲盘块数减1并返回。
回收：将回收盘块的盘块号记录空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当占中盘块数目达100，标识栈已满，将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。
文件共享与保护
不同的进程或用户使用同一个文件，实际上文件的实体只有一个。UNIX中，文件共享通过硬链接或软链接实现文件共享。对于一个文件的访问，常由用户访问权限和文件属性共同限制。
1 基于索引节点的共享方式（硬连接）
文件的物理地址及其它的文件属性属性，存放在索引节点中，文件目录中只设置文件名及指向相应索引节点的指针。
- count:在索引节点中有一个链接计数count，表示链接到本索引结点上的用户目录项数目。
当创建一个硬链接时，实际上是创建了一个指向同一物理文件的新文件路径。这个新路径与原始文件路径完全相同，它们都指向同一个文件的实际数据块。因此，无论使用哪个路径访问该文件，都会看到同样的文件内容。
硬链接的局限：
- 不能用于链接目录
- 不能跨越文件系统的范围
不同进程打开一个文件时，获得的文件描述符是独立的，其读写指针的位置不同，保存在各自的用户打开文件表中。
2 利用符号链实现文件共享（软链接）
软链接（Symbolic Link），也被称为符号链接或软连接，是操作系统中的一种特殊文件类型。软链接是一个指向文件或目录的文件，它包含了指向实际文件或目录的路径。
软链接可以理解为一个快捷方式或别名，它创建了一个新的文件路径，该路径指向另一个文件或目录的位置。与硬链接不同，软链接本身并不包含实际文件的数据，它只是一个指向文件的路径。
省流：快捷方式
符号链方式实现文件共享时，只是文件主才拥有指向其索引节点的指针，而共享该文件的其他用户则只由该文件的路径名，并不用于指向其索引节点的指针。
- 缺点：每次访问共享概念股文件时，需要根据给定的文件路径名，查找目录，直到找到该文件的索引结点。每次访问共享文件时，要多次的读盘。
- 优点：可以连接目录，通过计算机网络访问任何地方计算机中的文件。
3 对比
特性 | 硬链接 (Hard Link) | 软链接 (Symbolic Link) |
指向的内容 | 文件的 inode（数据块） | 文件的路径 |
文件的独立性 | 硬链接和原文件共享同一个 inode | 软链接有自己独立的 inode 和路径内容 |
跨文件系统 | 不支持 | 支持 |
删除文件后的行为 | 文件数据会在删除最后一个硬链接时删除 | 目标文件删除后，软链接会失效 |
支持目录 | 硬链接 (Hard Link) | 支持 |
特性性能 | 快速，直接引用数据块 | 需要解析路径，略有性能开销 |
4 文件保护
目录操作与文件操作并不相同，因此需要不同的保护机制。
4.1 口令保护
为文件设置一个口令，用户请求时必须提供口令
口令一般存放在对应的 FCB 或索引结点中
优点：保存口令的空间开销小，验证口令的时间开销也小
缺点：正确的口令存放在系统内部，不安全
4.2 加密保护
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密
优点：保密性强，不需要在系统中存储密码
缺点：编译/译码，或者加密/解密 需要花费一定的时间
4.3 访问控制
在每个文件的 FCB（或索引结点） 中增加一个访问控制列表（ACL），该表中记录了各个用户可以对该文件执行的操作
以组为单位：
文件系统的操作
文件属于抽象数据类型，包含以下操作
- 创建文件
- 删除文件
- 读文件
- 写文件
- 打开文件
- 关闭文件
只要完成了文件打开Open（）系统调用，后面再使用read（），write（），Lseek（），close（）等文件操作的系统调用，就不在使用文件名，而使用文件描述符。
1 创建文件（create 系统调用）
进行 Create 系统调用时，需要提供几个主要参数：
- 所需的外存空间大小(如：一个盘块，即 1 KB)
- 文件存放的路径地址(如：E:/操作系统 )
- 文件名(操作系统会默认取一个名字，如：新建文本文档.txt)
操作系统在处理 Create 系统调用时，主要做了两件事：
- 在外存中找到文件所需要的空间（通过空闲分区管理中的方法找到空闲空间）
- 根据文件存放路径找到该目录对应的目录文件，在目录文件中创建该文件对应的目录项，包括：文件名、文件的外存信息等
2 删除文件（delete 系统调用）
进行 Delete 系统调用时，需要提供几个主要参数：
- 文件存放路径（“D:/demo”）
- 文件名（“test.txt”）
操作系统在处理 Create 系统调用时，主要做了几件事：
- 根据文件存放路径找到该目录对应的目录文件，从目录文件中找到该文件对应的目录项
- 根据该目录项中记录的文件在外存的存放位置、文件大小信息，回收文件占用的磁盘块（回收磁盘块，根据空闲分区管理中的方法回收空闲块）
- 从目录表中删除对应的目录项
3 读文件（read 系统调用）
进程使用 read 系统调用完成写操作。需要指明是哪个文件（在支持 “打开文件” 操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需 要指明要读入多少数据（如：读入 1KB）、指明读入的数据要放在内存中的什么位置
操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
4 写文件（write 系统调用）
进程使用 write 系统调用完成写操作，需要指明是哪个文件（在支持“打开文件”操作的系统中，只需 要提供文件在打开文件表中的索引号即可），还需 要指明要写出多少数据（如：写出 1KB）、写回外存的数据放在内存中的什么位置
操作系统在处理write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存
5 打开文件（open 系统调用）
在对文件进行操作之前，要求用户先使用 open 系统调用 “打开文件”，需要提供的几个主要参数：
- 文件存放路径（“D:/demo”）
- 文件名（“test.txt”）
- 要对文件的操作类型（如：r 只读；rw 读写等）
操作系统在处理 Create 系统调用时，主要做了几件事：
- 根据文件存放路径找到相对应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的的操作权限
- 将目录项复制到内存的打开文件表中，并将对应表目的编号返回给用户，之后用户使用打开文件表的编号来指明要操作的文件
6 关闭文件（close 系统调用）
进程使用完文件后，要 “关闭文件” 操作系统在处理 Close 系统调用时，主要做了几件事：
- 将进程的打开文件表相应表项删除
- 回收分配给该文件的内存空间等资源
- 系统打开文件表的打开计数器 count 减 1，若 count = 0，则删除对应表项
其他
1 文件系统结构（以Linux为例）
前面提到 Linux 是用位图的方式管理空闲空间，用户在创建一个新文件时，Linux 内核会通过 inode 的位图找到空闲可用的 inode，并进行分配。要存储数据时，会通过块的位图找到空闲的块，并分配，但仔细计算一下还是有问题的。
数据块的位图是放在磁盘块里的，假设是放在一个块里，一个块 4K，每位表示一个数据块，共可以表示
4 * 1024 * 8 = 2^15 个空闲块，由于 1 个数据块是 4K 大小，那么最大可以表示的空间为 2^15 * 4 * 1024 = 2^27 个 byte，也就是 128M。也就是说按照上面的结构，如果采用「一个块的位图 + 一系列的块」，外加「一个块的 inode 的位图 + 一系列的 inode 的结构」能表示的最大空间也就 128M，这太少了，现在很多文件都比这个大。
在 Linux 文件系统，把这个结构称为一个块组，那么有 N 多的块组，就能够表示 N 大的文件。
下图给出了 Linux Ext2 整个文件系统的结构和块组的内容，文件系统都由大量块组组成，在硬盘上相继排布：
最前面的第一个块是引导块，在系统启动时用于启用引导，接着后面就是一个一个连续的块组了，块组的内容如下：
- 超级块，包含的是文件系统的重要信息，比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。
- 块组描述符，包含文件系统中各个块组的状态，比如块组中空闲块和 inode 的数目等，每个块组都包含了文件系统中「所有块组的组描述符信息」。
- 数据位图和 inode 位图， 用于表示对应的数据块或 inode 是空闲的，还是被使用中。
- inode 列表，包含了块组中所有的 inode，inode 用于保存文件系统中与各个文件和目录相关的所有元数据。
- 数据块，包含文件的有用数据。
你可以会发现每个块组里有很多重复的信息，比如超级块和块组描述符表，这两个都是全局信息，而且非常的重要，这么做是有两个原因：
- 如果系统崩溃破坏了超级块或块组描述符，有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本，该信息是可能恢复的。
- 通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转，这可以提高文件系统的性能。
不过，Ext2 的后续版本采用了稀疏技术。该做法是，超级块和块组描述符表不再存储到文件系统的每个块组中，而是只写入到块组 0、块组 1 和其他 ID 可以表示为 3、 5、7 的幂的块组中。
2 虚拟文件系统
2.1 VFS定义和作用
文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了中间层，这个中间层就称为虚拟文件系统（Virtual File System，VFS）。
VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样程序员不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。
在 Linux 文件系统中，用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间的关系如下图：
Linux 支持的文件系统也不少，根据存储位置的不同，可以把文件系统分为三类：
- 磁盘的文件系统，它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统。
- 内存的文件系统，这类文件系统的数据不是存储在硬盘的，而是占用内存空间，我们经常用到的
/proc和/sys文件系统都属于这一类，读写这类文件，实际上是读写内核中相关的数据数据。
- 网络的文件系统，用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等。
文件系统首先要先挂载到某个目录才可以正常使用，比如 Linux 系统在启动时，会把文件系统挂载到根目录。
2.2 VFS内部结构和对象类型
VFS层通过定义一个清晰的VFS接口，以将文件系统的通用操作和具体实现分开。多个VFS接口的实现可以共存在同一台机器上，它允许访问已装在本地的多个类型的文件系统。
VFS提供了在网络上唯一标识一个文件的机制。VFS基于称为vnode的文件表示结构，该结构包括一个数值标识符以表示位于整个网络范围内的唯一文件。该网络范围的唯一性用来支持网络文件系统。内核中为每个活动节点（文件或目录）保存一个vnode结构。
VFS根据文件系统类型调用特定文件类型操作以处理本地请求，通过调用NFS协议程序来处理远程请求。文件句柄可以从相应的vnode中构造，并作为参数传递给程序。它的下一层实现文件系统类型或远程文件系统协议。
下面简要的讨论一下Linux中的VFS结构。Linux VFS定义的4种主要对象类型是：
- 超级块对象（superblock object）表示整个文件系统。
- 索引节点对象（inode object）表示一个单独的文件。
- 文件对象（file object）表示一个打开的文件。
- 目录项对象（dentry object）表示一个单独的目录项（或者称作目录条目）。
VFS对每种类型的对象都定义了一组必须实现的操作。这些类型的每一个对象都包含了一个指向函数表的指针。函数表列出了实际上实现特定对象的操作函数。
所有超级块对象都以双向循环链表的形式链接在一起，对象的自旋锁（sb_lock）保护链表免受多处理器系统上的同时访问。
3 文件系统挂载
文件系统挂载(mounting)，即文件系统安装/挂载。
文件系统挂载需要做的事情有：
① 在 VFS 中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息，包含文件系统类型、容量大小等。
② 新挂载的文件系统，要向 VFS 提供一个函数地址列表。
③ 将新文件系统加到挂载点(mount point)，也就是将新文件系统挂载在某个父目录下。
4 崩溃一致性问题
如何在出现断点或系统崩溃的情况下，更新持久数据结构？
文件系统崩溃一致性(Crash Consistency)是指在文件系统发生崩溃、断电或其它不可预见的故障后，文件系统能够保证数据的一致性和完整性，并能够恢复到一个合法且可操作的状态，确保系统重新启动或恢复之后，数据不会出现损坏、丢失或不一致的情况。
以ext4 文件系统举例，当我们创建一个文件系统的时候，有下面4个步骤：
- 查找空闲 inode：通过检查 inode bitmap找到一个空闲的 inode，并在 inode bitmap中标记为已使用。
- 分配数据块：通过检查block bitmap找到空闲的数据块，并在block bitmap中标记为已使用。
- 更新 inode：将新文件的元数据写入 inode table中的相应位置。
- 更新目录项：在目标目录的 inode 数据块中添加一个新的目录项，包含文件名和对应的 inode 号。
因为磁盘是以扇区为最小单位，所以上面4个步骤不可能一次全部写入到磁盘中去，在1到4步骤中间的任意一个时间点系统突然崩溃，都会导致文件系统不一致。比如在2~3步骤中间断电，就会造成inode bitmap、block bitmap中标记已经使用，但是没有实际的文件与之对应，如果不回收，那么这几个块就可能永远不会被使用。
解决文件系统一致性的问题，常用的方法有：日志、写时复制、Soft Update（对文件系统所有写入操作进行排序，确保永远不会产生不一致的情况）、日志文件系统、基于反向指针的一致性，它们各有优缺点，目前并没有哪种方案可以适用所有场景。
（1）fsck的解决方法
- fsck：file system checker，一种早期系统用来处理崩溃一致性问题的方法。
- 目标：确保文件系统元数据一致性
- 思路：不处理不一致的发生，而是在发生后修复他们（重启的时候）
- fsck原理：在系统启动时运行fsck程序，处理不一致的情况
- 超级块检查：检查超级块是否合理
- 空闲块检查：扫描inode、间接块、双重间接块等等，以这些信息去更新bitmap（也就是说，比起bitmap，系统更信任inode的内容）
- inode状态：如果存在问题并且不易修复，则fsck直接清除该inode，并且更新相应的inode位图
- inode链接：检索引用计数，如果计算的计数与inode中的计数不一样，则更新inode中的计数；如果没有目录引用inode，则将该文件移动到lost + found目录
- 检查重复：如果两个inode引用同一个数据块，则会清除明显不对的inode，或者复制一份
- 坏块检查：扫描指针，如果指针显然不正确，则会删除该指针
- 目录检查：检查每个目录是否有.和…，引用的每个inode是否已经分配等等
- fsck的问题
- 太慢。每次启动系统都需要全面扫描一遍磁盘
- 很没必要。文件系统崩溃只是极少发生的情况，而且出问题的一般都是少数文件，因此每次都扫描所有文件的代价太大了
（2）文件日志系统
<1>实现思想
- 思想：借鉴数据库的日志思想，每次写磁盘之前，都先写日志
- 实现思路：为磁盘加上一个journal段，专用于存放日志
在ext4文件系统中，有一个独立的日志数据区，它的基本思想是：先将一组操作记录到日志区(日志提交完成)，然后再去实现这些操作(应用事务完成)，实现结束之后再把日志擦除(日志清理完成)。
日志处理时序流程图
事务开始:文件系统开始一组更新操作，并开启一个新的事务
收集日志:收集所有即将修改的数据(以及在 Journal 模式下的数据)
提交日志:更新日志头，标记该事务已经提交(commit)
应用事务:将日志中的修改应用到文件系统，将数据和元数据写入最终位置
清理日志:事务完成后，日志系统清理已提交的日志记录
<2>通过日志进行恢复
文件系统有了日志功能之后，在文件系统崩溃或是突然断电后就可以通过日志保持文件系统的一致性。基本的流程是，文件系统挂载后，系统会去扫描日志区域，看是否有未完成的事务，如果有，则判断该事件是否有提交：
- 如果未提交，本次修改操作就直接丢弃
- 如果有提交，根据日志记录的信息，重新执行修改操作
<3>优缺点
文件系统的日志功能，它的主要优点有两个：
- 可以保持一致性： 不会因为某些异常导致整个文件系统异常
- 可以减少文件系统检查时间： 传统使用fsck去扫描整个磁盘进行检查，非常耗时，有了日志功能后，直接扫描日志信息就可以了。
文件系统引入日志之后，明显的缺点有：
- 影响性能： 所有的操作都需要先写日志，再执行具体的操作，在高负载的情况下会导致IO压力增加，从而降低系统的整体性能。
- 写热点: 因为日志区会频繁的写入和擦除，对于有擦写次数限制的flash来说，比较容易把日志区域写穿。
📎 参考文章
- 无虑的小猪——操作系统部分文章合集
有关问题，欢迎您在底部评论区留言，一起交流~
- Author:Koreyoshi
- URL:https://Koreyoshi1216.com/article/13cc7b13-c6a7-80fc-90bc-f378f4bceeab
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!