考研笔记之操作系统（四） - 文件管理

文件管理

1. 简介
- 1.1 前情回顾
- 1.2 文件的属性
- 1.3 文件内部数据的组织方式
- 1.4 操作系统向上提供的文件功能
- 1.5 文件应如何放在外存
2. 文件的逻辑结构
- 2.1 无结构文件
- 2.2 有结构文件
- - 2.2.1 顺序文件
  - 2.2.2 索引文件
  - 2.2.3 索引顺序文件
  - 2.2.4 多级索引顺序文件
3. 文件目录
- 3.1 基本概念
- 3.2 文件控制块（FCB）
- 3.3 索引节点
- 3.4 目录相关操作
- 3.5 目录结构
- - 3.5.1 单级目录结构
  - 3.5.2 两级目录结构
  - 3.5.3 多级目录结构
  - 3.5.4 无环图目录结构
4. 文件的物理结构
- 4.1 文件块（磁盘块）
- 4.2 连续分配
- 4.3 链接分配
- - 4.3.1 隐式链接
  - 4.3.2 显示链接
- 4.4 索引分配
- 4.5 总结
5. 逻辑结构VS物理结构
6. 文件存储空间管理
- 6.1 存储空间的划分与初始化
- - 6.1.1 文件卷（逻辑卷）的概念
  - 6.1.2 目录区与文件区
- 6.2 空间管理的方法
- - 6.2.1 空闲表法
  - 6.2.2 空闲链表法
  - 6.2.3 位示图法
  - 6.2.4 成组链接法
- 6.3 总结
7. 文件的基本操作
- 7.1 创建文件
- 7.2 删除文件
- 7.3 打开文件
- 7.4 关闭文件
- 7.5 读文件
- 7.6 写文件
8. 文件共享
- 8.1 硬链接
- 8.2 软连接
- 8.3 总结
9. 文件保护
- 9.1 口令保护
- 9.2 加密保护
- 9.3 访问控制
- 9.4 总结
10. 文件系统的层次结构
11. 文件系统的全局结构
12. 虚拟文件系统
- 12.1 普通的文件系统
- 12.2 虚拟文件系统
- 12.3 文件系统的挂载

1. 简介

1.1 前情回顾

1.2 文件的属性

文件名：文件的名称，用于标识文件。通常包括文件扩展名，如 .txt、.docx 等。

文件路径：文件在文件系统中的位置，表示为一个路径。绝对路径是从根目录开始的完整路径，例如 /home/user/document.txt。

文件大小：文件占用的存储空间大小，通常以字节为单位。

文件类型：指文件的类型，如文本文件、二进制文件、图像文件、可执行文件等，通常通过文件扩展名识别。

创建时间：文件最初被创建的时间戳。

修改时间：文件最后一次被修改的时间戳。

访问时间：文件最后一次被读取的时间戳。

文件权限：定义了哪些用户或用户组可以读取、写入或执行该文件。例如在 Linux 系统中，权限通常用 rwx (读、写、执行) 表示。

文件所有者：文件的所属用户和用户组信息，决定了谁拥有该文件及其权限设置。

隐藏属性：某些文件可以设置为隐藏文件，使其在常规文件列表中不显示。

只读属性：文件可以被设置为只读，防止修改或删除。

符号链接或硬链接（在一些操作系统中）：可以指向文件或文件夹的快捷方式，符号链接是指向文件路径的引用，硬链接是指向文件的物理数据。

1.3 文件内部数据的组织方式

无结构文件

指文件内部的数据没有特定的组织方式或格式规范，通常也被称为非结构化文件。这类文件包含的数据没有固定的格式或严格的逻辑关系，数据通常以自由形式存在，因此解析和处理它们需要依赖外部的规则或人类理解。

有结构文件

指内部数据按照预定义的格式或规则进行组织和存储的文件。这类文件具有固定的数据模式，文件中的数据可以根据某种结构轻松解析、读写和查询。通常，它们用于存储和传输结构化信息，如表格、数据库记录或配置参数。

1.4 操作系统向上提供的文件功能

文件创建与删除

创建文件：操作系统提供创建新文件的功能，允许用户或应用程序在文件系统中生成空文件以存储数据。
删除文件：提供删除已有文件的功能，以释放存储空间。

文件读写

读取文件：允许用户或程序从文件中读取数据，通常通过打开文件后按需读取内容。
写入文件：支持向文件中写入数据，修改文件内容或将新数据存储到文件中。

文件打开与关闭

打开文件：在对文件进行读写之前，操作系统需要提供打开文件的功能，建立文件的操作上下文。
关闭文件：在文件操作完成后，必须关闭文件，释放相关的系统资源。

文件定位（文件指针管理）

