2.9.4 位示图

本课核心知识点整理

本节导学

位示图用于磁盘空闲空间管理。它用一个二进制位表示一个磁盘块的状态：空闲或已占用。0 和 1 哪个表示空闲，要看题目约定，不能凭习惯硬套。

位示图的优势是结构紧凑、查找和标记方便；代价是需要做块号、字号、位号之间的换算。考试最容易错在编号从 0 还是从 1 开始。

位示图如何表示磁盘块

假设一个字有 w 位，位示图中每一位对应一个磁盘块。若块号从 0 开始，块号 b 对应：

$$\text{字号}=\lfloor \frac{b}{w}\rfloor$$$$\text{位号}=bmodw$$

如果题目从 1 开始编号，先把块号减 1 转成从 0 开始，再代入公式。最后如果题目要求输出从 1 开始的字号/位号，再按题目编号规则转换回去。

为什么编号起点重要

例如每个字 16 位，块号 16 如果从 0 开始编号，它在第 1 个字的第 0 位；如果从 1 开始编号，块号 16 在第 0 个字的第 15 位。差一个起点，结果完全不同。

做题路线

1. 先看题目约定位值：0 表示空闲还是 1 表示空闲。
2. 再看块号、字号、位号是否从 0 开始。
3. 若从 1 开始，先减 1 变成从 0 开始计算。
4. 用每字位数 w 求字号和位号。
5. 如果题目要求按 1 起始输出，最后再加回编号偏移。

例题

单选

位示图中通常：

A一个位对应一个磁盘块B一个位对应一个进程C一个位对应一个线程D一个位对应一个用户

单选

位示图换算题最先要确认：

A只看文件名B先确认编号从0还是从1开始C直接乘以CPU频率D忽略每字位数

自查要点

1. 位示图中的一位表示什么？
2. 为什么编号起点会影响计算结果？