文件系统的实现

文件系统的实现讨论的是文件和目录是如何来实现的，磁盘空间是如何来管理的，如何才能使整个文件系统高效、可靠地运转。
    1，数据块
    如前所述，文件的逻辑结构一般是字节流，即无结构。用户程序可以在这种字节流的基础上，构造自己所需的各种数据结构。文件是存放在磁盘等存储设备当中的，而这些设备的访问单元并不是字节。例如，在磁盘中，是以扇区为单元来进行读写操作的。因此，对于文件系统而言，必须将用户提交的这种字节流（一个连续的逻辑地址空间）映射为磁盘所需要的扇区。为了实现设备的独立性，通常的做法是把磁盘空间划分为一个个大小相等的块（BLOCK），成为物理块，每个物理块包含若干个连续的扇区，同时把文件的字节流也分为大小相同的逻辑块，然后在文件系统的内部，以块为单位来进行操作，把每一个逻辑块保存在一个物理块中。

2．文件的实现

文件的实现需要解决两个方面的问题：一是如何来描述一个文件，用什么样的数据结构来记录文件的各种管理信息；二是如何来存储文件，如何把文件的各个连续的逻辑块存放到磁盘的空闲物理块当中，并记录逻辑块与物理块之间的映射关系。

（1）文件控制块

文件的描述方法就是文件控制块（File Control Block, FCB），它是操作系统为了管理文件而设置的一种数据结构，里面存放了与一个文件有关的所有管理信息。FCB是文件存在的标志。

对于不同的操作系统，它们的文件控制块所包含的内容是各不相同的。一般来说，主要包含两类信息。

l         文件的属性信息：包括文件的类型和长度、文件的所有者、文件的访问权限、文件的创建时间、最后访问时间已经最后修改时间等。

l         文件的存储信息：文件在磁盘上的存放位置，它被存放在那一些物理块当中。

（2）文件的物理结构

文件的物理结构研究的是如何把一个文件存放在磁盘等物理介质上。具体来说，就是以块为单位，研究如何把文件的一个个联系的逻辑块存放在不同的物理块当中，从而建立逻辑块与物理块之间的映射关系。文件的物理结构主要有三种形式：连续结构、链表结构和索引结构。

①     连续结构

连续结构也叫顺序结构，它的基本思想是把文件的各个逻辑块按顺序存放爱若干个连续的物理块当中。这种方法的优点是简单、易于实现。对于一个文件，系统只要记住它的第一个物理块的编号和物理块的个数，就可以通过简单的加法来实现从逻辑块到物理块的映射。例如，假设一个文件总共有N个逻辑块，而且第一个逻辑块是存放在第N个物理块当中，那么可以推算出第i个逻辑块是保存在第X+i-1个物理块当中。

连续结构也有它的缺点：首先，随着磁盘文件的增加和删除，将会形成空闲物理块与占用物理块相互交错的情形，这样，那些比较小的物理块区域就无法再利用，成为外碎片；其次，在连续结构方式下，文件的大小不能动态地增长。

连续结构主要用在CD-ROM、DVD等一次性写入的光学存储介质当中。对于这些应用，文件的大小都是已知的，所以是固定不变的，所以连续结构的两个缺点都不存在了，而优点还保留着。

②     链表结构

链表结构的基本思路是：把文件的各个逻辑块依次存放在若干个物理块当中，这些物理块既可以是连续的，也可以是不连续的，然后在各个块之间通过指针链接起来，前一个物理块指向下一个物理块，从而形成一条链表。在具体实现链表结构时，需要在每一个物理块当中，专门利用若干个字节来作为指针，指向下一个物理块。对于一个文件，系统只要记住它的链表的首节点指针，就可以定位到这个文件中的任何一个物理块。

链表结构克服了连续结构的缺点。由于不连续的物理块之间可以通过指针连续起来，所以每一个物理块都能够用上，不存在外碎片的问题，而且文件的大小也可以动态变化。