文件定位（seek）：支持移动文件的读写指针，允许程序从文件的任意位置读取或写入数据，而不仅仅是从头开始。

文件属性管理

查看文件信息：提供基本的文件属性查询功能，比如文件大小、创建时间、修改时间、权限等。
修改文件属性：支持更改文件的元数据，如修改权限、时间戳等。

权限与安全控制

文件权限管理：操作系统提供基本的权限控制，决定哪些用户或进程可以读取、写入或执行某个文件。

这些功能构成了文件管理的基本接口，是操作系统与应用程序或用户交互的最基础层，确保文件可以被有效地创建、存取和管理。

文件共享

指多个用户或进程通过操作系统提供的机制访问和使用同一个文件。操作系统支持的文件共享功能通常包括权限管理、文件锁定、多用户访问、以及网络文件共享。

文件保护

用于确保文件的安全性和完整性，防止未经授权的访问、修改、或破坏。文件保护功能通过权限管理、加密、备份、文件锁定等技术实现。

1.5 文件应如何放在外存

与内存一样，外存也是由一个个存储单元组成，每一个存储单元可以存储一定量的数据（比如1B）。每个存储单元对应一个物理地址。

类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址（如本例中，一块包含2¹⁰个地址，即1KB）。同样类似的是，文件的逻辑地址也可以分为（逻辑块号，块内地址），操作系统同样需将逻辑地址转换为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块的大小。

操作系统以”块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但它依然需要占用 1KB 的磁盘块。外存中的数据读入内存时同样以块为单位。

2. 文件的逻辑结构

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。

2.1 无结构文件

无结构文件是指文件内部的数据没有特定的组织方式或格式规范，通常也被称为非结构化文件。这类文件包含的数据没有固定的格式或严格的逻辑关系，数据通常以自由形式存在，因此解析和处理它们需要依赖外部的规则或人类理解。

特点：

无固定格式：文件中的数据没有预定义的结构或数据模型，数据可以以任何形式存储，如文本、图片、音频等。
难以解析：由于缺乏统一的格式，计算机很难直接处理或解析这些文件，需要额外的工具或方法（如自然语言处理、图像识别等）来提取信息。
自由度高：无结构文件可以包含多种类型的内容（如文本、图像、视频等），且这些内容没有特定的顺序或模式。
大小和格式不一致：文件可以是任意大小，可能包含不同形式的数据类型，如文本、二进制数据混合在一起。
信息检索困难：因为数据缺乏明确的索引和结构化信息，通常无法高效地搜索或查询其中的特定信息。

常见的文件类型：

纯文本文件（文本块）：虽然文本文件本身看似有一定的结构（如行和段落），但实际上并没有标准化的字段或记录划分。例如，一个未经处理的日志文件或手写的文章就是无结构文件。
- 示例：小说、手写的备忘录、邮件正文等。
图像文件：图像文件（如 JPEG、PNG）以像素数据存储视觉信息，但像素之间没有严格的结构关系。
- 示例：扫描的文档、拍摄的照片。
音频和视频文件：音频文件（如 MP3）和视频文件（如 MP4）虽然有特定的编码方式，但其内容（如语音、音乐或图像）本身没有结构，语义信息隐藏在音频波形或视频帧中。
- 示例：录音、电影文件。
PDF 文件：尽管 PDF 文件可以包含结构化文本和图像，但许多 PDF 文档的内容被视为无结构的，尤其是当文本部分以图片形式存在或未按逻辑划分时。
- 示例：扫描的书籍、合同等。
网页（HTML）文件：网页虽然有一定的 HTML 标签，但从信息语义的角度来看，数据内容本身往往是无结构的，除非有特定的格式或标准来组织内容（如表格或数据库嵌入）。
- 示例：博客文章、新闻页面等。
多媒体文件：包含图片、音频、视频混合在一起的数据文件，如 PowerPoint 演示文稿。
- 示例：演示文稿、视频片段、音乐专辑。

2.2 有结构文件

有结构文件是指内部数据按照预定义的格式或规则进行组织和存储的文件。这类文件具有固定的数据模式，文件中的数据可以根据某种结构轻松解析、读写和查询。通常，它们用于存储和传输结构化信息，如表格、数据库记录或配置参数。

特点：

预定义的数据结构：文件的数据是按照特定的规则或格式组织的，文件的每个部分都代表特定的信息。例如，字段和记录之间有明确的划分。
易于解析：因为数据有明确的结构和格式，计算机程序可以快速读取、写入和解析这些文件。
数据一致性强：由于有统一的格式和规则，文件中的数据通常符合一定的标准，减少了不一致性。
高效存储和检索：由于数据结构化，可以通过索引或其他方式高效存储和检索信息。

常见的文件类型：

