tarius.wu

首先，文件系统应该被看作一种存储和定位数据的机制。为了提供对磁盘高效且便捷的访问，操作系统通过文件系统来实现存储、定位、和提取数据。文件系统有两个不同的设计问题。

第一个问题是如何定义文件系统对用户的接口。具体方面涉及到定义文件及其属性，文件所允许的操作，组织文件的目录结构。这一层就是普通用户对文件系统的第一映像，如文件的类型，读写权限，目录是树型结构还是其它结构。这一层通常被称为逻辑文件系统。

第二个问题是创建怎样的数据结构和算法来将逻辑文件系统映射到物理外存设备上。这一层可以称之为底层文件系统。

1 逻辑文件系统

逻辑文件系统用来当作与用户的接口，用户不需要知道文件具体如何访问，只需知道文件名、文件在哪一个目录中，用户所具有的访问权限等。逻辑文件系统通过文件控制块（file control block，FCB）来维护文件结构，它包含文件的信息，如拥有者，权限和文件的位置。因此，FCB是逻辑文件系统和底层文件系统的联系纽带。在UNIX系统中，FCB被称做索引节点（i 节点）；而在NTFS中将FCB的信息存在主控文件表中，主控文件表采用关系数据库结构，每个文件占一行。

除了FCB，在格式化后的磁盘中还应存在以下数据结构：

•   引导控制块（boot control block）：存储从该分区引导操作系统所需要的信息。如内核镜像的位置，引导参数等。它通常为分区的第一块。如果该分区没有操作系统，那么这块的内容为空。UNIX文件系统称之为引导块，NTFS称之为分区引导扇区。
•     分区控制块（partition control block）：包含分区的详细信息，如分区的块数，块的大小，空闲块的数量和指针。UNIX系统称之为超级块(super block)，NTFS称之为主控文件表（master file table）。
•   目录结构：用来组织文件。

分区

硬盘等非易失性存储设备在使用前必须先被格式化，格式化的含义就是规定这个硬盘中的某个分区的文件系统是什么格式，是ext2，ext3，还是windows的fat32，ntfs等，这种格式化信息写在硬盘分区的固定位置上，如磁盘标签或卷头上。这样，当操作系统或其他能读写硬盘的实体一旦访问到某一硬盘分区，就会先读该分区的文件系统格式，看看自己是不是支持这种文件系统格式，如果不支持，就会读不到数据，当然也无法往该分区写数据。典型的如DOS就不认识NTFS格式。分区是硬件级的划分，因此它们是独立于任何操作系统的。

文件和目录

在UNIX中存在的任何东西都是文件，发生的任何事情都是进程。目录是文件类型的一种，目录中放置其所有组成文件的文件名和索引号（i节点），包括子目录在内。也就是说，目录是文件的分组集合。

目录实际上是一张表，每一项记录着所包含文件的文件名和一个指向该文件的指针。要访问一个文件，就必须先访问文件所在的目录，而这个目录可能是它上级目录的子目录。因此，访问文件的过程就是根据文件系统中最上层的目录来层层索引，先找到文件的起始地址，以找到文件的i节点，再从i节点上得到整个文件的物理存储信息和属性。

目录是一个表，查找表里的项目就带来了查找效率问题。一般目录列表有线性列表和哈希列表。其各自的效率问题这里不作讨论。

2 底层文件系统

在底层文件系统里我们要关心磁盘空间的划分方式以及文件的存储方式。这里列出了三种最基本的方式，现实中的实现都是以它们为基础的变形。磁盘的划分方式也即所谓的分区格式。

磁盘空间连续分配

连续分配要求每个文件在磁盘上占有一组连续的块。与内存空间的分配一样，连续分配的好处就是访问数据块的速度加快，比如在访问b块后访问b+1块时通常不需要移动磁头。只有从当前磁道的最后一个扇区到下个磁道的第一个扇区需要，需要移动一个磁道。连续分配的缺点和内存连续分配一样，就是带来了磁盘碎片。

链接分配

硬盘的访问最小单元是块，一般是512B。采用链接分配，每个文件是磁盘块的链表；磁盘块分布在磁盘的任何地方。

文件目录包括文件第一块的指针和最后一块的指针。

例如有一个5块的文件从第9块开始，然后是16，1，10，25；每一块都有一个指向下一块的指针，-1表示最后一块。

链接分配的缺点有两个：一是它只能用于文件的顺序访问；要访问一个文件的第i块，就要从该文件的起始块开始。二是指针需要空间。一个块有512B，指针要占用4B。

一种优化的办法是将硬盘的最小访问单元定义成几个块的组合，叫做簇。比如一个簇4块。按簇而不是按块来分配。这种方法提高了访问速度和指针的占用比，但增加了磁盘碎片。

MS-DOS和OS/2使用的FAT(文件分配表)格式就是链接分配的一种变种。

索引分配

索引分配可以解决链接分配不能有效地解决的随机访问问题，它把文件的所有块指针放在一起：索引块。

目录中文件条目包含索引块地址，索引块中的第i个条目指向文件的第i块。要读入第i块，只要读入索引块的第i项。