操作系统概念（十三）——文件系统实现

文件系统提供了在线存储和访问包括数据和程序在内的文件内容的机制，文件系统永久地驻留在外存上，外存可以永久存储大量数据。

一、文件系统结构

1、磁盘提供大量的外存空间来维持文件系统，磁盘的两个特点，使其成为存储多个文件的方便媒介：
①可以原地重写；可以从磁盘上读一块，修改该块，并将它写回到原来的位置
②可以直接访问磁盘上的任意一块信息。（随机或顺序方式）
2、为了改善I/O效率，内存与磁盘之间的I/O转移是以块为单位而不是以字节为单位来进行的，每个块为一个或多个扇区
3、为了提供对磁盘的高效且便捷的访问，操作系统通过文件系统来轻松地存储、定位、提取数据。
3、文件系统的两个设计问题
①如何定义文件系统对用户的接口
②创建数据结构和算法来将逻辑文件系统映射到物理外存设备上
4、文件系统按层来进行组织，包括如下（由上向下一次递进）：
①应用程序
②逻辑文件系统：管理元数据：文件系统的所有结构数据，而不包括实际数据（或文件内容）；根据给定符号文件名来管理目录结构；逻辑文件系统通过文件控制块(FCB)来维护文件结构
③文件组织系统：知道文件及其逻辑块和物理块，空闲空间管理器，可以将逻辑块地址转换成基本文件系统所用的物理块地址
④基本文件系统：向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写
⑤I/O控制：由设备驱动程序和中断处理程序组成，实现内存与磁盘之间的信息转移
⑥设备
5、个人理解：文件系统包括硬件实现和软件实现，硬件部分包括设备（磁盘等存储装置）与设备控制器，软件部分包括设备驱动程序、中断处理程序、文件组织模块（就是地址转换器）以及目录（我个人还是倾向于将其看做一个指针文件，也就是上文的逻辑文件系统）。

二、文件系统实现

（一）、概述

1、在磁盘上，文件系统可能包括如下信息：
①如何启动所存储的操作系统
②总的块数
③空闲块的数目和位置
④目录结构以及各个具体文件等
2、磁盘结构包括：
①（每个卷的）引导控制块：通常为分区的第一块。如果该分区没有OS，则为空。（其他名称：引导块（Linux）、分区引导扇区（WindowsNT））
②分区控制块：包括分区详细信息，如分区的块数、块的大小、空闲块的数量和指针、空闲FCB的数量和指针等（亦称为超级块（Linux）、主控文件表（WindowsNT））
③目录结构：用来组织文件
④文件控制块（FCB）：包括很多文件信息，如文件许可、拥有者、大小和数据块的位置等
3、一个典型的文件控制块包括：
①文件权限
②文件日期
③文件所有者，组，ACL
④文件大小
⑤文件数据块
4、内存中的结构：
①内存分区表：包含所有安装分区的信息
②内存目录结构：保存近来访问过的目录信息（对安装分区的目录，可以包括一个指向分区表的指针）
③系统范围的打开文件表：包括每个打开文件的FCB拷贝和其他信息
④单个进程的打开文件表：包括一个指向系统范围内已打开文件表中合适条目和其他信息的指针
5、访问打开文件表的索引叫做文件描述符或者文件句柄
6、打开文件：
①通过文件名在目录中找到文件的位置和相关信息
②通过目录在辅助存储器中找到（个人认为这里是新建）文件控制块，并对目录结构进行修改
7、读文件：
①通过索引（文件句柄）在当前进程打开的文件表中找到逻辑地址块
②通过上文找到的逻辑地址块，通过系统范围打开的文件表（个人理解是上文的文件组织系统）找到对应的物理地址块
③在辅助存储器中找到对应的数据块，通过文件控制块进行数据的传递

（二）、分区与安装

1、分区可以是“生的”，即没有文件系统，或是“熟的”，即含有文件系统。生的分区用于没有合适文件系统的地方。如：Unix中的交换区
2、引导信息能存在各个分区中，并且有自己的格式。它通常为一组有序块，作为二进制文件读入内存。引导信息除了包括如何启动一个特定操作系统外，还可以有其他指令。
3、根分区包括操作系统内核或其他系统文件，在引导时装入内存。其他分区根据不同操作系统可以在引导时自动装入或在此之后手动装入。

（三）、虚拟文件系统

1、虚拟文件系统(VFS)提供了一种面向对象的方法来实现文件系统
2、VFS允许在不同类型的文件系统上采用同样的系统调用接口（API）
3、API是针对VFS的接口，而非对任何特定类型的文件系统
4、简单地讲，由于现在，操作系统需要同时支持多个文件系统类型，这就牵扯到如何将多个文件系统合并成一个目录结构就有了虚拟文件系统，实际上，个人感觉并不难，只要指针到位，合并目录并不是一件很难的事情，难点在于，如何实现使用。如果不同的文件系统有着不同的调用函数，这个时候就会很难办。所以，这就是虚拟文件系统的作用，统一了调用函数，允许在不同类型的文件系统上采用相同的API，这样，我们在编写程序之后，编译器在生成可执行程序的时候，就不需要区分好几套不同的API来调用硬件设备，而是用一套就可以了

三、目录实现

1、最为简单的目录实现方法是使用存储文件名和数据块指针的线性列表（数组、链表等）：
①容易实现
②运行费时，采用线性搜索来查找特定条目（缺点）；许多操作系统采用软件缓存来存储最近访问过的目录信息
2、Hash表：采用Hash数据结构的线性表：
①减少了目录搜索时间
②碰撞：两个文件名哈希到相同的位置
③哈希表的最大困难是其通常固定的大小和哈希函数对大小的依赖性
3、个人理解，之前提到的目录的结构，包括单层、双层、树形、无环图等等，都是一种理论逻辑上的结构，这里讲的是采取什么样子进行实现，包括链表、数组等等，哈希表也是一种方式。

