位示图：磁盘空闲空间管理与字号计算¶

位示图（bitmap）用一个二进制位记录一个磁盘块是否已分配。 它属于操作系统的文件系统知识，帮助系统找到可用的存储空间。

理解位示图要分清三件事：磁盘块存文件数据，位示图记录分配状态，文件的索引或区段等元数据记录数据块的位置和顺序。

1. 一个位怎样表示一个块¶

磁盘或分区会被文件系统划分为分配单位，教材题目通常称为“块”。先约定：

0：空闲，可以分配。
1：已分配，不能重复分配。

假设只有 8 个块，位示图如下：

块号	0	1	2	3	4	5	6	7
对应的位	1	0	1	1	0	0	0	1
分配状态	已分配	空闲	已分配	已分配	空闲	空闲	空闲	已分配

需要一个新块时，可以找到块 1，把对应的位从 0 改为 1。回收块 3 时，则把对应位从 1 改为 0。

这里的“已分配”包括文件数据、文件系统元数据等用途；单独一个 1 不能告诉我们它属于哪个文件。题目或文件系统也可能使用相反的 0、1 约定，必须先看定义。

2. 字、字号、位号分别是什么¶

为什么要把位示图分成“字”¶

位示图可能有成千上万位。为便于存储和处理，可以每 w 位分成一组，这一组叫一个 字（word）；w 就是题目中的字长。

例如字长为 32 位，一个字可以容纳 32 个块的状态。它不是 32 个字节，也不是一个文件或一个磁盘块。

概念	在位示图题目中的含义
磁盘块号	要查询哪个磁盘块，例如块 100
字长	每个字有多少位，例如 32 位，也就是 4 字节
字号	目标位落在哪一组，例如字号 3
位号	目标位在这一组内的编号，例如位号 4

一般讨论计算机体系结构时，“字长”通常指处理器自然处理的数据宽度。位示图题目会直接给出分组所用的字长，应以题目定义计算；实际文件系统的位图格式也不必随 CPU 字长变化。

用一个小位图理解坐标¶

为了方便画表，下面暂取 每字 8 位，字号、位号和块号都从 0 开始：

字号	位号 0	位号 1	位号 2	位号 3	位号 4	位号 5	位号 6	位号 7
0	块 0	块 1	块 2	块 3	块 4	块 5	块 6	块 7
1	块 8	块 9	块 10	块 11	块 12	块 13	块 14	块 15
2	块 16	块 17	块 18	块 19	块 20	块 21	块 22	块 23

块 13 在字号 1、位号 5。字号和位号就像行号与列号，共同定位位示图中的一个状态位。

这是为讲解而把位号从左到右排列；具体格式可以规定别的位序，不能仅凭 CPU 大小端推断表中哪一侧是位 0。

3. 从块号计算字号和位号¶

先采用最简单的约定：块号、字号和位号均从 0 开始，块号直接对应位示图下标。 设块号为 b，每字有 w 位：

字号 i = b // w
位号 j = b % w

反过来：块号 b = i × w + j

// 表示整除取商，% 表示取余。这个公式来自除法的关系：

1	`b = i × w + j，且 0 ≤ j < w`

前面已经放满 i 个字，每字 w 位，共越过 i × w 位；再向后数 j 位，就到目标位置。因此无需死记，商决定在哪一组，余数决定组内位置。

例：每字 32 位，查询块 100¶

100 = 3 × 32 + 4

字号 = 3
位号 = 4

字号 0 覆盖块 0～31，字号 1 覆盖块 32～63，字号 2 覆盖块 64～95，字号 3 覆盖块 96～127。

因此块 100 在 字号 3、位号 4，用自然语言从 1 开始数，就是 第 4 个字的第 5 位。

如果编号不是从 0 开始¶

先把块号转换成从 0 开始的位示图下标，再分组，最后转换为题目要求的输出编号。

设位示图第一位对应的块号为 b₀，且之后连续对应各块：

位示图下标 k = b − b₀

从 0 开始的字号 = k // w
从 0 开始的位号 = k % w

若题目要求字号从 1 开始：字号再加 1
若题目要求位号从 1 开始：位号再加 1

例如块号从 1 开始，每字 32 位，查询块 32：下标为 31，所以它在字号 0、位号 31，而不是下一字的第一位。

