414_文件的物理结构（上）
# 4.1_4_文件的物理结构（上）
在这个小节中我们会开始学习文件的物理结构，也就是文件分配方式相关的一系列问题。那么这个小节的内容十分重要，在历年的考试当中都经常出现 2，3 题的这种选择题，甚至经常会在大题当中进行考察，所以这个小节的内容我们会讲的比较细致，会补充一些课本上没有提到的点。
那么在之前的学习当中，我们知道操作系统它作为最接近硬件的一个软件层次，需要对硬件进行管理，包括外存，也就是磁盘进行管理，那么操作系统对磁盘的管理主要是需要做这样两件事。
第一是需要对非空闲磁盘块进行管理，那么非空闲磁盘块也就是存放了文件数据的那些磁盘块，这就是这个小节要重点探讨的文件物理结构，文件分配方式的问题。
另外还需要对空闲的磁盘块，也就是暂时还没有存放任何数据的那些磁盘块进行管理，这是咱们之后的小节会探讨的文件存储空间管理的问题。这个小节我们先看上面这个问题
其实文件物理结构或者说文件分配方式要探讨的就是文件的数据到底应该怎样存放在外存中，这些数据应该被怎样组织起来的一个问题。总共会分为这样的三种方式，连续分配、链接分配和索引分配。其中链接分配又可以进一步细分为隐式链接和显示链接这样的两种。
在这个视频当中我们首先探讨连续分配和链接分配这两种方式，索引分配会在下个小节中再进行讲解。
# 文件块、磁盘块
在正式开始之前，我们需要先补充几个比较重要的知识点，在之前我们简单的提到过，类似于内存分页，磁盘中的这些存储单元会被分为一个个大小相等的块，这些块也可以称为磁盘块或者物理块，相应的系统也会为这些磁盘块进行一个编号，像这个是 0 号块，这个是 1 号款，以此类推。
另外在很多操作系统当中，磁盘块的大小会设置的和内存块，内存页面的大小相同，那这么做是有好处的，因为内存和外存之间的数据交换，也就是对磁盘的读写操作都是以块为单位进行的，每次读入一块或者每次写出一块，如果说能够保证外存的一个磁盘块和内存的一个内存块的大小是相等的，那么进行这种数据交换的时候就会很方便。
在之前内存管理章节中，我们学习过进程的逻辑地址空间会被划分为一个一个的页面，这样可以方便操作系统对进程进行管理。相应的在外存管理当中，为了方便对文件数据的管理，文件的逻辑地址空间也会被划分成一个一个大小相等的文件块，因此文件的逻辑地址也可以表示为逻辑块号和块内地址的形式，这就类似于一个进程的逻辑地址，可以表示为页号和业内地址的形式。
假设这个系统当中一个物理块的大小是 1KB，那么一个一兆字节大小的文件就可以分割为 1k 个块，所以这个文件的逻辑块号应该是从 0~1023 总共 1k 个块号，并且每一块的大小都是 1KB 这么大，因此用户在操作自己的文件的时候，可以用逻辑块号，还有块内地址这样的形式就可以定位到自己文件当中的任何一个位置。
这个文件的数据被分为一个的逻辑块之后，操作系统为文件分配存储空间也都是以块为单位进行的，比如说逻辑块号为 0 的块，被放到了物理块号为 4 的磁盘块当中，然后逻辑块号为 1 的块放到了这个位置，逻辑块号为 1023 放到这个位置。
不过用户对于自己的文件的这些各个逻辑块到底存放到了什么地方，这个信息用户是不可知的，因此用户在操作自己的文件的时候，是使用的是逻辑块号和块内地址这样的形式，于是操作系统就需要负责把用户提供的逻辑块号和块内地址转换为这个文件块实际存放的物理块号和块内地址，这也是文件的分配方式，文件物理结构这个部分需要重点关注的核心问题。
# 文件分配方式--连续分配
怎么把逻辑块号映射为物理块号？我们首先来看第一种文件分配方式，连续分配，连续分配方式的思想很简单，要求每个文件在磁盘上占用一组连续的块，比如说一个文件 AAA 它在逻辑上可以分为这样的三个块，如果说采用连续分配方式的话，这些逻辑上相邻的块在物理上也必须相邻，也必须是占用一组连续的块，并且依然需要保持这些块之间的这种相对顺序。
比如说 0 号逻辑快放到了 4 号物理块当中，1 号逻辑快放到了 5 号物理块当中，2 号逻辑快，放到了 6 号物理块当中。接下来我们要注意的问题是，如果采用的是这种方式的话，那么操作系统应该如何实现从逻辑括号到物理括号的这种映射和转变？
首先我们需要明确的是用户在操作自己的文件的时候，使用的是逻辑块号，块内地址这样的一个逻辑地址，其实块内地址是不需要转变的，因此操作系统只需要关心逻辑块号到物理块号的映射就可以了。
为了实现这个地址映射的功能，在文件的目录表当中必须记录两个文件的属性，第一是一个文件存放的起始块号，第二是这个文件的长度，也就是它总共占用了多少个块，比如说像 AAA 文件，它的起始块号是 4，并且它占用了连续的三个块，因此它的长度是 3，而另外一个文件 BBB 它的起始块号是 10，然后它占用了连续的 4 个块，因此它的长度又是 4，有了这些信息操作系统就可以完成地址转换的事情了。
假设用户给出了他想要访问的逻辑块号，那么操作系统需要先找到用户想要访问的文件对应的目录项，也就是 fcb。在这个 fcb 当中就可以知道文件存放的起始块号，再用起始块号加上用户提供的逻辑块号，就可以得到这个块存放的实际的物理块号了。
比如说用户想要访问 AAA 文件的逻辑块号为二的块，那么逻辑括号 2 加上它的起始块号 4 就得到物理块号 6。那么从这个图当中我们也可以看到逻辑块号为 2 的块确实是存放在物理块号为 6 的位置的，当然操作系统还需要验证用户提供的逻辑括号是否合法，它是否已经超过了这个文件的实际长度。 所以通过刚才的分析，我们会发现，如果采用的是连续分配方式的话，那么只要用户给出了自己想要访问的逻辑块号，操作系统就可以直接根据逻辑块号算出它对应的物理块号到底是多少。因此我们说连续分配方式是支持顺序访问和直接访问，也就是随机访问的。所谓的顺序访问就是指如果我要访问逻辑块号二的话，那么我必须先顺序的访问逻辑快号 0 和逻辑块号一，之后才能找到逻辑块号二，这是顺序访问。
而所谓的直接访问或者说随机访问就是指如果我要访问逻辑块号二的话，我并不需要访问其他的这些块，我可以直接找到逻辑块号二存放的位置，所以这是顺序访问和直接访问的含义，支持直接访问或者说随机访问也是连续分配方式最大的一个优点。
我们再来分析连续分配方式的第二个优点，这个地方我们需要用到一个现在暂时还没有讲过的知识点，磁盘这种硬件想要读取一个磁盘块的时候，需要把磁头放到磁盘块相应的位置，而访问不同的磁盘块是需要移动磁头的，并且如果两个磁盘块的距离越远，那么移动磁头所需要的时间就越长，比如说我现在需要连续的读这三个黄色的块，那么首先是把磁头放到第一个块的位置之后，移动到第二个块的位置，之再之后再移动到第三个块的位置。所以由于这三个块它们之间在物理上是相邻的，也就是它们相距距离是最短的，因此移动的过程其实磁头的移动距离也是最短的。
而假如我们此时想要读取的是紫色的这三个磁盘块的话，那么首先需要把磁头移动到第一个这个块对应的位置。读完了第一个块之后需要移动磁头到第二个位置。然后读完第二个磁盘块之后，也需要再移动磁盘，然后把它移动到第三个块的位置，因此如果这些块不相邻的话，那么读取一个块和下一块之间所需要的移动磁头的时间就会更长。
因此基于这个分析我们知道如果一个文件采用的是连续分配的方式的话，那么我们在顺序的读取文件的各个块的时候，所需要的读写时间是最短的，读写速度是最快的，因为整个过程所需要的磁头移动距离是最短的，这个知识点咱们还会在之后再进行进一步的探讨。这个地方我们只需要理解连续分配的文件，在顺序读写的时候速度最快，只需要理解这一点就可以了，这是连续分配方式的第二个优点。
接下来我们来看一下连续分配方式有哪些缺点。假设在这个图当中，黄色的部分是一个文件 a 所占用的连续的三个块，然后绿色的部分是空闲的块，橙色的区域表示其他的文件已经占用的磁盘块。如果说此时文件 a 想要拓展，也就是说想要再增加一个磁盘块的话，由于连续分配要求为一个文件分配的是连续的块，而文件 a 后面的相邻的块，此时已经被别的文件所占有了
因此如果要拓展文件 a 的话，那么我们不得不把文件 a 的数据整体的迁移到另外的有连续的 4 个块的区域当中，进行数据迁移的过程其实是需要耗费很大的开销的。
所以我们得出一个结论，由于连续分配方式要求文件在磁盘上占有的必须是一组连续的块，因此对文件的拓展是很不方便的，这是它的一个缺点。
再来看第二个缺点，假设此时在这个图当中橙色的这些区域表示的是非空闲块，而绿色的这些区域表示的是空闲此板块，那么此时会发现这儿总共有 5 个空闲的磁盘块，假如说此时我们要创建一个新文件，这个文件的大小需要占用三个磁盘块，由于这个文件它采用的是连续分配的方式，因此由于此时整个磁盘当中并没有连续的三个空闲块，因此我们没有办法为文件分配足够的存储空间。
相应的假设这个系统当中有很多文件都是大于一个块这么大小的，这些空闲的离散的快就很难被利用起来。所以如果说物理上采用这种连续分配的方式的话，存储空间的利用率会低，会产生难以利用的磁盘碎片。而这些磁盘碎片就有点类似于咱们在之前内存管理当中讲过的那种外部碎片，处理这些碎片的方式，也和处理外部碎片的思想是一样的，可以用紧凑的方式来解决，不过紧凑就意味着需要移动大量的这些磁盘块的内容，这个过程是需要花费很大的时间代价的，因此会产生磁盘碎片这个问题也是连续分配方式一个很明显的缺点。
所以连续分配方式要求每个文件在磁盘上占用一组连续的块，它的优点是支持顺序访问和直接访问，也就是随机访问，并且连续分配的文件在顺序访问时速度是最快的，但是它也有一些缺点，不方便文件的拓展存储空间利用率低，会产生磁盘碎片，这是连续分配方式我们需要掌握的一些知识点。
# 链接分配
接下来我们再来看第二种文件分配方式，链接分配
链接分配采取的是离散分配的这种思想，可以为文件分配离散的磁盘块，然后用指针链接的方式，它们把这些磁盘块都给串联起来，而链接分配方式又可以进一步分为隐式链接和显示链接两种， 我们首先来看隐式链接这种方式，如果采用的是这种方式的话，那么在文件的目录项，也就是文件对应的 FCB 当中需要记录这个文件的起始块号，还有结束块号，另外各个块之间都会用一定的存储空间存储指向下一块的链接指针，当然最后一个块是没有指向下一块的连接指针的，而这些指针对于用户来说是透明的。
采用这种方式的话，怎么实现逻辑块号到物理块号的转变，用户首先给出他要访问的逻辑块号 i ，然后操作系统会根据文件名找到它对应的 fcb 这个目录项，找到这个文件的起始块号，于是操作系统可以先读入这个文件的起始块，而这个块就是逻辑上的 0 号块，因为只有把这个块读入内存之后，才可以知道这个块指向下一块的指针的数据到底是多少，只有这样才可以再掉入下一个块。
于是下一个块调入内存之后，也可以再继续知道再下一个块存放的位置，于是再读入再下一个块，然后以此类推。因此如果说我们想要访问逻辑块号为 i 的逻辑块的话，操作系统首先需要先依次的读入 0 号到 i -1 号逻辑块，才可以找到 i 号块存放的位置。因此访问 i 号逻辑快，总共需要 i +1 次磁盘 lO 操作。
因此我们得到的结论是，如果采用的是链接分配--隐式链接的这种方式的话，那么这种文件它只支持顺序访问，不支持随机访问。也就是说如果我想要访问 i 号逻辑快的话，我只能先顺序的访问 0 ~ i-1 号块才可以。因此这种方式带来的问题就是查找的效率很低，另外呢，每一个块当中也需要耗费一定少量的存储空间来存放指向下一个块的指针内容。
接下来我们考虑下一个问题，采用这种方式是否方便拓展文件。假设此时这个文件需要拓展，也就是需要再给它分配一个新的磁盘块。由于这个文件的这些块可以是离散分配的，因此只需要从磁盘中随便找出一个空闲的块，把它挂到这个文件的链尾就可以了。
比如说此时我们给文件在新分配了一个 8 号块，于是把 8 号块挂到链的链尾，然后操作系统会修改这个文件，fcb 的结束块号这个内容把结束快号设为 8 号，所以可以看到采用这种方式的话，那么文件的拓展是很方便的，并且这种方式不会产生碎片问题，外存的利用率很高。
那么经过刚才的分析，我们知道了隐式链接的链接分配有这样的一些优点和缺点，这就是刚才咱们得到的结论，这就不再赘述。
# 显示链接
接下来我们再来看显示链接的链接分配方式，这种方式会把用于链接文件各个物理块的指针显示的存放在一张表当中，这个表就被称为文件分配表，英文缩写是 FAT， 磁盘当中的各个块的先后顺序都是统一记录在文件分配表当中的，所以一个磁盘它有多少个块在文件分配表当中就相应的会有多少个表项
假设此时有一个新创建的文件，文件名是 AAA，它依次占用了 2,5,0,1,这样的几个物理块，那么在 AA 这个文件的 FCB 也就是目录项当中，需要记录这个文件 AAA 它存放的起始块号起始块号是二号块。
另外在文件分配表当中会显示的记录文件 AAA 它这几个物理块的一个链接关系，比如说二号块是起始块，2 号块的下一块是 5 号块，所以 fat 的表项 2 号块的下一块就应该记录为 5，5 号块的下一块是 0 号块，所以 5 号块的下一块表项记录为 0，0 号块的下一块是 1 号块，所以这个地方记录为一，而一号块是最后一个块。所以一号物理块的下一块这个数据可以把它设置为一个特殊的值，比如说是-1，用来表示这儿就是这个文件的结尾，这样的话就完成了 2501 这样的一个顺序的记录。
同样的假设有一个文件 BBB，它依次存放在 4，23 和 3 这样的几个盘块当中。那么 BBB 这个文件对应的 fcb 当中需要记录它的起始块号是 4 号块，然后 4 号块的下一个块是 23，所以表项应该记录为 23，23 号块的下一块是 3 号块，所以这个地方记录为 3，,3 号块是文件的末尾，所以这个地方记录为-1，这样的话也完成了 BBB 文件 4，23，3 这样的一个顺序的记录，所以这种方式把每个文件的各个盘块的链接信息显示的统一的放在了这样的一个文件分配表 FAT 当中，所以这是它为什么称作显示链接的一个原因。
从这个地方我们也可以看到，一个磁盘仅需要设置一张 FAT 就够了，每个文件的这些盘块的先后顺序都是统一的存放在这张表当中的，并且在我们开机的时候，fat 文件分配表它会被读入内存，并且会一直常驻内存，而 fat 的这些一个一个的表项在物理上是需要连续存储的，并且每 1 个表项的长度相同，比如说下一块这个数据我们可以用 4 个字节来表示，所以物理块号这个字段可以是隐含的。
接下来我们再来看一下，采用这种方式的话，怎么实现文件逻辑块号到物理块号的一个转变。一个用户给出他想要访问的逻辑块号 i ，然后操作系统首先需要找到这个文件对应的目录项，也就是它的 fcb，找到这个文件的起始块号，起始物理块号，比如说一个用户想要访问的是文件 AAA 的二号逻辑块，那么操作系统首先找到 AAA 这个文件的 0 号逻辑块存放的物理块号是 2，接下来系统会查询内存当中的文件分配表，找到表项就可以知道，0 号逻辑块的下一个块，也就是 1 号逻辑块应该是存放在 5 号物理块当中的，接下来会继续查询表项，发现一号逻辑块的下一块，也就是 2 号逻辑块，它是存放在 0 号物理块当中的，于是查询到这个位置就可以知道用户想要访问的 AAA 这个文件的二号逻辑块存放的物理块号了。由于 fat 它是常驻内存的，因此查询 FAT 的过程并不需要读磁盘操作，
所以通过分析我们得出这样的结论，采用显示链接的链接分配方式的话，那么这种文件它既支持顺序访问，也支持随机访问。我们想要访问 i 号逻辑块，并不需要顺序的依次访问，0~ i-1 号逻辑块，我们可以直接通过 fat 表查到 i 号逻辑块存放的地址，并且由于这个查询的过程并不需要访问磁盘，所以相比于隐式链接的那种方式来说，采用显示链接访问速度会块很多，显然这种方式也不会产生外部碎片，并且可以很方便地实现对文件的拓展。
因此通过这一系列分析，我们知道了显示链接的优点和缺点，我们需要特别注意的是一个磁盘只会对应一张文件分配表，并且在开机的时候文件分配表就会被读入内存并且常驻内存，因此查询文件分配表的过程并不需要读磁盘操作，所以这也造就了显示链接方式支持随机访问，并且在这个地址转换的过程当中访问效率更高的一个特点。不过它的缺点就是文件分配表它需要占用一定的存储空间。
大家需要注意的是，如果题目当中没有明确的告诉我们到底是显示链接还是隐式链接，那么如果它只是简单的提到链接分配的文件，我们默认它指的是隐式链接的链接分配方式。
# 小结
好的，那么这就是小节的全部内容，我们介绍了连续分配和链接分配两种方式，链接分配都可以进一步分为隐式链接和显示链接
所有的知识点的总结，我们会放到下一个小节，介绍完索引分配之后再统一的进行。