CSV（逗号分隔值文件）
- 结构：每一行表示一条记录，行内的字段用逗号或其他分隔符分开。
- 特点：简单易用，数据以二维表格形式存储，适合存储结构化的表格数据。
- 应用：常用于导出数据库表、电子表格文件，或在不同系统之间传递数据。
示例：
```
Name, Age, City
Alice, 30, New York
Bob, 25, San Francisco
```
JSON（JavaScript Object Notation）
- 结构：基于键值对的嵌套数据格式，支持数组和对象的复杂嵌套结构。
- 特点：易于人类阅读和编写，广泛用于数据交换，特别是 Web 服务和 API。
- 应用：常用于前后端数据传输、配置文件和 RESTful API 的数据交换格式。
示例：
```
{"name": "Alice","age": 30,"city": "New York","skills": ["Python", "Java", "SQL"]
}
```
XML（可扩展标记语言）
- 结构：通过标签 <tag> 来定义数据的层次结构，数据组织成嵌套的标签对，适合复杂数据的层次表达。
- 特点：严格的语法要求，数据之间有明确的层次关系，适合表达复杂的结构化数据。
- 应用：用于配置文件、Web 服务的消息传递、文档和数据交换格式等场景。
示例：
```
<person><name>Alice</name><age>30</age><city>New York</city>
</person>
```
SQL 数据库文件
- 结构：基于关系型数据库的表格结构，每个表包含行和列，列表示字段，行表示记录。
- 特点：数据高度结构化，支持复杂的查询、关联和操作，通常使用索引和主键优化检索效率。
- 应用：用于存储和管理大量有组织的数据，如用户信息、订单记录、产品目录等。
YAML（YAML Ain’t Markup Language）
- 结构：数据以缩进的层次化方式表示，通常用于配置文件和数据序列化，支持数组、对象和键值对等数据类型。
- 特点：语法简洁、可读性高，适合存储配置数据和结构化信息。
- 应用：常用于配置文件（如 Kubernetes 配置、Ansible 剧本等）。
示例：
```
name: Alice
age: 30
city: New York
skills:- Python- Java- SQL
```
关系型数据库文件
- 结构：基于表格的关系模型，表中包含多个字段和记录，字段之间有严格的关系约束（如主键、外键等）。
- 特点：数据高度组织化，支持事务管理和复杂的查询操作，适合管理大量结构化的数据。
- 应用：用于存储和查询结构化数据，如 Oracle、MySQL、PostgreSQL 数据库文件。
Excel 文件（XLS、XLSX）
- 结构：数据按表格的行和列组织，可以包含多个工作表，每个单元格可以存储数字、文本、公式等。
- 特点：除了存储数据，还支持复杂的公式计算、图表生成等功能。
- 应用：用于财务报表、数据分析、统计信息等场景。
配置文件（INI、Properties 文件）
- 结构：通常是键值对的形式，存储配置信息。
- 特点：简单易用，适合存储简单的配置信息，易于读取和修改。
- 应用：常用于软件配置，如数据库连接、应用程序设置等。
示例 (INI 文件)：
```
[Database]
host = localhost
port = 5432
user = admin
password = secret
```
日志文件（带格式的日志）
- 结构：通常每一行代表一条日志记录，并按固定格式记录时间戳、日志级别、消息内容等信息。
- 特点：结构化的日志数据易于解析，支持通过正则表达式或日志分析工具进行处理。
- 应用：用于记录系统或应用的运行状态，方便后期审计和调试。
示例：
```
2024-10-02 10:15:23 [INFO] Application started successfully
2024-10-02 10:16:01 [ERROR] Conne ction timeout
```

2.2.1 顺序文件

文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长或变长的。各个记录在物理上可以顺序存储或链式存储。

链式存储

无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找。

顺序存储

如果记录是可变长的记录，无法实现随机存取，每次只能从第一个记录开始一次往后查找。

如果记录是定长记录，若实现随机存取，记录长度为L，则第i个记录存储位置即为i*L。若采用串结构，无法快速找到关键字对应的记录。若采用顺序结构，可以快速找到某关键字对应的记录。

2.2.2 索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序的查找前i-1个记录，但是很多应用场景中有必须使用可变长记录。如何解决这个问题？

对于以上问题，我们可以建立一张索引表来解决。

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如：学生信息表中，可以用关键字“学号”建立一张索引表。也可以用“姓名”建立一张索引表。这样就可以根据姓名快速的检索文件了。

2.2.3 索引顺序文件

思考索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每条记录只有8B，而每个索引项却要占用32B，那么索引表都要比文件内容本身要大4倍，这样对存储空间的利用率就很低了。

索引顺序文件就是用来解决这个问题的。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组数据对应一个索引表项。

例题

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找 5000个记录。