四、分配方法

1、分配方法指的是如何为文件分配磁盘块，常用的分配方法有以下三类
2、个人理解：由于文件很多，而且牵扯到各种操作，所以就需要对文件进行一个磁盘的分配，类似于进程在内存上的分配。

（一）、连续分配

1、每个文件占据磁盘上的一组连续的块
2、特点：
①简单，只需要记录文件的起始位置以及长度
②访问文件很容易，所需的寻道时间也最少
3、存在的问题：为新文件找空间比较困难（类似于内存分配中的连续内存分配方式）；文件很难增长
4、由于访问连续分配文件所需要的寻道数最小，在确实需要寻道时所需要的寻道时间也最小
5、基于扩展的连续分配方法：
①许多新的文件系统采用一种修正的连续分配方法
②该方法开始分配一块连续空间，当空间不够时，另一块被称为扩展的连续空间会添加到原来的分配中。
③文件块的位置就成为开始地址、块数、加上一个指向下一扩展的指针。
6、这里实际上就是进程分配中的单区间分配方法，这样也一样会有外部碎片的问题

（二）、链接分配

1、每个文件是磁盘块的链表；磁盘块分布在磁盘的任何地方。
2、特点：
①简单，只需要起始位置
②文件创建与增长很容易
③无法随机访问
④块与块之间的链接指针需要占用空间
⑤存在可靠性问题
3、簇：将多个连续块组成簇，磁盘以簇为单位进行分配
4、链接分配方法的变种-文件分配表FAT：
①每个分区的开始部分用于存储该FAT表。
②每个磁盘块在该表中有一项，该表可以通过块号来索引。
③目录条目中含有文件首块的块号码。根据块号码索引的FAT条目包含文件下一块的地号码。这种链会一直继续到最后一块，该块对应FAT条目的值为文件结束值。未使用的块用0值来表示。
④为文件分配一个新的块只要简单地找到第一个值为０的FAT条目，用新块的地址替换前面文件结束值，用文件结束值替代0。
⑤如果不对FAT采用缓存，FAT分配方案可能导致大量的磁头寻道时间。但通过读入FAT信息，磁盘能找到任何块的位置，从而实现随机访问。
5、个人理解，实际上就是在磁盘中创建了一个很长的文件链表

（三）、索引分配

1、将所有的数据块指针集中到索引块中
①索引块中的第i个条目指向文件的第i块。
②目录条目包括索引块的地址
2、索引分配支持直接访问，且没有外部碎片问题
3、索引块本身可能会浪费空间
①链接方案：一个索引块通常为一个磁盘块。对于大文件，可以将多个索引块链接起来。
②多层索引：类似于内存的间接寻址方式（一级、二级间接…）
③组合方案：如Unix的inode，实际上就是层次段表，或多级段表
3、普通的索引分配与内存分配中的分页（注意，普通的是分页）很像，因为磁盘实际上就是大小确定的块，因为大小确定，所以也会有一个类似于页表的情况。而拓展的索引分配与内存分配中的分段（注意，不是分页，分页是分成了大小一致的块，分段是分成了大小不一的段！！！）有些类似，同样是有一个类似于段表的结构，然后通过段表的指针去找到文件，这是因为拓展的索引分配允许块与块之间进行合并与组合

五、空闲空间管理

1、为了记录空闲磁盘空间，系统需要维护一个空闲空间链表，它记录了所有空闲磁盘空间，即未分配给文件或目录的空间。（不一定以链表的方式实现）
2、位向量（n块）
①bit[i] = 0即block[i]空闲
②bit[i] = 1即block[i]被占用
③空闲块数计算：一个字的位数 × 值为0的字数 ＋ 第一个值为1的位的偏移
3、位向量需要额外的空间来存储
4、链表(空闲链表)：将所有空闲磁盘块用链表连接起来，并将指向第一空闲块的指针保存在磁盘的特殊位置，同时也缓存在内存中。
①不容易得到连续空间
②没有空间浪费
5、分组：将n个空闲块的地址存在第一个空闲块中，而最后一块包含另外n个空闲块的地址，如此继续。
6、计数：通常，有多个连续块需要同时分配或释放。因此，可以记录第一块的地址和紧跟第一块的连续的空闲块的数量n。

六、效率与性能

1、效率依赖于：
①磁盘分配
②目录算法
③文件名目录项中保存的数据的类型
2、性能：
①磁盘缓冲：将最近使用过的块放在内存的某个地方
②优化顺序访问：马上释放与预先读取
③留出一块内存作为虚拟磁盘（或RAM磁盘）来提高个人计算机的性能
3、页缓存：使用虚拟内存技术，以将文件数据作为页而不是面向文件系统的块来缓存。
4、内存映射I/O使用了页缓存
5、I/O通过文件系统再使用缓冲缓存

七、恢复

1、一致性检查：比较目录中的数据与磁盘中的数据块，以消除不一致性
2、使用系统程序将数据从磁盘备份到其他存储设备（如磁盘，磁带），简单地将，就是增加备份
3、从备份上恢复数据以恢复丢失的文件或磁盘

八、结语

操作系统结束了，最终写了十三篇的总结，估计字数可以破五万了吧哈哈哈哈…好了，不说玩笑话，下学期的这几章的逻辑线我会尽快发出来，各位不要急。也祝愿各位还有我自己考试，考个好成绩，不求80评优秀，只求60过个年哈哈哈哈哈哈哈

来源：麓山君陌