I/O设备概述

设备管理

• 设备中断处理

• 缓冲区管理

• 设备分配和去配

• 设备驱动调度

• 虚拟设备的实现

• 解决设备和CPU速度不匹配的问题, 使得主机和设备充分并行工作, 提高设备使用效率;

• 屏蔽设备的物理细节和操作过程, 配置驱动程序, 提供统一界面(抽象为裸设备或设备文件).

*总线层次结构(简要了解即可)

单总线结构模型

三级总线结构模型

南北桥

基于通道的服务器总线模型

• 支持CPU、主存和多个I/O通道之间的数据传送;

• 支持I/O通道和I/O控制器, 以及I/O控制器和设备之间的数据传送.

标准设备模型

标准协议(轮询)

中断机制

直接内存访问 DMA

• 数据传送过程是不连续的和不规则的;

• CPU大部分情况下与Cache进行数据交换, 直接访问内存较少.

I/O处理器(I/O通道)

• CPU遇到I/O任务, 组织通道程序, 置通道程序地址字CAW, 启动指定通道;

• 通道从CAW获得通道程序, 控制I/O设备进行操作, CPU执行其他任务;

• I/O操作完成后, I/O通道发出中断, CPU处理中断, 并从通道程序状态字CSW获得通道执行情况, 处理I/O操作.

*I/O软件的层次结构(初学者可以跳过)

I/O中断处理程序

设备驱动程序

• 包括与设备密切相关的所有代码, 从上层(独立于设备的I/O软件)接收I/O请求, 把用户提交的逻辑I/O请求转化为物理I/O操作的启动和执行;

• 监督设备是否正确执行, 访问数据缓冲区, 进行必要的纠错处理;

• 控制设备的初始化, 启动, 数据传输, 组织通道程序, 处理中断.

独立于设备的I/O软件

• 等待驱动就绪: 读取状态寄存器(0x1F7)直到驱动 READY 而非忙碌.

• 向命令寄存器写入参数: 写入扇区数, 待访问扇区对应的逻辑块地址(LBA), 并将驱动编号(master=0x00, slave=0x10, 因为 IDE 允许接入两个硬盘)写入命令寄存器(0x1F2-0x1F6).

• 开启 I/O: 发送读写命令到命令寄存器. 向命令寄存器(0x1F7)中写入 READ-WRITE 命令.

• 数据传送(针对写请求): 等待直到驱动状态为 READY 和 DRQ(驱动请求数据), 向数据端口写入数据.

• 中断处理: 在最简单的情况下, 每个扇区的数据传送结束后都会触发一次中断处理程序. 较复杂的方式支持批处理, 全部数据传送结束后才会触发一次中断处理.

• 错误处理: 在每次操作之后读取状态寄存器. 如果 ERROR 位被置位, 可以读取错误寄存器来获取详细信息.

用户空间的I/O软件

*I/O缓冲(初学者可以跳过)

• 解决CPU与设备之间速度不匹配的矛盾

• 协调逻辑记录大小和物理记录大小不一致的问题

• 减少I/O操作对CPU的中断次数, 提高CPU和设备的并行性(摊销)

• 放宽对CPU中断响应时间的要求

单缓冲

• 输入:
1. I/O设备将数据读入到指定的缓冲区.
2. 当缓冲区填满后, 设备I/O操作暂停.
3. CPU从缓冲区中读取数据并进行处理.
4. CPU处理完缓冲区数据后, I/O设备才能继续填充下一个缓冲区(通常是重新使用同一个缓冲区).

• 输出:
1. CPU将要输出的数据写入缓冲区.
2. 当缓冲区填满后, CPU暂停写入.
3. I/O设备从缓冲区中读取数据并进行输出.
4. I/O设备输出完缓冲区数据后, CPU才能继续填充下一个缓冲区.

• 优点: 实现简单, 所需内存空间少.

• 缺点: 效率不高. I/O设备和CPU之间仍然存在等待关系. 当CPU处理缓冲区数据时, I/O设备必须等待; 当I/O设备填充/清空缓冲区时, CPU也可能需要等待. 这种“串行”的工作方式限制了I/O吞吐量. 它至少会引入一个传输时间或处理时间(取决于哪个更快)的延迟.

• 适用于: 对I/O速度要求不高的场景.

双缓冲

• 输入:
1. I/O设备将数据读入缓冲区A.
2. 当缓冲区A填满后, I/O设备立即切换到缓冲区B继续读入数据.
3. 与此同时, CPU开始处理缓冲区A中的数据.
4. 当缓冲区B填满且CPU处理完缓冲区A的数据后, CPU切换到缓冲区B处理, I/O设备切换回缓冲区A继续读入数据.
5. 两个缓冲区交替使用, 形成流水线效应.

• 输出:
1. CPU将数据写入缓冲区A.
2. 当缓冲区A填满后, CPU立即切换到缓冲区B继续写入数据.
3. 与此同时, I/O设备开始从缓冲区A读取数据并输出.
4. 当缓冲区B填满且I/O设备输出完缓冲区A的数据后, I/O设备切换到缓冲区B输出, CPU切换回缓冲区A继续写入数据.

• 优点:
• 显著提高I/O效率和系统吞吐量. I/O操作和CPU处理可以并行进行, 形成流水线, 减少了等待时间.
• 提高了设备的利用率.

