第11周 星期二 第2大节

• 视频：screen_操作系统与分布式计算_第11周_星期二_第2大节.mp4
• 字幕：transcripts/第11周_星期二_第2大节.txt

时间轴

• [07:48] 多重索引 vs 链式索引讨论
• [14:10] UNIX inode（索引节点），不含文件名
• [15:37] 混合索引结构（10直接+1一级+1二级+1三级），最大约40GB
• [24:29] 文件目录与FCB
• [31:24] 目录结构演变：一级→二级→多级（树形）
• [51:07] 无环图目录结构（文件共享）
• [58:28] inode分离FCB，硬链接 vs 软链接
• [01:08:47] 存储空间分配：空闲区表→位视图→空闲块链→成组链接法
• [01:50:32] 文件系统调用：create/delete/open/close/read/write
• [02:14:00] 内存映射文件、文件保护与备份
• [02:18:30] 文件系统分层架构

文件物理结构：多重索引 vs 链式索引

链式索引（Linked Index）

• 索引块之间以链表方式串接，每个索引块末尾有指针指向下一个索引块
• 缺点：
  • 随机访问必须从第一个索引块开始顺序遍历（线性访问），导致多次磁盘IO
  • 链上某个链接丢失后，后续所有索引块不可达
  • 文件大小随索引块数量线性增长（每增加一个索引块，文件容量增加一个索引块的寻址范围）

多重索引（Multi-level Index）

• 类似多级页表，索引块之间通过更高层索引表组织
• 优点：
  • 随机访问O(1)查表时间（通过索引表直接定位物理块）
  • 文件容量呈指数级增长：二级索引可寻址 n × n 个物理块，三级可达 n × n × n
  • 链断裂风险更低

UNIX inode（索引节点）

基本概念

• inode（index node）是UNIX系统中每个文件对应的唯一控制结构
• inode中不包含文件名——这是刻意设计
• inode包含内容：
  • 文件访问控制信息（模式、权限）
  • 链接数（link count），记录有多少个目录项指向该inode
  • 文件创建者、文件长度（字节）、访问时间等
  • 文件在外存上的存储位置信息（索引表地址）

为什么inode不含文件名

• 将FCB拆分为”文件名+inode号”（目录项）和”inode”（控制信息）两部分
• 便于实现文件共享——多个目录项可指向同一inode，控制信息仅存一份，保证一致性

UNIX混合索引结构

结构组成（共13个地址项）

10个直接地址（直接指向物理块）    → 10 × 1K = 10K
 1个一级间接地址（指向索引块）     → 341 × 1K = 341K
 1个二级间接地址                   → 341 × 341 × 1K ≈ 116M
 1个三级间接地址                   → 341 × 341 × 341 × 1K ≈ 40GB

• 假设物理块大小 = 1K，每个地址项占3字节，每块可存341个地址项

最大寻址范围

• 总计 ≈ 10K + 341K + 341²K + 341³K ≈ 40GB

设计动机：适配不同大小文件

• 小文件（≤10K）：直接寻址，无需读索引块，效率最高
• 中等文件（10K~341K）：一级间接索引
• 大文件（341K~116M）：二级间接索引
• 超大文件（116M~40GB）：三级间接索引
• 避免了固定多级索引对小文件的性能浪费（多级索引需要多次IO读索引块）

文件逻辑结构与物理结构

• 逻辑结构：文件在用户视角的组织方式（如字符流、记录等），与存储设备无关
• 物理结构：文件在外存上的实际存储方式（连续、链式、索引）
• 连续存储适用于磁带（只能顺序访问）；磁盘支持随机访问，三种结构均可
• 索引结构类似于内存的页式存储管理——逻辑块到物理块的映射通过索引表实现

文件目录与FCB

FCB（File Control Block）

• 文件控制块，操作系统用于管理文件的控制信息结构
• 核心字段：
  • 文件名
  • 文件创建者/所有者
  • 文件在外存上的位置（索引表地址）
  • 创建/修改/访问时间戳
  • 访问口令
  • 文件权限（只读/读写等）
• FCB与文件体分离：FCB只管控制信息，不关心文件内容

文件目录

• 文件目录是FCB的集合，以目录文件形式存放在磁盘特定位置
• 目录文件本身是一个特殊文件，存放的是其下各文件的FCB
• 目录的核心功能：
  • 按名存取：用户只提供文件名，系统通过目录找到文件物理位置
  • 提高检索速度：高效组织目录结构以加速文件定位
  • 文件共享：同一文件可被多个路径访问
  • 解决重名：不同用户/目录下文件可以同名