若采用索引顺序文件结构，可把10000个记录分为100组，每组100条记录。如下图所示，如果需根据姓名查找数据，则需要现在左侧的索引表中找到姓名所在分组，然后在此分组中查询到具体的数据。在索引表中查询每个分组平均需要((1+100)x100/2)/100次，大约为50次。在分组中查询每个数据平均需要 ((1+100)x100/2)/100次，大约为50次。所以整个过程共需要50+50=100次。和顺序查找相比降低了很多。

2.2.4 多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级素引表。例如，对于一个含10⁶个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这 10000 个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

因此根据关键字进行检索的时候需要50+50+50=150次查询。

3. 文件目录

3.1 基本概念

磁盘上的信息是以文件的形式来组织、存储和访问的，但是这样一来会有两个问题。第一个问题，如果系统中的文件太多了怎么办？在我们的计算机上，可能安装了各种各样的应用程序，而每一个应用程序可能需要一系列不同类型的文件。第二个问题，如果多个用户使用一台计算机，那么他们可能会有不同的文件。以上两个问题如果不按照一定的组织和分类管理文件的话，用户肯定是不能很好的对这些文件进行管理的。那么，如果需要让计算机上的文件变得井然有序，且用户可以根据字符串的形式快速定位到相应的文件，就需要引入目录的概念了。

什么是目录呢，大家打开电脑后最先接触的就是目录这个东西了。需要注意的是，如下图，在文件目录中存储的是文件的元信息（metadata），而不是具体的磁盘文件数据。文件目录主要用于帮助操作系统组织、查找和管理文件，存储的信息通常包括文件名、文件类型、文件大小、文件的创建和修改时间等，还可能包含一个指向存储在磁盘上的文件数据的指针或索引（例如指向文件控制块FCB或直接指向文件数据所在的磁盘块）。文件的实际数据则存储在磁盘的具体位置上。其实就跟书本或博客的目录是类似的。

文件目录可以理解为是一个表格，其中记录了在该目录下的每一个文件的文件名和其他的一些管理信息。一般来说，每一个文件都会在此目录中有对应的一行，即一个目录项。

这张表格本省也是以文件的形式放在磁盘上，具体来说，该文件的内容是这样生成的：把每一个目录项变成一个字节流，假如为32B，然后把各个目录项依次拼接在一起，就新城了一个文件。另外，在目录的管理上，也有相关的一些系统调用，如创建目录、删除目录、修改目录名等。

3.2 文件控制块（FCB）

FCB 的有序集合称为“文件目录”，一个FCB就是一个文件目录项。

FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。

3.3 索引节点

索引节点其实就是FCB的改进，因为其实我们在查找各级目录的过程中，只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表瘦身来提升效率。

瘦身后的目录项就不需要存储太多的信息了，只需要存储文件名和索引节点的指针就可以了。

假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共需要占用
640/16=40 个盘块。按照文件名检索目录时，平均需要查询多少个目录项，平均需要启动磁盘多少次？

平均需要查询的目录项：((1+320)*320/2)/320≈320个。

平均需要启动磁盘的次数：平均需要查询的目录项/每个磁盘块的PCB个数=320/16=20次。

若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要读入 320/64=5次磁盘块。显然，这将大大提升文件检索速度。

文件目录以及索引节点的使用过程

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置〞即可找到文件。存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件。

3.4 目录相关操作

搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项

创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项

删除文件：当州除一个文件时，需要在目录中删除相应的目录项

显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性

修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

3.5 目录结构

文件目录的结构可以根据文件系统和使用的目录组织方式有所不同。以下是几种常见的文件目录结构：

3.5.1 单级目录结构

概念：对于系统中的所有文件，只创建一个目录文件，即一张线性表格，每个文件占用其中的一个目录项。
特点：
- 目录结构非常简单，所有文件都存储在同一级别。
- 文件名必须是唯一的，无法支持子目录。
优点：实现简单，文件查找容易。
缺点：文件数量较多时，容易导致文件名冲突，且管理复杂度高，无法组织层次化的文件。

示例：

root/file1.txtfile2.txtfile3.txt

3.5.2 两级目录结构

概念：每个用户有自己独立的文件目录，系统为每个用户创建一个单独的目录，所有用户共享一个根目录。
特点：
- 解决了单级目录文件名冲突的问题。
- 用户之间文件独立管理，但仍然不支持子目录。
优点：每个用户有自己的命名空间，文件名不再唯一。
缺点：不能支持进一步的子目录结构，目录层次较为简单。

示例：

root/user1/file1.txtfile2.txtuser2/fileA.txtfileB.txt

3.5.3 多级目录结构

