文件系统的实现

操作系统中有很多种文件（FAT32、NTFS、ext2、ext3等），层次接口不尽相同。对于文件系统，要了解其实现的方法，目录是如何实现的、文件是如何实现的、存储空间管理。

1. 文件系统层次结构

用户调用接口->文件目录系统->存取控制验证->逻辑文件系统与文件信息缓冲区->物理文件系统->磁盘分配模块

如果要我们设计一个文件系统，不管是什么类型，都应该从这个流程出发。

有线性列表和哈希表两种方式，前者实现简单，查找效率低。后者查找效率要高于前者。

文件的实现研究的就是文件的物理结构，如何为文件分配磁盘块是一个问题。一般的方式有三种：

连续分配
线性排序，实现简单，存取速度快。文件不易于动态增加，可用空间不连续。也就是有外部碎片存在。
链接分配
较连续分配有更高的利用率，同时又分为隐式链接和显示链接。前者的缺点是无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指针消耗了一定的存储空间。由于指针丢失，数据就访问不到了。显示链接用一张连接表来保存指针，称为FAT（文件分配表）
索引分配
可直接访问，无外部碎片。缺点：开销他，索引快大小无法权衡。

未完待续