操作系统4.1.5 文件存储空间管理

曾经终败给现在 2023-02-25 03:39 5阅读 0赞

![format_png][]

本节学习需要注意的三个方面：

1.  用什么方式记录、组织空闲块？
2.  如何分配磁盘块
3.  如何回收磁盘块

### 一、存储空间的划分与初始化 ###

**存储空间的划分（为磁盘分区）**：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）

在存储空间初始化时，需要将各个文件卷划分为目录区、文件区。

1.  目录区：主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息
2.  文件区：主要存放文件数据

![format_png 1][]

有些系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷，如下图。

![format_png 2][]

### 二、存储空间管理——空闲表法 ###

**空闲表法**：即用一张表记录磁盘中空闲的盘块。**此方法适用于“连续分配方式”**。

空闲表的表项由**空闲盘的起始块号**和**空闲盘块数**组成。如下图所示

![format_png 3][]

**Q：采用这种方法如何分配磁盘块？**

与内存管理中的动态分区分配类似，为一个文件分配**连续的存储空间**。同样可以采用**首次适应算法、最佳适应算法、最坏适应算法，临近适应算法**来决定要为文件分配哪些区间。

> 例如，如果新创建的文件请求3个块，按照首次使用算法，从10号块开始有5个连续的块可以满足需求，所以把10、11、12三个块分配给文件，分配后的空闲盘块表如下
> 
> ![format_png 4][]

**Q：如何回收磁盘块？**

与内存管理中的动态分配很类似，当回收某个存储区时需要分为四种情况：

1.  回收区前后都没有相邻空闲区——为空闲盘块表增加一个表项即可；
2.  回收区前后都是空闲区——将回收区和回收区前后的两个空闲区合并为一个空闲区；
3.  回收区前是空闲区——将回收区和前空闲合并为一个空闲区；
4.  回收区后是空闲区——将回收区和后空闲合并为一个空闲区。

> 这里以回收区前后都是空闲区为例，磁盘是第一幅图的状态，
> 
> 如果回收21、22号磁盘块，那么回收后的空闲盘块表如下图所示。
> 
> ![format_png 5][]

其他情况与之类似，**回收时注意表项能合并的话就需要合并。**

### **三、**存储空间管理——空闲链表法 ###

空闲链表法分为两种：**空闲盘块链和空闲盘区链。**

![format_png 6][]

下图分别表示空闲盘块链和空闲盘区链。

![format_png 7][]

> **空闲盘块链**中存储着下一个空闲盘块的指针。
> 
> **空闲盘区链**中连续的空闲盘块组成了一个空闲盘区，每个盘区中的第一个盘块记录了盘区长度和指向下一个盘区的指针。
> 
> 如21、22、23号3个盘块组成的盘区，21号盘块中记录了指向下一个盘区的指针（即指向6、7号盘块组成的盘区的指针）和盘区的长度3，其他的盘块类似。

**1、空闲盘块链**

操作系统保存着**链头、链尾指针。**

**①如何分配**：如过某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

**②如何回收**：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

下图表示分配了3个盘块：

![format_png 8][]  
下图表示回收了3个盘块：

![format_png 9][]

从上面可以看出，空闲盘块法**适用于离散分配的物理结构**。为文件分配多个盘块时可能要**重复多次操作**。

**2、空闲盘区链**

操作系统保存着**链头、链尾指针**。

**①如何分配：**

1）若某文件申请K个盘块，由于空闲盘区链将连续的盘块组成一个盘区，所以若某个盘区大小满足可以实现一次分配，同样可以采用首次适用、最佳适用等算法，从链头开始检索，按照一定的规则找到一个大小符合要求的空闲盘区分配给文件。

2）若没有合适的连续空闲块，也可以将不同的盘区的盘同时分配给一个文件，同样分配后也需要修改相应的指针链和盘区大小等数据。

**②如何回收：**

1）若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。

2）若回收区没有和任何空闲区相邻，将回收区作为一个单独的一个空闲盘区挂到链尾。同样也需要修改链表指针和盘区大小等信息。

