位示图

定义

位示图是一种以位为单位记录存储单元忙闲状态的数据结构。它让存储空间中的每一个物理块对应一个二进制位，位的取值表示该块处于空闲还是已分配状态，所有盘块对应的位汇合起来就是位示图^[1]。作为一串比特的集合，位示图既可以写作位图，也可以称为位向量，其中每个比特对应一个磁盘块^[2]。

位示图一般按 m 行 n 列组织，并使 m×n 等于存储空间的总块数，它描述的是文件存储器即磁盘空间的使用情况，每一位对应一个物理块^[3]。位示图在 操作系统 中与空闲区表、空闲链表、成组链接等方法并列，是 文件系统 管理空闲磁盘块的常用手段之一^[4]。

原理

位示图在程序里通常用一个二维数组描述，数组中的每个元素取一位的值^[1]。约定 0 表示空闲、1 表示已分配是常见做法，也有些系统把两个取值颠倒过来，二者在本质上相同，都是用一位的两种状态区分空闲与占用^[1]。

磁盘块的分配分三步完成：首先在位示图中顺序查找一个或一组取值为 0 的位；如果找到的位置在第 i 行、第 j 列，就用 $b = n(i-1)+j$ 换算成对应的盘块号，其中 n 为每行的位数；最后把该位改写为 1，表示这个块已经分配出去^[1]。

磁盘块的回收是上述过程的逆运算：先由待回收的盘块号 b 反求行号与列号，$i = (b-1) \div n + 1$、$j = (b-1) \bmod n + 1$，再把位示图中对应的位由 1 改回 0^[1]。若按机器的字来组织，块号也可写成字号、字长与位号的关系式，例如字长为 32 位时，编号 4195 的物理块落在位示图第 132 个字的第 3 位，分配时只需把这一位置 1^[5]。

发展历程

磁盘空闲空间的管理方法有若干种，位示图是其中较通用的一种，早于它出现的思路还有空闲区表与空闲链表^[4]。采用位示图的早期系统包括 NOVA 机的 RDOS、PDP-11 的 DOS，以及微型机上的 CP/M、Apple-DOS^[1]。苹果的 Macintosh 也用位向量来记录磁盘空闲块^[6]。

Linux 的 ext2 把位图与块组结合起来，每个块组中各设一个块位图块和一个索引节点位图块，前者记录本组数据块的占用情况，后者记录 索引节点 表项是否在用。其后继 ext4 沿用这一设计，块位图跟踪块组内数据块的使用，inode 位图记录索引节点表项的使用，同样是一位对应一个数据块或一个索引节点^[7]。

为降低管理开销，有研究在基本位示图之上引入二级位示图目录的概念，并把它推广成多级位示图目录法，用于存储资源的分配与回收^[8]。位示图的思想后来还被移植到其他领域，例如在光网络路由与频谱分配研究中出现频谱位示图，用于表述频谱资源的虚实状态^[9]。

应用

最直接的用途是空闲磁盘块的管理：系统通过位示图判断哪些块可以使用，分配时置位、释放时复位，不必为分配和回收反复启动磁盘读写^[1]。由于相邻的位对应相邻的盘块，位示图还便于找出成组连续的空闲块，需要 6 个连续空闲块时，只要找出 6 个连续为 0 的位即可^[1]。

在教学与软件资格考试中，位示图是空闲存储空间管理的常见考点，题目往往给定字长、物理块大小和磁盘容量，要求计算位示图占用的字数，或者判断某个块号落在第几个字、第几位^[3]。操作系统课程实验中也常用二维位示图模拟盘块的分配与回收，把行优先编号的位与盘块号相互换算^[10]。

位示图式的状态表示还见于日常系统：Git 贡献度热力图用颜色区分某一天是否有代码提交，售票软件中的座位图用不同颜色区分座位是否售出，都可以看作这一思路的延伸^[4]。

局限

位示图的规模由存储空间的总块数决定，尽管它是各种空闲空间管理结构中最紧凑的一种，磁盘容量大时整张图仍会相当可观；只有当位示图能够整体放入内存，这种方法才有效率，因此它更适用于容量相对较小的磁盘。以 4GB 容量、块大小 4KB 的磁盘为例，仅管理空闲块就需要约 128KB 的位示图^[6]。

位示图本身只保存每个块的忙闲标志，并不直接给出空闲块的块号，分配时需要顺序扫描寻找空闲位，还要用公式把行列号换算成块号，额外增加了计算量^[1]。当位向量过大时，可以把它划分成若干区域，并建立记录各区域空闲块数量的汇总结构，以加快查找^[6]。

位示图还存在与实际情况不一致的风险，例如位图状态错误可能导致同一个块被重复分配。ext4 为此为块位图和索引节点位图计算 校验和，一旦校验失败就把相应块组标记为损坏，在分配时跳过该块组^[11]。

参见

• 文件系统 —— 位示图主要用于记录其空闲磁盘块的占用情况。

• 索引节点 —— ext2、ext4 用 inode 位图记录索引节点的分配情况。

• 成组链接法 —— 与位示图并列的另一种空闲磁盘块管理方法。

• 文件分配表 —— 另一种记录磁盘块占用与链接关系的表格结构。

• 位向量 —— 位示图所采用的基本数据表示形式。