• 缺点:
• 需要两倍的内存空间来存放缓冲区.
• 实现相对单缓冲复杂一点, 需要额外的逻辑来管理两个缓冲区的切换.

• 适用于: 频繁的、大批量的I/O操作, 如文件读写、网络数据传输、图形显示(避免画面撕裂)等.

循环缓冲

1. 生产者-消费者模型: 循环缓冲通常用于实现生产者-消费者模型. I/O设备是“生产者”, 不断地将数据写入空闲的缓冲区. CPU是“消费者”, 不断地从已满的缓冲区中读取数据进行处理.

2. 指针管理: 操作系统会维护两个或多个指针:
• 一个“写入指针”/“头部指针”指向下一个可供I/O设备写入数据的空闲缓冲区.
• 一个“读取指针”/“尾部指针”指向下一个可供CPU读取数据的已满缓冲区.

3. 环形结构: 当读写指针到达缓冲区数组的末尾时, 它们会“环绕”回到数组的开头, 形成一个循环.

4. 同步机制: 需要同步机制(如信号量、互斥锁)来确保生产者不会覆盖消费者尚未读取的数据, 以及消费者不会读取尚未填充的数据. 当所有缓冲区都满时, 生产者必须等待; 当所有缓冲区都空时, 消费者必须等待.

• 优点:
• 提供了更高的并行性和平滑性, 进一步减少了I/O等待.
• 更有效地应对I/O速率波动, 因为有更多的缓冲区来吸收临时的数据峰值.
• 特别适合连续的数据流处理.

• 缺点:
• 实现复杂, 需要更复杂的逻辑来管理多个缓冲区和同步.
• 需要更多的内存空间(取决于缓冲区的数量).

• 适用于: 高速数据流传输, 如实时音频/视频处理、网络通信协议栈、日志系统、驱动程序与操作系统内核之间的数据交换等.

设备独立性

• 应用程序与具体物理设备无关, 系统增减或变更设备时不需要修改源程序;

• 易于应对各种I/O设备故障, 提高系统的可靠性;

• 增加设备分配的灵活性, 有利于更加有效地利用设备资源, 实现多道程序设计.

*独占型外围设备的分配(初学者可以跳过)

1. 静态分配: 进程运行之前一次性申请所有需要的设备资源, 实现简单, 能防止死锁, 但会降低设备利用率;

2. 动态分配: 随用随申请, 需要并发互斥管理, 可以提高设备利用率, 但是可能引发死锁.

• 设备类表: 每类设备对应于设备类表中的一个表项, 字段包括设备类, 总台数, 空闲台数, 设备表起始地址等;

• 设备表: 每类设备都有各自的设备表, 用于登记这一类(逻辑)设备中的每一台物理设备, 字段包括物理设备名, 逻辑设备名, 占有设备的进程, 分配标志, 好/坏标志等.

*SPOOLing系统(初学者可以跳过)

• “井”: 用作缓冲的存储区域, 调节供求之间的矛盾, 消除人工干预带来的损失

• “预输入程序”: 操作系统将一批作业从输入设备上预先输入到磁盘的输入缓冲区中暂时保存(“预输入”), 此后由作业调度程序调度作业执行, 作业使用数据时不必再启动输入设备, 只要从磁盘的输入缓冲区中读入

• “缓输出程序”: 作业执行中不必直接启动输出设备, 只要将作业的输出数据暂时保存到磁盘的输出缓冲区, 当作业执行完毕后, 由操作系统组织信息成批输出

• “井管理程序”

• 缓冲处理: 数据不是直接发送到外设, 而是先存储在磁盘等中间介质中. 进程只经由井管理程序从输入井读入数据, 向输出井输出信息, 使得全部I/O都基于磁盘.

• 异步操作: 输入/输出设备可以与CPU并行工作, 提高系统并发能力.

• 排队机制: 多个作业的I/O请求被排队, 按照一定策略有序处理.

1. 用户提交打印任务.

2. 任务被保存到SPOOL目录(一个磁盘区域).

3. 打印机空闲时, 系统将任务一个个送去打印.

• 提高CPU和外设的使用效率

• 支持多任务同时进行

• 避免I/O操作对程序执行的阻塞

• SPOOLing适用于速度慢、资源共享的设备(如打印机)

• 它与缓冲不同: 缓冲是短期内存存储, 而SPOOLing是长期/批量存储

• 打印任务调度

• 批处理系统的输入输出

• 数据备份任务

*磁盘(硬件内容, 可以略读或跳过)

一些名词

• 卷: 存储介质的物理单位, 对应于一盘磁带、 一块软盘、一个光盘片、一个硬盘分区等;

• 块: 存储介质上连续信息所组成的一个区域, 也叫做物理记录, 是主存储器和辅助存储器进行信息交换的物理单位, 每次总是交换整数块的信息. 不同类型存储介质的块的大小常常各不相同;

• 顺序存取设备: 严格依赖信息的物理位置次序进行定位和读写, 例如磁带机;

• 随机存取设备: 每个物理记录有确定的位置和唯一的地址, 存取任何一个物理块所需的时间几乎不依赖于此信息的位置.

对外接口