下图表示按照首次适应算法分配3个盘区

![format_png 10][]

从上面可以看出，空闲盘区链对**离散分配、连续分配都适用**。**为一个文件分配多个盘块时效率更高**。

### **四、**存储空间管理——位示图法（最常考） ###

![format_png 11][]

**位示图：**磁盘内存被划分为一个个磁盘块，可以用二进制位对应一个盘块。

“0”代表盘块空闲，“1”代表盘块已分配。

位示图一般用连续的“字”来表示，下图中一个字的字长是16位，字中的每一位对应一个盘块。

因此可以用（字号，位号）对应一个盘块号。

也可能用（行号，列号）来表示。

**注：盘块号、字号、位号也可以从1开始，只是本案例中从0开始。**

（王道书上给的是从1开始的算法）

**①如何实现盘块号与（字号、位号）相互转换？**

> **n表示字长**
> 
> （字号，位号） = （i, j）的二进制位对应的**盘块号 b = n \* i + j**
> 
> b号盘块对应的**字号 i = b / n，位号 j = b % n**

> 1.  （0,1）—> b = 16 \* 0 + 1 = 1号块，从图可看出1号图已分配，同时位示图中（0,1）的二进制位也是1表示已分配
> 2.    (1,10) —> b = 16 \* 1 + 10 = 26号块，从图可看出26号块是未分配的
> 3.   b = 13 —> i = 13 / 16 = 0，j = 13 % 16 =13，对应的（字号，位号） = （0，13），从位示图可以查出对应的二进制位为0，表示未分配
> 4.   b = 31 —> i = 31 / 16 = 1，j = 31 % 16 =15，对应的（字号，位号） = （1，15），从位示图可以查出对应的二进制位为0，表示未分配

**②如何分配：**

若文件需要k个块，

1.  顺序扫描位示图，找到k个相邻或不相邻的“0”；
2.  根据字号、位号算出对应的盘块号，将相应的盘块分配给文件；
3.  将相应的位设置为“1”（设置为已分配状态）

**③如何回收：**

1.  根据回收的盘块号计算出对应的字号、位号；
2.  将相应的二进制位设置为“0”（设置为未分配状态）

从上面可以看出：**位示图法对连续分配和离散分配都适用**。

### **五、**存储空间管理——成组链接法 ###

空闲表法、空闲链表法不适用大型文件系统，因为空闲表或空闲联保可能过大。

UNIX系统中采用了**成组链接法**对磁盘空闲块进行管理。这是将上述两种方法相结合的而形成的一种空闲管理方法。

**文件卷的目录区**中专门用一个磁盘块作为**超级块**，当系统启动时需要**将超级块读入内存**。并且要保证与外存中的“超级块”的**数据一致**。

![format_png 12][]

> 1、超级块实际上是一个栈结构，用来存放当前**可用的一组空闲盘块号（最多含100个号）**以及**栈中尚有空间的块号数量N**。

![format_png 13][]

> 2、文件区中的所有空闲盘块分为若干个组，假设所有空闲盘块号是201~9999（**实际上分组中的盘块号码是不要求连续的，不要求连续的，不要求连续的**，这里是为了表述方便，认为空闲盘块连续的），将这些盘块进行分组，每组100个。
> 
> 3、每一组含有的盘块总数N和该组的所有盘号块记入**前一组的第一个盘块中**。这样各组的第一个盘块可以链成一条链。
> 
> 4、如果是最后一组，那么将前一个分组的第一个盘块的中存放空闲盘块链的结束标志符，如**“-1”表示下一组是最后一个分组了**。

![format_png 14][]

**①如何分配？**

分配过程是从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将**栈顶指针下移一格**，若该盘块号已是栈底（即第一个盘块），这是当前栈中最后一个可分配的盘块号。

由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，不能直接将它分配掉，需要将它记录的下一组信息保存下来，所以必须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。

然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把**栈中的空闲盘块数减1** 并返回。

