一、文件系统

在操作系统中，文件系统是用于管理存储设备上数据组织与存取的一种机制。
它是操作系统的重要组成部分，承担着对文件的创建、读写、组织、存储、访问控制等管理任务。

功能：

1. 文件的创建与删除；
2. 文件的读写与访问；
3. 目录管理；
4. 访问控制与权限管理；
5. 空间管理（分配与回收）；
6. 文件共享与保护；
7. 挂载与卸载文件系统。

文件系统的关键内容：

• 文件（File）：用户数据和程序的逻辑单位，如文本、图像、音频、可执行程序等。
• 目录（Directory）：用于组织和管理文件的结构化机制。
• 路径（Path）：标识文件位置的字符串，如 /home/user/file.txt。
• 卷（Volume）：操作系统逻辑上的存储单位，一个卷可以是整个磁盘或其中的一部分。
• 文件控制块（FCB）：用于描述文件属性的数据结构，如文件名、大小、创建时间、权限、指向数据块的指针等。

二、文件的实现

参考书——现代操作系统(第3版)。

1. 连续分配（Contiguous Allocation）

• 所有文件内容存储在连续的物理块中。
• 优点：访问速度快。
• 缺点：容易造成碎片，不易扩展。

连续分配示意图：

2. 链式分配（Linked Allocation）

• 每个文件由多个块组成，块之间通过指针链接。
• 优点：无外部碎片，易于扩展。
• 缺点：随机访问慢，可靠性差（指针损坏）。

链式分配示意图：

3. 索引分配（Indexed Allocation）

• 每个文件有一个索引块，索引块中存放文件所有块的地址。
• 优点：支持快速随机访问，灵活。
• 缺点：索引块可能较大，占用额外空间。

4. i节点（index-node）

• i节点（Index Node） 是文件在磁盘上的元信息结构，不包含文件名，但包含文件的所有属性和数据块索引信息。
• 每个文件都有一个 i节点，系统通过目录项找到 inode 来访问文件内容。
• i节点是 Unix 和类 Unix 系统（如 Linux）中文件的核心数据结构，是文件控制块（FCB）的一种实现方式。

i节点包含信息：

项目	描述
文件类型	普通文件、目录、符号链接等
文件权限	rwx 属性（用户、组、其他）
所有者信息	UID（用户ID）、GID（组ID）
时间信息	创建时间（ctime）、访问时间（atime）、修改时间（mtime）
链接计数	表示有多少目录项引用此 inode
文件大小	字节为单位
数据块指针	指向实际数据块的指针：直接块、间接块等

文件访问中i节点：

[文件名] → [目录项] → [inode编号] → [inode结构] → [数据块指针] → [磁盘块]

• 用户层通过文件名访问，内核则始终是“通过 inode 访问内容”。

碎片问题

• 内部碎片：文件未填满一个块，浪费部分空间。
• 外部碎片：磁盘上存在零散的空闲块，不能合并使用。

处理方法：

• 周期性磁盘整理（defragmentation）；
• 使用索引分配或日志文件系统避免外部碎片；
• 文件系统设计支持空间复用与预分配。

四、目录的实现

1. 目录的结构

单级目录结构：

• 所有文件放在一个目录下，简单但不支持组织管理。

两级目录结构：

• 每个用户一个独立目录，支持多用户。

树型目录结构（层次结构）：

• 支持嵌套子目录，是现代文件系统的主流结构（如 Linux、Windows）。

图型目录结构（带链接）：

• 支持硬链接与符号链接，实现多个路径访问同一文件。

2. 目录的实现方式

（1）线性表结构：

• 所有目录项依次存放；
• 查找效率低：O(n)；
• 简单实现，适合小目录。

（2）哈希表：

• 提高文件名查找效率；
• 增加实现复杂度；
• NTFS、某些嵌入式文件系统使用。

（3）B+树/红黑树等平衡树：

• 快速查找/插入/删除；
• ext4、NTFS中使用（ext4使用 HTree/B-tree）。

五、空闲空间的管理策略

1. 位图法（Bitmap）

• 用一个位图表示磁盘块的占用情况：1=已占用，0=空闲。

优点：

• 查找连续空闲块快；
• 节省空间（1位表示1块）。

缺点：

• 对大磁盘位图也会很大。

2. 链表法（Free List）

• 所有空闲块用链表链接；

优点：

• 实现简单；
• 插入删除效率高。

缺点：

• 不易查找连续空闲块。

3. 分组法（Grouping）

• 空闲块分组，每组记录若干空闲块的位置。

优点：

• 减少读取空闲块的次数；
• 提高分配速度。

4. 计数法（Counting）

• 记录空闲块的起始块号和连续块数。

优点：

• 适用于大块连续空闲空间；
• 表示效率高。

六、文件系统的实现结构

1. 应用层接口（API）：如 open(), read(), write(), close() 等。
2. 逻辑文件系统（LFS）：处理文件描述、权限控制等。
3. 文件组织模块（FOM）：处理目录和文件结构。
4. 基本文件系统（BFS）：处理块分配、缓冲管理等。
5. I/O 控制层（IOCS）：驱动硬件与设备控制器。

七、常见的文件系统类型

文件系统	支持平台	特点
FAT32	Windows	简单、兼容性强，但不支持大文件（>4GB）
NTFS	Windows	支持权限、加密、压缩、日志
ext3/ext4	Linux	稳定可靠，支持日志、多用户管理
XFS	Linux	高性能、适合大文件
APFS	macOS	Apple 专用，支持快照与加密

八、现代特性（高级功能）

• 日志文件系统（Journaling）：记录操作日志，提高容错能力。
• 配额管理：限制用户使用磁盘空间。
• 快照（Snapshot）：保存文件系统某个时间点状态。
• 加密与压缩：提高数据安全性与存储效率。
• RAID 支持：将多个物理磁盘组合成一个逻辑磁盘来实现数据冗余、性能提升或二者兼顾。