54415文件存储空间管理
# 4.1_5_文件存储空间管理
在这个小节中我们会开始学习文件存储空间管理相关的知识点，在之前的小节中我们学习了文件的物理结构，也就是对非空闲磁盘块的管理，在这个小节中学习的对存储空间的管理，其实就是对空闲的那些磁盘块的管理。
那么这个小节我们首先会介绍存储空间的划分与初始化，要介绍几个比较重要的概念，文件卷、目录区和文件区，之后这个小节的重点内容是要介绍存储空间管理的几种方法，空闲表法、空闲链表法、位示图法和成组连接法，我们会按从上至下的顺序依次讲解。
在学习这几种管理方法的时候，大家需要从这样的三个角度来进行理解和记忆。第一，这些方法是用什么样的数据结构，用什么样的方式来记录和组织那些空闲的磁盘块的。第二要注意的是用某一种方法是怎么分配磁盘块的。第三个是要注意怎么回收磁盘块。
# 存储空间的划分与初始化
我们首先来看存储空间的划分与初始化，如果自己安装过 windows 操作系统的同学肯定有这样的经验，就是在安装系统的时候有一个必经的步骤，就是要让我们为磁盘分区，也就是分成我们平时熟悉的什么 c 盘、d 盘、e 盘这样的一些逻辑磁盘。这些所谓的 cdef 盘，就是我们这儿所谓的文件卷或者叫逻辑卷，逻辑盘，逻辑磁盘，我们的一些文件就是存放在这些各个文件卷里的
另外在存储空间的初始化的过程当中，也需要把这些文件卷进行进一步的划分，划分为目录区和文件区。
其中目录区主要是用于存放文件目录相关的一些信息，像咱们之前学过的文件目录，像 fcb 还有索引节点，这些就是存放在目录区当中的。另外用于磁盘存储空间管理的那些信息，那些数据结构也是存放在目录区当中。比如说咱们这个小节接下来会学习的什么空闲表，还有位示图之类的这些数据结构，就是要存放在目录区当中
那文件区就是用来存放普通的文件数据，所以这是文件区和目录区的区别。
另外在有的支持超大型文件的那些操作系统当中，也支持多个物理磁盘组成一个文件卷，像平时咱们自己使用的电脑都是把一个物理磁盘划分成多个这种逻辑磁盘，但是在有的系统当中可以把多个物理磁盘合并成一个逻辑磁盘一个文件卷，这是存储空间的划分与初始化需要注意的几个知识点。
首先是要知道什么是文件卷或者叫逻辑卷逻辑盘，另外我们需要知道文件卷会划分成目录区和文件区，也还需要知道文件区和目录区分别是用于存放什么数据的。另外我们需要注意的是，文件卷是可以由多个物理磁盘组成的。
# 空闲表法
接下来我们来看第一种存储空间的管理方法，空闲表法。假设一个系统当中此时是这种情况，绿色的这些是表示空闲块，橙色的是表示非空闲的块，假设使用的是空闲表法的话，此时这个系统的磁盘对应的空闲表就是这个样子。
其实空闲表和我们在内存管理的动态分区分配当中，学习过的空闲表是极其类似的，它就是记录了每一个空闲区间的起始位置，还有空闲区间的长度这两个信息。像第一个空闲区间是 0,1 这两个连续的空闲块，所以这个空闲区间对应的是第一个表项，它的第一个空闲磁盘块号是 0，然后空闲盘块数是二。再来看空闲区间，10~14，这些都是空闲的磁盘块，所以它对应的第三个表项，第一个磁盘块号就是 10，然后空闲盘块数就是 5，这个很好理解。那空闲表法一般来说适用于文件的物理结构是连续分配的这种场景下，
接下来我们要探讨的问题是采用这种方法应该怎么分配磁盘块，其实和内存管理的动态分区分配是很类似的，我们首先需要知道的是采用这种方式的话，为文件分配的是一个连续的存储空间，我们同样可以采取像首次适应，最佳适应最坏适应这些算法来决定到底要为文件分配哪一个空闲区间。
我们直接来举个例子，假设此时新创建了一个文件，这个文件请求要用三个磁盘块，那么如果我们采用的是首次适应算法的话，系统会依次检查空闲表当中的各个表项，然后找到第一个能够满足三个块这样需求的一个空闲区间。第一个空闲区间只有 2 个空闲块显然不满足，第二个依然不满足，第三个有 5 个空闲块，因此这个空闲区间是第一个能够满足三个连续的块这样的要求的一个空闲区间，所以我们从空闲区间当中摘出三个磁盘块分配给文件，也就是 10 ，11 ，12 这三个磁盘块，那么把它们分配了之后，这儿空闲区间的属性就改变了，因此我们也需要修改空闲区间相应的一些数据，把它的起始盘块号变成 13 号，然后它的空闲盘块数量就只剩下两个，这是首次适应算法的一个例子，
最佳适应和对话适应其实和咱们之前在内存管理当中介绍过的思想是一样的，最佳适应就是要找到一个能够满足他的要求，并且最小的一个空闲区间进行分配，最坏适应的话就是找到一个能够满足他需求，并且最大的一个连续的空闲区间进行分配。因为学习过内存管理，所以这些应该都不难理解，这就不再展开。
接下来我们要探讨的问题是我们应该如何回收磁盘块，其实和动态分区分配依然是很类似的，当我们回收某一个存储区的时候，回收某一些磁盘块的时候，我们需要注意的就是表项合并的问题需要注意，我们可能会遇到这样的 4 种情况
第一种情况是回收区的前后都没有相邻的空闲区，这种情况下会在空闲表当中新增一个表项。
第二种情况回收区的前后都是空闲区，这种情况需要把它前后的空闲区还有新回收的区域，把它合并成同一个空闲区，因此如果发生第二种情况的话，那么表项的数量是会减少一个的。
第三种情况，回收区的前面是空闲区，
第四种情况回收区的后面是空闲区，三和四这两种情况并不会导致空闲表的表项的数量有所改变。
我们直接来看第二个情况的例子，回收区前后都是空闲区的这种例子。假设此时有我们删除了一个文件，系统要回收它所占用的 15，16 17 这几个磁盘块，因此回收 15 16 17 这几个磁盘块的时候会发现，回收区的前面和后面都是有两个相邻的这种空闲区间，因此我们需要把这一整片的空闲区把它给合并，因此需要把空闲表当中的这两个表项合二为一变成这种形式，第一个空闲盘块号是 13，空闲盘块数是连续的 8 个，所以这个地方是 8。
所以可以看到当我们的回收区的前后都是有相邻的空闲区的话，那么当我们把它回收了之后，会导致空闲表的表项数量减一。另外的这三种情况，大家再结合咱们之前内存管理当中学习过的那些内容，再自己进行分析一下，这就不再展开
以上就是空闲表法需要注意的一些问题，第一个需要注意的系统是怎么记录这些空闲区间的信息的。第二个问题我们需要注意的是应该怎么进行磁盘块的分配。第三个我们需要注意的是应该怎么回收这些磁盘块。接下来的一些存储空间管理方法，需要注意的也是这样的三个问题。
# 空闲链表法
那么下面我们来看第二种方法空闲列表法，空闲链表法又可以进一步划分为空闲盘块链和空闲盘区链，它们的区别在于空闲盘块链它是以盘块为单位，就组成一条空闲链，就像这个样子，每一个空闲的盘块中都会存储着指向下一个空闲盘块的指针，
而空闲盘区链是以盘区为单位组成一条空闲链，所谓的盘区就是一些连续的空闲盘块可以组成一个盘区，比如说像这个地方 12 ，13，14，这几个空闲盘块由于它们是连续的，所以把它们组成一个盘区，然后作为空闲链当中的其中一个节点，所以这是空闲盘区和空闲盘块的一个区别，通过这个图应该很好理解。各个空闲盘区当中的第一个盘块里边会记录盘区的长度，还有下一个盘区的指针，比如说像这个地方 21 号盘块当中就记录了盘区的长度是三，并且记录了指向下一个盘区的呃指针，也就是指向 6 号磁盘块，这是空闲盘块链和空闲盘区链的一个区别。
空闲盘块链
接下来我们来看一下采用这两种方式的话，对磁盘块的分配与回收有什么区别。如果采用的是空闲盘块链的话，那么首先系统会保存着链头和链尾的指针，比如说像这个例子当中念头就是 20 号磁盘块，链尾就是 0 号磁盘块，那么当需要分配 k 个磁盘块的话时候，系统就会从链头的位置开始，依次从链头摘下 k 个磁盘块进行分配，并且修改空闲链的链头指针，大家都学过数据结构，所以这个地方很好理解。
回收也很简单，我们需要回收的磁盘块会把它依次挂到链尾，并且需要修改空闲链的链尾指针，所以这就是空闲盘块链进行分配和回收的时候需要做的事情。从空闲盘块链的分配与回收的过程，我们也可以看到，这种方式一般来说是适用于离散分配的物理结构，由于进行分配的时候，都是要从链头一个的摘下这些空闲磁盘块，所以为一个文件分配多个磁盘块的时候，可能需要重复多个操作，需要依次从链头摘下。
空闲盘区链
接下来我们要讨论的是，如果采用的是空闲盘区链的时候，应该怎么分配与回收？首先与空闲盘块链相同的是操作系统，同样是需要保存链头和链尾的指针。在进行分配的时候，如果说一个文件申请 k 个板块，那么我们同样是可以采用首次适应，最佳适应等等那些算法，从链头开始检索，然后按照算法的规则找到一个大小合适的这种空闲盘区分配给文件。而如果说我们没有找到合适的这种连续空闲块的时候，也可以把不同盘区的盘块同时分配给一个文件。
假如1 个文件它此时是需要 6 个磁盘块，那么由于在盘区链当中找不到连续的 6 个空闲磁盘块，所以我们也可以把中间的三还有最后三个磁盘区都分配给文件，这是分配的时候一般来说会采取的策略。
如果说要回收一些磁盘块的话，和咱们之前介绍的空闲表法一样，我们主要需要注意的是回收区和空闲盘区的一个合并的问题。如果说此时回收的这几个空闲盘块，没有与他们相邻的这种空闲盘区的话，那么回收区就会作为一个单独的空闲盘区，挂到链的链尾，比如说此时回收的是 17 ，18 这两个盘块，那么由于他们的前面和后面都没有相邻的空闲盘区，所以 17 ，18 会作为单独的一个空闲盘区，然后把它挂到链的链尾。
这种空闲盘踞链既适用于离散分配，也适用于连续分配，并且比起空闲盘块链来说，他给一个文件分配多个盘块的时候效率要更高，因为空闲盘块链只能从这个链当中一个一个的把这些磁盘块择下来，而空闲盘区链可以一次摘出一大片连续的空闲区间，所以它在分配多个磁盘块的时候，效率是要更高的。
# 位示图法
接下来我们再来看第三种，存储空间的管理方法，位示图法，这也是咱们在考试当中最常考的一种方法，这种方法的原理其实也很简单，就是用一个的二进制位来分别对应各个盘块的是否已分配这样的一个信息，比如说在这个例子当中，我们用零代表一个盘块空闲，用一代表一个盘块不空闲已分配，
像这个地方如果绿色的表示的是空闲，橙色表示的是不空闲的话，前 4 个应该是 0101，这个地方就是 0101，与他们都是一一对应的，后面的 8 个都是非空闲的，所以之后应该有 8 个连续的一、12345678 这 8 个连续的一分别对应这 8 个非空闲的块，再接下来的 4 个块是空闲的，所以接下来的 4 个二进制位应该是 0，所以位示图法的这种原理并不难理解。
一般来说位示图的数据在系统当中存储的时候都是会存储成一系列连续的字，比如说在这个例子当中一个字的字长是 16 位，也就是这样的一行是 16 位，每 1 个字有 16 个二进制位组成，因此我们可以用字号和位号这样的 2 元组来定位到其中的某一个二进制位。
所以考试当中经常考察的内容就是怎么从字号和位号推算出它所对应的盘块号，或者怎么从盘块号逆推出这个盘块号所对应的字号和位号，这也是我们需要重点掌握的内容。
在做类型的题目的时候，大家一定需要注意题目的条件，盘块号、字号、位号这些到底是从 0 开始的还是从一开始的？像这个例子当中盘块号字号位号都是从 0 开始的，如果说我们用 n 表示字长的话，这个字号位号 i，j 转换成对应的盘块号的公式就可以写成 ni 加上 j
我们来验证一下，字号为 0，位号为 1 二进制位，它所对应的盘块号是多少呢？由于字长是 16，而字号为 0，所以这个地方 ×0 再加上尾号 j 也就是加上 1 =1。所以二进制位所对应的盘块号应该是 1 号块。
另外如果字号为 1，位号为 10 的话，那么它所对应的盘块号就应该是 16，也就是字长乘以字号 1，再加上尾号 J 也就是 10，最后等于 26。所以字号为 1位号为 10 的二进制位对应的是 26 号磁盘话，大家也可以自己数一下，他们俩确实是相对应的，这是字号和位号转换成盘块号的一个算法。
如果说要用盘块号推出字号和位号，怎么算呢？字号 i 等于盘块号 b 除以字长 n 然后取整数部分，然后位号等于盘块号对 n 取余，所以在这个例子当中，如果说盘块号为 13 的话，那么它所对应的字号和位号就分别是 0 和 13，也就是对应的是而精之谓。如果说盘块号为 31 的话，它所对应的就应该是字号为一，位号为 15，也就是 4 号为一位，号为 15，也就是而进之位，所以它和 31 号块是相对应的，大家也可以自己数一下。这个例子当中我们给出的是盘块号字号位号都是从 0 开始的情况，在咱们王道书上给出的是这几个数据都是从一开始的一个算法，但是不管是从 0 开始，还是从一开始，大家都需要能够自己推出来，这个并不需要死记硬背。
接下来我们要考虑的问题是采用位示图法的话，怎么进行磁盘块的分配和回收？在进行分配的时候，如果说某个文件需要 k 个块，那么系统可以顺序的扫描这些位示图，然后找到 k 个相邻或者不相邻的 0，因为 0 代表的是空闲块，另外需要用这些 0 对应的字号和位号计算出它们所对应的盘块号到底是多少，然后把这个盘块分配给文件，并且要把相应的位设置为一，也就设置为已分配的状态。
回收的过程也很简单，就是需要根据回收的盘块号来计算出它所对应的字号和位号，然后再用字号和位号找到相应的二进制位，把二进制位设为 0。
因此从分配和回收的过程也可以看到，用字号和位号转换成盘块号，还有用盘块号转换成它所对应的字号和位号，这个是十分重要的。如果说采用的是位示图法的话，在连续分配和离散分配的这种场景下都适用。假如说是要求连续分配的话，那么我们在扫描位示图的时候就可以尝试找到连续的 k 个块；而如果说采用的是离散分配的方式的话，那么在找这 k 个块的时候，就不需要一定要找到连续的 k 个 0，这是位示图法需要注意的一系列事情。
# 成组链接法
接下来我们来看最后一种存储空间的管理方法成组链接法。咱们之前介绍的空闲表法，还有空闲链表法是不太适合于大型的文件系统的，因为在大型文件系统当中，空闲表和空闲链表有可能会很长很大，在 UNIX 系统当中采用的是成组连接法，对磁盘的空弦块进行分组的管理，
在文件卷等目录区当中会设置一个专门的磁盘块，把它作为所谓的超级块，这个超级块的作用咱们一会再解释，当系统启动的时候需要把超级块读入内存，并且在整个过程当中需要保持内存和外存当中超级块的数据一致。
接下来我们来看一下这个超级块到底有什么作用。在超级块当中记录了下一组空闲盘块的数量，比如说下一组总共有 100 个空闲盘块，另外它还需要记录这 100 个空闲盘块的盘块号分别是多少，通过这些盘块号，我们就可以依次找到下一个分组的各个盘块了。
所以这是第一个空闲盘块的分组，总共有 100 个，他们分别是 201 号磁盘块一直到 300 号磁盘块，这个地方需要注意的一点是 300 号磁盘块它作为分组的第一个磁盘块，也就是这个第一个位置对应的磁盘块，在这个块当中还需要记录下一组空闲盘块的一些信息。
同样的这个地方 100 表示的是下一个空闲盘块的分组，总共有 100 个空闲盘块，这些数字就是代表了下一个分组当中各个盘块的盘块号。所以通过这些盘块号，我们又可以找到再下一个分组的盘块分别是哪些
同样与之前类似，在这一个分组当中，400 号盘块它是分组当中的第一个盘块，所以 400 号盘块也会再记录，再下一个分组的盘块数量，还有各个盘块的盘块号，用这种方式，我们就可以把整个系统当中所有的空闲盘块给一一连起来了。在倒数第二个分组的第一个盘块这儿，我们可以把这个数字设置成一个特殊的值，-1，就代表再下一个分组已经是最后一个分组了。所以如果找到这个只为-1 的节点的话，那么就证明在之后已经没有更多的分组了。 另外大家需要注意的是，其实每一个分组的这些盘块号并不要求连续，这个地方我把这些数字设置成连续的原因，是为了让大家更方便的看出每一个分组到底有多少个盘快，像分组 201，300 总共 100 个数，也就对应 100 个盘块，这和这个地方记录的这一组的盘块数量刚好是对应的，只是为了让大家方便看出这件事情。
另外大家需要注意的是在乘组链接法当中，每一个分组的盘块数量有一个上限，像这个例子当中每个分组最多只有 100 个盘块，另外一个大家需要注意的是最后一个分组的盘块数是要比其他的这些分组要更少一块，那原因是出在这个-1
接下来我们要探讨的是怎么进行磁盘块的分配。假设此时某一个文件需要分配一个空闲块，首先是需要检查第一个分组当中的盘块到底够不够这个文件的需求。那由于此时超级块，已经是读入内存的了，所以我们在进行检查的时候并不需要读磁盘操作，我们只需要找到内存当中超级块的这些数据，并且检查下一组的空闲盘块数是否大于此时要求得到的空闲盘块数。由于 1 是小于 100 的，所以说明第一个分组当中的这些空闲盘块是足够分配的。接下来就会把分组当中的最后的盘块分配给这个文件，也就是 201 号盘块，这个盘块分配出去之后，就需要把这个地方的数据删除，并且要把下一个分组的空闲盘块数把它减一，也就是从 100 变成 99，这样的话就完成了分配一个空闲块这个事情。
接下来我们再来看，如果说此时是需要分配 100 个空闲块的话怎么办？首先第一件事也是检查，第一个分组到底够不够分配。由于此时第一个分组的数量总共有 100 个空闲盘块，因此第一个分组是足够的。因此接下来我们会把第一个分组的这 100 个磁盘块全部分配出去，不过这个地方需要注意的是 300 号磁盘块，存储了再下一个分组的这些磁盘块的信息。因此如果我们把 300 号磁盘块直接分配给文件不做任何处理的话，和下一组的这些链接的信息就断掉了。因此在我们把 300 号磁盘块正式分配给文件之前，我们需要把 300 号磁盘块当中的这些数据把它复制到超级块当中，这样的话就可以保证虽然分组已经全部分配给这个文件了，
但是下一个分组的这些链接信息，我们依然是保存在超级块当中的，
如果说文件要求的是更多数量的空闲块的话，那么我们依然是可以用同样的方式把这些分组一个的全部分配出去。不过需要注意的就是每一个分组正式分配出去之前，需要把分组指向下一个分组的那些链接信息都先复制到超级块当中，所以超级块其实就充当了一个链头的作用，在这个链头当中永远要保持指向下一个分组的一些信息。
接下来我们再来看一下怎么回收一个空闲块。假设每个分组的磁盘块上限是 100 块，而第一个分组此时只有 99 块，那么假如此时还要再回收一个空闲块的话，由于此时第一个分组还没满，所以我们可以把空闲块把它插到第一个分组当中。比如说我们回收的是 201 号块，那么我们可以把 201 号块的链接信息把它放到超级块当中，并且把超级块当中的下一组的空闲盘块数从 99加一变成 100，这是第一种情况，如果分组没满的话，那么可以把回收的空闲块插到第一个分组当中。
那再来看第二种情况，假设此时第一个分组已经满了总共有 100 个块，如果此时还要再回收一个空闲块的话，应该怎么处理呢？由于分组已经满了，显然空闲块不能把它放到分组当中，所以我们可以把新回收的空闲块作为一个新的分组。不过需要注意的是，我们需要把超级块当中的内容复制到新回收的块当中，这样的话新回收的块，它作为一个新的分组，它就拥有了指向下一个分组的这些链接的指针。而由于我们的超级块，永远是要指向第一个分组的，所以超级块的数据就需要进行修改，让它指向第一个分组，也就是新的回收块组成的新分组。由于新分组当中此时只有一个空线块，所以这个地方的数据是一，然后指向它的块号也就是 300，这是回收的时候遇到的第二种情况。
# 小结
小节当中我们介绍了文件存储空间管理相关的知识点，刚开始我们介绍了文件卷、目录区、文件区的概念，这些概念大家需要结合我们的生活经验，什么 c 盘 d 盘 e 盘那些进行理解和记忆。
另外大家需要注意的是一个文件卷当中，目录区中会包含文件目录，还有像空闲表、位示图超级块这些用于文件管理相关的这些数据，而文件区就是用于存放普通的文件数据的 之后我们介绍了 4 种存储空间管理的方法，空闲表法有可能结合首次适应、最佳适应、最坏适应等等这些算法来进行考察。大家还需要回顾咱们在内存管理章节当中学习过的这些算法的策略，在空闲表法当中我们需要注意在回收的时候是不是应该对表项进行合并。 接下来我们又介绍了空闲链表法它分又进一步可以细分为空闲盘块链和空闲盘区链，空闲盘块链是以盘块为单位组成一个空闲链，而盘区链是以盘区为单位组成一个空闲链，要注意它们俩的区别。第三种位示图法，这是咱们在考试当中最常考察的一个考点，大家要能够自己推出盘块号，还有字号位号之间的这种转换的公式。另外在做题的时候需要注意，二进制 0 和 1 到底哪一个是代表盘块空闲，哪一个是代表不空闲，还需要注意字号，位号盘块号到底是从 0 开始的还是从一开始的
最后我们介绍了成组连接法，这是 UNIX 系统采用的一种策，略适合于大型文件系统。成组链接法的规则比较复杂，并且不太方便用文字进行描述，所以这个知识点也很难作为考题进行考察。不过只要理解了刚才咱们分析的那些过程，即使考到了，其实也没有关系，肯定是可以做出来的。