链表结构的缺点是：在访问一个文件是，只能顺序地进行访问，如果想随机地访问，那么速度会比较慢。例如，为了访问一个文件的第n个逻辑块，文件系统必须从这个文件的第一个物理块开始，按照每一个物理块当中的链表指针，顺序地去遍历前n个块，所以时间比较长。

为了解决这个问题，人们又对链表结构进行了改进，提出了带有文件分配表的链表结构。它的基本思路是：在链表结构的基础上，把每一个物理块当中的链表指针抽取出来，单独组成一个表格，也就是文件分配表(File Allocation Table, FAT)，并把它存放在内存当中，然后，如果要随机地区访问文件的第n个逻辑块，可以先从FAT表中查到相应的物理块地址，之后根据这个地址直接去访问磁盘，这样速度就比较快。

文件分配表的具体实现是，在整个文件系统中设置一个一维的线性表格，它的表项个数就等于磁盘上物理块的个数，并按照物理块编号的顺序来建立索引。对于系统中的每一个文件，在它的文件控制块中记录了这个文件的第一个物理块的编号X1，然后在FAT表的第X1项中，记录了该文件的第二个物理块编号X2.就这样一直下去，从而形成了一个链表。在链表的最后一个节点中，存放了一个特殊的文件结束的标识。

图3-65所示是文件分配表的一个例子。通过文件1的目录项可以知道，它的第一个逻辑块存放在第一个物理块中。然后去查询FAT表，可以知道，它的第二、第三个逻辑块分别存放在第二、第三个物理块中。FAT表的第三项是一个特殊的值0xFFFF，表明文件的结束，所以该文件总共有三个块。类似的，文件2也有三个数据块，分别存放在第四、第五和第七个物理块中。

③     索引结构

索引结构的基本思路是：把文件当中每一个逻辑块所对应的物理块编号直接记录在这个文件的文件控制块当中，这样的文件控制块称为是I节点，或索引节点（index node）。这样，对于系统中的每一个文件，都有一个自己的索引节点。通过这个索引节点，就能够直接实现逻辑块与物理块之间的映射关系。例如，如果要去访问文件的第i个逻辑块，可以先到其索引节点的地址映射表中查一下第i项的内容，就可以知道相应的物理块编号，然后就可以直接去访问磁盘了。

3.目录的实现

在实现目录时，不同的文件系统采用了不同的实现方法。一般来说，可以分为两种类型：即直接法和间接法。

l         直接法：如图3-66（a）所示，它把文件控制块的内容直接保存在目录项当中。因此，每一个目录项就等于某个文件的文件名加上它的FCB，包括文件的各种属性信息和它在磁盘上的存放位置。

l        

l         间接法：如图3-66（b）所示，每一个文件的FCB不是保存在它的目录项当中，而是单独存放。然后在每一个目录项里面，只有两个内容：文件名和该文件的FCB所在的地址。

不管是哪一种类型的实现方法，目录的基本功能都是一样的，即如果用户给出一个文件名，就返回相应文件的FCB.

4.空闲空间管理

为了管理磁盘上的空闲空间，系统会维护一个空闲空间列表，上面记录了磁盘上所有的空闲物理块。在具体实现这个空闲列表时，主要有三种方法：位图发、链表法和索引发。

l         位图法：每一个物理块用一个位（bit）来表示。如果该物理块空闲，相应位的值为1；如果该物理块已分配，相应位的值为0.若磁盘有N个物理块，则对应于N个bit。然后将这些连续的位流分隔为一个个字节，每八位一个字节，再把这些字节组织成一个个字，如每个字四个字节，这样就得到了相应的位图。

l         链表法：在每一个空闲的物理块上都有一个指针，然后把所有的空闲块通过这个指针链接起来，形成一个链表。文件系统只要记住这个链表的首节点指针，就可以去访问所有的空闲物理块。

l         索引法：对链表法的一种修改。同样构造一个空闲链表，但是这个链表中的物理块本身并不参与分配，而是专门用来记录系统中其他空闲物理块的编号（索引）。