#文件管理

#考点定位

• 大纲章节：文件与文件系统（概念）；文件逻辑结构（顺序文件、索引文件、索引顺序文件）；文件目录（FCB 与索引结点、目录结构、文件共享）；文件物理结构（连续分配、链接分配、索引分配）；文件存储空间管理（空闲表、空闲链、位示图、成组链接）；磁盘组织与管理（磁盘结构、调度算法、访问时间）
• 常见题型：选择题（结构特点辨析、目录/共享判断）+ 计算小题与大题（混合索引最大容量、位示图字号位号、磁盘调度磁道移动数、磁盘访问时间）——本章是 OS 计算题的稳定出处
• 考查频率：高（几乎每年至少一道选择；混合索引、位示图、磁盘调度轮流出综合计算）
• 工程师读者注意：你天天和文件系统、SSD 打交道，但考试考的是机械盘时代的模型（磁道、寻道、盘块链接），且计算题的编号口径（从 0 还是从 1 开始）直接决定对错——按本站模板算，别用工程直觉跳步
• 前置知识：操作系统概述（层次结构、中断）；进程与线程（打开文件表在进程与系统两级，与 PCB/PCB 组织衔接）

#一、文件与文件系统

#1.1 文件的定义与属性

定义（考点口径）：文件是以计算机硬盘为载体的、存储在计算机上的相关信息的集合，具有文件名，且文件体（内容）与文件属性（元数据）分离存储。用户通过文件名"按名存取"，由文件系统完成名字到物理位置的映射。

文件的属性（元数据，选择题按"哪些属于文件属性"命题）：

#1.2 文件的分类

#1.3 文件系统的功能

文件系统是 OS 中负责管理文件的软件机构，提供：文件命名与按名存取、目录管理、存储空间分配回收、文件共享与保护、向用户提供接口（创建/删除/读写/打开/关闭）。打开文件的本质：将文件的目录项（FCB/索引结点信息）复制到内存的"打开文件表"中，此后按内存中的信息快速存取，避免反复查目录——进程级打开文件表在 PCB 中，系统级打开文件表全系统一张。

#二、文件的逻辑结构

逻辑结构是用户视角的文件组织形式，与存储介质无关；物理结构（第四节）是 OS 视角在磁盘上的存放形式。两者的映射是文件系统的核心职责。

#2.1 无结构文件与顺序文件

无结构文件（流式文件）：一串字节，OS 不解释内容，长度按字节计。Unix/Windows 普通文件均如此。

有结构文件（记录式文件）：由若干记录组成，每条记录是相关数据项的集合。按记录长度是否固定分为定长记录与变长记录。

顺序文件：记录按某种顺序排列，是最简单的逻辑结构。分两种：

顺序文件的存储方式（物理上）：顺序存储（定长记录可随机存取第 i 条记录：地址 = 起始 + (i−1)×L）或链式存储（只能顺序存取）。可变长记录即使顺序存储也无法随机存取（不知每条长度）。

顺序文件的特点（选择题高频）：

• 批量存取（顺序读写整块记录）时效率最高；但对单条记录的查找/插入/删除很慢
• 磁带（顺序存取设备）上唯一可用的文件组织形式

#2.2 索引文件

为解决变长记录无法随机存取的问题：为文件建立索引表，每条记录对应一个表项，含指向记录的指针（逻辑地址）和记录长度，索引表按关键字有序排列（便于二分/分块查找），表项定长。

• 索引表本身定长记录，可顺序存储，支持随机存取第 i 条索引
• 每查一条记录都要先查索引表——索引表很大时可建多级索引
• 典型用途：对时间要求苛刻的定长记录快速查找

#2.3 索引顺序文件（考点：平均查找次数计算）

索引顺序文件 = 顺序文件 + 分组索引：记录按关键字分组，为每组建一条索引项（指向该组第一条记录）。它是顺序文件与索引文件的折中：既保留顺序文件批量处理高效，又能通过索引加速单条查找。

