文件系统

文件系统功能

分配磁盘空间
- 管理文件块（哪一块属于哪个文件）
- 管理空闲空间（哪一块是空闲的）
- 分配算法（策略）
管理文件集合
- 定位文件及其内容（定位）
- 通过名字找到文件的接口
- 分层文件系统
- 按不同方式组织文件（不同的文件系统）
提供安全特性
- 分层保护数据安全
- 可靠性/持久性

文件系统数据结构

一个基本的文件系统应该包含哪些内容？

卷控制块（Unix：“superblock”）
- 每个文件系统一个
- 记录文件系统的详细信息
- 块、块大小、空闲块、计数/指针等
文件控制块（Unix：“inode”）
- 每个文件一个
- 记录文件的详细信息
- 权限、所有者、大小、位置等
目录节点（Linux：“dentry”）
- 每个目录项一个
- 将目录项数据结构及树形布局编码成树形数据结构
- 只需文件控制块、父节点、项目列表等

虚拟文件系统

现在的存储介质多种多样，OS必须能够兼容不同的硬件，因此现代OS都采用分层结构

通过分层，对下兼容不同的存储介质，对上提供统一的API。

文件系统的实现

文件系统在磁盘上的布局（以MBR分区表为例）

磁盘的0号扇区称为主引导记录（Master Boot Record，MBR）。在MBR的结尾是分区表，分区表中的一个分区被标记为活动分区。在计算机引导时，BIOS读入并执行MBR。MBR做的第一件事就是确定活动分区，读入它的地一个块，称为引导块，并执行之。引导块中的程序将装载该分区中的操作系统。

除了引导块，不同格式的硬盘分区还可能包含以下项目：

超级块（superblock）：超级块包含文件系统的所有关键参数，在计算机启动时，或者该文件系统首次使用时，超级块会被读入内存。超级块的典型信息包括：文件系统类型的魔数、文件系统中块的数量、以及其它重要的管理信息。
空闲块的信息：例如可以用位图或者指针列表的形式给出。
i节点：每个文件对应一个i节点，i节点包含了文件的方方面面的属性。
根目录：存放文件系统目录树的根部。
目录和文件：磁盘的大多数空间存放了所有的目录和文件

文件的实现

众所周知，文件是以块的形式存放在磁盘上的，每个块典型的大小是4KB，如何记录各个文件分别用到了哪些块？不同操作系统采用不同的方法。

i节点（index-node）

给每个文件赋予一个i节点的数据结构，其中列出了文件属性和这个文件所有磁盘块的地址。
这种机制的一个很大的优势是：只有在对应文件打开时，其i节点才在内存中。
i节点的一个问题是，如果每个i节点只能存储固定数量的磁盘地址，那么当一个文件所包含的磁盘块的数目超出了i节点所能容纳的数目怎么办？

一个解决方法是：最后一个磁盘地址不指向数据块，而是指向一个包含额外磁盘块地址的块的地址。更高级的解决方法是：可以有两个或更多个包含磁盘地址的块，或指向其它存放地址的磁盘块的磁盘块。（参考下文的多级索引块）

连续分配

最简单的分配方案就是把每个文件作为一连串连续数据块存储在磁盘上。

优点：

实现简单，记录文件用到的块只需记录两个数字：第一个磁盘块的地址，和文件的块数。
读操作性能好：只需一次寻址，就不再需要寻址和旋转延迟（针对机械硬盘）。

缺点也很明显：

磁盘会变的零碎：比如当删除一个文件，这个位置就会留下一个空洞，时间久了就会很多零碎空间。当然对于连续分配的策略也有很多算法，可以参考内存分配。但是磁盘的性质以及速度不比内存，总之这不是一个好的方案。
无法对文件扩展：如果想要向空洞中存入文件，就必须提前知道文件的大小。

虽然看似连续分配方案不值得讨论，但是它确实也有合适的应用场景：

比如：CD-ROM

链表分配