若位示图只覆盖某个数据区，b₀ 是该区域的起始块号。若保留块也有对应位，通常只是把这些位标记为不可用，不能擅自从块号中扣除保留块数量。

4. 原题：16385 号物理块与 1000 GB 磁盘¶

题目条件：系统字长 32 位，磁盘物理块大小为 4 MB，物理块与位示图的字都依次编号为 0、1、2……。求：

16385 号物理块的状态记录在哪个字中？
容量为 1000 GB 的磁盘，需要多少个字来存储位示图？

第一问：定位状态位¶

16385 = 512 × 32 + 1

字号 = 512
位号 = 1（按位号也从 0 开始计算）

题目明确规定 字号从 0 开始，因此第一空按字号填写 512。这也是从 1 开始数的第 513 个字。

题干虽然用了“第几个字”的口语表达，作答仍要服从它明确给出的编号约定。“字号 512”和“从头数第 513 个字”指向同一位置。

第一问只需要块号和字长。4 MB 是每个块存多少数据，不能拿它替代每字 32 位来计算字号。

第二问：先求块数，再求字数¶

按此类教材题常用的二进制换算，即 1 GB = 1024 MB 计算：

磁盘块数 = 1000 × 1024 MB ÷ 4 MB
         = 256000 个块

位示图位数 = 256000 位
位示图字数 = 256000 ÷ 32
           = 8000 个字

位示图字节数 = 8000 × 4
             = 32000 字节
             = 31.25 KiB

因此第二空为 8000。这里计算的是位示图本身的大小，没有计入日志、副本等其他元数据。

严格区分单位时，二进制单位应写作 GiB、MiB。若题目明确要求十进制 1 GB = 1000 MB，则有 250000 个块，需要 ⌈250000 / 32⌉ = 7813 个完整的字；解题前应确认单位约定。

补充例题：300 GB 磁盘、1 MB 物理块¶

题设：磁盘容量为 300 GB，物理块大小为 1 MB，字长为 32 位。按 1 GB = 1024 MB 计算：

1
2
3

物理块个数 = 300 × 1024 / 1 = 307200 个
位示图需要 = 307200 位
位示图字数 = 307200 / 32 = 9600 个字

所以，300 × 1024 确实是物理块个数。若题目问“位示图占多少个字”，还要再除以字长 32，答案是 9600 个字。

5. 位示图需要多大空间¶

设需要描述 N 个块，每字 w 位：

要计算的量	公式	原因
有效状态位数	`N` 位	每块对应一位
按字节存储的最小空间	`⌈N / 8⌉` 字节	每字节 8 位，不足一字节也要占一字节
按完整字存储的字数	`⌈N / w⌉` 个字	不足一字也要占一字
按完整字存储的字节数	`⌈N / w⌉ × (w / 8)` 字节	假设字长是 8 的倍数

⌈x⌉ 表示向上取整。例如 33 个块、每字 32 位，需要 33 个有效位：按字节紧凑存储至少 5 字节，若按完整字存储则要 2 个字，即 8 字节。末尾未对应实际块的位不能作为空闲块使用。

已知磁盘容量和块大小时，先统一单位，再计算可描述的块数。题目通常能整除；若只计算一个区域中可用的完整块，区域末尾不足一块的部分不算额外完整块。

6. 图片等文件可以分散存储吗¶

可以。文件的逻辑内容有顺序，但占用的磁盘块不必相邻。

假设一个普通图片文件大小为 10 KiB，文件系统每块 4 KiB，不考虑压缩和稀疏文件。它需要 3 个数据块，可以这样分配：

文件内的逻辑块	文件中的字节偏移	分配到的磁盘块
0	0～4095	2
1	4096～8191	7
2	8192～10239	13

位示图把块 2、7、13 标记为已分配。文件的索引、区段等结构负责记录逻辑块到磁盘块的对应关系；最后一块只有 2 KiB 属于文件内容，在这个简化例子中仍占用一个 4 KiB 块。

读取时，文件系统按文件的逻辑顺序返回数据，应用程序得到的仍是一条有序的字节流，图片可以正常解码。磁盘上的先后位置不决定文件内容的先后顺序。