经典计算（模拟题，必须掌握）：设文件有 $N$ 条记录，分成 $\sqrt{N}$ 组，每组 $\sqrt{N}$ 条。先在索引表中顺序（或折半）查组，再在组内顺序查记录，平均查找次数：

$\frac{\sqrt{N}}{2} + \frac{\sqrt{N}}{2} = \sqrt{N}$

例：$N = 10000$，分 100 组、每组 100 条，平均查找 $\frac{100}{2} + \frac{100}{2} = 100$ 次；而不分组顺序查找平均要 $\frac{10000}{2} = 5000$ 次。若记录更多，可建两级分组（组内再分小组），思路同 ISAM/B+ 树（可类比 数据结构中的分块查找，模型完全一致）。

#三、文件目录

#3.1 FCB 与索引结点

文件控制块 FCB：文件存在的唯一标志。目录本身就是"目录文件"，其内容就是一个个 FCB（目录项）。

FCB 的内容（三大类，背诵口径）：

1. 基本信息：文件名、文件类型、物理地址（起始块号/索引表位置）、文件大小
2. 存取控制信息：所有者、访问权限
3. 使用信息：创建/修改时间、当前使用状态（是否打开、被谁打开）

按名存取的过程：用户给文件名 → OS 查目录找到对应 FCB → 校验权限 → 按物理地址存取。

索引结点（inode）的引入（高频考点）：查找文件时只需文件名，但 FCB 把全部信息放目录项里，目录庞大的话检索开销巨大。Unix 的做法：

• 目录项中只保留文件名 + 指向索引结点的指针，其余信息全部移入索引结点，目录大小大幅缩减，查目录时减少读盘次数
• 磁盘索引结点（存于磁盘）：文件所有者、类型、大小、时间、链接计数 count、物理地址（地址项数组——正是混合索引的载体）
• 内存索引结点（文件打开时复制入内存）：磁盘索引结点副本 + 当前状态、访问计数、是否被修改等

#3.2 目录结构

树形目录的两个必考点：

1. 绝对路径 vs 相对路径：绝对路径从根开始，每次都从根查起，访盘较多；引入"当前目录（工作目录）"后，相对路径从当前目录查起。OS 为每个进程设置当前目录。
2. 删除共享结点（无环图）：为共享结点设引用计数（链接计数），每增一个共享指针 count+1，删除时 count−1，count 归 0 才真正删除。

#3.3 文件共享（硬链接与符号链接）

硬链接相当于多个指针指向同一对象（引用计数即"析构时机"）；符号链接就是 Windows 快捷方式 / Unix ln -s。考试答题用左表口径。

#四、文件的物理结构（外存分配方式）

物理结构研究文件的盘块序列如何在磁盘上组织。设文件逻辑上划分为大小相等的逻辑块，逻辑块号到物理盘块号的映射由物理结构决定。三种基本方式：连续、链接、索引。

#4.1 连续分配

每个文件占用一组连续的盘块，FCB 中记录起始盘块号与文件长度（块数）。

• 优点：顺序读写快（一次寻道读整块区域）；支持随机（直接）存取：第 $i$ 块物理块号 = 起始块号 + $i$；目录项小
• 缺点：产生外部碎片（与内存连续分配同理，可用紧凑缓解但代价大）；文件难以动态增长（需预留空间或迁移）；磁盘利用率低

#4.2 链接分配

隐式链接：每个盘块末尾存指向下一个盘块的指针，FCB 记录首块号与末块号。

• 优点：无外部碎片、外存可动态增长、目录项小
• 缺点：只支持顺序访问，读第 $i$ 块必须从头走链；指针占空间；可靠性差（断链丢整个后续）；一块一指针开销大

显式链接（FAT，文件分配表）：把所有盘块的"下一块指针"集中抽出，建成一张FAT 表，每个表项对应一个物理盘块，存放该文件的下一块块号（文件结尾、空闲用特殊标记）。FAT 在系统启动时读入内存并常驻。