• 块设备(Block Device): 磁盘在操作系统中通常作为块设备出现, 数据以固定大小的块(如512字节或4KB)进行读写. 块设备支持随机访问, 允许操作系统直接寻址任意块. 所以可以将具有n个扇区的磁盘视为一个扇区数组, 从0~n-1编址. 磁盘保证对单个扇区的写入是原子的(要么完成更新, 要么完全没更新);

• 文件系统接口: 在用户层面, 磁盘通过挂载文件系统呈现为目录结构, 用户通过文件路径进行访问. 常见文件系统有FAT32、NTFS、ext4等. 文件系统负责将逻辑文件映射到磁盘物理块;

• 逻辑卷管理(LVM)接口: 操作系统可以通过逻辑卷管理器将多个物理磁盘抽象为逻辑卷, 实现磁盘的灵活分区、扩展与快照功能, 提升管理灵活性;

• 虚拟磁盘接口: 在虚拟化环境中, 磁盘可能表现为虚拟磁盘(如VDI、VMDK文件), 由虚拟机管理程序映射到物理磁盘资源, 提供隔离的存储空间.

基本内部结构

• 盘片(Platter): 圆形磁性材料的薄盘, 是数据存储的载体, 通常由多个盘片堆叠组成.

• 磁头(Head): 用于读写数据, 通常每个盘面对应一个磁头.

• 磁臂(Actuator Arm): 带动磁头在盘面上移动以定位到特定磁道.

• 主轴(Spindle): 驱动盘片高速旋转, 常见转速有5400 RPM、7200 RPM、10000 RPM等.

• 磁道(Track): 盘面上的同心圆区域, 用于组织数据. 在扇区线密度相同的情况下, 外圈周长更大, 包含的扇区更多. 考虑到移动磁头需要时间, 为了让磁头移动之后能继续访问下一个连续扇区(而非等待一周旋转), 磁道之间常常采取磁道偏斜设计, 即将相邻号的扇区错开一些, 使得磁头就位之后刚好续上下一个连续扇区;



不同盘面上位于相同位置的磁道构成柱面

• 扇区(Sector): 磁道上最小的数据单元, 常为512字节. 每个磁道分为多个固定扇区, 相邻扇区组合成簇.

• 柱面(Cylinder): 多个盘片上相同编号的磁道集合, 形成柱状结构.

• 磁道缓冲区(Track Buffer): 现代磁盘驱动器中自带的少量缓存(通常为8MB或16MB), 用于保存单条磁道上的所有扇区(方便响应对同一磁道上多个扇区内容的多次访问).

延迟计算

单磁道旋转延迟

多磁道寻道时间

• 最小寻道时间: 磁头已在目标磁道上, 为0.

• 平均寻道时间: 通常由厂商提供, 或通过经验模型估算.

• 最大寻道时间: 从最外层磁道到最内层磁道, 取决于磁盘物理结构.

传输时间

磁盘调度

💡

移臂调度: 减少寻道

最短寻道时间优先(SSTF)

• 选择距离当前磁头位置最近的请求进行处理.

• 优点: 减少平均寻道时间.

• 缺点: 可能导致远端请求长时间得不到响应(饥饿问题).

扫描算法(SCAN/LOOK)

• SCAN(双向扫描): 磁头朝一个方向移动时处理沿途的请求, 到达最末端后反向.

• C-SCAN(单向扫描): 只在一个方向上处理请求, 到达末端后快速返回起始端, 不处理请求.

• LOOK/C-LOOK(电梯调度): 扫描的改进, 当前移动方向上前方没有访问请求时就回头. “C”决定是双向还是单向.

• 优点: 相对公平, 减少饥饿现象.

• SCAN适合负载均匀场景, C-SCAN适合高请求密度场景.

分步SCAN(FIFO和SCAN的混合策略)

FSCAN

最短定位时间优先(SPTF)

• 选择预计完成时间最短的请求处理, 考虑寻道时间和旋转延迟的综合.

• 优点: 在高精度延迟控制场景下更优.

• 缺点: 计算复杂度较高, 依赖较详细的硬件特性模型.

旋转调度: 减少旋转

循环排序

优化分布

• 交替排序: 对扇区间隔编号. 交叉因子n:1表示相邻编号扇区会间隔n-1个扇区位, 防止处理当前扇区数据时, 下个要访问扇区已经转过;

• 将相邻扇区集中成簇读写(例如磁道缓冲区, 直接读一整条磁道);

• 按柱面集中存储数据(改串行为并行);

*廉价冗余磁盘阵列 RAID(硬件内容, 可以略读或跳过)

对外接口

• 逻辑块设备接口: RAID隐藏了底层多个磁盘的存在, 提供一致的逻辑块地址空间.

• 透明性: 上层应用和文件系统无需了解数据如何分布在多个磁盘上, 读写操作由RAID系统自动调度.

• 热插拔支持: 在支持热备份的RAID级别中, 对外接口可支持磁盘热插拔, 提高系统可用性.

• 性能与冗余增强: 在不同RAID级别下, 对外表现为更高的吞吐量(如RAID 0)或更高的容错能力(如RAID 1/5).

基本内部结构

• 多个物理磁盘: 通过硬件或软件组合而成.

