操作系统学习笔记（六）文件管理系统实现
阅读前的思考
- 在目录中找到某个文件可以使用什么方法？
- 文件的逻辑结构和物理结构有什么区别？单个文件的逻辑结构和物理结构之间是否存在某些制约关系？
上面的文件系统基础介绍了目录和文件的逻辑结构，现在我们介绍一下它们的物理结构。
文件系统的层次结构
现代操作系统有多种文件系统类型，如FAT32，NTFS，ext2，ext3，ext4等，因此文件系统的层次结构也不尽相同。下面这种是一种比较通用的层次结构。
不支持在 Docs 外粘贴 block
- 用户调用接口
文件系统为用户提供与文件及目录相关的调用，如新建，打开，读写，关闭，删除文件，建立，删除目录等。这一层由若干模块组成，每个模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块。
- 文件目录系统
文件目录系统的主要功能是管理文件目录，其任务有：
- 管理活跃文件目录表。
- 管理读写状态信息表。
- 管理用户进程打开表。
- 管理与组织存储设备上的文件目录结构。
- 调用下一级存取控制模块。
- 存取控制验证模块
实现文件保护主要由该级软件完成，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。
- 逻辑文件系统与文件信息缓冲区
根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。
- 物理文件系统
将逻辑记录的相对块号转换成实际的物理地址。
- 辅助分配模块
主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空间
这里应该要回头联系下内存分配
- 设备管理程序模块
分配设备，分配设备读写缓冲区，磁盘调度，启动设备，处理设备中断，释放设备读写缓冲区，释放设备等。
目录的实现
目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表对应线性查找，哈希表对应散列查找。
- 线性列表
最简单的目录实现方法，是使用存储文件名和数据块指针的线性表。
在创建新文件时，必须搜索目录上有没有同名的文件存在，然后在目录表上增加一个目录项，删除文件则根据给定的文件名搜索目录，接着释放它的空间。
重用目录项有很多方法：
- 可以将目录项标记为不再使用。
- 将其加到空闲目录项表上。
- 可以将目录表中最后一个目录项复制到空闲位置，降低目录表长度。
这里的空闲目录表的思想，有点像内存的页面分配策略（固定分配局部置换，可变分配全局置换，可变分配局部置换）
采用链表结构可以减少删除时间，优点在于实现简单，不过由于线性表的特殊性，比较费时。
- 哈希表
最大的困难是哈希表的长度固定以及哈希函数对表长的依赖。
目录查询是通过在磁盘上反复搜索完成的，需要不断的进行I/O操作，开销较大。
所以为了减少I/O操作，把当前使用的文件目录复制到内存。
文件的实现
文件的实现，研究的是文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。
这个问题有两个方面：
- 文件的分配方式，讲的是对磁盘非空闲块的管理。
- 文件存储空间管理，对磁盘空闲块的管理。
文件的分配方式
连续分配
连续分配方法要求每个文件在磁盘上占有一组连续的块，如下图所示，磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。
文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。一个文件的目录条目包含开始块的地址和该文件所分配区域的长度。
连续分配支持顺序访问和直接访问，其优点是实现简单，存取速度快。缺点是长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件了，一旦需要增加，就需要重新找一片更大的连续内存，然后把数据复制过去。因而这种方式只适用于长度固定的文件。
链接分配
链接分配采取离散分配的方式，消除了外部碎片，显著提高磁盘利用率，且文件可以很容易地动态增长，无需事先指导文件的大小。
链接分配又可以分为隐式链接和显式链接两种形式。
- 隐式链接
隐式链接如图所示，每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方，排除最后一个盘块外，每个盘块都有指向下一个盘块的指针。
创建新文件时，目录中增加一个条目。每个目录项都有一个指向文件首块的指针，该指针初始化为NULL表示空文件，大小字段为0，写文件会通过空闲空间管理系统找到空间块，将该块链接到文件的尾部，然后写入。
隐式链接的缺点是无法直接访问盘块，只能通过指针顺序访问文件，且盘块指针会消耗一定空间，其稳定性也是一个问题，一旦某一个指针丢了，会导致文件数据丢失。
- 显式链接
把用于链接文件各物理块的指针，从每个物理块的末尾提取出来，显式存放在内存的一张链表中。该表在整个磁盘中仅设置一张（也就是说，并不是每个文件都有自己的一张表），称为文件分配表（File Allocation Table， FAT）。每个表项存放对应块的下一块链接指针，即下一个盘块号。文件的第一个盘块号记录在目录中，后续的盘块号通过查FAT找到。
注意，上图中的盘块号只是一个隐含的序号而已，并不占用空间，就像是数组的索引一样。
FAT的表项和全部磁盘块一一对应。用一个特殊数字-1表示文件末尾，-2表示是空闲块。
FAT在系统启动时就会被读入内存。
索引分配
链接分配解决了连续分配的外部碎片和文件大小的管理问题，但是链接分配并不能有效支持直接访问（FAT除外）。索引分配解决了这个问题，它把每个文件的所有盘块号几种放在一起构成了索引块。
每个文件都有自己的索引块。这是一个磁盘块地址的数组。 索引块的第i个条目指向文件的第i个块。目录条目包括索引块地址。要读第i块，通过索引块的第i个条目的指针来查找和读入所需要的块。
创建文件时，索引块的所有指针都设为空，首次写入第i块时，先从空闲块空间中取一个块，将其地址写入索引块的第i个条目。
索引块的大小是个重要的问题，每个文件都必须有一个索引块，因此索引块应该尽可能小，但是如果索引块太小了，就无法支持大文件，我们有几种方案可以用来解决这个问题：
- 链接方案。一个索引块通常为一个磁盘块，因此本身可以直接读写。为了处理大文件，可以将多个磁盘块链接起来。
- 多层索引。多层索引使第一层索引块指向第二层的索引块，第二层索引块再指向文件块，这种方法根据最大文件大小的要求，可以继续到第三层或第四层。
- 混合索引。将多种索引方式相结合的分配方式。例如系统既采用直接地址，又采用单击索引分配方式或者二级索引分配方式。
| 访问第n条记录 | 优点 | 缺点 | |
|---|---|---|---|
| 连续分配 | 需访问磁盘1次 | 顺序存取时速度快，文件定长时可根据文件起始地址和记录长度随机访问。 | 文件存储要求连续的存储空间，会产生碎片，不利于文件的动态扩充。 |
| 链接分配 | 需访问磁盘n次 | 可解决外存的碎片问题，提高外存空间的利用率，动态增长较为方便。 | 只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗额外空间。 |
| 索引分配 | m级需访问磁盘m + 1次 | 可以随机访问，文件易于增删 | 索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大。 |
这三种方案都需要目录项中或者索引节点（i节点）中存放索引块的地址。
文件存储空间管理
文件存储器空间的划分与初始化
一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大文件的文件卷也可以由多个物理盘组成。
在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目录区）是分离的。由于存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的逻辑卷中的文件。
逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格以及存放逻辑卷信息的超级块。
文件存储器空间管理
文件存储设备分成许多大小相同的物理块，并以块为单位进行信息交换。因此文件存储设备的管理实质上是对空闲块的组织和管理。它包含空闲块的组织，分配和回收问题。
这种物理块的划分思想有些像内存中页的划分，进程中的叫页，内存中的叫页框。
空闲表法
空闲表法属于连续分配方式，它与内存的动态分配方案类似，为每个文件分配一块连续的存储空间。
系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应于一个空闲表项，其中包括表项序号，该空闲区第一个块号，该空闲区盘块数等。再将所有空闲区按其起始盘块号递增的次序排列。
首先，这里说的属于连续分配方式，指的是空闲盘区的组织方式是连续的方式。
其次看了这种方式以后，会有一种熟悉的感觉，很像内存的页面分配（策略有最佳适应算法等。）
空闲链表法
将所有空闲盘区拉成一条空闲链，根据构成链所用的基本元素不同，可把链表分成两种形式，空闲盘块链和空闲盘区链。
空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链。当用户因创建文件而请求分配空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时可能要重复多次操作。
空闲盘区链将磁盘上的所有空闲盘区（每个盘区可能包含多个盘块）拉成一条链。在每个盘区上除了含有用于指示下一个空闲盘区的指针外，还应该有能指明本盘区大小的信息。分配盘区的方法与内存的动态分区类似，通常采用首次适应算法，在回收盘区时，同样也要将回收区与相邻的空闲盘区合并。
空闲表法，空闲盘区链比较类似，都与内存的动态分区类似。
位示图法
利用二进制中的一位表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制与之对应。当其值为0时，表示盘块空闲，为1时，表示已分配。
成组链表法
空闲表法和空闲链表法都不适合大型文件系统，因为这会使空闲表或者空闲链表过大。
在UNIX中，采用的是成组链表法，这种方法结合了空闲表和空闲链表两种方法，克服了表太大的缺点
其大致思想是：把顺序的n个空闲扇区地址保存在第一个空闲扇区，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，如此继续，直至所有空闲扇区都予以链接。
假设磁盘最初全为空闲扇区，其成组链接如图所示，通过这种方式可以迅速找到大批空闲块地址。
这种成组链表法与多级的思想还不是完全相同。
表示文件存储器空闲空间的“位向量”表或第一个成组链块，以及卷中的目录区，文件区划分信息都需要存放在辅存储器中，一般放在卷头位置，在UNIX中称为超级块。
在对卷中文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与辅存卷中超级块的一致性。
回答开始问题
- 在目录中查找某个文件有什么方法
可以采用线性列表法或哈希表法。线性列表把文件名组织成一个线性表，查找时依次与线性表中的每一个表项比较。
若把文件名按序排列，则二分法可以降低平均查找时间，但是建立新文件会增加维护线性表的开销。
哈希表用文件名通过哈希函数得到一个指向文件的指针，这种方法非常迅速，但是要注意哈希冲突。
- 文件的逻辑结构和物理结构有什么区别？单个文件的逻辑结构和物理结构是否存在某种制约关系？
文件的逻辑结构是用户的可见结构，即用户使用文件的结构。
文件的物理结构是文件在存储器上的组织结构，它表示一个文件在辅存上的安置，链接，编目的方法，它和文件的存取方法以及辅存设备的特性都有着密切的联系。
单个文件的逻辑结构和物理结构之间虽无明显的制约或者关联关系，但是如果物理结构选择不慎，也很难体现逻辑结构的特点。比如一个逻辑结构是顺序结构，但是物理结构是隐式链接结构文件，即使理论上可以快速找到，但是还是需要在磁盘块上一块一块找。
再次注意，逻辑结构指的是文件记录之间的管理，比如按照关键字顺序排序。