• 查物理块号在内存完成，因此支持随机访问（沿 FAT 链在内存走，无需访盘），读任意一块只需 1 次访盘
• FAT 还兼任空闲盘块管理（标记空闲的表项），分配回收方便
• 代价：FAT 本身占内存，磁盘很大时 FAT 很大（FAT32 等由此得名）

#4.3 索引分配

为每个文件建索引表（索引块）：第 $i$ 个表项 = 文件第 $i$ 块的物理块号。FCB 中指向索引块。

• 优点：支持随机访问、无外部碎片、易于增删；缺点：索引块额外空间开销；小文件也要一个索引块（浪费）；大文件一个索引块装不下 → 多级索引。

多级索引：索引项指向的仍是索引块，$k$ 级索引访问一个数据块需读 $k$ 个索引块 + 1 个数据块 = $k+1$ 次访盘（索引表不在内存时）。

#4.4 混合索引（Unix 方式）——必考计算

Unix 的索引结点地址项混合存放：直接地址 + 多级间址。设块大小 $B$ 字节、每个地址项（指针）$P$ 字节，则每个索引块可存 $\dfrac{B}{P}$ 个指针。

例题（模拟题，完整计算）：某文件系统盘块大小 1 KB，地址项 4 B，索引结点含 10 个直接地址项、1 个一次间址项、1 个二次间址项、1 个三次间址项。求最大文件容量，并求访问字节偏移量所在数据块时（索引结点已在内存、各间址块未缓存）的访盘次数。

第一步：每个盘块可容纳指针数 $\dfrac{1\text{KB}}{4\text{B}} = 256$ 个。

第二步：层级递推表（答题模板）：

结论：最大文件 $= (10 + 256 + 65\,536 + 16\,777\,216) \times 1\,\text{KB} = 16\,843\,018\,\text{KB} \approx 16.06\,\text{GB}$。

访盘次数（索引结点已调入内存，间址块不在内存）：访问直接块数据 → 1 次（直接得块号，读数据块）；一次间址数据 → 读间址块 + 读数据块 = 2 次；二次间址数据 → 3 次；三次间址数据 → 4 次。

设计哲学：小文件（绝大多数）走直接地址最快，特大文件靠多次间址扩展——工程上就是"分级索引"，与 B+ 树、页表多级化的思想一致。

#4.5 各物理结构读写对比表（读第 $i$ 块的访盘次数，文件已打开、FCB 在内存）

#五、文件存储空间管理

对空闲盘块的组织，四种方法对照记忆（与内存动态分区管理高度同构）。

#5.1 空闲表与空闲链

空闲表：每个空闲盘区（连续多个盘块）一个表项（首个空闲块号、连续块数），适合连续分配方式；分配时用首次/最佳适应，回收时注意相邻盘区合并——与内存动态分区完全同构。

空闲盘块链：所有空闲盘块拉成一条链，逐块分配/回收，简单但效率低（逐块操作）。

空闲盘区链：以"盘区"（连续若干块）为链结点，分配时按需求找合适盘区，可拆分，兼顾效率。

#5.2 位示图（必考计算）

用每一位表示一个盘块：0 空闲，1 已占用（或反之，以题干为准）。字长 $n$ 位（通常 $n=32$）。

核心公式（块号、字号、位号均从 0 开始编号）：

$\text{字号} = \left\lfloor \frac{\text{块号}}{n} \right\rfloor, \qquad \text{位号} = \text{块号} \bmod n$

反向：$\text{块号} = n \times \text{字号} + \text{位号}$。

若题目改为从 1 开始编号（王道真题出现过）：先各减 1 化归为从 0，算完再加 1；即 $\text{字号} = \left\lceil \frac{\text{块号}}{n} \right\rceil$，位号 $= (\text{块号}-1) \bmod n + 1$。

例题（模拟题）：磁盘容量 1 TB，盘块大小 4 KB，字长 32 位。求：(1) 位示图需要多少字、占多少空间；(2) 块号 1000 对应的字号与位号（均从 0 编号）；(3) 第 3 字的第 5 位（从 0）对应哪一块。

