考研全科复习

Appearance

408 ​

操作系统 ​

OS-04-05 文件的物理结构（连续/链接/索引分配） ​

一、定位信息 ​

  • 所属圈层：核心层
  • 前置知识回顾：理解磁盘的基本结构（磁道、扇区、磁盘块），知道文件数据最终存储在磁盘块中。了解文件控制块（FCB/inode）中包含文件数据的物理地址信息。
  • 知识网络位置：本单元是文件管理的核心内容之一，与OS-04-04（逻辑结构）形成对照。物理结构决定了文件在磁盘上的存储方式，直接影响文件的存取效率和空间利用率。
  • 考点热度等级：H级（高频重点）——三种物理分配方式是几乎每年必考的核心知识点。

二、知识点讲解 ​

2.1 连续分配（Contiguous Allocation） ​

连续分配将文件存储在磁盘上连续的磁盘块中。FCB记录文件的起始块号和长度。

地址转换：给定逻辑块号 nn，物理块号 = 起始块号 + nn。

优点：

  • 顺序访问和随机访问都很快
  • 实现简单，地址计算简单

缺点：

  • 外部碎片：文件删除后产生碎片，需要紧凑操作
  • 文件大小固定：创建时需要声明文件大小，无法动态增长
  • 不利于文件扩展：如果文件需要增长，可能后面没有连续空间

2.2 链接分配（Linked Allocation） ​

链接分配将文件存储在离散的磁盘块中，每个块的末尾存储指向下一个块的指针。FCB记录文件的起始块号和结束块号。

隐式链接：每个磁盘块的最后几个字节存储下一个块的指针。

  • 顺序访问：沿指针链遍历
  • 随机访问：几乎不可能（需要从头遍历）
  • 可靠性差：一个块的指针损坏，后续数据全部丢失

显式链接（FAT, File Allocation Table）：将所有磁盘块的链接指针集中存储在一张**文件分配表（FAT）**中。

  • FAT常驻内存，查找效率高
  • 支持随机访问（通过FAT直接查到目标块）
  • FAT占用内存空间

2.3 索引分配（Indexed Allocation） ​

索引分配为每个文件创建一个索引块，索引块中存储该文件所有数据块的块号。FCB记录索引块的位置。

  • 支持随机访问
  • 无外部碎片
  • 索引块占用额外空间

多级索引：当文件很大时，一个索引块不够用，需要多级索引。

  • 一级索引：索引块直接指向数据块
  • 二级索引：索引块指向二级索引块，二级索引块指向数据块
  • 以此类推

Unix/Linux的inode使用混合索引：直接指针 + 一级间接 + 二级间接 + 三重间接。

三、记忆与理解辅助 ​

1. 类比记忆：

  • 连续分配 = 电影院座位（必须坐在一起，找人很快但座位不好安排）
  • 链接分配 = 票据传递（每人拿一张票指向下一个位置，找人需要挨个问）
  • 索引分配 = 图书馆索引卡（通过索引卡直接找到书的位置）

2. 口诀："连续好找不好扩，链接好扩不好找；索引折中效率高，FAT表在内存跑。"

3. 三种物理结构对比表（★高频考点）：

对比项连续分配链接分配索引分配
存储方式连续磁盘块离散磁盘块+指针离散磁盘块+索引表
顺序访问快快（沿指针）快
随机访问快（直接计算）不支持（隐式链接）快（查索引表）
外部碎片有无无
文件扩展困难容易容易
额外空间无指针（每个块）索引块
可靠性高低（指针损坏→数据丢失）高
典型系统早期系统FAT12/FAT16Unix/Linux、NTFS

4. FAT表结构：

FAT表（常驻内存）
┌──────┬──────┐
│ 块号 │ 下一块│
├──────┼──────┤
│  0   │  -1  │ ← 文件A结束
│  1   │  3   │ ← 文件A的第1块→第3块
│  2   │  -1  │ ← 空闲
│  3   │  5   │ ← 文件A的第3块→第5块
│  4   │  1   │ ← 文件B的第4块→第1块
│  5   │  -1  │ ← 文件A结束
└──────┴──────┘
文件A: 起始块=1 → 3 → 5 → 结束
文件B: 起始块=4 → 1 → 结束

四、例题与精解 ​

例题1（基础巩固） ​

题目：某文件系统磁盘块大小为 1KB1\text{KB}，某文件大小为 5KB5\text{KB}。分别计算在连续分配、链接分配和索引分配下，读取文件第 3KB3\text{KB} 处的数据（偏移3072字节）需要多少次磁盘访问。