概念：也称为树状目录结构，文件系统采用树状结构进行组织，允许子目录嵌套在父目录下。每个用户或进程可以有多个子目录，且每个目录中可以有文件和其他子目录。
特点：
- 支持多级目录，能够递归地包含文件和子目录。
- 文件系统中每个目录和文件都有唯一的路径。
优点：层次化的组织方式，文件查找和管理更加高效，支持更大规模的文件管理。
缺点：目录结构较复杂，查找文件可能需要遍历多层目录。

示例：

root/home/user1/docs/file1.txtfile2.txtimages/pic1.jpgpic2.jpguser2/project/code.pydata.csv

3.5.4 无环图目录结构

概念：采用无环图（DAG，Directed Acyclic Graph）结构，允许一个文件或目录有多个父目录。即一个文件或目录可以被多个用户或目录引用，但不允许形成循环。
特点：
- 支持多个父目录，允许文件共享。
- 通过符号链接或硬链接实现文件或目录的共享。
- 设置一个共享技术器来表示指向该共享文件的链数，当共享计数器为0时，才真正删除该结点，否则仅删除用户请求的共享链。
优点：文件共享方便，多个用户或目录可以指向同一个文件。
缺点：需要避免目录循环的问题，文件的管理较复杂。

示例：

root/home/user1/file1.txtuser2/link_to_user1_file1 (指向user1/file1.txt)

4. 文件的物理结构

即文件的分配方式，文件的数据应该怎样存放在外存中？

操作系统需要对磁盘块进行哪些管理

对非空闲磁盘块的管理
对空闲磁盘块的管理

文件的分配方式又分为以下三种：

连续分配
链接分配
索引分配

4.1 文件块（磁盘块）

指文件系统中用于存储文件数据的最小单位。在文件系统中，文件被分割成多个块，这些块在物理存储介质上按顺序或以其他方式分布。这种分块的设计能够有效管理存储空间，提高读写效率，并支持大文件的存储和访问。

在内存管理中，进程的逻辑地址空间被分割为一个一个页面。

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

用户在使用文件时，是通过文件的逻辑地址来操作文件的，操作系统负责要负责从逻辑地址到物理地址的映射。

4.2 连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

用户通过逻辑地址来操作自己的文件，操作系统如何实现逻辑地址到物理地址的映射？

（逻辑块号，块内地址）→（物理块号，快内地址）。只需要转化块号就行，块内地址保持不变。

如何实现逻辑块号到物理块号的转变？

如上图所示，文件aaa采用的连续分配方式，起始物理块号是4，共占用3个文件块。所以用户给出要访问的逻辑块号后，操作系统只需要将访问的逻辑块号+起始物理块号就可以得到物理块号了，因此连续分配方式支持顺序访问和直接访问。当然，还需要验证一下访问的逻辑块号是否越界，如果逻辑块号≥长度就不合法了。

总结

优点：在机械硬盘中，读取某个磁盘块时，需要移动磁头，访问的两个磁盘块的距离越远，移动磁头的时间就越长。所以连续分配的文件在顺序读写时速度是最快的。

缺点：此分配方式容易产生外部碎片，且如果文件大小大于磁盘中任何一组连续的空闲磁盘块的时候，需要对磁盘块进行整理，并对数据进行复制，这是很浪费时间的。

不利于文件扩展，如果刚开始文件占用三个磁盘块，且旁边无可用磁盘块，如果需要扩展，就需要将原有数据进行复制，也会很浪费时间。

4.3 链接分配

4.3.1 隐式链接

目录中记录了文件存储的起始块号和结束块号，当然也可以增加一个字段表示文件的长度。

除了文件中最后一个磁盘块外，其他的磁盘块都会保存下一个磁盘块的指针。并且这些指针都是透明的。

如何实现逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项 (FCB)。

从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推。因此，读入号逻辑块，总共需要 i+1 次磁盘I/O。

总结：

优点：采用这种分配方式的文件扩展方便，当文件需要扩展时，只需要将文件尾部的磁盘块的指针指向新的磁盘块即可。且磁盘空间利用率是很高的，不会产生外部碎片。

缺点：采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。指向下一个磁盘的支持也需要耗费少量的内存空间。

4.3.2 显示链接

把用于链接文件各物理块的指针显示分配地存放在一张表中，即文件分配表（FAT，File Allocation Table）中。

假设某个新创建的文件“aaa”依次存放在磁盘块2→5→0→1，文件尾部的磁盘块对应的下一块指针为-1，即文件分配表中物理块号为1的下一块指针应该为-1。

假设某个先创建的文件“bbb”依次存放在磁盘块4→23→3。

注意：一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

如何实现逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件的目录项…

从目录项找到物理起始块号，若i>0，查询内存中的FAT，依次向后找到i号磁盘对应的物理块号。逻辑块号转换成物理块号的过程不需要读盘操作。