• (1) 盘块数 $= \dfrac{2^{40}\text{B}}{4\text{KB}} = 2^{28}$ 块；需字数 $= \dfrac{2^{28}}{2^5} = 2^{23}$ 字，占 $2^{23} \times 4\,\text{B} = 32\,\text{MB}$
• (2) 字号 $= \lfloor 1000/32 \rfloor = 31$，位号 $= 1000 \bmod 32 = 8$
• (3) 块号 $= 32 \times 3 + 5 = 101$

#5.3 成组链接（Unix 空闲盘块管理，大题可考手推）

把空闲盘块每 100 块分一组，每组第一块存放下一组的盘块号与块数（相当于显式分组链），所有组串起来；内存中设空闲盘块号栈，存放第一组（当前可分配组）的全部盘块号。

• 分配：栈顶出栈一个盘块分配；当栈中只剩最后一块（存放下一组信息的块）时，先把该块内容读入栈（载入下一组），再把该块本身分配出去
• 回收：空闲块入栈，栈满（100 块）前直接压栈；栈满时回收的新块：把栈中 100 个块号写入新块，栈清空后只压入新块——新块成为下一组的"组长"

特点：绝大部分分配回收只操作内存栈，仅跨组时一次访盘；兼具空闲表（成组信息在组首块）与链（组间链接）的思想。

#六、磁盘组织与调度

#6.1 磁盘的结构与地址

机械磁盘由盘片叠装：每个盘面一个磁头，盘面上同心圆为磁道，每道分若干扇区（最小读写单位，通常 512 B）。各盘面同半径磁道组成柱面。磁盘物理地址 = 柱面号（磁道号）· 磁头号（盘面号）· 扇区号。

访盘时移动磁臂（所有磁头同轴联动）：寻道到目标柱面 → 旋转盘面到目标扇区 → 读写。相邻逻辑扇区物理上交错分布（考虑处理时间），现代磁盘对 OS 透明，OS 面向逻辑块地址 LBA。性能要点：同一柱面上的块连续访问不需要再寻道，所以 OS 分配文件块尽量同柱面。

#6.2 磁盘访问时间

$T_a = T_s + T_r + T_t$

• $T_s$：寻道时间（磁臂移动到目标磁道），由磁头移动磁道数 × 单磁道移动时间 + 启动时间构成
• $T_r$：旋转延迟，平均转半圈：$T_r = \dfrac{1}{2} \times \dfrac{60}{\text{rpm}} \times 1000$ ms
• $T_t$：传输时间，读写 $b$ 字节：$T_t = \dfrac{b}{rN}$（$r$：转/秒；$N$：每磁道字节数）

例题（模拟题）：磁盘转速 7200 rpm，平均寻道时间 8 ms，每磁道 1 MB。读一个 4 KB 扇区需要多久？

• 每转一圈 $\dfrac{60}{7200} = 8.33$ ms，平均旋转延迟 $\dfrac{8.33}{2} \approx 4.17$ ms
• 传输时间 $= 8.33 \times \dfrac{4\text{KB}}{1024\text{KB}} \approx 0.03$ ms
• 总计 $8 + 4.17 + 0.03 \approx 12.2$ ms——寻道与旋转占绝对大头，这正是调度算法优化的对象

#6.3 磁盘调度算法（六算法同序列手推，单步动画见交互演示 · 磁盘调度）

题目条件：磁道编号 0～199，磁头当前在 53 号磁道，沿磁道号增大方向移动，等待服务的请求序列（按到达顺序）：

$98,\ 183,\ 37,\ 122,\ 14,\ 124,\ 65,\ 67$

FCFS（先来先服务）：完全按到达顺序。

总计 640 道。公平但对机械运动完全不友好。

SSTF（最短寻道时间优先）：每步选距当前磁头最近的请求。

总计 236 道。平均性能好，但远端请求可能饥饿（本题 183 就是最后才被服务）。

SCAN（电梯算法）：沿当前方向服务到磁盘末端（本题到 199），再折返。设定方向：磁道号增大。