为每个文件构造磁盘块链表，每个块的地一个字作为指向下一块的指针，块的其它部分存放数据。

优点：

不会因为磁盘碎片而浪费空间

缺点：

随机访问相当慢：众所周知，访问链表的时间复杂度是On，而且指针是存在磁盘上的。
降低了系统的运算效率：由于指针占去了一些字节，磁盘存储的字节数不再是2的整数次幂。许多程序都是以2的整数次幂来读写磁盘块的，所以要读出完整的一个块大小的信息，就需要读两个磁盘块。

采用内存中的表进行链表分配（解决链表分配的不足）

内存中建立一个文件分配表（File Allocation Table，FAT）操作系统只需在内存中记录文件的起始块号，起始块中保存着下一个块的块号。
假如一个1TB的磁盘，块大小是1KB，那么这张表需要有10亿项，每项至少3个字节，为了提高查找速度，有时需要4字节。根据系统对空间或时间的优化方案，这张表要占用3GB或4GB的内存，所以这个方法并不适用于大容量磁盘。

索引分配

为每个文件创建一个名为“索引数据块”的非数据数据块，存储文件数据块的指针列表
文件头包含了索引数据块
优点：
- 创建、增大、缩小很容易
- 没有碎片
- 支持直接访问
缺点：
- 当文件很小时，存储索引的开销有点大
- 索引块容量有限，无法保存大文件。
针对大文件的存储，可以采用多级索引块

目录的实现

目录系统的主要功能是把ASCII文件名映射成定位文件数据所需的信息。打开文件时，操作系统利用用户给出的路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。

一种简单的实现方案是：
目录中有一个固定大小的目录项列表，每个文件对应一项，其中包含一个文件名、一个文件属性的结构体、以及用以说明磁盘块位置的一个或多个磁盘地址。

对于采用i节点的系统，还有一种方法：
把文件属性存放在i节点中而不是目录项中，这种情形下目录项会更短。

共享文件

文件系统本身是一个有向无环图（Directed Acyclic Graph， DAG）而不是一棵树。将文件系统组织成有向无环图使得维护复杂化，但也是必须付出的代价。

硬链接： 在UNIX系统中，每个目录项都关联一个i节点，共享一个文件时，就是多个目录项指向同一个i节点。i节点本身保存一个链接计数器，所以系统知道目前有多少目录项指向这个文件。

软链接（符号链接）： 让系统建立一个类型为LINK的新文件，新文件中只包含了它所链接的文件的路径名。

文件描述符

当打开一个文件时，会返回一个文件描述符。OS为每个进程维护一个打开文件表，文件描述符是这个列表中的索引。
打开的文件中，包含以下元数据：

文件指针：指向最近一次读写位置，每个打开了这个文件的进程都有一个指针
文件打开计数：记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件列表中移除
文件磁盘位置：文件在磁盘中的位置，缓存数据访问信息
访问权限：每个程序访问模式信息

打开文件表

打开文件表是一个系统级的列表，一个进程一个。每个卷控制块也会保存一个，所以如果文件被打开将不能被卸载。
每个进程的打开文件表，通过系统的总的打开文件表，指向最终的文件

空闲空间列表

操作系统如何管理磁盘上的空闲空间？

位图实现方案

使用位图代表空闲数据块列表：
- 例如：111111100100111001 如果某一位为0，表名数据块是空闲的，反之则已分配。
优点：
- 使用简单
缺点：
- 可能会是一个big vector：160G disk –》40M blocks –》5MB bits
- 如果空闲空间在磁盘中均匀分布，那么在找到0之前需要扫描n（磁盘上数据块的总数）/r（空闲块的数目）
安全保护：内存中的位图分配状态、磁盘中的位图分配状态、磁盘块的分配，必须是一致的。
- 解决方法：先在磁盘位图设置bit[i] = 1，然后分配block[i]，最后在内存中设置bit[i] = 1

操作系统 - 文件系统