文件系统(一)--文件系统基础知识

前面主要是学习linux进程管理的调度，其细节越来越多，结合目前移动设备，其调度算法越来越复杂，涉及到芯片涉及，电源管理，多核负载等，这块内容暂时告一段落，本章正式进入到文件系统的学习。
到目前为止，我们看到了两项关键操作系统的发展：

• 进程，是虚拟化CPU
• 地址空间，是虚拟化的内存
  在这两种抽象的共同作用下，程序运行时就好像它在自己的私有的独立世界中一样，好像它有自己的处理器(或多处理器)，好像它有自己的内存空间，这种假象使得对系统的编程变得越来越容易，在这一部分中，我们还需要加一个持久存储。

现在的磁盘是具有大容量、低成本以及持久化的特点，即使发生断电、磁盘上的数据也不会丢失。但是对于一般用户而言，磁盘的使用是一个非常痛苦的，因为他们不清楚如何驱动一个磁盘，以及计算数据在磁盘上存放的位置。对于操作系统是一个魔术师，它提供 用户各种抽象 。前面章节我们学习了进程的抽象是CPU，虚拟内存的抽象是内存，对于磁盘来说，操作系统提供给用户就是在磁盘外面包裹一层容易使用的抽象，用户直接与这层抽象打交道，而无需了解磁盘的技术细节。在操作系统中，这层为磁盘提供的 抽象就是文件系统 。

本章主要是学习文件系统的基本原理，主要涉及以下的内容：

• 文件系统的存储方式
• 文件系统的分配方式

1. 文件系统的分类

1.1 文件结构

文件的构造有以下几种方式

• 流式文件： 构成文件的基本单位是字符，文件是由逻辑意义、无结构的一串字符的字节序列，对于操作系统不关心序列的内容是什么，操作系统能看到的都是字节(Byte)，其文件的内容只能在用户程序中进行解释。

  把文件看成字节序列提供了最大的灵活性，用户程序可以向文件中写任何内容，并且可以通过任何方便的形式命令，操作系统不提供任何帮助，也不会构成障碍。所有的unix版本和windows都使用这种文件模型

• 记录式文件： 文件是具有固定长度的记录的序列，每个记录都有其内部结构，可以按照记录进行读、写、查找等等操作。

• 树式文件： 这种组织结构中，文件由一颗记录树构成，记录树的长度不一定相同，每个记录树都在记录中的固定位置上包含一个key字段，这颗树按照key进行排序，从而可以对特定的key进行快速查找。如图，用户可以读出制定Hen记录，而不用关系记录在文件中的确切位置，用户也可以在文件中添加新记录，但是用户不能决定添加在何处位置，该位置由操作系统决定。

1.2 文件的存储

对于文件是存储介质上的存放方式，对于物理结构，主要解决两个问题：

• 假设一个文件被划分成N块，这N块在磁盘上是怎么存放的？
• 其地址(块号)是如何记录的？

1.2.1 连续结构

对于不同的文件系统采用不同的方式，首先我们从文件存储的结构来看看连续存储的结构，把每个文件作为一连串连续的数据块存储在磁盘上。因此，在具有1KB块的数据上，将为50KB分配50个连续的磁盘块

从磁盘开始处(块0)处开始写入占用4块长度的File A，然后是一个占用6块长度的File C，紧跟着在A的末尾开始写，每个文件都会在新的文件块中写，对于这种方式有什么缺点呢？是不是跟我们的内存管理很像，例如D/E被删去了，此文件所占用的块也随之释放，就会在磁盘中留下一些空闲块，这个是不是跟内存管理很像，就会形成很多的磁盘碎片(外碎片)。

对于这种连续存储结构的优缺点：

• 优点

  • 连续文件存储实现比较简单，支持顺序存取和随机存取，只需要记住两个数字就可以了，一个是第一块的文件地址和文件块的数量，给定第一个块的编号，就可以通过简单的算法找到任何其他块的编号
  • 读取性能比较强，可以通过一次操作从文件中读取整个文件，只需要一次寻找第一个块，对于磁盘的访问，后面就不需要寻道时间和旋转延迟，所 需要磁盘寻道次数和寻道时间最少