总计 $146 + 185 =$ 331 道（53→199 共 146，199→14 共 185）。不饥饿，但中点两侧等待时间不均匀（刚扫过的区域要等一个来回）。

C-SCAN（循环扫描）：只沿一个方向服务，到末端后直接跳回起点端再继续同向扫描（回程不服务）。方向：磁道号增大。

总计 $146 + 14 + 23 =$ 183 道（跳转 199→0 的移动通常不计入，若题目声明计入则加 199）。等待时间对所有磁道均匀。

LOOK：SCAN 的实用版——到该方向最远请求（183）即折返，不必到达磁盘末端 199。

总计 $130 + 146 + 23 =$ 299 道。

C-LOOK：C-SCAN 的实用版——到最远请求 183 后直接跳到最小请求 14，再同向扫描（跳转不计）。

总计 $130 + 23 =$ 153 道。

汇总对比（同一序列）：

注意：移动总道数小不代表绝对时间短（还有旋转延迟），调度只优化寻道。近年真题出现过把"磁道数"换算成时间的题，看清单位再算。

#常见坑

1. 编号口径：位示图、混合索引题目，块号/字号/位号从 0 还是从 1 开始，结果差 1——先看题干，没有说明按从 0 处理并在卷面注明
2. FAT 属于链接分配而非索引分配：显式链接的本质仍是链，只是指针集中到内存表中；说"FAT 支持随机访问"是对的（查内存 FAT 不访盘），但"链式物理结构不支持随机访问"指的是隐式链接
3. 索引分配读一块不是 1 次访盘：默认索引块在磁盘上，"文件已打开"只保证 FCB/索引结点在内存，索引表/间址块是否调入内存看题干
4. 混合索引计算别丢直接块：最大容量 = 直接块 + 一次间址 + 二次间址 + 三次间址全部相加；"$256^3$"算错指数是最常见计算失误
5. SCAN vs LOOK：SCAN 到磁盘最边缘磁道（0 或 199），LOOK 只到最远请求；C-SCAN 跳转是否计入移动道数看题目声明，两种答案都要会
6. 硬链接删除：删除一个链接只是 count−1，文件数据与索引结点在 count=0 时才真正释放；符号链接删除原文件后链接悬空但不自动消失
7. 磁盘调度手推必须写轨迹表：大题按步给分，只写总数容易因一步看错全错；注意 SSTF 距离相等时通常选沿当前方向的那个（题目会给唯一解）

#自测

1. （判断）FAT 表常驻内存后，采用显式链接分配的文件支持随机存取。（ ）
2. 索引顺序文件中 4096 条定长记录分成若干组，每组条数取多少时平均查找次数最少？最少平均查找次数是多少？
3. 某文件系统的索引结点含 6 个直接地址项、1 个一次间址项、1 个二次间址项，盘块 1 KB、地址项 4 B，该文件系统单个文件最大是多少 KB？
4. 位示图字长 32 位，块号、字号、位号均从 0 开始，块号 2000 的字号与位号是多少？
5. 磁头位于 53 道、方向增大，请求序列 98, 183, 37, 122, 14, 124, 65, 67：SSTF 第一个服务的磁道是？SCAN（到端点 199 折返）总共移动多少道？

#自测答案

1. 对。FAT 在内存中沿链查物理块号不访盘，读任意一块只需 1 次访盘，支持随机存取。
2. 每组 $\sqrt{4096} = 64$ 条，分 64 组；平均查找 $\frac{64}{2} + \frac{64}{2} = 64$ 次。
3. 每块 256 指针：$6 + 256 + 256^2 = 6 + 256 + 65536 = 65798$ 块，即 65798 KB（$\approx$ 64.25 MB）。
4. 字号 $\lfloor 2000/32 \rfloor = 62$，位号 $2000 \bmod 32 = 16$（$62 \times 32 = 1984$）。
5. SSTF 第一个服务 65（距 53 最近且唯一最近）；SCAN 总移动 $53 \to 199 \to 14$ = $146 + 185 = 331$ 道。