结论：采用显示链接方式的文件，支持顺序访问。又因为其FAT是存储到内存中的，不需要访问磁盘，这样也是支持文件的随机读取的（系统可以通过查找内存中的链表直接跳转到文件的某个部分，而不是顺序读取整个文件。）。由于块号转换的过程不需要访问磁盘，因此显示连接的分配方式相对于隐式链接来说，响应速度是要快很多的。

总结

显式链接–把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点：文件分配表的需要占用一定的存储空间。

4.4 索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

假设某个新创建的文件“aaa”的数据依次存放在磁盘块2→5 →13→9。7号磁盘块作为“aaa”的索引块，索引块中保存了索引表的内容。
注：在显式链接的链式分配方式中，文件分配表FAT 是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张。

可以用固定的长度表示物理块号（如：假设磁盘总容量为1TB=2⁴⁰B，磁盘块大小为1KB，则共有2³⁰个磁盘块，则可用4B 表示磁盘块号），因此，索引表中的“逻辑块号” 可以是隐含的。

如何实现逻辑块号到物理块号的转变？

用户给出需要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）…

从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表就可以找到i号逻辑快在外存中存放的位置。

所以，索引分配方式也是支持随机访问的。文件扩展也很容易实现（只需给文件分配一个空闲块，并添加一个索引项即可）。

思考：

若每个磁盘块为1KB，一个索引表项为4B，则一个磁盘块只能存放256个索引项。如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？

链接方案

如果一个文件的索引表太长，导致一个磁盘块放不下，那么可以将多个索引块链接起来存放，即磁盘块的最后一个索引表项存放的值下一个索引块。

假设磁盘块大小为1KB，一个索引表项占用4B。现在有一个文件A为64MB，采用链接方案存储数据，那么需要用多少个磁盘块存储数据，读取文件时候，平均需要读取多少个磁盘块呢？

一个磁盘块可以存储的索引表项 = 磁盘块大小/索引表项大小 = 1KB/4B = 256个，但是这里需要注意的是，最后一个位置（索引表项）应该存储下一个索引表在的磁盘块的指针，所以一个磁盘块可以存储255个索引表项，但是为了方便计算，先按照256个计算。

文件A可以被分为（64MB/1KB=65536）个磁盘块，即为65536个索引项。

一个磁盘块可以存储256个索引项，那总共需要65536/256=256个磁盘块来存储索引表。但是此处采用的是链接方案，每个磁盘块的最后一个位置应该存储下一个索引表在的磁盘块的指针，所以共需要存储255个指针，最少需要一个磁盘块。所以，最后结论是一共需要257个磁盘块存储。

平均需要读取的磁盘块的数量：(((1+257)x257)/2)/257≈129个

总结

优点：实现简单

缺点：因为索引表之间采用的是链接方案，所以，在内存中检索索引项的时候需要查询到之前的索引表才能找到物理磁盘位置，比较浪费时间。
多层索引

建立多层索引，原理类似于多层页表。使第一层的索引块指向第二层的索引块，还可以根据文件大小要求再建立第三层、第四层索引块。多级索引中的一级索引块通常只占用一个磁盘块。也就是说，在文件的目录项中，只需要存储一级索引块所在的磁盘块的地址就可以了。且需要注意的是：每层的每个索引表的大小不能超过磁盘块大小。

假设一个磁盘块大小为1KB，一个索引表项占用4B，则一个磁盘块只能存放256个索引项。

若文件采用两层索引，则该文件的最大长度可以达到256x256x1KB=65536KB=64MB。

可根据逻辑块号算出应该查找索引表中的哪个表项。

如：要访问 1026 号逻辑块，则

1026/256=4， 1026%256=2。

因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026 号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。

若采用三层索引，则文件的最大长度为
256x256x256x1KB =16GB
类似的，访问目标数据块，需要4次磁盘I/O。

采用K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K＋1次，读磁盘操作。
混合索引

多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。

若顶级索引表还没读入内存

访问 0~7号逻辑块：两次读磁盘
访问 8~263：三次读磁盘
访问 264~ 65799：四次读磁盘

对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）

4.5 总结

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。若文件太大，索引表项太多，可以采取以下三种方法解决：

①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入 0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。

②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级素引表未调入内存，则访问一个数据块只需要K＋1次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。

③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级问接索引（指向单层素引表）、还包含两级间接索引（指向两层索引表）。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