所以，连续存储结构分配方式具有实现简单，高性能的特点

• 缺点

  • 文件不能动态增加，预留空间的方式带来浪费，重新分配，就需要重新移动
  • 不利于文件插入删去
  • 也会跟内存管理的方式一样，带来外部碎片问题，刚开始的时候，碎片问题不是一个大问题，因为每个新文件都会在之前文件的结尾处进行写入。但是，当磁盘最终被填满后，要么压缩磁盘，要么重新使用空闲块的空间。压缩磁盘的开销太大，因此不可行；空闲块需要维护一个空闲列表，但是页会存在一个问题，为空闲块匹配合适大小的文件，需要知道该文件的最终大小。

想象以下这种的设计结构，例如用户想启动一个word进程，创建文档，应用程序首先会询问最终创建的文档有多大，否则应用程序就不会继续运行。如果空闲块的大小要比文件的大小小，程序就会终止。因为没有连续的空间来存储该文件，但是实际上磁盘上有很多零散的碎片。

在许多年前，连续分配由于其简单和高性能被实际使用在磁盘文件系统中，对于生活中，CD-ROM就广泛的使用了连续分配的方式，这种制度光碟只能写入一次，信息将永久的保存，使用时通过光碟的移动读出信息。后来由于用户不希望创建文件时，就指定文件的大小，于是就慢慢放弃放弃了这种想法。

1.2.2 链接结构

一个文件的信息存放在若干不连续的物理块中，各个块之间通过指针来链接，前一个物理块指向下一个物理块

下面此磁盘块的链接方式存储文件，每个块的第一个字作为指向下一个块的指针，块的其他部分存储数据，如下是磁盘的整个链表分配方案

与连续分配方案不同，这一方法可以充分利用每个磁盘块，除了最后一个磁盘块外，不会因为磁盘碎片浪费存储空间。同样，在目录项中，只能存储第一个文件块，那么其他文件块也能够被找到。

链表的方式存放是 离散的，不用连续的 ，于是就可以 消除磁盘碎片 ，可大大提高磁盘空间的利用率，同时 文件的长度可以动态扩展 。

对于这种连续链接结构的优缺点：

• 优点：

  • 提高了磁盘空间的利用率，不存在外部碎片问题
  • 有利于文件插入和删去
  • 有利于文件动态扩充

• 缺点：

  • 存取速度慢，不适用于随机存取，尽管顺序读取非常方便，但是随机访问却很困难，这也是数组和链表的一大区别
  • 可靠性问题，如指针出错
  • 更多的寻道次数和寻道时间
  • 链接指针占用一定的空间，许多程序都是以长度为2的整数次幂来读写磁盘，由于每个块的前几个字节被指针所使用的，所以要读出一个完成的块大小信息，就需要当前块的信息和下一块的信息拼凑而成，因此就引发了查找和拼接的开销

  1.2.3 使用内存表进行链表分配

  由于连续分配和链表分配都有其缺点，所以提出了使用内存表来解决该问题，取出每个磁盘块的指针，把它们放在内存中的一个表中，就可以解决上述链表中的两个不足之处，

  

  这个图中有两个文件，其内容为

  • 文件A依次使用磁盘块的地址为4、7、2、10、12，文件A从地址4开始，顺着链表就能找到文件A的全部磁盘块
  • 文件B依次使用磁盘块的地址为6、3、11、14，文件B从第6块开始，顺着链表就能找到文件B的全部磁盘块

  

  同时会发现，这两个链表都以不属于有效磁盘编号的特殊标记(-1)结束，内存中这种表格称为文件分配表。但是使用这种方式，就是必须要把整个链表放到内存中，对于1TB的磁盘和1KB的大小块，那么这张表就需要有10亿项，每一项对应于这10亿个磁盘块中的一块，每项至少3个字节，为了提高查找速度，有时需要4个字节，那么这张表就需要3GB或2.4GB的内存。对于FAT的管理方式采用这种方式，但是不能较好的扩展在大型磁盘中，由于其比较实用，并仍被各个windows版本所支持。

  1.2.4 索引结构

  索引分配允许文件离散地分配在各个磁盘块中，系统会为 每一个文件建立一个索引表 ，索引表中记录了文件中每个逻辑块对应的物理块。索引表存放的磁盘块叫做 索引块 ，文件数据存放的磁盘块叫做 数据块 。

  索引的实现是为每个文件创建一个「 索引数据块 」，里面存放的是 指向文件数据块的指针列表 ，说白了就像书的目录一样，要找哪个章节的内容，看目录查就可以。

