文件系统的实现
目录
1.文件系统布局
2.文件的实现
3.目录的实现
4.共享文件
5.日志结构文件系统
6.日志文件系统
7.虚拟文件系统
1.文件系统布局
文件系统存放在磁盘上，磁盘划分为一个或多个分区，每个分区有一个独立的文件系统。
一个磁盘包括一个个的扇面，编号从0开始递增，整数计数。第0个扇面在整个文件系统中占有重要的意义。该扇面存放的是主引导记录（Master Boot Record, MBR）.该记录的内容是一个个小小的程序，用来启动计算机，如果该扇面损坏，则整个磁盘无法使用。
MSR后面是分区表，给出了每个分区起始和结束地址。
每个分区的第一块为引导块，引导块中的程序将装载该分区中的操作系统。
文件系统还包含一些关键参数，包含在超级块中。
2.文件的实现
文件的实现就是记录各个文件分别用到了哪些磁盘块
（1）连续分配
文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。如果文件有n块长并 从位置b开始，那么该文件将占有块b, b+1, b+2, …, b+n-1。 一个文件的目录条目包括 开始块的地址和该文件所分配区域的长度。
优点：
- 实现简单
- 读操作性能好
缺点：
缺点在于，文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加， 就需要大量移动盘块。此外，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎 片相似)，并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。
（2）链表分配
链接分配是釆取离散分配的方式，消除了外部碎片，故而显著地提高了 磁盘空间的利用率；又因为是根据文件的当前需求，为它分配必需的盘块，当文件动态增长 时，可以动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、 改也非常方便。
每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何 地方，除最后一个盘块外，每一个盘块都有指向下一个盘块的指针，这些指针对用户是透明. 的。目录包括文件第一块的指针和最后一块的指针。
创建新文件时，目录中增加一个新条目。每个目录项都有一个指向文件首块的指针。该 指针初始化为NULL以表示空文件，大小字段为0。写文件会通过空闲空间管理系统找到空 闲块，将该块链接到文件的尾部，以便写入。读文件则通过块到块的指针顺序读块。
缺点在于无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指 针消耗了一定的存储空间。
（3）内存中的表进行链表分配
取出每个磁盘块的指针字，把它们放在内存中的一个表中，解决了上述方案的不足。
该表在整个磁盘仅设置一张，每个表项中存放链接指针，即下一个盘块号。在该表中，凡是 属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件 地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行 的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的 所有盘块号都放在该表中，故称该表为文件分配表（File Allocation Table, FAT)。
缺点：必须把整个表放在内存中，如果磁盘很大，文件分配表就会很大，占有很多内存空间。
（4）i 节点
i 节点的方法是：每个文件都有一个 i 节点（index node）。其中列出来文件属性和文件块的磁盘地址。
给定 i 节点，就能找到文件的所有块。
只有文件打开时， 对应的 i 节点才在内存中，比 FAT的方法节省了很多内存空间。
3.目录的实现
（0）目录的功能
目录的功能就是把ASCII文件名映射成定位文件数据所需的信息。
操作系统利用用户给出的路径名找到相应的目录项，根据系统的不同，目录项可能是整个文件的磁盘地址、第一个块的编号、或者是 i 节点。
（1）文件属性的存储
对于文件属性，有的系统，文件的属性和文件名一起放在目录项中。 i 节点的系统中，文件属性放在 i 节点中。
（2）文件名的存储
还有一个重要的问题就是文件名的存放，因为文件名的大小是不固定的 ，如MS-DOS，文件名是1 ~ 8个字符。UNIX中是1 ~ 14字符。
如果为每个文件预留最大的空间来保存文件名，会造成大量浪费目录空间。
有两种方法，如下图：
a)方法缺点：删除文件后，留下长度可变的空隙。就和连续磁盘文件一样，会造成大量空间浪费。
b)方法：对堆进行管理，可以高效的利用目录空间。但是管理比较复杂。
（3）文件查找
查找文件名时，线性地从头到尾堆目录进行搜索。
对于非常长的目录，线性搜索就太慢了。使用散列表。
哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优 点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突。最大的困难 是哈希表长度固定以及哈希函数对表长的依赖性。
4.共享文件
为了节省空间和多用户之间协作，必须要可以共享文件。
C目录下有一个文件，B目录与该共享文件的联系称为链接（link）。文件系统本身就是一个有向无环图，而不是一棵树。
**共享文件带来的问题：**如果磁盘地址存在目录项中，当链接文件时，必须把 C目录项中的磁盘地址复制到 B 目录项中。如果B或C往该文件中添加内容，新的数据块只能列入添加工作的用户的目录。违背了共享的目的。
解决方案有二：
1）硬链接：目录块中不存放磁盘地址，而是把磁盘地址放在一个小的数据结构中，这就是UNIX中的 i 节点的方法。共享文件时，B 目录项和 C目录项都指向同一个 i 节点。
2）符号链接：系统建立一个类型为LINK的新文件，把该文件放在 B 目录下，使得B与C的一个文件存在链接。新的文件只包含了它所链接文件的路径名。
当B 读该链接文件时，看到是LINK类型，就找到该文件所连接的文件的路径名，并且去读那个文件。
缺点：
硬链接：C试图删除文件时删不了，因为还关联着B，只能删除C的目录项。
符号链接：需要额外的开销。有时需要多次访问磁盘。
5.日志结构文件系统
……
6.日志文件系统
……
7.虚拟文件系统（VFS）
为了使不同的操作系统整合到统一的结构中，UNIX实现了虚拟文件系统（VFS）。
将多种文件系统统一成一个有序的结构。
**关键思想：**抽象所有文件系统共有的部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。
VFS对用户进程提供上层接口，即POSIX接口。
向下层提出VFS接口，当设计一个新的文件系统时，必须提供VFS需要的接口。
VFS的工作步骤：
比如，一个文件系统装载在/usr并且一个进程调用它：
open("/usr/include/unistd.h", O_RDONLY);
解析路径时，VFS看到新的文件系统被装载在/usr，并且通过搜索已经装载文件系统的超块表来确定它的超块。
然后找到所装载的文件的根目录，查找路径include/unistd.h。然后VFS创建一个v节点并调用实际文件系统。以返回所在文件 i 节点的信息。这些信息和其它信息一起复制到v节点中（RAM中），而这些所谓的其他信息中最重要的是指向包含调用 v节点操作的函数表的指针，比如read、write、close。
v节点被创建好之后，VFS在文件描述符表中创建一个表项，并指向v节点。最后VFS向调用者返回文件描述符，调用者可以用它去读、写、关闭文件。
随后，当进程用文件描述符来读一个文件时，VFS通过进程表和文件描述符表来确定v节点的位置，并跟随指针指向函数表。运行实际文件系统中的代码。