408 高频考点精讲:外存空间管理¶
模块归属:操作系统 · 文件管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
1. 考查频次统计¶
- 近十年考查频次:4 次(2017 年第 26 题、2019 年第 26 题、2024 年第 26 题、2025 年第 31 题)
- 历年总考查频次:6 次(大纲统考历年)
- 出题形式:单项选择题(高频独立考查)、综合解答题(常与文件物理结构、目录检索、磁盘寻道调度融合考查)
2. 命题特点与考查重心¶
外存空间管理属于操作系统文件管理的核心支撑机制。纵观近十年命题趋势,命题组主要围绕以下四个维度展开: 1. 外存分配粒度与内部碎片计算:重点考查扇区(物理读写单位)与簇/块(文件系统分配单位)的层次区别,以及文件按簇向上取整造成的空间开销与碎片计算(如 2017 年第 26 题)。 2. 管理数据结构的属性辨析与功能边界:考查位示图、空闲表、空闲链表、成组链接法的功能特性,特别是文件分配表(FAT)在“物理链接结构”与“空闲空间管理”上的双重身份判定(如 2019 年第 26 题、2025 年第 31 题)。 3. 元数据空间开销与动态状态相关性:重点考查各类管理结构占用外存空间的大小是否随“当前空闲块数量”发生动态变化,位示图空间开销的恒定性是极其重要的选择题考点(如 2024 年第 26 题)。 4. 位示图坐标变换与综合计算:在综合题中,位示图通常作为磁盘空间分配的状态载体,要求考生熟练进行“物理块号 \(\leftrightarrow\) (字号, 位号)”的精准双向转换,并计算位示图自身占用的内存或外存开销。
3. 近十年考查年份分布表格¶
+------+------+------+------+------+------+------+------+------+------+
| 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
+------+------+------+------+------+------+------+------+------+------+
| -- | #26 | -- | #26 | -- | -- | -- | -- | #26 | #31 |
+------+------+------+------+------+------+------+------+------+------+
二、 具体考察内容¶
1. 核心概念与工作机制¶
(1) 外存分配的基本单位与层次结构¶
- 物理扇区(Sector):磁盘硬件控制器进行物理读写的最小物理单位,经典扇区大小通常为 \(512\text{ B}\)$ \text{(现代高级格式化磁盘扇区大小多为} $\(4\text{ KB}\))。
- 逻辑块(Block)/ 簇(Cluster):操作系统文件系统层面对外存空间进行分配、寻址和管理的基本逻辑单位。一个簇由 \(2^k\)$ \text{个连续的物理扇区组成(如} $\(1\text{ KB}\)、\(2\text{ KB}\)、\(4\text{ KB}\) 等)。
- 分配原则:操作系统分配外存空间时,一律以“簇(块)”为最小分配粒度。无论文件实际末尾剩余数据量多么微小,只要超过现有簇容量,必须分配一个完整的全新簇。这必然导致文件最后一个簇内未被数据填满的部分形成内部碎片(Internal Fragmentation)。
(2) 空闲表法(Free Table)¶
- 数据结构:在系统外存特定区域建立一张空闲盘块表,每个表项对应一个连续的空闲盘区,包含两个核心字段:
起始空闲块号和空闲块数。 - 分配机制:采用动态分区分配算法(如首次适应算法、最佳适应算法、最坏适应算法)。为请求进程分配一个连续的盘区。
- 回收机制:当文件释放外存时,系统检查回收盘区与空闲表中现有空闲区是否物理相邻。若向前相邻、向后相邻或两端相邻,则执行合并操作;若不相邻,则新建表项。
- 优缺点分析:
- 优点:支持文件的连续分配,数据物理连续,顺序读写性能高。
- 缺点:外存容易产生大量外部碎片,需要进行碎片整理(紧凑);空闲表占用空间随空闲区离散碎片数量变化。
(3) 空闲链表法(Free List)¶
- 空闲盘块链(Free Block List):
- 将外存中所有空闲盘块串联成单向链表。每个空闲块内部开辟微小的指针空间,保存下一个空闲块的物理盘块号。
- 分配时:从链首逐个摘取指定数量的盘块,修改链头指针。
- 回收时:将释放盘块逐一挂入链尾或链首。
- 评价:无需额外的专用外存表格空间,但为大文件分配多个盘块时需要频繁进行磁盘 I/O 读取链表指针,效率极低。
- 空闲盘区链(Free Area List):
- 将连续的空闲盘块视作一个盘区,盘区第一个块记录本区长度及指向下一个空闲盘区的指针。
- 评价:分配效率高于空闲盘块链,支持连续空间申请,但回收与合并逻辑较为复杂。
(4) 位示图法(Bitmap / Bit Map)¶
- 数据结构:利用二进制的一位(bit)来映射一个物理盘块的占用/空闲状态。
- 通常定义:
0表示盘块空闲,1表示盘块已分配占用(具体题目以题干约定为准)。 - 位示图在内存中表现为一个二维位阵列(Bit Array),也可视作连续的机器字(Word)序列。
- 分配流程:
- 顺序扫描位示图,查找值为
0的二进制位(常借助硬件级位操作指令提高检索速度)。 - 根据该位所在的行号(字号)与列号(位号),通过映射公式推导出对应的物理盘块号。
- 将该位的值由
0修改为1。 - 修改内存中的位示图副本,并在适当时机写回外存。
- 回收流程:
- 根据释放文件的物理盘块号,通过逆映射公式计算出对应的行号(字号)与列号(位号)。
- 将该位的值由
1置为0。
(5) 成组链接法(UNIX Group Linking)¶
成组链接法是大型操作系统(如 UNIX System V)普遍采用的高效外存空闲块管理技术,兼具链表法无需巨大连续外存表与空闲表高效批量分配的优势。
- 数据结构:
- 空闲盘块号栈(Free Block Stack):存放在系统内存的超级块(Superblock)中,包含两个核心变量:
- N:当前栈中可分配的空闲盘块数(栈顶指针)。
- Free[100]:保存当前组空闲盘块号的栈数组(假设每组最大容量为 100 块)。
- 链接结构:将全部空闲块划分为若干组(如每组 100 块)。将第一组的 100 个块号存放在超级块栈中;第一组的第一个块(底端块,Free[0])作为指针块,其内部保存第二组的块数及第二组的全部块号;第二组的第一个块存放第三组的全部信息……依此类推。最后一组的第一个块存放特殊结束标志(如 0),表示空闲块链结束。
- 分配机制:
1. 当超级块栈顶指针 \(N > 1\)$ \text{时,直接分配栈顶盘块 Free[N - 1],执行} $\(N \leftarrow N - 1\)。
2. 当超级块栈顶指针 \(N = 1\) 时,当前可用的盘块正是指向下一组的指针块(Free[0])。此时操作系统将该块内部保存的下一组块数及块号整体读入超级块栈中,随后将该指针盘块分配给用户,实现空闲组的无缝平滑切换。
- 回收机制:
1. 当超级块栈未满(\(N < 100\)$ \text{)时,将回收块号压入栈顶:Free[N]} $\(\leftarrow\)$ \text{回收块号,执行} $\(N \leftarrow N + 1\)。
2. 当超级块栈已满(\(N = 100\)$ \text{)时,将当前超级块栈中的全部数据(包含} $\(N\)$ \text{及 100 个盘块号)整体写入新回收的盘块中,将该回收块作为新一组的指针块。然后清空超级块栈,并将新回收块的块号写入超级块的 Free[0],重置} $\(N \leftarrow 1\)。
(6) 文件分配表(FAT)的外存管理双重性¶
- 物理结构属性:FAT 属于文件物理结构中的显式链接分配(Explicit Chaining Allocation)。表项不仅记录属于某一文件的各个簇的先后串联次序,文件的首簇号保存在目录项中。
- 外存空间管理属性:FAT 的表项与存储介质上的物理簇存在严格的一一对应映射。FAT 表项使用特定数值标识物理簇的状态:
- 值为
0x00000000(以 FAT32 为例):明确标识该物理簇为空闲状态。 - 值为
0x0FFFFFF7:标识该物理簇为损坏簇(Bad Cluster)。 - 值为
0x0FFFFFF8\(\sim\)0x0FFFFFFF:标识该簇为文件数据的终止簇(EOF)。 - 其它非零有效值:指向该文件下一个数据块所在的物理簇号。
- 结论:文件分配表(FAT)不仅管理文件的物理存储拓扑,其本身直接兼任全盘的外存空闲空间管理结构,操作系统通过检索 FAT 表项即可完成空闲块的查找、分配及状态标记。
2. 核心定理推导与数学计算模型¶
(1) 外存实际占用量与簇向上取整模型¶
设文件物理字节大小为 \(L\)$ \text{,文件系统定义的分配单元(簇或块)大小为} $\(S_{\text{cluster}}\)。 - 分配簇数 \(K\): $\(K = \left\lceil \frac{L}{S_{\text{cluster}}} \right\rceil\)$ - 实际分配的外存空间大小 \(V_{\text{alloc}}\): $\(V_{\text{alloc}} = K \times S_{\text{cluster}} = \left\lceil \frac{L}{S_{\text{cluster}}} \right\rceil \times S_{\text{cluster}}\)$ - 文件产生的内部碎片量 \(\Delta\): $\(\Delta = V_{\text{alloc}} - L\)$
(2) 位示图外存空间开销的绝对恒定性定理¶
设磁盘总物理容量为 \(C_{\text{disk}}\)$ \text{,每个物理盘块大小为} $\(B\)。 - 物理盘块总数 \(N_{\text{total}}\): $\(N_{\text{total}} = \frac{C_{\text{disk}}}{B}\)$ - 位示图所需二进制位数 \(M_{\text{bits}}\): $\(M_{\text{bits}} = N_{\text{total}}\)$ - 位示图占用的物理存储字节数 \(S_{\text{bitmap}}\): $\(S_{\text{bitmap}} = \left\lceil \frac{N_{\text{total}}}{8} \right\rceil \text{ Bytes}\)$ - 若以机器字长 \(W\)(单位:bit)为存储单位,则位示图占用字数: $\(S_{\text{word}} = \left\lceil \frac{N_{\text{total}}}{W} \right\rceil\)$
定理推论:位示图占用的物理存储空间大小仅取决于磁盘的总物理容量与盘块大小(即物理总块数 \(N_{\text{total}}\)),与当前文件系统中空闲块的数量、分配状态及离散分布情况严格无关。
(3) 位示图物理地址与逻辑坐标双向映射推导模型¶
设机器字长为 \(W\)$ \text{位,行号(字号)记为} $\(i\)$ \text{,列号(位号)记为} $\(j\)$ \text{,对应的外存物理盘块号记为} $\(b\)。在 408 统考中,根据题目对编号起始基数(从 0 开始还是从 1 开始)的设定,存在四种严格的数学映射分支:
分支一:字号 i、位号 j、块号 b 均从 0 开始编号(最常见工程模型)¶
- 坐标推导块号: $\(b = i \times W + j\)$
- 块号反解坐标: $\(i = \left\lfloor \frac{b}{W} \right\rfloor, \quad j = b \bmod W\)$
分支二:字号 i、位号 j、块号 b 均从 1 开始编号(传统教材经典模型)¶
- 坐标推导块号: $\(b = (i - 1) \times W + j\)$
- 块号反解坐标: $\(i = \left\lfloor \frac{b - 1}{W} \right\rfloor + 1, \quad j = ((b - 1) \bmod W) + 1\)$
分支三:字号 i、位号 j 从 0 开始,块号 b 从 1 开始编号¶
- 坐标推导块号: $\(b = i \times W + j + 1\)$
- 块号反解坐标: $\(i = \left\lfloor \frac{b - 1}{W} \right\rfloor, \quad j = (b - 1) \bmod W\)$
分支四:字号 i、位号 j 从 1 开始,块号 b 从 0 开始编号¶
- 坐标推导块号: $\(b = (i - 1) \times W + (j - 1)\)$
- 块号反解坐标: $\(i = \left\lfloor \frac{b}{W} \right\rfloor + 1, \quad j = (b \bmod W) + 1\)$
3. 核心对比辨析¶
下表针对外存空间管理的六种典型机制,从物理连续性、空间占用特征、I/O开销及算法适用场景展开全景对比:
| 机制名称 | 核心数据结构 | 空间开销与空闲块数关系 | 连续空间分配支持 | 分配/回收 I/O 开销 | 典型适用场景 |
|---|---|---|---|---|---|
| 空闲表法 | 空闲盘区登记表(起始块号、块数) | 正相关(随空闲碎片数量动态变化) | 极好(直接按连续盘区分配) | 较低(仅需修改内存中空闲表后刷盘) | 连续分配文件系统、小容量软盘 |
| 空闲盘块链 | 单向盘块链(指针内置于空闲块) | 无关(零额外表空间,指针利用空闲块本身) | 极差(仅支持离散单块分配) | 极高(分配大文件需多次读盘寻道跟踪链表) | 早期微型文件系统、离散分配系统 |
| 空闲盘区链 | 盘区双向链表(首块记录长度与指针) | 正相关(随连续空闲盘区数动态变化) | 良好(可直接按盘区分配) | 适中(需读写盘区头块指针) | 支持混合分配的中小型系统 |
| 位示图法 | 二进制位阵列(Bit Array) | 完全无关(严格由磁盘总块数决定) | 良好(可通过字操作快速找连续空闲位) | 极低(常驻内存处理位操作,定期同步) | 各类主流现代操作系统(Linux, Windows) |
| 成组链接法 | 超级块空闲栈与多级指针盘块 | 正相关(指针块数量与空闲块总数成正比) | 良好(组内盘块物理上常聚集相邻) | 极低(常驻内存栈操作,仅跨组时发生单次I/O) | UNIX System V / 大型商业操作系统 |
| 文件分配表 (FAT) | 显式全局簇链表(FAT 表) | 完全无关(表项总数严格等于全盘物理簇数) | 较好(遍历查找连续空闲表项) | 低(FAT 表整体常驻或缓存于内存中) | FAT12 / FAT16 / FAT32 移动存储介质 |
三、 近十年真题精讲(2016~2025)¶
【真题 1】2017 年 408 第 26 题 · 外存分配基本单位与存储空间计算¶
题目:
某文件系统的簇和磁盘扇区大小分别为 1KB 和 512B。若一个文件的大小为 1026B,则系统分配给该文件的磁盘空间大小是( )。
A. 1026B
B. 1536B
C. 1538B
D. 2048B
【解析】¶
- 知识定位:本题考查外存存储空间的分配单位(簇)与实际占用外存的向上取整计算模型。
- 核心推导步骤:
- 分配单位判定:磁盘扇区(\(512\text{ B}\)$ \text{)是磁盘硬件读写的物理单位,而文件系统分配外存空间时,是以逻辑分配单位簇(Cluster)为基本粒度的。题目明确指出当前文件系统的簇大小为} $\(1\text{ KB} = 1024\text{ B}\)。
- 所需簇数计算:待存储文件大小为 \(L = 1026\text{ B}\)$ \text{。由于} $\(1026\text{ B} > 1024\text{ B}\),单簇容量不足以容纳该文件,文件系统必须为该文件分配第二个簇。所需簇数为: $$ \text{K = \left\lceil \frac{1026\text{ B}}{1024\text{ B}} \right\rceil = 2\text{ 个簇}} $$
- 分配外存大小计算:系统分配给该文件的实际外存磁盘空间大小为: $\(V_{\text{alloc}} = K \times S_{\text{cluster}} = 2 \times 1024\text{ B} = 2048\text{ B}\)$
- 内部碎片分析:该文件实际占用了 \(2048\text{ B}\)$ \text{磁盘空间,其末尾留下的内部碎片为} $\(2048\text{ B} - 1026\text{ B} = 1022\text{ B}\)。
- 选项逐项辨析:
- A 选项(1026B):错误。外存不按字节分配,必须按簇的整数倍分配。
- B 选项(1536B):错误。\(1536\text{ B} = 3 \times 512\text{ B}\),该选项是将磁盘扇区作为外存分配单位得出的错误干扰项。尽管外存物理介质由扇区组成,但操作系统上层文件管理分配的最小单位是簇,不能分配半个簇(1.5个簇)。
- C 选项(1538B):错误。纯粹的数值拼凑干扰项,无任何理论依据。
- D 选项(2048B):正确。2 个簇的物理总大小即为 \(2048\text{ B}\)。
正确答案:D
【真题 2】2019 年 408 第 26 题 · 空闲外存管理数据结构辨析¶
题目:
下列选项中,可用于文件系统管理空闲磁盘块的数据结构是( )。
Ⅰ. 位图
Ⅱ. 索引结点
Ⅲ. 空闲磁盘块链
Ⅳ. 文件分配表 (FAT)
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ、Ⅳ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅲ、Ⅳ
【解析】¶
- 知识定位:本题考查文件系统各类核心数据结构的功能划分与空闲空间管理机制的判定。
- 核心推导步骤与选项逐项辨析:
- Ⅰ项分析(位图 / 位示图):位示图(Bitmap)使用二进制位的 0 和 1 标记全盘每个磁盘块的空闲或占用状态,是极其经典的空闲磁盘块管理数据结构,Ⅰ项正确。
- Ⅱ项分析(索引结点 Inode):索引结点是类 UNIX 文件系统用于描述已存在文件元属性的核心数据结构。它记录文件的文件所有者、访问权限、物理块索引指针、文件大小及时间戳等信息。索引结点用于组织文件本身的物理结构和属性,不能用于全盘空闲磁盘块的统筹管理,Ⅱ项错误。
- Ⅲ项分析(空闲磁盘块链):空闲磁盘块链将所有空闲块串联成一条链表,通过链首指针和各块内部的指针实现空闲块的分配与回收,是经典的外存管理数据结构,Ⅲ项正确。
- Ⅳ项分析(文件分配表 FAT):FAT 表中的表项与物理盘块(簇)一一对应。表项的值不仅用于记录文件的下一个簇号以实现链式存储,更通过特殊保留值(如
0表示空闲簇、0xFFF7表示坏簇)记录了外存空间的使用状态。文件系统通过直接遍历和修改 FAT 即可完成空闲块的查找与分配,因此 FAT 完全具备空闲磁盘块管理功能,Ⅳ项正确。 - 综合结论:Ⅰ、Ⅲ、Ⅳ 均可用于管理空闲磁盘块,对应的组合选项为 B。
正确答案:B
【真题 3】2024 年 408 第 26 题 · 外存管理数据结构空间开销特性¶
题目:
文件系统需要额外的外存空间记录空闲块的位置,占用外存空间大小与当前空闲块数量无关的是( )。
A. 位示图
B. 空闲表
C. 成组链接
D. 空闲链表
【解析】¶
- 知识定位:本题考查外存空闲管理数据结构所占存储空间与系统动态状态(空闲块数量)的函数依赖关系。
- 核心推导与干扰项逐项剖析:
- A 选项(位示图):
- 位示图为磁盘中的每一个物理块固定分配一个二进制位(Bit)。
- 若磁盘共有 \(N\)$ \text{个物理块,则位示图所占的位数固定为} $\(N\)$ \text{位,占用的外存空间大小恒为} $\(\lceil N / 8 \rceil\) 字节。
- 无论当前系统中有多少块处于空闲状态(哪怕全盘全满或全盘全空),位示图的总位数始终等于全盘总物理块数 \(N\),其大小完全独立于当前空闲块的数量。故 A 选项正确。
- B 选项(空闲表):
- 空闲表记录离散的连续空闲盘区(每个表项包含起始块号与块数)。
- 当系统频繁分配与释放产生大量离散碎片时,空闲连续盘区的数量随之激增,空闲表所需的表项数量及占用的外存空间将显著膨胀;反之,若空闲块合并为一个大的连续区,表项则减少。其大小与空闲块数量及其分布形态紧密相关。故 B 选项错误。
- C 选项(成组链接):
- 成组链接法将空闲块按固定容量(如 100 块)分组链接。
- 每一组的第一个块需要作为指针块保存下一组全部盘块的索引。若系统中空闲块总数增加,所需的分组数量及用于存放下一组指针的专用物理盘块数量成比例增加;空闲块减少时,所占用的组指针块数也相应减少。因此其占用的外存空间与空闲块数量正相关。故 C 选项错误。
- D 选项(空闲链表):
- 空闲盘区链法中,链表结点的数量随着离散空闲盘区的增减而动态伸缩。
- 即便是空闲盘块链,虽然指针内置在空闲块内部,但整个链表覆盖的物理存储块也是随着空闲块数量的变化而动态增减的。故 D 选项错误。
正确答案:A
【真题 4】2025 年 408 第 31 题 · 外存空间使用状态记录机制辨析¶
题目:
下列选项中,可被文件系统用于外存空间使用情况的是( )。
A. 目录
B. 系统打开文件表
C. 文件分配表(FAT)
D. 文件控制块(FCB)
【解析】¶
- 知识定位:本题考查文件系统各核心元数据结构的职能边界判定,重点聚焦于外存空间全局使用状态的记录载体。
- 核心推导步骤与选项逐项辨析:
- A 选项(目录):
- 目录的核心功能是建立“文件名”到“文件元数据(FCB 或 Inode 编号)”的逻辑映射关系,旨在实现“按名存取”,并不反映全盘物理外存块的使用与空闲状态。故 A 选项错误。
- B 选项(系统打开文件表):
- 系统打开文件表是操作系统内核在主存(内存)中维护的动态运行态数据结构。用于跟踪当前系统中所有已被进程打开的文件,记录其系统打开计数、文件读写偏移量指针、访问控制权限及对应 Inode 缓存指针等,不用于持久化记录外存物理空间的使用情况。故 B 选项错误。
- C 选项(文件分配表 FAT):
- FAT 表是建立在卷(Volume)上的全局物理映射表。FAT 的每一个表项与磁盘上的每一个物理簇严格一一对应。
- FAT 表项的值直接刻画了该簇的占用与链接状态(特定编码表示空闲簇、占用簇、坏簇、文件尾簇)。文件系统正是通过遍历、检索和更新 FAT 表项,全面掌握并管理整个外存空间的使用与空闲情况。故 C 选项正确。
- D 选项(文件控制块 FCB):
- FCB 是单一文件的元数据描述符,存储单个文件的名称、属性、逻辑大小及物理块起始地址等。FCB 仅对自身所属文件负责,无法提供全盘外存空间的使用全貌。故 D 选项错误。
正确答案:C
四、 综合考法拓展¶
外存空间管理在 408 综合解答题(41~45题)中具有极强的跨模块融合特性,常与多级索引文件结构、FAT 文件系统、磁盘物理规格换算以及内存缓冲区调度联合命题。以下提炼三大经典综合考法模型:
1. 考法模型一:位示图与多级索引文件系统的空间联动推导¶
- 题型特征:给出磁盘总容量(如 \(16\text{ TB}\)$ \text{)、物理盘块大小(如} $\(4\text{ KB}\)$ \text{)、系统字长(如} $\(64\text{ 位}\)),同时设计混合索引文件结构(直接索引 + 一级间接 + 二级间接)。
- 核心设问与破题路径:
- 计算位示图所占的物理块数:
- 先求总盘块数:$$ \text{N = \frac{16\text{ TB}}{4\text{ KB}} = \frac{16 \times 2^{40}}{4 \times 2^{12}} = 2^{32}\text{ 块}} $$。
- 计算位示图位数:$$ \text{2^{32}\text{ 位}} $$。
- 计算位示图字节数:\(2^{32} / 8 = 2^{29}\text{ B} = 512\text{ MB}\)。
- 计算位示图外存块数:$$ \text{\frac{512\text{ MB}}{4\text{ KB}} = 128\text{ K 块} = 131072\text{ 块}} $$。
- 新文件创建与块分配时的位示图同步:
- 写入一个 \(10\text{ KB}\)$ \text{的文件,需要分配} $\(\lceil 10 / 4 \rceil = 3\) 个物理块。
- 若该文件采用直接索引,除了为数据分配 3 个数据盘块外,是否需要额外分配索引块?若 FCB 中直接包含 10 个直接块指针,则只需 3 个数据块,位示图中需将 3 个原本为 0 的二进制位置为 1。
- 此时必须注意:修改内存位示图的同时,必须将这 3 个位所属的位示图物理盘块标记为脏块,并在关闭文件或执行
fsync时刷回磁盘。
2. 考法模型二:成组链接法的动态模拟追踪¶
- 题型特征:给出超级块空闲栈容量(如 100 块),当前超级块栈中剩余 \(k\) 块,给出若干组的指针块关系,要求模拟进程连续申请或释放若干盘块后,超级块栈的内容变化及发生的磁盘 I/O 行为。
- 解题模板与规范:
- 连续申请盘块导致跨组:
- 若当前 \(N = 1\),进程申请 1 个盘块。
- 第一步:取出当前栈底唯一的盘块号 \(P = \text{Free}[0]\)。
- 第二步:发起一次物理磁盘读操作,将盘块 \(P\)$ \text{内部存储的下一组空闲盘块信息(块数} $\(N'\) 及盘块号列表)读入超级块栈。
- 第三步:将盘块 \(P\) 分配给请求进程使用。
- 得分要点:必须答出“发生一次磁盘读 I/O,将新组信息加载至超级块内存栈,再分配原指针块”。
- 连续释放盘块导致栈满:
- 若当前 \(N = 100\)$ \text{,进程释放一个盘块} $\(Q\)。
- 第一步:发起一次物理磁盘写操作,将当前超级块栈中的全部数据(包含当前块数 100 及 100 个块号)整体写入新释放的盘块 \(Q\) 中。
- 第二步:重置超级块栈:将盘块 \(Q\)$ \text{记录为新组的第一个块(} $\(\text{Free}[0] = Q\)$ \text{),栈顶指针设为} $\(N = 1\)。
- 得分要点:必须明确指出“发生一次磁盘写 I/O,现存栈数据下刷至新盘块,超级块栈清空并初始化为 1”。
3. 考法模型三:FAT 表项跨链、空间检索与物理寻址¶
- 题型特征:给出簇大小、FAT 表项位宽(如 FAT32 每个表项占 4 字节),给出目录项中的起始簇号及 FAT 表的片段内容,要求推导文件的物理块分布及空闲簇分配过程。
- 核心推导要点:
- 文件读取时,通过首簇号查 FAT 对应表项,读取下一簇号,直至遇到
EOF。 - 为文件追加数据时,操作系统从头或从上次分配位置顺序扫描 FAT 表,寻找表项值为
0的簇作为新分配簇。 - 将原文件的末尾簇表项内容由
EOF修改为新分配的簇号,并在新分配簇的 FAT 表项中写入EOF。
五、 考点速记清单¶
1. 核心要点速记¶
- 分配单位:磁盘读写最小单位是扇区;文件系统分配最小单位是簇(块)。
- 内部碎片:文件大小非簇大小整数倍时产生,最后一个簇的剩余空间即为内部碎片。
- FAT 的双重身份:既是文件的物理链接分配结构,又是全盘的空闲空间管理结构。
- 索引结点(Inode):仅用于管理具体某个文件的元属性,绝不能用于管理全盘空闲块。
- 空间开销唯一无关项:只有位示图占用的外存大小严格由磁盘总块数决定,与当前空闲块数量绝对无关。
2. 核心计算公式汇总¶
- 簇分配数: $$ \text{K = \left\lceil \frac{\text{文件大小}}{\text{簇大小}} \right\rceil} $$
- 实际占用磁盘空间: $$ \text{V = K \times \text{簇大小}} $$
- 位示图存储字节大小: $\(S = \left\lceil \frac{C_{\text{disk}} / B_{\text{block}}}{8} \right\rceil \text{ Bytes}\)$
- 位示图坐标变换(基数从 0 开始): $\(b = i \times W + j \iff i = \lfloor b / W \rfloor, \quad j = b \bmod W\)$
-
位示图坐标变换(基数从 1 开始): $$b = (i
-
1) \times W + j \iff i = \lfloor (b
-
1) / W \rfloor + 1, \quad j = ((b
-
1) \bmod W) + 1$$
3. 易错陷阱提示¶
- 陷阱一:编号基数混淆: 做位示图计算大题时,务必首先寻找题干中的编号定义。看清“字号/行号从 0 还是 1 开始”、“位号/列号从 0 还是 1 开始”、“盘块号从 0 还是 1 开始”。三者若有不同,需利用代入验证法(如代入第 0/1 块验证公式)。
- 陷阱二:字长单位混淆: 公式中的 \(W\)$ \text{为机器字长对应的二进制位数(bit),若题目给出“字长为 32 位”,则} $\(W = 32\)$ \text{;若给出“字长为 4 字节”,计算时必须换算为} $\(4 \times 8 = 32\text{ 位}\)。
- 陷阱三:扇区与簇的分配混淆: 计算文件占用磁盘大小时,题干常同时给出扇区大小(如 512B)与簇大小(如 4KB)。切记外存分配以簇为单位向上取整,切勿以扇区为单位取整。
4. 快速解题口诀¶
文件分配先看簇,向上取整算碎末;
空闲管理问无关,唯有位图定如山;
FAT身兼两重职,Inode只管单个词;
成组链接栈底换,进出跨组才读盘。