文件系统实现

1.1 文件系统要实现什么

磁盘构成部分：分区表、空闲块映射表、目录项和数据

磁盘经过低级格式化分成了大小相同的块(block)，也称为分区(sector)，每个块的大小为512Bytes，现在很多磁盘扇区的实际大小为4KBytes，但是逻辑大小仍然为512Bytes,为了兼容老的系统 再经过分区、构建文件系统、分区挂载就可以使用了。在磁盘中，最前面的分区存放的是分区表信息，接着是空闲块信息，用于给文件分配扇区，然后是文件系统的目录项，记录了每个文件的信息。

文件系统主要实现以下几点：

管理文件目录
空间分配方法
空闲空间管理

现在用在大多数操作系统都支持多种文件系统，比如，大多数的CD-ROM采用标准的ISO 9660格式，为了支持这种可移动媒介的文件系统，每个操作系统都有一个或多个基于磁盘的文件系统

Unix使用的Unix 文件系统(UFS)是基于Berkeley 文件系统(FFS)
Windows支持FAT、FAT32以及NTFS等等，现在主要使用的是NTFS
Linux支持40多种文件系统，标准的Linux文件系统是可扩展的文件系统，用的比较多的是ext3和ext4，现在主要使用ext4
MacOS之前使用的是HFS文件系统系统，现在Apple设备都换成了AFS文件系统

1.2 文件目录

在文件系统中，文件目录用于组织文件，其中每个条目称为文件控制块(File Control Block)，通过文件控制块来维护文件结构，FCB包含有关文件的信息，包括所有者、权限、文件内容的位置等，结构如下如所示：

其中文件数据指针，可以理解为指示文件内容存放在哪些扇区上，文件指针记录的是扇区号

其中文件目录实现的关键是FCB与文件内容的关联方法

下面以Unix的文件系统介绍以下如何实现FCB与文件内容的关联

INODES

在Unix的UFS中，它的FCB被称为索引节点inode，每个inode都有一个唯一的编号，包含的内容有：

文件类型、文件模式(ACL)、文件硬链接数、文件拥有者的UserID、GroupID、文件大小、一个存放扇区地址的数组以及时间信息

我们在《Linux文件系统》中简单介绍过INode，通过对比inode和上面FCB的信息后发现，少了一个关键的文件名，其实在UFS中，它的目录项存储是文件名和Inode的编号，如下图所示：

这样可以使目录项足够简简洁，同时由于文件名的长度固定的，Inode的编号长度也是固定的；查找文件的时，根据文件名找到对应的INode编号，然后再根据编号找到对应的文件信息

UFS中，相比开头介绍的磁盘的结构，又多了一个Inode区

注：在Inode条目中，只能记录15个磁盘扇区的地址，如果文件太大怎么办呢？这个问题放到后面解决

1.3 空间分配方法

对于如何给文件分配磁盘空间，常用方法有三种：连续分配、链接分配和索引分配

1.3.1 连续分配

连续分配结构如下：

每个文件在磁盘上占用连续的物理块，在文件目录项中，需要记录文件的起始扇区和所占扇区数，这种方式的优点和缺点都很明显

优点：

实现比较简单
根据扇区的逻辑地址计算物理地址很方便，文件tr占用三个扇区，逻辑地址分别为0，1，2，根据起始扇区的物理地址，可以很快计算出其他扇区的物理地址

缺点：

文件之间产生的较小的空闲碎片空间，可能无法使用
文件增加或删除比较难，比如上面的mail文件，如果要增加3个扇区大小的文件内容，就会导致没有足够大的连续空间使用，文件起始扇区可能需要往前移动，如果前面也没有足够大的空间，就需要用一块新的连续空间来存储mail文件

1.3.2 链接分配

链接分配的结构如下:

文件所占用的物理块分散在磁盘的不同位置，通过指针将它们链接起来，目录项里面存放了起始扇区和结束扇区，中间的扇区通过指针链接

优点：不必连续，没有碎片产生

缺点：

空间浪费了一部分，每个扇区都需要预留一部分空间存放下一个扇区的位置
断链的风险，如果中间某个扇区的丢失了指向下一个扇区的指针，将导致后面扇区的数据都无法访问
每次访问数据都必须从头开始顺序访问

1.3.3 索引分配

索引分配结构如下：

将文件占用的所有物理块号按照逻辑顺序(0,1,2……)保存在一张索引表中，存有索引表的物理块称为索引块(index block)，而在目录项中，只需要记录该文件对应的索引块即可

优点：随机访问，没有碎片

缺点：索引块也要占用磁盘空间

如果一个索引块不够存储文件的索引表，就还需要更多的索引块来存储，那么在文件的目录项中，可能就不能只存放一个索引块的地址了，这个问题如何解决呢？

在前面UFS文件系统的INode中，记录了每个Inode的表项，可以记录15个索引块的地址，如果文件很大，15个索引块仍然不够使用时，又该如何解决呢？

UFS使用多级索引块来解决这个问题，结构如下：

每个文件都有一个索引块，UFS的每个索引块有15个物理块地址

0~11号物理块地址属于直接物理块，这些物理块(扇区)直接存放文件的数据
12号物理块属于一级间接物理块，这个物理块不再是直接存放文件数据，而是存放索引块的地址信息，这个地址对应的物理块再用来存放数据
13号物理块属于二级间接物理块，这个物理块也是存放的索引块的地址，而对应的这些索引块存放的仍然是索引块地址，最后的索引块保存的地址才是文件数据对应的索引块地址
14号物理块属于三级间接物理块，结构跟上面一样

假设每个物理块的大小为512字节，每个索引块的地址用4Btye表示，则每个物理块可以存放128个物理块的地址，计算每级索引块可以存放多少物理块数据

direct blocks：12

single indirect：128

double indirect：128^2

triple indeirect：128^3

这个UFS的多级索引在ext2老的版本中使用,新的ext4文件系统已经不是这种方式了

1.4 空闲空间管理

文件系统为文件分配空间时，首先要知道磁盘的哪些扇区是可用的，哪些是不可用的，就像文章开头的磁盘结构图一样，需要存储空闲块的信息，

1.4.1 BIT MAP(位图)

空闲空间列表用位图或者位向量来表示，每一个块用一个bit来表示，如果物理块是空闲的，就用1表示，如果物理块已经被分配，就用0表示，位图结构如下图所示：

00111100111111000110000000011100000……

第1、2号物理块表示已经被占用，第3至6号物理块表示空闲

1.4.2 LINKED LIST

将所有的空闲块使用指针链接起来，然后使用一个头指针指向第一个空闲的物理块，当为文件分配空间时，头指针向后移动即可，当回收物理块时，把空闲的物理块再链接到整个空闲链表的尾部即可

1.5 文件系统结构

1.5.1 层次化的文件系统

文件系统实现的就是上图红色方框内的内容，当应用程序发起一个读写A文件(file name)X位置(逻辑位置)数据的请求，系统从目录中找到这个文件并读出相应的FCB(由上图中的逻辑文件系统实现)，按照既有的分配方案计算X位置所在的物理块号(由文件组织模块完成)，分配方案对应于前文的空间分配方法，无论用那种方法，都可以计算出逻辑位置对应的实际物理块号，编制一个对物理块号的读写请求(由基础文件系统完成)，然后发给磁盘控制器