Re：从零开始的文件分配方式（考研向）

前言

我们之前学习了cache的地址映射和分页存储管理方式，总的来说：

• 地址映射是cache和主存之间的映射
• 分页存储管理方式讲的是 进程的页与页框之间的映射 以及我们如何借助进程的页表将逻辑地址转换为物理地址（基本地址变换）

其中具体的细节可以参考我的这篇 文章链接

这些说白了 最后都是在内存里面找我们想要的地址 而对于我们文件的物理结构讲的是内存与磁盘（外存）之间的映射，类似的 他们之间的数据交换也是以块为单位，这样的好处就是能够保证块内地址在移动之后依旧保持不变，
具体如下图：

思维导图

连续分配

两个优点

采用顺序分配的第一个优点就是支持随机访问 为啥我们看下面这张图是不是就非常清楚了 每个文件我们是不是只需要知道它在磁盘（外存）当中的起始块号和长度（用于判断是否越界）因为是连续存放的，而每个块大小又是一样的，这样不就能够算出来这个文件的任何一个数据块在磁盘的位置了吗 也就是随机访问

在我们前面学习机组的时候 我们在了解了磁盘的读写过程 （图片来源: 里昂学长）

简单回顾之后我再结合我们本章要说的顺序分配，说白了就是连着放 这样是不是就减少了我们磁头地移动距离 这就是我们顺序分配的第二个优点

两个缺点

第一个缺点：
简单说就是拓展的成本太高 我们举一个极端的情况就是现在我们有9999个连续的存放的块 假设里面都空间全部占满 我们现在想加入一个块达到拓展的目的 此时磁盘当中正好有连续的10000个连续的磁盘块，此时我们虽然很想在这9999后面再开辟一个新的块来达到目的，奈何连续存放是达不到的 我们只能讲这9999个块迁移到新的连续空间+我们需要拓展的空间正好占满10000个连续的块

• 第二个缺点：如果我们只使用连续的大片空间 想象一下是不是会出现很多很多散落在内存当中的小磁盘块没有办法被很好的利用起来，回顾我们之前的分块存储思想 是不是就会出现很多的内部碎片 之后我们才有了分页（段）存储——>多级页表——>然后又引入了虚拟内存，介绍了请求分页存储管理方式

• 采用我们之前所介绍的紧凑技术虽然可以解决这种问题 但是我们说过这种技术是需要耗费很大的时间代价的
  
  总结：
  

链接分配

引入

其实就是将那些散落在内存当中的磁盘块通过某种方式链接起来 类比于我们在学习数组（顺序存储）的时候，如果内存当中没有足够的连续空间的时候我们引入了链表来解决这个问题 现在也是如此 具体地链接方式分为隐式链接和显式链接两种

隐式链接

目录只存放起始块号和结束块号 我们在存储的时候 会开辟额外的一个指针域 每次都将下一个盘块的位置信息存储在里面，这样就能够顺藤摸瓜找到每一个磁盘块

解决连续分配提到的缺点

显式链接

这个其实在学的时候我就觉得非常表数据结构当中 树那一章所学的双亲孩子链表 对应文章链接
说白了就是对于每一个磁盘块，我们将他的下一块的信息整理成一章表格
（我的理解是只不过是将链式关系通过一张表来呈现了）
这样我们就可以通过查表的方式找到该文件所包含的所有磁盘块

相比于隐式链接 我们通过表格的形式达到了随机访问的功能 比如当我们想要去查找第i块我们之间从表中去找哪个磁盘块的下一块是它是不是就行了 并不用想向隐式链接一样 一个一个地顺序访问

• 链接分配小结：
  

索引分配

其实就是将我们上面的链式关系通过一张索引表来实现 里面按逻辑块号顺序存储了它与物理块号的映射（类似页表）

结语

PS：明天更完 劳逸结合 加纳（懒得敲了 QWQ~）