• 条带化(Striping): 将数据划分为多个条带(Stripe), 分布在不同磁盘上, 提高并行读写性能.

• 冗余机制: 某些级别(如RAID 1、RAID 5)引入数据副本或奇偶校验位, 实现容错能力.

• RAID控制器:
• 硬件RAID控制器: 独立处理RAID逻辑, 减轻CPU负担, 提供更高性能.
• 软件RAID: 由操作系统管理, 成本低, 适用于普通服务器或桌面环境.

• 缓存与写策略: 部分RAID控制器带有缓存, 可配置写回或直写策略, 影响性能和可靠性.

故障模型

• 磁盘单点故障: 部分RAID级别可容忍一个或多个磁盘失效(如RAID 1、5), 系统仍能正常工作.

• 双盘失效: 标准RAID 5无法容忍两个磁盘同时失效, 需使用RAID 6等更高级别.

• 控制器或缓存故障: 硬件RAID控制器损坏可能导致整个阵列不可用, 应配备备份控制器或冗余设计.

• 数据不一致或写入中断: 在断电或系统崩溃情况下, 未完成的写操作可能导致冗余信息不一致(写孔问题).

RAID 0: 条带化

• 结构: 将数据按条带划分, 交错写入多个磁盘. 单个块的大小可以任意设置, 较大的块定位成本低但是并行性差, 较小的块反之, 需要权衡.

• 优点:
• 所有磁盘可以并行读写, 拥有极高的读写性能, 适用于高带宽应用.
• 无冗余开销, 磁盘空间完全可用.

• 缺点:
• 无容错能力, 任一磁盘损坏都会导致整体数据丢失.

• 适用场景: 对性能要求高且数据可重建的场合(如视频编辑、临时数据处理).

RAID 1: 镜像

• 结构: 每份数据在两个或多个磁盘上保持完全一致的副本.

• 优点:
• 具备完整的容错能力, 任何一个磁盘损坏数据仍然可用.
• 读性能提升, 可从多个磁盘并发读取.

• 缺点:
• 存储效率低, 磁盘利用率为50%(双盘镜像).

• 适用场景: 对数据安全性要求极高的系统, 如数据库、金融系统.

RAID 10: 混合策略

RAID 4: 奇偶校验

• 结构:
• 数据条带化分布在多个磁盘上.
• 单独设置一个磁盘存放所有奇偶校验信息.

• 优点:
• 支持容忍单个磁盘故障, 具有容错能力.
• 相较RAID 1节省空间, 效率更高.

• 缺点:
• 奇偶校验磁盘成为性能瓶颈, 每次写操作都需更新该磁盘.

• 适用场景: 对写入压力不高的中等容错场景.

RAID 5: 旋转奇偶校验

• 结构:
• 类似RAID 4, 但奇偶校验信息分散在各个磁盘中, 按条带轮转分布.

• 优点:
• 容忍单盘故障.
• 无奇偶校验磁盘瓶颈, 读写性能均衡.
• 存储利用率较高(N块磁盘中有 N-1 块可用于数据).

• 缺点:
• 写操作涉及读取旧数据和校验信息, 写性能低于RAID 0.
• 无法容忍双盘故障.

• 适用场景: 适合读多写少的通用服务器、存储系统.

总结

文件和目录API

文件

💡

*补充: 文件的逻辑/物理结构(初学者可以跳过)

文件的逻辑结构

又称为逻辑文件, 是独立于物理环境的, 用户概念中的抽象信息组织方式, 是用户能观察到并加以处理的数据集合.

文件的逻辑结构分为两种形式: 流式文件/记录式文件.

• 流式文件: 文件内的数据不组成记录, 只是由一串字节组成的信息流序列, 常常按长度读取所需信息, 也可以插入特殊字符作为分界(如字节流)

• 记录式文件: 一种有结构的文件, 是若干逻辑记录(文件中按信息在逻辑上的独立含义所划分的信息单位)所组成的记录流文件(如每个职工的工资信息是一个逻辑记录, 整个单位职工的工资信息便组成了该单位工资信息的记录式文件).

文件的物理结构

又称为物理文件, 指文件在物理存储空间中的存放方法和组织关系. 涉及块的划分、记录 的排列、索引的组织、信息的搜索等许多问题, 其优劣直接影响文件系统的性能.

物理结构分为顺序/连接/直接/索引文件几种.

• 顺序文件: 将一个文件中逻辑上连续的信息存放到存储介质中在物理上相邻的块中, 形成顺序结构, 优点是存取记录速度较快, 缺点是建立之前要确定文件长度一遍分配空间, 修改/插入/增加文件记录有困难;

• 连接文件(串联文件): 使用连接字来表示文件中各个物理块之间的先后次序, 第一块文件信息的物理地址由文件目录给出, 而每一块的连接字指出了文件的下一个物理块位置; 连接字内容为0时, 表示文件至本块结束, 即按链表结构存储, 所谓”连接字”即为链表指针(什么破翻译), 常用于输入井和输出井. 优点是易于对文件记录做增、删、改, 易于动态增长记录, 不必预先确知文件长度, 存储空间利用率高, 缺点是存放指针需额外的存储空间, 且待获得连接字后才能找到下一物理块的地址, 因而仅适用于顺序存取, 不能随机存取;