超级超级超级重要考点：①要会根据多层索引、混合索引的结构计算出文件的最大长度（key：各级索引表最大不能超过一个块）；②要能自己分析访问某个数据块所需要的读磁盘次数 (Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件一一顶级索引块是否已调入内存）

5. 逻辑结构VS物理结构

接下来我们用一个例子来进行区分

首先创建一个文件，其中文件中写入了10000个Hello world!

#include <stdio.h>int main() {// 定义文件指针FILE *filePointer;// 使用 "w" 模式创建文件，若文件不存在则创建，存在则覆盖filePointer = fopen("example.txt", "w");// 检查文件是否成功打开if (filePointer == NULL) {printf("文件创建失败！\n");return 1;}// 向文件中写入内容for (int i = 1; i <= 10000; ++i) {fputs("Hello world!",filePointer);}// 关闭文件fclose(filePointer);printf("文件已成功创建并写入内容。\n");return 0;
}

用户视角下的文件

我们获取文件中的下标为16的字符，我们直接可以根据库函数和下标获取就行了。操作系统自然会根据文件的逻辑块号找到具体的磁盘块。

#include<stdio.h>int main(int argc, char const *argv[])
{FILE *f  = fopen("example.txt","r");if (f == NULL){printf("%s\n", "打开文件失败");return 1;}fseek(f,16,SEEK_SET);char c = fgetc(f);printf("下标为16的字符是%c\n",c);fclose(f);return 0;
}

操作系统下的无结构文件

在操作系统的视角下，文件就是一堆二进制的数据，可以采用不同的方案存储这些数据。可以采用连续分配、链接分配、索引分配的任意一种。

操作系统下的顺序文件


#include <stdio.h>typedef struct {int number;char name[30];char major[30];
} Student;void writeStudentToFile(int n);void readStudentFromFile(int number, Student *stu);int main() {writeStudentToFile(10000);Student stu;readStudentFromFile(123, &stu);printf("学生学号是%d\n", stu.number);printf("学生姓名是%c\n", stu.name[0]);printf("学生专业是%c\n", stu.major[0]);return 0;
}void writeStudentToFile(int n) {FILE *sfp = fopen("student.info", "w");if (sfp == NULL) {printf("打开文件失败");return;}char cArr[10] = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'z'};char cArr1[10] = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};Student sArr[n];for (int i = 0; i < n; ++i) {sArr[i].number = i;sArr[i].name[0] = cArr[i % 10];sArr[i].major[0] = cArr1[i % 10];}fwrite(sArr, sizeof(Student), n, sfp);fclose(sfp);
}void readStudentFromFile(int number, Student *stu) {FILE *fp = fopen("student.info", "r");if (fp == NULL) {printf("打开文件失败\n");return;}// 根据索引定位学生信息fseek(fp, number * sizeof(Student), SEEK_SET);if (fread(stu, sizeof(Student), 1, fp) != 1) {printf("读取学生信息失败\n");fclose(fp);return;}fclose(fp);
}

在用户视角下，这个文件是一个连一组连续数据组成的一个文件，但是对于操作系统来说是没有什么差别的，可以用任何存储方式来存储。

6. 文件存储空间管理

6.1 存储空间的划分与初始化

6.1.1 文件卷（逻辑卷）的概念

安装windows操作系统时，一个必经步骤是为磁盘分区（C盘，D盘，E盘等）。这些分区就可以成为逻辑卷或者逻辑盘。

6.1.2 目录区与文件区

6.2 空间管理的方法

6.2.1 空闲表法

如何分配磁盘块：

与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空问。同样可采用首次适应、最佳适应、最坏适应等算法来決定要为文件分配哪个区间。

如何回收磁盘块：

与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区：③回收区前面是空闲区：④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。

6.2.2 空闲链表法

空闲盘块链

以盘块为单位组成一条空闲链

操作系统保存着空闲链的链头、链尾指针。

如何分配

若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收

回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

特点

这种方式适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
空闲盘区链

以盘区为单位组成一条空闲链。

操作系统同样保存着链头、链尾。

如何分配

若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，然后分配给文件。若没有合适的连续空闲区，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收

若回收区和某个空闲区相邻，则需要将会收取合并到空闲盘区中，若回收区没有和任何空闲区相邻，则将回收区作为单独的一个空闲盘区挂到链尾。

特点

离散分配，连续分配都适用。为一个文件分配多个盘区时效率会更高。

6.2.3 位示图法

每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。为试图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中每一位对应一个盘块。因此可以用（字号，位号）对应一个盘块号。有的题目中也描述为（行号，列号）

考试时，要求能够自己推出盘块号与（字号、位号）相互转换的公式。需要注意：盘块号、字号、位号到底是从0开始还是从1开始。

比如下面图片中，盘块号、字号、位号都是从0开始的，用n来表示字长。那么可以得到以下公式：
$(字号, 位号) = (i, j) 的二进制位对应的盘块号 b = n * i + j$

$b 号盘块对应的字号 i = b / n ，位号 j = b$

6.2.4 成组链接法

