【软考学习16】用位示图法，轻松解决空闲存储空间的管理难题

川长思鸟来 2023-09-26 09:49 52阅读 0赞

> 本文将学习了用**位示图法**，解决空闲存储空间的管理难题，位示图在 **GIT 贡献度、高铁票务、电影票务**等领域有着较多应用场景，我们要学会**计算位示图的物理块问题**。

![在这里插入图片描述][3b51f155fd3c42cca3f6de69e1220f49.png]

--------------------

### 一、空闲存储空间 ###

磁盘是用来存储程序数据的，存在没有放满的情况，即有空闲存储空间的情况，我们**需要将这些空闲存储空间管理起来，以便某个程序需要运行时，给这个程序分配相应的空间**。

空闲存储空间的管理有四种不同的方法，分别是**空闲区表法**、**空闲链表法**、**位示图法**和**成组链接法**。

#### 1.1 空闲区表法 ####

空闲区表法，**使用一张表来记录哪些地方是空闲的**，以便把它们管理起来。

#### 1.2 空闲链表法 ####

空闲区表法，把空闲的区块都链起来，**链成一张链表**，需要分配空间时，根据链表顺序进行遍历，从而分配相应的空间。

#### 1.3 位示图法 ####

最主要的空闲区域管理方法，后面详细介绍。

#### 1.4 成组链接法 ####

对这些空闲的区块，**既分组又分链**，进行空闲区域管理的方法。

--------------------

### 二、位示图法的应用 ###

**位示图法**的原理，就是画一张位示图，然后图中每个格子表达的区域，**用 1 表示该区域已被占用，用 0 表示该区域没被占用**。

我们将所有的存储空间分成很多个物理块，就能够很直观的看出哪些物理块正在被使用，哪些物理块是空闲的，从而轻松解决空闲存储空间的管理难题。

![在这里插入图片描述][ff8e16bb051a45f2a4762cc12b86f9d9.png_pic_center]  
在开源项目托管网站上，一般都有 GIT 贡献度热力图功能，如下图所示。

![在这里插入图片描述][82ef825abc8b40a79e8eb66d120e62fd.png]  
这个热力图，代表着过去的每一天，你有没有在提交代码。

如果提交了，那一天的区域显示绿色；反之如果没有提交，那就显示白色。

这其实就是**示图法**的一个直接应用。

--------------------

![在这里插入图片描述][ff8e16bb051a45f2a4762cc12b86f9d9.png_pic_center]  
又比如在购买高铁票时，在购票软件中会显示座位图，如下图所示。

![在这里插入图片描述][bd4f489bab574237972aa8a30d3979ac.png_pic_center]  
对于已被购买的座位，通常用灰色来表示，旅客无法再点击购买。

反之还没被购买的座位，会显示绿色背景，提示旅客可以购买，这也是**位示图法**在高铁票务场景的一个实际运用。

在高铁票务场景是这样，在电影院，也是一样，也可以**用位示图法来解决票务空闲空间**的问题。

### 三、例题 ###

请看下面的例题：

> 在某个文件管理系统中使用位示图，磁盘的物理块编码**从 0 开始编号**，**系统字长 32 位**，每一位对应文件存储器上的一个物理块，如下图所示。  
> 假设将 4195 号物理块分配给某文件，那么该物理块使用位示图的**第几个字**来描述？系统应该将该字的**第几个位置置几**？  
> ![在这里插入图片描述][6be891b38dd74a2993f8137069088039.png_pic_center]

首先看到例题中，一个字节占 4 个物理块，第 4195 号物理块（**从 0 开始编码**）实际上就是我们认为的第 4196 个物理块（**我们通常从 1 开始计算**）。

所以我们用 4196 / 32，等于 131.125，也等于 131 余 4。

也就是超过 131 了，所以前面 131 个物理块都填满，那么**当前占的物理块位置是第 132 个**。

题目要求将某些物理块占用，并且分配使用，肯定是要置为 1 的。

第 1 到 第 131 个物理块占用了 131 \* 32 个位置（4192），即从 **0 到 4191**。

第 132 个物理块的第**零**位置，那就是 **4192**。

第 132 个物理块的第**一**位置，那就是 **4193**。

第 132 个物理块的第**二**位置，那就是 **4194**。

第 132 个物理块的第**三**位置，那就是 **4195**。

所以答案就是**将第三位置 置 1**。

### 四、总结 ###

本文学习了用**位示图法**，解决空闲存储空间的管理难题，位示图在 **GIT 贡献度、高铁票务、电影票务**等领域有着较多应用场景，我们要学会**计算位示图的物理块问题**。

[3b51f155fd3c42cca3f6de69e1220f49.png]: https://img-blog.csdnimg.cn/3b51f155fd3c42cca3f6de69e1220f49.png
[ff8e16bb051a45f2a4762cc12b86f9d9.png_pic_center]: https://img-blog.csdnimg.cn/ff8e16bb051a45f2a4762cc12b86f9d9.png#pic_center
[82ef825abc8b40a79e8eb66d120e62fd.png]: https://img-blog.csdnimg.cn/82ef825abc8b40a79e8eb66d120e62fd.png
[bd4f489bab574237972aa8a30d3979ac.png_pic_center]: https://img-blog.csdnimg.cn/bd4f489bab574237972aa8a30d3979ac.png#pic_center
[6be891b38dd74a2993f8137069088039.png_pic_center]: https://img-blog.csdnimg.cn/6be891b38dd74a2993f8137069088039.png#pic_center