命题意图：考查三种物理分配方式的随机访问效率。

精解：

1. 审题分析：文件5KB，块大小1KB，共5个块。读取偏移3072字节处（第4个块，块号从0开始）。

2. 解题思路：分析每种方式定位第4个数据块需要的磁盘访问次数。

3. 完整步骤：

偏移3072字节 = 第 ⌊3072/1024⌋=3\lfloor 3072/1024 \rfloor = 3 号逻辑块（第4个块，从0开始编号）

连续分配：

  • 物理块号 = 起始块号 + 3
  • 直接访问该物理块 → 1次 磁盘访问

链接分配（隐式链接）：

  • 需要从起始块开始，沿指针链遍历到第4个块
  • 块0 → 块1 → 块2 → 块3，共遍历4个块
  • 需要 4次 磁盘访问

索引分配：

  • 读取索引块（获取第3号逻辑块对应的物理块号） → 1次
  • 读取数据块 → 1次
  • 共 2次 磁盘访问

4. 方法反思：连续分配随机访问最快（O(1)O(1)），链接分配最慢（O(n)O(n)），索引分配居中（O(1)O(1)但需要读索引块）。这也是为什么现代文件系统都采用索引分配（或其变种）。

例题2（中等提升） ​

题目：某系统采用FAT（文件分配表）管理磁盘块，磁盘共有 10001000 个块，FAT表每项占 22 字节。 （1）FAT表总大小是多少？ （2）若内存有 4KB4\text{KB} 用于缓存FAT表，能否将整个FAT表放入内存？ （3）文件F的FAT链为：100→200→350→500→EOF100 → 200 → 350 → 500 → \text{EOF}。读取文件的第 33 个逻辑块需要多少次磁盘访问？

命题意图：考查FAT表的结构和使用。

精解：

1. 审题分析：1000个块，FAT每项2字节。需要计算FAT大小和查找效率。

2. 解题思路：FAT大小 = 块数 × 每项大小。查找逻辑块需要沿链遍历。

3. 完整步骤：

（1）FAT表大小 = 1000×2=20001000 \times 2 = 2000 字节

（2）4KB=40964\text{KB} = 4096 字节 > 20002000 字节，可以将整个FAT表放入内存。

（3）文件F的FAT链：100→200→350→500→EOF100 → 200 → 350 → 500 → \text{EOF}

  • 第0个逻辑块：块100
  • 第1个逻辑块：块200
  • 第2个逻辑块：块350
  • 第3个逻辑块：块500

由于FAT表在内存中，可以直接查表得到第3个逻辑块对应的物理块号 = 500。 只需 1次 磁盘访问（读取块500的数据）。

4. 方法反思：FAT表的显式链接相比隐式链接的优势在于——FAT表可以常驻内存，通过查表直接找到目标块，无需遍历。这也是FAT文件系统（如FAT32）在U盘等小存储设备上仍然广泛使用的原因。

五、考情分析 ​

  • 考查频次：文件物理结构在近5年真题中出现频率高，约4-5次。
  • 常见题型：选择题（分配方式判断、存取效率比较）、综合题（结合inode的多级索引计算）。
  • 分值占比：选择题2分，综合题5-8分。
  • 命题趋势：近年来倾向于将物理结构与inode、磁盘调度结合考查。FAT表的计算是经典考点。基于大纲与命题规律推测。

六、易错点提醒 ​

  1. 错误表现：认为链接分配支持随机访问。 错误原因：混淆了隐式链接和显式链接（FAT）。 正确理解/做法：隐式链接不支持随机访问（需要从头遍历）；显式链接（FAT）通过内存中的FAT表支持随机访问。考试中说"链接分配"通常指隐式链接。

  2. 错误表现：计算索引分配的磁盘访问次数时，忘记索引块本身的读取。 错误原因：只计算了数据块的访问。 正确理解/做法：索引分配需要先读索引块（1次），再读数据块（1次），共2次。多级索引需要读取每一级的索引块。

  3. 错误表现：认为连续分配没有碎片问题。 错误原因：只看到连续分配没有"内部碎片"，忽略了"外部碎片"。 正确理解/做法：连续分配有外部碎片——文件删除后产生的碎片可能太小无法利用。这也是连续分配逐渐被淘汰的原因之一。

七、来源标注 ​

  • 依据2026考研统考408大纲
  • 依据《操作系统概念》（Operating System Concepts, Silberschatz）第11章
  • 依据汤小丹《计算机操作系统》第4版第4章

考研全科复习资料 - 基于2026考研统考大纲

仅供学习参考