目录结构演变

1. 一级目录结构

• 所有FCB存放在一个线性表中（或哈希表组织）
• 查找方式：逐项匹配文件名（线性查找平均长度 N/2）
• 问题：
  • 文件不能重名
  • 不便于文件共享
  • 查找速度慢（文件多时）
• 适用于早期单道批处理系统（单用户）

2. 二级目录结构

• MFD（Master File Directory，主目录）：存放各用户目录项
• UFD（User File Directory，用户目录）：每个用户自己的文件FCB集合
• 引入路径概念，文件名包含路径信息
• 适用于多用户操作系统
• 问题：同一用户下仍不能重名

3. 多级（树形）目录结构

• 当前主流操作系统的目录结构
• 任意级目录下既可放子目录也可放文件
• 叶子节点是文件，中间节点是目录
• 优点：
  • 利于文件分类
  • 不同目录层级下可重名
  • 通过当前目录 + 相对路径缩短查找路径
• 缺点：不便于文件共享（树中叶子只能在一个枝条上）

无环图目录结构与文件共享

无环图目录

• 在树形目录基础上允许一个文件同时属于多个不同目录
• 同一文件在外存上只存一份物理副本，通过不同路径访问
• 解决了树形目录无法共享的问题
• 问题：多个目录项指向同一文件体时，FCB一致性难保证

inode分离FCB的解决方案

• 将FCB拆分为两部分：
  1. 目录项：只包含文件名 + inode号
  2. inode节点：存放完整的文件控制信息（独占一份）
• 多个目录项的inode号相同 → 指向同一inode → 访问同一文件体
• inode中的link count记录共享数

硬链接（Hard Link）

• 不同目录项指向相同的inode节点
• link count递增；删除时link count减1，仅当减至0时才真正删除文件体
• 读取方式：直接通过inode定位文件物理块

软链接 / 符号链接（Symbolic Link / Soft Link）

• 类似于Windows的快捷方式
• 文件体中存放的是目标文件的路径名
• 访问时：打开符号链接文件 → 读出路径 → 按路径逐级查找 → 找到目标文件的FCB → 读取文件
• 删除原文件时：不检查是否有符号链接指向它（软链接不影响link count）
• 原文件删除后，符号链接成为”悬空链接”

存储空间分配

文件卷

• 文件系统存储空间的基本逻辑单位
• 可对应一个物理盘、一个分区（C/D/E区），或多个物理盘的组合

1. 空闲区表（Free List）

• 类似内存的空闲分区表：记录每个连续空闲区的起始块号和块数
• 适用于连续文件存储结构（需要找连续的空闲空间）
• 分配时查找足够大的空闲区进行切割

2. 位视图法（Bitmap / Bit Vector）

• 每一位代表一个物理块的状态：0=空闲，1=占用
• 一个字节可表达8个物理块
• 例：10GB磁盘，每块4K，共2.5M个块，位视图需 2.5M÷8≈312.5KB，约78个盘块
• 优点：易于找到连续空闲块（扫描连续0）
• 缺点：大磁盘时位视图本身占用较大额外空间
• 地址转换：
  • 字节号 = 相对块号 ÷ 8（商）
  • 位号 = 相对块号 ÷ 8（余数）
  • 相对块号 = 字节号 × 8 + 位号
• 通常加载到内存中以提高分配回收效率
• Windows NTFS使用位视图方式

3. 空闲块链（Free Block Chain）

• 每个空闲物理块中存放下一个空闲块的指针，所有空闲块链接成链表
• 链头保存在管理块中（常驻内存）
• 分配：从链头取一块，先读取其中的指针更新管理块，再分配出去
• 回收：将回收块加入链头
• 优点：以空记录空，不占用额外存储空间
• 缺点：每次分配/回收需读写磁盘块（IO频繁），系统开销大

4. 成组链接法（Group Linking）—— UNIX方案

• 对空闲块链的优化改进：一组一组地组织空闲块
• 每组的第一个空闲块记录下一组空闲块的信息（块号+数量）
• 第一组信息存放在内存专用块中（减少磁盘IO）
• 分配：
  • 专用块中空闲块数 > 1：直接分配，块数减1
  • 专用块中空闲块数 = 1：需先将该块中的下一组信息读入内存专用块，再分配该块
  • 若第一单元为0，则磁盘已满
• 回收：
  • 专用块空闲块数 < 组容量：直接写入
  • 专用块已满：先将专用块内容写入回收的第一个空闲块，再更新专用块
