文件系统实现
上一章（10章 文件系统）主要讲文件系统提供了可以在线存储和访问文件内容（包括数据和程序）的机制。文件系统永久驻留在外存上。
本章就主要关注在常用外存上的文件存储和访问问题。为了提高I/O效率，内存和磁盘之间的I/O传输以块（block）为单位执行。文件系统可以提供高效和便捷的磁盘访问，以便允许轻松存储，定位，提取数据。
所以文件系统：在存储设备上组织文件的方法和数据结构。 也是OS中负责来管理和存储文件信息的模块。
两个问题：1.如何定义文件系统的用户接口。 2.如何映射逻辑文件系统到物理外存。
文件系统结构
文件系统由许多不同的层组成
1.I/O控制：包括设备驱动程序和中断处理程序。 用来在主内存和磁盘系统之间传输信息。设备驱动程序的作用：控制I/O设备的运行，向硬件控制器发送专门的控制指令（硬件控制器利用这些指令来使I/O设备与系统其它部分相连），操作系统通过设备驱动程序控制设备。
2.基本文件系统：物理块读写，向设备驱动程序发送控制命令。（也管理内存缓冲区和保存各种文件系统、目录和数据块的缓存。）
3.文件组织模块：管理文件，逻辑块和物理块。可以将逻辑块地址转为物理块地址，并且可以为文件分配物理块。
4.逻辑文件系统：管理文件系统中的元数据（除了文件数据外的所有结构数据），目录结构，管理FCB。
当采用分层结构实现文件系统时，可最小化代码的重复。I/O控制的代码，有时还包括基本文件系统的代码，可以用来多个文件系统。但每个文件系统可以拥有自己的逻辑文件系统和文件组织模块。可是分层可能会增加操作系统的开销，导致性能降低。使用分层，包括采用多少层，每层做什么等决定是设计新系统的主要挑战之一。
文件系统实现
基本概念：
物理块（簇）：1个或多个（2^n）扇区组成，基本文件读写单位。
（物理）分区（partition）：磁盘分割成若干个独立的空间，每个空间称为分区
两大类分区：主分区和扩展分区
主分区：能够安装操作系统的启动分区
扩展分区：不能直接使用，必须分成若干逻辑分区
卷（逻辑磁盘）（Volume）：磁盘上的逻辑分区，建立在物理分区上 （一般每个卷可以建立一个文件系统）
文件系统的实现需要采用多个磁盘和内存的结构。
磁盘文件系统结构：
引导控制块：包含了系统引导操作系统的各种信息，只有安装操作系统的分区才有。在UFS（UNIX文件系统称为引导块，在NTFS（Windows NT文件系统）中称为分区引导扇区）
卷控制块（分区控制块）：包括卷或者分区的详细信息，如分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等 在UFS中称为超级块，在NTFS中存在主控文件表中。
目录结构和FCB
用户文件
内存文件系统结构：
内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。这些结构类型可能包括：
分区表：所有安装分区信息
目录缓冲结构：保存最近访问的目录信息
系统打开文件表：包括每个打开文件的FCB的副本以及其他信息
进程打开文件表：包括一个指向整个系统打开文件表中的适当条目的指针，以及其他信息。
当对磁盘读出或写入时，缓冲区保存文件系统的块
打开文件操作：系统调用open（）将文件名传递到逻辑文件系统
系统调用open（）首先搜索整个系统的打开文件表，以便确定这个文件是否已被其他进程使用。如果是，则在单个进程的打开文件表中创建一个条目，并让其指向现有的整个系统的打开文件表。该算法能节省大量开销。如果这个文件尚未打开，则根据给定的文件名来搜索目录结构。部分的目录结构通常缓存在内存中，以加速目录操作。在找到文件后，它的FCB会复制到内存的整个系统的打开文件表中。该表不但存储FCB，而且还跟踪打开该文件的进程的数量。接下来，在单个进程打开文件表中会创建一个条目，指向整个系统打开文件表的条目的一个指针，以及其他的一些域（可能包含文件的当前位置的指针和打开文件 的访问模式。）调用open（）返回单个进程的打开文件表的适当条目的一个指针，以后，所有文件操作通过这个指针执行。
虚拟文件系统
目的：支持多个文件系统，把多个文件系统整合成一个目录结构，为用户屏蔽各个文件系统的差异。
提供了一种面向对象的方法来实现文件系统，为不同类型的文件系统提供了接入VFS的接口，为用户提供了统一的系统调用接口。
分配方法
磁盘直接访问的特点在文件实现时提供了灵活性。在几乎每种情况下，很多文件都是存储在同一个磁盘上。主要问题是如何为文件分配空间，以便有效的使用磁盘空间和快速访问文件。
物理块块号：一维空间，从0开始编号，可以根据物理设备的特性进行转换。
连续分配
每个文件在磁盘上占有一组连续的块。
优点：
- 支持随机访问（可直接访问指定块号的物理块）
- 存取速度快（上一个块到下一个块移动距离短）
- 适用一次性写入操作
缺点： - 浪费空间（小空间无法分配）
- 文件不能动态增长
- 不利于文件的插入和删除（需要移动数据）
连续分配的改进：基于扩展的文件系统（局部连续）
扩展：一组连续的磁盘块集合
扩展是在文件分配时被分配
一个文件可能包含一个或多个扩展
需要一个指向下一个扩展的指针
链接分配
每个文件是磁盘块的链表，磁盘块可能会散布在磁盘的任何地方。
优点：
- 可以离散存放，提高磁盘的利用率
- 可以动态扩充文件大小
- 便于文件的插入和删除操作
缺点： - 无法实现随机访问，访问文件慢
- 可靠性差
优化方法：多块集合成组、、
或者 显示链接！
指针集中存放，把所有指针存放在一张链接表中（文件分配表 FAT）
索引分配
FAT相当于是系统有存放指针的文件分配表
索引分配就是分散的FAT 每个文件都有一张文件分配表 即索引表
索引块：存放指向文件每个物理块块号的物理块
空闲空间管理
由于磁盘空间有限，如果可能，需要将删除文件的空间重新用于新文件。为了跟踪空闲磁盘空间，系统需要维护一个空闲空间列表（但并不一定按列表来实现）