> Eg1：如果此时新建一个文件需要一个空闲块
> 
> 1.  检查第一分组的块数是否足够。1<100，所以足够分配
> 2.  将栈顶的盘块号即201号盘块对应的盘块分配出去，且将那个空闲块的数据删除，如下图
> 3.  空闲盘块号由100减为99
> 
> ![format_png 15][]

> Eg2： 需要100个空闲块
> 
> 1.  检查分组的块数是否足够。100=100，是足够的
> 2.  将第一分组中的100个空闲块分配出去。但是由于**300号盘块记录了再下一组的信息，因此需要将300号盘块从外存（磁盘）读入内存，将300号盘块记录的信息**，**写入空闲盘块号栈（复制到超级块中）**
> 3.  将100个空闲区都删除
> 
> ![format_png 16][]

**②如何回收？**

在系统回收空闲盘块时，须调用盘块回收过程进行回收。

它是将回收盘块的盘块号**记入空闲盘块号栈的顶部**，并执行**空闲盘块数加 1** 操作。

当栈中空闲盘块号数目已达 100 时，表示栈已满，便将现有栈中的100 个盘块号**记入新回收的盘块中**，再将其盘块号作为**新栈底**。

> Eg1：以分配的第一个图为例，201盘块被分配出去了，如果此刻有个文件被删除了，其占用的盘块是199号，系统需要回收这个盘块，发现此时空闲盘块号栈中记录空闲块数为99，直接将盘块号记录栈顶，将空闲盘块数加1即可。
> 
> ![format_png 17][]

> Eg2：如果此时又有一个文件被删除了，其占用的盘块是190，此时空闲盘块号数已经达到100了，就需要将现在空闲盘块栈中信息记入新回收的块中。
> 
> ![format_png 18][]

### **六、小结** ###

![format_png 19][]

注意：

1.  目录区包含什么 
2.  空闲表法分配时会与哪些算法结合
3.  位示图法要能推出盘块号、字号、位号的公式
4.  字号、位号、盘块号到底从0开始还是1开始
5.  成组链接法很难出考题

[format_png]: /images/20230209/4abf52916a68456c91df063ebc39b968.png
[format_png 1]: /images/20230209/483db6fed4204ae997a37ea7b31832cf.png
[format_png 2]: /images/20230209/3ffb66ba9f514847ae138dbb345482b0.png
[format_png 3]: /images/20230209/0d4b38e92fb04174ace4fe97970cc180.png
[format_png 4]: /images/20230209/f965ed32b88c4f14baabdf59daccdb4d.png
[format_png 5]: /images/20230209/38703c4c8d9c4cc9aef718058b8199c8.png
[format_png 6]: /images/20230209/97b8e947b27747f5a8e78ae9fc9359a8.png
[format_png 7]: /images/20230209/44c826ce76c24024aaa151498748ddec.png
[format_png 8]: /images/20230209/ef0ce58d0f814170877b35502617926a.png
[format_png 9]: /images/20230209/5044773ac4ac4b28b7913c82336af2c2.png
[format_png 10]: /images/20230209/02f79575185f40d9b6a009008361e672.png
[format_png 11]: /images/20230209/347229126be74589b94f6396c0565c3c.png
[format_png 12]: /images/20230209/80aadbcf9da6423186fe684646791260.png
[format_png 13]: /images/20230209/8d25726bcc0f4002806acdf9f6dacfa1.png
[format_png 14]: /images/20230209/fa9cea93128742149ea65411dd5a6593.png
[format_png 15]: /images/20230209/79c79485d78d4150a80b2057f632fe49.png
[format_png 16]: /images/20230209/cf93aa6f2b864c73ab9fc7a1207a8da2.png
[format_png 17]: /images/20230209/83ce5a56bffa4812959611a9c17997a4.png
[format_png 18]: /images/20230209/eb1874104f9042db83275a0a0b9615e0.png
[format_png 19]: /images/20230209/9cda156a8b744057b903a271ce1c949d.png