这里的分散通常以块或区段为单位，并不是把每一个二进制位随意散落。现代 SSD 还会在设备内部做地址映射，文件系统看到的块地址也不等于闪存芯片上的实际位置。

位示图不能单独恢复文件。 它只记录哪些块已分配，不记录文件名、文件长度，也不记录一个文件各块的先后关系。

7. 位示图存在哪里，什么时候使用¶

磁盘保存，内存缓存¶

使用位示图的持久化文件系统通常把它保存在磁盘或 SSD 上的 文件系统元数据区域。运行时，操作系统会把需要的位图片段读入内存缓存，在分配和回收时使用，并按文件系统的写回、日志等机制保存更新。

它可能按块组或区域分成多份，不一定是一整张连续加载到内存的大表。数据块位图和 inode 位图也要区分：前者记录块是否分配，后者记录 inode 是否分配。

CPU 执行文件系统代码，存储控制器负责具体 I/O；位示图不是 CPU 硬件访问磁盘前必须读取的表。

读文件通常不需要先查位示图¶

读取已有文件时，核心路径可以简化为：

文件名 / 已打开的文件
    → 文件元数据
    → 根据文件偏移找到对应数据块
    → 从缓存或存储设备取得数据

文件的索引等元数据解决“数据在哪里”；空闲空间位示图解决“还有哪些块可以分配”。两者分工不同，普通读取不需要先扫描位示图。

不只是新增和删除文件时起作用¶

操作	通常怎样影响位示图
读取已有文件	通常无需改变数据块位图
原地覆盖已分配块中的内容	通常无需分配新块；写时复制等机制可能例外
创建空文件	可能分配 inode，但文件自身未必立即分配数据块；父目录扩展也可能需要空间
追加数据、预分配空间	需要新块时查找空闲位置并标记已分配；仍写在已有块内时不一定变化
截断文件、打洞	释放完整数据块时更新分配状态
删除文件名	等文件的数据真正可以回收时，再释放相应块
碎片整理、迁移或一致性检查	也可能读取、调整或重建分配信息

在 Unix 类文件系统中，删除一个文件名后，如果仍有其他硬链接，或者进程仍打开着文件，数据通常不会立即释放。具体回收时机还受快照、写时复制等机制影响。

把位从 1 改成 0 表示空间可重新分配，不等于已经把块中的旧数据清零。系统也必须协调位图、文件索引和其他元数据的更新，避免重复分配和空间泄漏。

8. 思维导图¶

--- markmap: height: 600 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 位示图 ## 一块一位 - 表示空闲或已分配 - 先确认 0、1 的含义 - 不记录文件名、归属和块的顺序 ## 字号与位号 - 每字 w 位，先换算为从 0 开始的下标 k - 字号 = k // w，位号 = k % w - 商决定分组，余数决定组内位置 - 从 1 开始的输出编号再加 1 ## 空间计算 - N 个块需要 N 个有效位 - 最少字节数 = ⌈N / 8⌉ - 完整字数 = ⌈N / w⌉ - 容量与块大小先统一单位 ## 文件与磁盘块 - 文件逻辑内容有序，磁盘块可以不连续 - 索引或区段记录数据位置 - 位图用于分配和回收空间 ## 保存与使用 - 持久化在文件系统元数据中，运行时可缓存到内存 - 普通读取不必先扫描位图 - 扩展、截断、回收、检查等都可能涉及位图 - 标记空闲不等于擦除旧数据

9. 练习与关联阅读¶

文件管理：继续学习连续分配、链接分配与索引分配。
索引文件结构与容量计算：理解文件数据块如何定位，以及多级索引的容量计算。
计算机系统学习指南：查找操作系统教材与课程。
OSTEP 文件系统模拟练习：通过 vsfs.py 观察 inode 位图、数据块位图和文件元数据。模拟器把普通文件简化为空文件或一个数据块，适合观察创建、写入、链接和删除；多块文件的分配需结合教材继续学习。

手算自测：在块号、字号、位号都从 0 开始、每字 32 位的条件下，块 31、32、33 分别对应哪里？答案依次是 (0, 31)、(1, 0)、(1, 1)。检查分组边界最容易发现误加或漏加 1 的问题。

返回操作系统章节