• 优点：
  • 以空白块记录空白块，无需额外空间
  • 一次IO读入一组（如100个）空闲块信息，大幅减少IO次数
  • 绝大部分分配回收在内存中完成

文件系统调用

文件的建立与删除

create（建立文件）

1. 检查参数合法性（文件名格式、卷名是否存在等）
2. 在目录结构适当位置创建FCB项
3. 填入FCB参数（文件名、创建者、创建时间等）
4. 分配外存空间（或采用lazy策略，真正写入时才分配）
5. 建立索引表，将索引表信息填入FCB

delete（删除文件）

1. 检查参数，获得文件名
2. 根据文件名查找FCB
3. 根据FCB中的索引表找到文件占用的外存空间
4. 释放空间（并非清零）——仅从索引表中清除物理块号，磁盘内容仍保留，因此误删后可恢复
5. 从目录结构中删除FCB项

文件的打开与关闭

open（打开文件）

1. 检查参数合法性，获得文件路径名
2. 查找目录结构，找到FCB
3. 将FCB从外存调入内存，存入内存活跃文件目录表
4. 建立本次打开的读写状态信息表（记录当前读写指针位置等）
5. 将读写状态信息表地址存入进程PCB的打开文件表
6. 返回文件描述符FD

为什么读写前必须先open？ —— open负责将FCB调入内存并建立进程级的读写状态信息，后续read/write直接使用这些内存结构。

多个进程可同时打开同一文件：共享FCB（避免重复从外存加载），但各自拥有独立的读写状态信息表。

close（关闭文件）

1. 根据FD在PCB打开文件表中找到对应的读写状态信息表
2. 释放读写状态信息表空间
3. 如果活跃文件目录表中该FCB不再被任何进程使用（引用计数为0），则释放该FCB占用的内存空间

为什么读写后必须close？ —— 否则FCB和读写状态信息表持续占用内存，造成资源泄漏。

文件的读写

read / write

1. 核实参数，根据FD获得读写状态信息表
2. 通过读写状态信息表获得活跃目录表中的FCB
3. 从FCB核实操作许可（如只读文件不可write）
4. 根据FCB中的定位信息，将逻辑地址转换为物理地址（索引表映射）
5. 通过文件缓冲区读写数据（减少IO次数）
6. 调用外存驱动程序完成IO

内存映射文件（Memory-Mapped File）

• 将文件直接映射到进程的虚拟地址空间
• 对文件的读写如同对内存的读写（通过指针直接访问）
• 利用虚拟页式存储管理机制处理缺页（自动从外存加载）
• 适合大文件的高效随机访问

文件保护与备份

文件保护方式

1. 访问控制：FCB中设置权限（只读/读写），通过操作合法性验证保护
2. 口令保护：文件属性中设置口令，访问时需核对
3. 加密保护：写入时加密（密钥映射），读出时解密，防止未授权访问

文件破坏的两类原因

1. 不正确的访问方式：越权操作（如对只读文件写）→ 通过访问控制防范
2. 存储介质损坏/病毒破坏：→ 通过备份防范

备份方式

• 全量转储：所有文件完整备份到其他介质
• 增量转储：只备份每天变化的部分
• 同步备份（镜像盘）：写入时同时写入两个备份盘

文件缓冲管理

• 文件读写不直接按字节操作外存，而是在内存中设置文件读写缓冲区
• 读写数据先经缓冲区，缓冲区满了才整块IO到外存
• 缓冲区中的文件信息可按哈希表/哈希队列组织

文件系统分层架构

1. 用户调用接口与初始化模块

• 处理用户进程发出的文件系统调用
• 参数合法性检查与补充
• 将上层调用转化为底层系统调用接口
• 负责用户空间与内核空间的数据传输

2. 文件目录系统

• 管理目录结构的组织（FCB的建立/删除/查找）
• 管理内存活跃文件目录表
• 管理文件读写状态信息表
• 将上层调用向下传递

3. 存取控制验证模块

• 从目录信息获取访问权限
• 验证当前操作是否合法

4. 逻辑文件系统 + 文件信息缓冲区

• 将用户读写的逻辑记录转化为逻辑块号和块内偏移
• 管理文件读写缓冲区
• 将逻辑块映射到物理块

5. 物理文件系统

• 将逻辑块号转化为物理块号
• 调用底层硬盘驱动程序
• 完成实际的数据IO（内存↔外存）

文件系统设计目标

• 方便灵活（用户无需关心物理存储细节）
• 安全可靠
• 支持文件共享
• 实现按名存取