前面主要是学习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 文件系统里，虽然解决大文件的存储，但是对于大文件的访问，需要大量的查询，效率比较低。

文件方式的存储做个总结

方式	访问磁盘次数	优点	缺点
顺序存储	需访问磁盘1次	顺序存取速度快，当文件定长时可以根据文件起始地址及记录长度进行随机访问	要求连续的存储空间，会产生外部碎片，不利于文件的动态扩展
链表存储	需要访问磁盘n次	无外部碎片，提高了外存空间利用率，动态增加较方便	只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗内存或磁盘空间
索引存储	m级需要访问m+1次	可以随机访问，易于文件的增删	索引表增加存储空间的开销，索引表查找策略对文件系统效率影响较大

2 参考文档

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

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

现代操作系统