• 直接文件(散列文件): 通过散列计算逻辑记录的键值建立与其物理存储地址之间的对应关系, 可能出现哈希冲突, 可通过拉链法、循环探查法、二次散列法、溢出区法等方式解决;

• 索引文件(即使用inode): 为每个文件建立一张索引表(即inode), 每个条目包含一个记录的键(或逻辑记录号)及其存储地址(直接/间接指针). 索引表的地址(inode号)可由文件目录指出, 查阅索引表找到相应记录(即inode), 然后获得数据存储地址(即数据块指针). 优点: 是连接文件的一种扩展, 易于增删改的同时还能随机存取. 缺点是访问索引再访问数据块需要两次访存开销, 若将索引(inode)提前调入内存(变成活跃inode)则可以减少开销.

目录

文件系统API

创建文件

读写文件

文件重命名

文件元数据

删除文件

创建目录

读取目录

删除目录

硬链接

1. inode只在单一而非跨文件系统内唯一, 故不在同一文件系统内的文件和inode不能建立硬链接;

2. 不能创建目录的硬链接, 因为可能导致目录树中出现环.

符号链接

创建和挂载文件系统

文件系统实现

极简文件系统 VSFS

数据区域

inode

💡

inode记录了诸如文件类型, 文件大小, 文件所有者, 访问权限, 访问和修改时间, 文件包含数据块的位置等元数据信息.

特别地, inode中不包含人类可读的高级文件名.

1. 直接指针: 在inode中维护若干个指针, 每个指向一个数据块. 缺陷: 能维护的指针数量有限 → 文件大小有上限, 对大文件支持不佳.

2. 二级索引: 在inode中维护若干个直接指针和一个间接指针, 间接指针指向一个专门用于存放直接指针的数据块(可以形象理解为”直接指针库”). 所有的直接指针都指向一个数据块.

3. 多级索引: 指针库中继续存放指向其他指针库的间接指针, 即可通过树结构构建指数级增长的数据块映射. 大部分文件很小, 所以多级索引的树结构为不平衡树.

💡

例题:

位图

超级块

目录组织

创建文件

1. 为新文件分配inode和活动inode, 将活动inode加入主存活动inode表(存放活动inode的主存区域);

2. 将inode号和文件名组成新目录项写入目录文件数据;

3. 初始化新inode(如存取权限和链接计数等);

4. 分配用户打开文件表(维护fd → 系统打开文件表项的映射)项和系统打开文件表(维护系统打开文件表项 → 活动inode表表项的映射)项, 并初始化(如文件读写偏移);

5. 将各表项用指针链接起来, 将文件描述符fd返回给用户, fd即为该文件在用户打开文件表中的索引.

删除文件

1. 将指定文件的目录项从所在目录中删去;

2. 文件的链接用户-1, 若变为0则释放文件占用的存储空间(使用unlink(fileName)调用)

打开文件

