编程知识 cdmana.com

操作系统复习笔记——第十一章 文件系统实现

  • 11.4 分配方法
    • 11.4.1 连续分配
      • 连续分配方法要求每个文件在磁盘上战友一组连续的块。磁盘地址为磁盘定义了一个线性序列。
      • 文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。如果文件有n块长并从位置b开始,那么该文件将占有块b,b+1,b+2…,b+n-1。一个文件的目录条目包括开始块的地址和该文件所分配区域的长度,
      • 对一个连续分配文件的访问很容易。要顺序访问,文件系统会记住上次访问过块的磁盘地址,如需要可读入下一块。要直接访问一个从块b开始的文件的块i,可以直接访问块b+i。因此连续分配支持顺序访问和直接访问。
      • 问题: 外部碎片
      • 如何确定一个文件需要多少空间。
      • 解决方法:终止用户程序 并加上合适的错误消息。用户必须分配更多空间并在此运行程序。这些重复运行可能代价很好。另一种可能是找一个更大的孔 ,复制文件内容到新空间,释放以前的空间。
      • 修正的连续分配方案:开始分配一块连续空间,当空间不够时,另一块被称为扩展的连续空间会添加到原来的分配中,这样,文件块的位置就称为开始地址、块数、加上指向下一扩展的指针。
    • 11.4.2 链接分配
      • 链接分配 解决了连续分配的所有问题。采用链接分配,每个文件是磁盘块的链表;磁盘块分布在磁盘的任何地方。目录包括文件第一块的指针和最后一块的指针。
      • 连接分配创建文件,可以简单地在目录中增加一个新条目,对于链接分配,每个目录条目都有一个指向文件首块的指针。创建文件时,无需说明文件大小,只要有空闲块,文件就可以增大。因此,无需合并磁盘空间。
      • 缺点:只能有效地用于文件的顺序访问。不能有效地支持文件的直接访问。同时指针需要空间。
      • 解决方法: 将多个快组成簇(cluster)按簇而不是块分配
      • 一个采用链接分配方法的变种是文件分配表 FAT的使用
    • 11.4.3 索引分配
      • 链接分配解决了连续分配的外部碎片和大小声明问题。但是,如果不用FAT,那么链接分配就不能有效支持直接访问,这是因为块指针与块一起分布在整个磁盘,且必须按顺序读取。索引分配(indexed allocation)通过把所有指针放在一起,即通过索引块解决了这个问题。
      • 索引分配支持直接访问,且没有外部碎片问题,这是因为磁盘上的任一块都可满足更多空间的要求。索引分配会浪费空间。索引块指针的开销通常要比链接分配指针的开销大。设想一下在一般情况下,每个文件只有一块或两块长。采用链接分配,每块只浪费一个指针。采用索引分配,尽管只有一个或两个指针为非空,也必须分配一个完整的索引块。
      • 索引分配存在问题的解决方案:
      • 链接方案 多个索引块 链接起来
      • 多层索引
      • 组合方案
    • 11.4.4 性能
      • 性能:不考消耗的情况下,只考虑收益/效率
      • 效率 :单位资源收获的收益
  • 11.5 空闲空间管理
    • 为了记录空闲磁盘空间,系统需要维护一个空闲空间链表。(free-space list)空闲空间链表记录了所有空闲磁盘空间,即未分配给文件或目录的空间。当创建文件时,搜索空闲空间链表以得到所需要的空间,并分配给新文件。这些空间会从空闲空间链表中删除。当删除文件时,其磁盘空间会增加到空闲空间表上。空闲空间链表虽然称为链表,但不一定表现为链表,
    • 11.5.1 位向量
      • 通常,空闲空间表实现为位图(bit map)或位向量(bit vector)。每块用一位表示。如果一块为空闲,那么其位为1;如果一块已分配,那么其位为0。
      • 这种方法的主要优点是查找磁盘上第一个空闲块和n个连续空闲块时相对简单和高效。
    • 11.5.2 链表
      • 空闲空间管理的另一种方法是将所有空闲空间磁盘块用链表连接起来,并将指向第一空闲块的指针保存在磁盘的特殊位置,同时也缓存在内存中。
      • 不过,这种方案的效率不高;要遍历整个表时,需要读入每一块,这需要大量的I/O时间。好在遍历整个表并不是一个经常操作。通常,操作系统只不过简单地需要一个空闲块以分配给一个文件,所以分配空闲表的第一块就可以了。FAT方法将空闲块的计算结合到分配数据结构中,不再需要另外的方法。
    • 11.5.3 组
      • 对空闲链表的一个改进是将n个空闲块的地址存在第一个空闲块中。这些块中的n-1个确实为空,而最后一块包含另外n个空闲块的地址,如此继续。大量空闲块的地址可以很快地找到,这一点有别于标准链表方法。
    • 11.5.4 计数
      • 另外一种方法是利用这样一个事实:通常,有多个连续块需要同时分配或释放,尤其是在使用连续分配和采用簇时更是如此。因此,不是记录n个空闲块的地址,而是可以记录第一块的地址和紧跟第一块的连续的空闲块的数量n。这样,空闲空间表的每个条目包括磁盘地址和数量。虽然每个条目会比原来需要更多空间,但是表的总长度会更短,这是因为连续块的数量常常大于1。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

版权声明
本文为[种花家的奋斗兔]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1747165

Scroll to Top