操作系统中的文件系统概念和实现&磁盘结构和调度算法

文件系统

文件系统概念

文件系统是操作系统中管理持久数据的核心子系统。它提供了一种抽象机制，使用户能够方便地在磁盘上存储和检索信息，而无需了解底层存储细节。

文件

文件定义

文件是字节序列的抽象，为操作系统提供了最大的灵活性。

文件命名

不同操作系统采用不同的文件系统和命名约定：

• FAT16/32: MS-DOS和早期Windows系统
• NTFS: 较新的Windows系统
• exFAT: 微软优化的FAT系统
• ext2/3/4: Linux系统常用文件系统

文件结构

• 字节序列: 最简单和最灵活的结构
• 记录序列: 具有固定长度记录的序列
• 树状结构: 按键字段排序的记录树

文件类型

• 普通文件: 用户创建的数据文件
• 目录: 包含其他文件信息的特殊文件
• 字符特殊文件: 用于I/O的设备文件（UNIX系统）
• 块特殊文件: 用于块设备的文件（UNIX系统）

文件访问方法

• 顺序访问: 按顺序读取所有字节，早期操作系统只有这种类型
• 随机访问: 可以直接访问文件中的任意位置

文件属性

包括创建日期、修改时间、所有者、大小等元数据信息。

文件操作

主要的文件操作系统调用包括：create, delete, open, close, read, write, append, seek, get attributes, set attributes, rename。

目录

在很多操作系统中，目录本身也是文件

目录结构

• 一级目录系统: 所有文件都在一个目录中
• 层级目录系统: 树状结构，允许更好的文件组织

路径名

• 绝对路径: 从根目录开始的完整路径
• 相对路径: 相对于当前工作目录的路径

目录操作

主要的目录操作包括：create, delete, opendir, closedir, readdir, rename, link, unlink。

文件系统实现

文件存储实现的关键问题是记录各个文件分别用到哪些磁盘块。不同的操作系统用到不同的方法

文件系统布局

• 主引导记录（MBR）: 包含分区表和引导代码。结尾是分区表。该表给出每个分区的起始结束地 址
• 分区: 每个分区包含独立的文件系统

文件实现方式

	定义	优点	缺点
连续分配	文件占用连续的磁盘块	实现简单&操作性能较好
链表分配	文件块通过链表连接	充分利用磁盘块&随机访问快	占用字节，每个磁盘块存储数据的字节数不再是2的整数次幂
文件分配表（FAT）	使用内存中的表进行链表分配，内存中这样的表格称为文件分配表 (File Allocation Table，FAT)	解决链表分配的不足
i节点:	给每个文件赋予一个称为i节点的数据结构，其中列出了文件属性 和文件的磁盘地址

目录实现

简单目录：包含固定大小的目录，在目录项中有磁盘地址和属性
采用i节点的系统：把文件属性存放在i节点中而不是目录项中。这种情形下，目录项会更短。

共享文件和链接

允许多个目录项指向同一个文件，形成有向无环图（DAG）结构。

日志结构文件系统（LFS）

解决磁道的寻道时间没得到优化。设计用于优化写操作性能，将所有修改作为日志追加到磁盘末尾。

日志文件系统

使用日志来记录文件系统操作，提高系统崩溃后的恢复能力。

虚拟文件系统（VFS）

将多个文件系统整合到一个统一的结构中。提供统一的文件系统接口，允许多种文件系统共存。

文件系统管理和优化

磁盘空间管理

• 块大小选择: 权衡存储效率和性能
• 空闲块管理: 使用链表或位图
• 磁盘配额: 限制用户磁盘使用量

文件系统备份

定期备份以防止数据丢失和系统故障。

文件系统一致性

使用如fsck（文件系统检查）等工具来检查和修复文件系统不一致。

性能优化

• 块缓存: 减少磁盘访问
• 预读: 提前读取可能需要的块
• 减少磁盘臂移动: 优化文件布局
• 碎片整理：重新组织文件，使其占用连续的磁盘空间，提高访问效率。

磁盘

生磁盘：根据盘块号来使用磁盘；
熟磁盘：根据文件来使用磁盘

磁盘的物理结构

• 盘面: 多个类似DVD的圆盘堆叠在一起，每个盘面由磁性材料覆盖，用于存储数据。
• 磁道: 每个盘面上的同心圆，磁道是数据存储的基本单位之一。
• 扇区: 每个磁道上的一小段区域，是磁盘上最小的存储单位。通常一个扇区包含512字节，但也有其他大小的扇区配置。

磁盘I/O过程

• 寻道: 将磁头移动到指定磁道，这通常是最耗时的步骤，因为涉及机械臂的移动。
• 旋转: 等待磁盘旋转，使得所需扇区移动到磁头下，该过程也会花费一定时间。
• 传输: 读取或写入指定扇区的数据，一旦磁头定位到位，数据传输的速度非常快。

磁盘编址

• 使用盘块号（block）进行抽象，简化用户操作。
• 系统根据盘块号计算出具体的柱面（C）、磁头（H）、扇区（S）。
• 计算公式： $盘块号 = C * (Heads * Sectors) + H * Sectors + S$
• 编址方式: 先用完一个磁道，再移动到下一个柱面，以减少寻道时间。

磁盘调度算法

FCFS (First-Come, First-Served)

• 按请求到达的顺序处理
• 优点: 公平
• 缺点: 可能造成磁头频繁移动，效率低

SSTF (Shortest Seek Time First)

• 选择距离当前磁头最近的请求
• 优点: 减少寻道时间
• 缺点: 可能造成远处请求的”饥饿”

SCAN (电梯算法)

• 磁头沿一个方向移动，处理遇到的所有请求，到达边界后改变方向
• 优点: 避免”饥饿”，平衡效率和公平性

文件在磁盘上的实现方式

顺序结构

• 文件占用连续的磁盘块
• 使用文件控制块（FCB）记录起始块和大小
• 优点: 简单，支持随机访问
• 缺点: 文件增长困难，可能造成外部碎片

链式结构

• 文件的各个块通过指针链接
• 优点: 支持动态增长，无外部碎片
• 缺点: 只支持顺序访问，可靠性较低

索引结构

• 使用索引表记录文件块的位置
• 优点: 支持随机访问和动态增长
• 缺点: 需要额外的存储空间用于索引表

磁盘空间管理

• 块大小: 通常在1~4KB之间，现代大容量磁盘可能使用更大的块（如64KB）。
• 记录空闲块的方法:
  • 空闲块链表: 用链表连接所有空闲块
  • 位图: 用位表示块的使用状态（0表示已用，1表示空闲）
• 磁盘配额: 限制每个用户可使用的最大文件数和块数

磁盘性能优化

• 使用块高速缓存（block cache）减少磁盘访问
• 块提前读（read-ahead）: 预读可能需要的块到缓存
• 减少磁盘臂移动: 尽量将相关数据放在相邻位置
• 磁盘碎片整理: 重新组织文件，使其连续存储，并整合空闲空间

磁盘备份

• 用于从意外灾难或错误操作中恢复
• 可以是全量备份或增量备份

文件系统一致性

• 使用日志文件系统（如NTFS, ext3, ReiserFS）来保证文件系统的一致性。
• 在系统崩溃后，可以通过日志快速恢复文件系统状态。