1. 遍历路径名,(在磁盘中)通过父目录的inode号索引到父目录的内容, 再从父目录的内容条目中找到子目录或目录中文件的inode号, 递归查找(起点: 根目录使用约定的周知inode号, Unix中一般为2, 找到目标文件的inode后将其读入内存(令其成为活动inode);

2. 进行权限检查, 若检查通过则在进程私有的用户打开文件表中, 在全局的系统打开文件表中, 以及系统的全局主存活动inode表中各添加一个条目, 并用指针结构将它们链接起来. 最终将文件描述符fd返回给用户.
💡
全局打开文件表中, 可以为不同的进程维护不同的记录, 如为多个进程独立维护文件读写偏移等.

不同用户打开文件表项可以通过指向同一个系统打开文件表项来实现文件共享(共享文件读写偏移), 也可以指向不同系统打开文件表项, 再让不同的系统打开文件表项指向同一个活动inode表项(分别拥有自己的文件读写偏移).

读取文件

1. 打开文件;

2. 检查read权限;

3. 若权限合法, 则发出read()系统调用, 设置文件偏移量并开始读取, 从用户打开文件表索引到系统打开文件表, 再索引到活动inode表, 查阅活跃inode以获取每个块的位置, 从磁盘中读取块, 更新inode的相关字段, 文件偏移量实时更新;

4. 结束访问后调用关闭过程.

写入文件

关闭文件

1. 根据fd找到用户打开文件表项, 再由此找到系统打开文件表项, 再由此找到活动inode表项;

2. 释放用户打开文件表项;

3. 将对应系统打开文件表项中的引用数f_count-1, 若减到0则释放该系统打开文件表项;

4. 将对应活动inode中的引用数i_count-1, 若减到0则将该inode中的内容写回磁盘的相应位置, 然后释放该活动inode.

文件共享

1. 静态共享: 不同目录项对应的文件名共享inode(硬链接/符号链接);

2. 动态共享: 多个运行时进程并发访问同一个文件的数据.

缓存和缓冲

*主存映射文件(初学者可以跳过)

1. 虚拟地址空间映射:
当一个文件被主存映射时, 操作系统并不会立即将整个文件内容加载到物理内存中. 相反, 它会在进程的虚拟地址空间中分配一块区域, 并将这块区域与磁盘上的文件建立起一一对应的关系.

2. 按需分页/按需加载(Demand Paging):
实际的数据加载是按需进行的. 当程序首次访问映射区域中的某个地址时, 如果对应的文件内容(通常是一个页大小的数据块)不在物理内存中, 就会触发缺页中断(Page Fault). 此时, 操作系统会负责将该页从磁盘加载到物理内存中, 并更新页表, 使虚拟地址能够正确地映射到物理地址.

3. 内存访问代替I/O操作:
一旦数据被加载到物理内存, 后续对该区域的访问就变成了直接的内存访问, 就像访问普通的内存数组一样. 这比传统的I/O操作快得多, 因为避免了:
• 系统调用开销: 传统I/O操作需要频繁地在用户态和内核态之间切换.
• 数据拷贝: 传统I/O操作通常涉及数据从内核缓冲区到用户缓冲区, 以及从用户缓冲区到内核缓冲区的两次拷贝. 主存映射文件通过直接映射, 减少了甚至避免了这种不必要的拷贝.

4. 数据同步:
对映射内存区域的修改会自动(或在特定情况下由操作系统控制)同步回磁盘上的原始文件. 这意味着你修改内存中的数据, 就是直接修改文件本身.

• 高效文件I/O: 这是最常见的用途. 对于处理大文件(例如数据库文件、日志文件、大型图像文件等), 主存映射文件可以提供比传统 read()/write()更高的性能, 因为它避免了数据拷贝和频繁的系统调用.

• 进程间通信(IPC)/ 共享内存: 多个进程可以将同一个文件映射到各自的虚拟地址空间中. 这样, 它们就可以通过访问这块共享的内存区域来高效地进行数据交换, 而无需复杂的消息传递或管道机制. 这是实现共享内存的一种重要方式.

• 加载程序和动态链接库: 现代操作系统在加载可执行程序(.exe)和动态链接库(.dll/.so)时, 通常会使用主存映射技术. 程序代码和数据被映射到进程的虚拟地址空间, 只有当实际需要时才会被加载到物理内存, 这大大加快了程序启动速度并节省了内存.

• 页面文件(Page File)的实现: 虚拟内存系统利用磁盘上的页面文件(也称为交换文件或交换区)作为物理内存的扩展. 这个页面文件在某种意义上就是一种主存映射文件, 操作系统将其映射到虚拟内存空间, 用于实现内存页的换入换出.

• 性能提升: 显著减少了I/O操作的开销(系统调用、数据拷贝), 尤其适合大文件和随机访问.

• 简化编程: 程序员可以像操作内存一样操作文件, 无需关心文件指针、缓冲区管理等细节, 代码更简洁.

• 多进程共享: 提供了一种高效、直接的进程间共享内存的方式.

• 节省内存: 对于部分文件访问, 可以只加载文件的一部分到内存, 避免一次性加载整个大文件. 操作系统可以利用其内存管理机制(如页面置换算法)自动管理哪些文件页应该驻留在物理内存中.

• 对齐限制: 内存映射通常以内存页(例如4KB)为单位进行. 如果文件大小不是页大小的整数倍, 可能会导致一些内存浪费(但通常不是大问题).

• 同步问题: 如果多个进程同时写入同一个共享映射文件, 需要适当的同步机制(如互斥锁、信号量)来避免数据竞争和损坏.

• 错误处理: 当底层文件发生错误(如磁盘损坏)时, 内存访问可能会导致进程崩溃或异常.

• 资源管理: 映射文件会占用进程的虚拟地址空间和文件句柄, 需要正确地解除映射和关闭文件.

快速文件系统FFS

旧文件系统的局部性问题

FFS: 柱面组

文件和目录的分配策略

• 对目录: 找到被分配目录的数量较少(希望跨组平衡目录)且包含大量自由inode(希望随后能分配一堆文件)的块组.

• 对文件: 首先确保将文件的inode与其数据块分配到相同的块组中(防止inode与数据块之间的长时间寻道), 并将同一目录下的所有文件与该目录放在同一个块组中(不同目录下的文件则可能相互远离).

• 例外: 对大文件, 若按照一般文件分配, 则一个大文件很容易填满整个块组, 会影响其他相关文件进入该块组, 破坏文件存储的局部性, 不符合需要. 因此对于大文件, FFS将一定数量的数据块分配到第一个块组, 将下一个大块(间接指针指向的部分)放在另一个块组中, 递归进行, 从而跨组平衡大文件, 给每组都留下空间. 缺陷是跨块组访问同一文件的大块会损失性能, 但这是大文件和小文件之间的权衡. FFS采取的具体策略: 基于inode本身的结构, 12个直接指针指向的数据块与inode放在同一块组中, 其余每个间接块(指针库)及其指向的所有块(数据块/下一级指针库)都放在不同的组中. 这种策略下除了开头的12个块, 文件的每 个块都放在单独的组中.

其他设计

• 引入子块(比标准块小的块)以支持小文件, 减少内部碎片. 小文件增大到一定程度后复制到一个完整的标准块, 并释放子块以备将来使用. 然而频繁复制效率低下, 所以常常通过缓冲来避免使用子块(除非必需否则不用);

• 针对性能优化磁盘布局, 不用连续扇区分布, 而是间隔分布扇区, 用于适应连续请求与旋转之间的时间差(即下一个请求到达时还能赶上下一个连续扇区, 若连续分布扇区则会错过, 多转一圈). FFS会根据磁盘的性能参数决定布局时应该跳过多少块安排下一个扇区;

• 现代磁盘优化: 将整个磁道读取到内部磁盘缓存(磁道缓冲区)中, 连续访问时不需要连续读取扇区, 而是直接读缓冲区即可;

• FFS引入长文件名, 符号链接和原子rename操作.

文件系统检查程序FSCK

“不怕在写入开始之前或完成之后发生崩溃, 就怕在完成了部分步骤但还有剩余部分未完成时崩溃, 让文件系统处于中间态. ”

1. 超级块: fsck首先检查超级块是否合理, 主要是进行健全性检查, 例如确保文件系统大小大于分配的块数. 通常, 这些健全性检查的目的是找到一个可疑的(冲突的)超级块. 在这种情况下, 系统(或管理员)可以决定使用超级块的备用副本;

2. 空闲块: 接下来, fsck扫描inode、间接块、双重间接块等, 以了解当前在文件系统中分配的块, 生成正确版本的分配位图. 因此, 如果位图和inode之间存在不一致, 则最终信任inode内的信息并修正位图. 对所有inode执行相同类型的检查, 确保所有(看起来像)已分配的inode都在inode位图中有标记;

3. inode状态: 检查每个inode是否存在损坏或其他问题. 例如, fsck 确保每个分配的inode的类型字段均有效(即常规文件、目录、符号链接等). 如果inode字段存在问题且不易修复, 则认为该inode可疑, 将其清除并更新inode位图;

4. inode链接: fsck还会验证每个已分配的inode的链接数. fsck从根目录开始扫描整个目录树, 并为文件系统中的每个文件和目录构建各自的链接计数. 如果新计算的计数与inode中找到的计数不匹配, 则采取纠正措施, 通常是修复inode中的计数. 如果发现已分配但没有被任何目录引用的inode, 则将其移动到lost+found目录.

5. 重复: fsck还检查重复指针, 即两个不同的inode引用同一个块的情况. 如果其中某个inode明显错误则可能会被清除. 或者, 可以复制指向的块, 从而根据需要让每个inode指向相同数据的不同副本.

6. 坏块: 在扫描所有指针列表时, 还会检查坏块指针. 如果指针指向明显超出其有效范围的某个地址(例如指向大于其所在分区大小的块), 则认为该指针有问题. 在这种情况下, fsck不能做任何太聪明的事情, 只是从inode或间接块中删除该指针.

7. 目录检查: fsck不了解用户文件的内容, 但是了解目录数据的格式(因为目录包含由文件系统本身创建的特定格式的元数据, 而非任意数据). 因此fsck对每个目录的内容执行额外的完整性检查, 确保“.” 和“..”条目在最前面, 且目录条目中引用的每个inode都已分配, 且整个层次结构中没有目录被引用超过一次.

预写日志

概述

物理日志结构

元数据日志

日志自身的原子写入

使用日志进行恢复

1. 如果在日志写入期间崩溃(导致日志都没写全), 就直接抛弃该更新;

2. 事务已经完整登记到日志, 在根据日志写入更新期间发生崩溃, 则按顺序重放(replay)事务, 试着再写一遍. 这种策略称为重做日志(redo logging).

块复用问题

1. 禁止复用: 永远不复用块, 直到该块从日志中绝迹;

2. 撤销记录: 将删除行为作为一条”撤销记录”写入日志, 重放之前先扫描日志检查, 从而对有撤销记录的块特判, 不进行重放.

其他方案

1. 软更新: 对文件系统的所有写入行为排序(例如先写指向的数据块再写指向它的inode, 保证inode永远不会指向垃圾), 但是构建顺序规则需要复杂的文件系统知识;

2. 写时复制: 永远不会覆写文件或目录, 只选择磁盘上从未使用的位置存放更新, 完成大量更新后翻转文件系统的根结构以纳入指向方才更新的地址的指针;

3. 反向指针: 在每个数据块中加上反向指针, 指向其所属的inode, 与inode中的正向指针形成双重验证, 获得惰性崩溃一致性;

4. 乐观崩溃一致性: 尽可能多地向磁盘发出写入, 使用事务校验和等技术检测不一致, 可以将性能提高一个数量级, 但是需要特殊的磁盘接口才能实现.

日志结构文件系统LFS

概述

1. 内存大小不断增长, 可以缓存更多数据, 从而读取行为多数时候可以从缓存中直接获取数据, 磁盘流量中写入流量的占比日益增大, 因此文件系统的性能越来越依赖于写入性能;

2. 随机I/O与顺序I/O的速率差距不断扩大, 因为寻道时间和旋转延迟下降较慢, 而传输带宽迅速增大, 因此若能以顺序方式访问磁盘则可以获得极大的性能优势;

3. 当时的文件系统在许多常见工作负载(如创建新文件)下表现不佳, 需要多次写入多个结构, 而且写入之间存在很多短寻道和旋转延迟;

4. 对RAID支持不好.

顺序写入设计

查找inode

1. 若放在周知的固定地址: 固然简单有效, 但是在该地址与写入目标地址之间横跳会导致寻道开销;

2. 实际采用的策略: 将imap追加到紧随最新一次写入之后的位置. 因此, 当写入新数据块时, LFS实际上将新数据块本身, 其inode和最新版本的完整imap一同写入磁盘.

读取文件

目录数据

垃圾收集

💡

Q: 如何判定块的死活?

A: LFS在每个段的头部维护一个”段摘要块(segment summary block)”, 记录该段中每个数据块的inode号及其在所属文件中的偏移量. 根据这些信息可以直接确定块的死活.

判定流程: 查段摘要块找到要判定的块的inode号 → 查imap找到该数据块的inode → 查inode检查指针字段, 检查指针是否指向该数据块(实际上是正向指针和反向指针对质). 如果一致则存活, 不一致则为垃圾.

在实际实现时LFS做了更多设计, 方便判定块的死活, 例如为文件inode在imap中的记录和所属段的段摘要块中分别维护一个版本号. 当文件被截断或删除时版本号++, 并在imap和新的所属段中登记. 要判定某个块是否存活时只需要检查所属段的段摘要块中的版本号是否与imap中的匹配即可, 匹配则存活, 否则为垃圾.

1. 何时清理: 固定周期性清理/空闲时间清理/磁盘已满时清理/...;

2. 清理哪些块: 一种可能方法(分离冷热段): 常发生覆盖的段(热段)少清理(因为刚清理并转移了活块就可能又产生新的垃圾), 不常发生覆盖的段(冷段)多清理(垃圾就是垃圾, 存活就是存活).

崩溃恢复和日志

虚拟文件系统(VFS)

1. 应用层: 用户调用VFS的API, 可直接使用标准UNIX文件系统调用来操作文件, 无需考虑具体文件系统特性和物理存储介质;

2. 虚拟层: 对所有具体文件系统的共同特性进行抽象, 构建一个与具体文件系统实现无关的虚拟层, 并在此层次上定义与用户的一致性接口, 即组成虚拟文件系统VFS(依赖倒置的中心);

3. 实现层: 用各种文件系统作为基础来实现VFS规定的接口功能.

VFS的数据结构组成

1. 超级块: 代表一个文件系统(即VFS自身);
存放已挂载的文件系统信息. 如果是基于磁盘的文件系统, 该对象便对应于存放在磁盘上的文件系统控制块. 每个超级块对象都对应一个文件系统.
当挂载一个具体的文件系统时, 内核调用alloc_super()函数为其分配一个VFS超级块, 并从磁盘读取具体文件系统超级块中的信息填充进来. VFS超级块在具体文件系统挂载时建立, 并在卸载时自动删除, 可见VFS超级块仅存在于主存中.

2. inode节点: 代表文件;
存放通用的文件信息, 如果虚拟化的是基于磁盘的文件系统, 则该对象对应于存放在磁盘上的文件inode. 每个inode都有一个inode号, 唯一标识某个文件系统中的指定文件.
对于UNIX类文件系统来说, 这些信息从磁盘inode直接读入VFS的inode对象中. 具体文件系统存放在磁盘上的inode称为静态inode, 它的内容被读入主存VFS的inode才能工作, 后者也称为活动inode.

3. 目录项: 代表路径中一个组成部分;
存放目录项与对应文件进行链接的各种信息(文件名与inode号的二元组的列表). VFS把最近最常使用的dentry对象放在目录项Cache中, 加快文件路径名搜索过程, 以提高系统性能.

4. 文件对象: 代表已经由进程打开的文件对象.
存放已打开文件与进程的交互信息, 这些信息(用户打开文件表, 系统打开文件表)仅当进程访问文件期间才存于主存中. 文件对象在执行open()系统调用时创建, 执行close()系统调用时撤销.
每个文件都用一个32位数字来表示下一个读写的字节位置, 通常称它为文件偏移(offset), 每当打开一个文件时, 文件偏移被置0, 读写操作便从这里开始. 允许通过lseek()系统调用对文件位置作随机定位.
Linux建立文件对象(file结构)来保存打开文件的读写偏移, 还把指向该文件inode的指针也放在其中, 称为系统打开文件表.
操作系统之所以不直接使用dentry结构, 是因为多个进程能够打开同一个文件. 每一个file结构中记录了文件访问模式, 读写指针等信息, 实际上对应了一个进程的一次打开过程, 而dentry只能表示静态的存储关系. 简而言之, 在运行时可以有任意个对应同一文件对象的file结构, 而dentry只能与文件对象做静态对应(一一对应, 或者静态的软硬链接).
VFS使用文件描述符fd描述打开的文件. 每个进程用一个files_struct结构来记录文件描述符的使用情况, 这个结构称为用户打开文件表. 进程PCB的task_struct结构的成员files中存有一个指针指向该用户打开文件表.

文件系统在VFS中的注册与注销

文件系统在VFS中的挂载与卸载

1. 文件系统挂载
明确文件系统类型名、所在物理设备名和安装点, 再用mount命令挂载.

2. 文件系统挂载过程
寻找匹配的file_system_type, 查找安装点VFS inode, 分配一个VFS超级块, 利用read_super()函数读入磁盘中具体文件系统的超级块参数, 申请一个vfsmount数据结构.