我们首先通过文件名，找到索引表对应的块号为24，发现24的索引表的对应的㘞块号是1->8->3->14->28。

首先用户给出需要访问的逻辑块号i，操作系统需要找出所需要访问的文件的目录项，在FCB中可以找到索引块对应的物理块号，通过该物理块号，可以找到索引表，将索引表读入内存，就能在索引表找到逻辑块i对应的物理块。所以，支持顺序访问和随机访问，文件拓展实现容易（只需要给文件分配一个空闲块，并增加一个索引项即可），但是索引表需要占用一定空间。

优点：

保持了链接结构的优点，又解决了其缺点

• 既能满足顺序存取，又能随机存取
• 满足了文件动态增长，插入，删去的要求
• 能充分利用磁盘空间

缺点：

• 较多的寻道次数和寻道时间
• 索引表本身带来了系统开销，如内存、磁盘空间、存取时间

那我们现在需要考虑另外一个问题，假设磁盘块的大小为512byte，一个索引项为4byte，那么一个磁盘块只能记录128个索引项，但是如果一个文件大小超过了128个磁盘块，那么索引项使用一个磁盘块就无法存放了，此时该如何解决呢？

我们比较容易想到的就是，既然一个磁盘块存放不下，那么就使用两块，对的，这种想法是没错的，但是我们要考虑的是在使用多个磁盘块的时候，如果将这多个磁盘块关联起来，同时还能不降低查询效率？这里就产生如下的方案：

• 链接索引方式： 一个盘块存储一个索引表，多个索引表链接在一起
• 多级索引方式： 将文件的索引表地址放在另一个索引表中
• 综合模式： 直接索引方式与间接索引方式结合

链接索引方式

它的实现方式是 在索引数据块留出一个存放下一个索引数据块的指针 ，于是当一个索引数据块的索引信息用完了，就可以通过指针的方式，找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题，万一某个指针损坏了，后面的数据也就会无法读取了。

多级索引方式

还有另外一种组合方式是索引 + 索引的方式，这种组合称为「 多级索引块 」，实现方式是 通过一个索引块来存放多个索引数据块 ，一层套一层索引，像极了俄罗斯套娃是吧。

linux采用三级索引结构

• 每个文件的索引表有15个索引项，每项2个字节
• 前12项直接存放文件的物理块号(直接寻址)
• 如果文件大于12块，则利用第13项指向一个物理块，在该物理块中存放文件物理块的块号(一级索引)，假设扇区大小为512字节，物理块等于扇区块大小，一级索引表可以存放256个物理块
• 对于更大的文件，还可以利用第14和第15项，作为二级和三级索引表

所以，这种方式能很灵活地支持小文件和大文件的存放： - 对于小文件使用直接查找的方式可减少索引数据块的开销； -对于大文件则以多级索引的方式来支持，所以大文件在访问数据块时需要大量查询；

这个方案就用在了 Linux Ext 2/3 文件系统里，虽然解决大文件的存储，但是对于大文件的访问，需要大量的查询，效率比较低。

文件方式的存储做个总结

2 参考文档

操作系统——文件系统概述、文件逻辑地址、目录、物理地址

一口气搞懂「文件系统」，就靠这 25 张图了

现代操作系统