文件系统的实现

计算机以文件形式管理各种信息，大多数的文件都需要存储在辅助存储器中，用户使用文件系统对文件进行操作。文件系统是操作系统中负责管理和存取文件的程序模块，能够对外存文件存储空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索。[1]
文件系统的实现就是对文件物理结构的研究，即文件数据在物理存储设备上是如何分布和组织的。主要包括文件的分配方式和文件存储空间管理两个方面。

一、文件分配方式

文件分配对应于文件的物理结构，是指文件在辅助存储器上存储的结构形式。[2] 简单地说，就是指如何为文件分配磁盘块。不同的操作系统往往支持不同的分配方法，而在同一个系统中，通常只支持一种方法。分配背后的主要思想是有效利用文件空间和快速访问文件。目前常用的文件分配方法有连续分配、链接分配和索引分配三种。

1.1 连续分配

连续分配是最简单的分配方法，它把一组连续的盘块分给一个文件。利用连续分配的方法，逻辑文件的信息可以有序地存储在邻近的一组物理盘上。[3] 这种分配方式保证了逻辑文件的记录顺序与存储文件占用磁盘的顺序一致。
连续分配适合对文件的顺序访问，当然也适合直接访问。其优点是顺序存取速度快，一次可以存取多个盘块，改进了I/O性能。[4] 同时实现简单，只需要知道文件存储的起始块号和文件块数，就可以通过简单加法立即找到所需的文件信息。
连续分配的缺点是不便于文件长度动态增加。要求建立文件时就确定它的长度，依此来分配相应的存储空间，因此只适用于长度固定的文件。反复增删文件后会产生外部碎片，即在存储介质上存在很多空闲块，从而造成浪费。

1.2 链接分配

链接结构的特点是使用指针来表示文件中各个记录之间的关联。采用离散方式为文件分配外存空间，每个文件都是磁盘块的链接列表。
与连续分配方案不同，链接分配可以充分利用每个磁盘块，消除了外部碎片，提高了存储空间利用率。此外，因为采用链表的思想，文件动态增长时，可以动态地再为它分配盘块。文件的增、删、改也可以非常方便地实现。[5]

1.3 索引分配

链接分配不利于直接访问。索引分配解决了这个问题，它把将文件的全部逻辑记录都散存在辅存的各物理块中，为文件建立一张索引表。
索引分配除了具备链接分配的优点外，还克服了它只能作顺序存取的缺点。可以方便地进行随机存取。[6]
索引分配的主要缺点是由于索引块的分配，外存空间浪费较大。这个问题可以通过链接方案、多层索引和混合索引来解决。

二、文件存储空间管理

文件存储空间（外存）由系统和用户共享。为了有效利用外存空间，提高文件访问速率，系统需要对外存中的空闲块资源进行妥善管理。目前常用的文件存储空间管理技术主要有空闲表法、空闲链表法和位示图法

2.1 空闲表法

在系统运行过程中，文件频繁地被创建和删除。为了记载磁盘上哪些盘块当前是空闲的，空闲表法为外存上的所有空闲区建立了一张空闲盘块表，该表记录着当前磁盘上空闲的物理块。[7]
空闲表法适用于连续文件的存储分配与回收。但增加了目录大小和目录管理复杂性，分配和回收时查询代价较大。

2.2 空闲链表法

空闲链表法是把文件存储设备上的所有空闲盘区用指针链接在一起，形成一个链表，并设置一个头指针指向该空闲盘区的第一个物理块。[8]
空闲链表法操作简单，但是效率较低，每次分配或回收一个空闲块时，都要启动磁盘才能取得空闲块内的指针，或把指针写入归还的物理块中。

2.3 位示图法

利用一串二进位值反映磁盘空间的分配情况，每个盘块都对应一个二进制位。如果盘块是空闲的，对应位是1；如果盘块已分出去，则对应位是0。[9]
主要优点是占用空间少，操作较快，能实现文件存储空间的高速分配和回收。缺点是分配时需要顺序扫描位示图，且空闲块号并未在位示图中直接反映出来，需要进一步计算。

参考文献

[1] 胡元义，黑新宏. 操作系统原理[M]. 北京：电子工业出版社，2018.
[2] [4] [8] 屠立忠. 操作系统教程[M]. 北京：电子工业出版社，2013.
[3] [9] 曾宪权. 操作系统原理与实践[M]. 北京：电子工业出版社，2016.
[5] 罗宇，邹鹏，邓胜兰. 操作系统（第3版）[M]. 北京：电子工业出版社，2011.
[6] [7] 孟庆昌，朱欣源. 操作系统（第2版）[M]. 北京：电子工业出版社，2009.