空闲表法、空闲链表法不使用与大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统采用了成组链接饭对磁盘空闲块进行管理。

文件卷的目录区中专门采用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且保证内存和外存中超级块的数据保持一致。

需要注意的是超级块中的第一个盘块号指向的盘块存储的是下一组空闲盘块的空闲盘块号。且以此类推，直到存储空闲盘块号的盘块的存储的第一个磁盘号为-1，表示已经没有下一组空闲块。

既然存储空闲盘块的原理我们了解呢，那到使用时该如何分配呢？

场景1：需要的空闲块数量n小于100

检查第一个分组的空闲块数量是否满足需求，发现100>n，第一个分组的空闲块的数量是足够的。所以只需要将第一组的空闲块数量减n，然后将分配出去的空闲块号从分组中移除就可以。

场景2：需要100个空闲块

检查空闲块数量100 = 100，空闲块数量足够。
将超级块中的数据可以放在一个变量中，方便等下分配时直到分配给哪些空闲块。
先将300号磁盘块中的数据复制到超级块，此时，300号磁盘块也是可以被覆盖的状态，可以认为是空闲的状态。
将第二步变量中的空闲块分配出去。

场景3：需要的空闲块数量n大于100小于200

检查空闲块数量：由于请求的空闲块数 n 在 100 到 200 之间，系统首先会检查当前超级块中的可用块数是否足够分配给请求。超级块中已经维护了一组空闲块数量（如图所示为100），因此此时还需分配 n-100 个空闲块。
将超级块中的空闲块存入变量：将超级块中的空闲块号复制到一个变量 x 中，这包括超级块记录的100个空闲块号。此时剩余需要分配的块数量为 n-100。
检查 300 号块中的空闲块数量是否足够：300 号块包含了一个分组内的所有空闲块号，图中显示它包含的数量应当大于 n-100。因此不需要进入 400 号块查找新的空闲块，300 号块中的空闲块完全足够用于分配。
从 300 号块分配空闲块：将 n-100 个空闲块从 300 号块中分配出去，并将这些块号追加到变量 x 中。
更新超级块：将 300 号块中的空闲块列表替换为超级块中的内容。这意味着此时超级块将更新成新的空闲块列表，并准备好分配给下一个请求。
完成分配：最后，将变量 x 中记录的所有空闲块分配给文件使用。这包括从超级块中取得的100个块以及从 300 号块中取得的 n-100 个块。

其他场景就可以以此类推了。

如何回收呢？

场景1：超级块中有m个空闲块，此时我们回收n个磁盘块，且m+n≤100。

直接回收，更改超级块的空闲块数量，在空闲块列表上添加空闲盘块即可

场景2：超级块中有m个空闲块，此时我们回收n个磁盘块，且200>m+n>100。

先将超级块的空闲信息补满，即补到100，
将超级块的信息复制到一个新的磁盘块。
将剩余的回收且未维护到空闲列表的磁盘块维护到超级快中。

其他场景就可以以此类推了。

6.3 总结

在这里插入图片描述

7. 文件的基本操作

7.1 创建文件

进行 Create 系统调用时，需要提供的几个主要参数

所需的外存空间大小（如：一个盘块，即1KB）
文件存放路径（“D:/Demo”)
文件名

操作系统在处理 Create 系统调用时，主要做了两件事：

在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

7.2 删除文件

进行 Delete 系统调用时，需要提供的几个主要参数：

文件存放路径
文件名

操作系统在处理 Delete 系统调用时，主要做了几件事：

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）
从目录表中删除文件对应的目录项。

7.3 打开文件

在很多操作系统中，在对文件进行操作之前，要求用户先使用 open 系统调用“打开文件”，需要提供的几个主要参
数：

文件存放路径(“D:(Demo”)
文件名(“test.txt”）
要对文件的操作类型（r,rw等）

操作系统在处理open系统调用时，主要做了几件事：

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限。
将目录项复制到内存中进程的打开文件表中，并将对应表目的编号返回给用户。之后用户使用打来文件的编号来指明要操作的文件。
1. 系统也会在内存中维护一张打开文件表，整个系统只有一张。

7.4 关闭文件

进程使用完文件后，要“关闭文件”，操作系统在处理 Close 系统调用时，主要做了几件事：

将进程的打开文件表相应表项删除。
回收分配给该文件的内存空间等资源。

7.5 读文件

进程使用read系统调用完成写操作。需要指明是哪个文件（在支持“打开文件” 操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据（如：读入 1KB）、指明读入的数据要放在内存中的什么位置。
操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

7.6 写文件

进程使用 write 系统调用完成写操作，需要指明是哪个文件（在支持“打开文件” 操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如：写出1KB）、写回外存的数据放在内存中的什么位置。
操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。