王道操作系统 4.3 文件系统

4.3 文件系统

4.3.1 文件系统结构

文件系统(File system)提供高效和便捷的磁盘访问，以便允许存储、定位、提取数据。

4.3.2 文件系统布局

1.文件系统在磁盘中的结构

坏扇区对于操作系统也是透明的，它意识不到坏扇区的存在

物理格式化后是逻辑格式化，也叫高级格式化

文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。文件系统可能包括如下信息：启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。如下图所示。

主引导记录（MasterBootRecord，MBR)，位于磁盘的0号扇区，用来引导计算机，MBR后面是分区表，该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区，当计算机启动时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一块，即引导块。
引导块（bootblock)，MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统，也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。

除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如上图所列的一些项目。
超级块（superblock)，包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
文件系统中空闲块的信息，可以使用位示图或指针链接的形式给出。
i 结点。索引结点，连续存放，每个文件对应一个结点，可以把 i 结点区看成一个大数组；
根目录，它存放文件系统目录树的根部。
其他部分，存放了其他所有的目录和文件。

2.文件系统在内存中的结构

内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。这些结构的类型可能包括：

内存中的安装表(mount table)，包含每个己安装文件系统分区的有关信息。
内存中的目录结构的缓存，包含最近访问目录的信息。对安装分区的目录，它可以包括一个指向分区表的指针。
整个系统的打开文件表，包含每个打开文件的FCB副本及其他信息。
每个进程的打开文件表，包含一个指向整个系统的打开文件表中的适当条目的指针，以及其他信息。

进程创建：

为了创建新的文件，应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式，它将为文件分配一个新的FCB。然后，系统将相应的目录读入内存，使用新的文件名和FCB进行更新，并将它写回磁盘。

一旦文件被创建，它就能用于I/O，不过，首先要打开文件。系统调用open()将文件名传递给逻辑文件系统。

调用open()首先搜索整个系统的打开文件表，以确定这个文件是否已被其他进程使用。
- 如果已被使用，则在单个进程的打开文件表中创建一个条目，让其指向现有整个系统的打开文件表的相应条目。该算法在文件已打开时，能节省大量开销。
- 如果这个文件尚未打开，则根据给定文件名来搜索目录结构。部分目录结构通常缓存在内存中，以加快目录操作。
找到文件后，它的FCB会复制到整个系统的打开文件表中；该表不但存储FCB，而且跟踪打开该文件的进程的数量。
然后，在单个进程的打开文件表中创建一个条目，并且通过指针将整个系统打开文件表的条目与其他域（如文件当前位置的指针和文件访问模式等）相连。
调用open()返回的是一个指向单个进程的打开文件表中的适当条自的指针。以后，所有文件操作都通过该指针执行。
一旦文件被打开，内核就不再使用文件名来访问文件，而使用文件描述符（Windows称之为文件句柄）

**之后再用文件描述符fd进行read调用：**根据进程的打开文件表找到系统打开文件表，在系统打开文件表里面找到FCB，通过FCB得到文件地址

进程关闭：

当进程关闭一个文件时，就会删除单个进程打开文件表中的相应条目，整个系统的打开文件表的文件打开数量也会递减。当所有打开某个文件的用户都关闭该文件后，任何更新的元数据将复制到磁盘的目录结构中，并且整个系统的打开文件表的对应条目也会被删除。

4.3.3 外存空闲空间管理

一个存储设备可以按整体用于文件系统，也可以细分。例如，一个磁盘可以划分为4个分区，每个分区都可以有单独的文件系统。包含文件系统的分区通常称为卷（volumme)。卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成RAID集，如图所示。

在一个卷中，存放文件数据的空间（文件区）和FCB的空间（目录区）是分离的。

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。

空闲表法

空闲表法属于连续分配方式，它与内存的动态分配方式类似，为每个文件分配一块连续的存储空间。
空闲链表法

将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，分为两种形式：

空闲盘区链：将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。
位示图法

位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。

这样，一个m×n位组成的位示图就可用来表示m×n个盘块的使用情况，如图所示。行为位号，列为字号

注意：盘块号、字号、位号到底是从0开始，还是从1开始。两者计算盘块号方式不同。
- 盘块的分配
  - 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位。
  - 将找到的一个或一组二进制位，转换成与之对应的盘块号。
  - 若找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算（n为每行位数）：
    $$
    \begin{cases}b=n(i-1)+j, & \text{字、位、盘块号从1开始}
    b=ni+j& \text{字、位、盘块号从0开始}\end{cases}
    $$
  - 修改位示图，令$map[i,j]=1$
- 盘块的回收
  - 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为
    1
    2
    i=(b-1)/n + 1
    j=(b-1)%n + 1
  - 修改位示图，令$map[i,j]=0$。
空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大。
成组链接法

天勤：

链太长了，不好，从头到尾扫描一遍效率很低。这是空闲盘块链

把相邻的空闲块分成一组，这样可以短很多，这就是空闲盘区链。但是也有缺点，因为只有相邻的相邻的空闲块才能分成一组，但是系统中绝大多数都是单独的空闲块，退化成空闲盘块链了

那如果给每一组内部都加上指针，让每一组内部也是链表，那一组里面就可以有不相邻的空闲块，这就是成组链接法的基本思想：就是在每组的第一个空闲块保存同一组其他块的索引，然后把各个空闲分区的第一块空闲块用链表串起来（相当于多个索引表串起来构成一个链表），这样可以通过第一块找到同组的其他块。这样链表不会很长，每组内也不是非得是相邻的空闲块

我们遇到的是上图这种，其实链接关系没有发生变化。但是分组却发生了变化，如下图所示

1号块需要事先调入内存，称为超级块。里面保存了一个栈

N是下一组的空闲盘块数量，其他地方存的就是下一组空闲块地址

2号盘块也是如此

最后一个超级块的第一个地方写的-1表示这是最后一组空闲块分区

空闲块分配：

1.分配的不是保存节点的那个块，那么就直接出栈然后N减1就行

2.分配的是每组保存其他块索引的那个块（也就是指针指着的那一组就剩下一个块了）。先把2号块里面保存的索引和N保存到超级块去，然后把2号块出栈作为普通块供分配，如下图所示

空间回收：

1.超级块没满，那就直接入栈超级块即可，如下面的4

2.超级块满了

假设上面那张图使得超级块满了，那就把超级块的内容（栈信息）复制到刚刚新回收的盘块3中，然后清空超级块，然后把盘块3入栈超级块并更新盘块数量信息N。如果再来新的（盘块2），这时因为超级块没满就直接入栈超级块

王道：

在UNIX系统中采用的是成组链接法，这种方法结合了空闲表和空闲链表两种方法，它具有上述两种方法的优点，克服了两种方法均有的表太长的缺点。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保
证内存与外存中的“超级块”数据一致。

用来存放一组空闲盘块号（空闲盘块的块号）的盘块称为成组链块。
- 成组链接思想：把顺序的n个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块（作为成组链块）则用于保存另一组空闲盘块号，如此继续，直至所有空闲盘块均予以链接。
- 盘块的分配
  
  分配1个空闲块：
  - ①检查第一个分组的块数是否足够。1＜100，是足够的。
  - ②分配第一个分组中的1个空闲块，并修改相应数据
  分配100个空闲块：
  - ①检查第一个分组的块数是否足够。100=100，是足够的。
  - ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中
- 盘块的回收
  
  需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

4.3.4 虚拟文件系统

虚拟文件系统（VFS）为用户程序提供了文件系统操作的统一接口，屏蔽了不同文件系统的差异和操作细节。

UFS是linux文件系统

普通文件系统

下图普通的文件系统，不同的外部存储设备，它的文件系统可能是不相同的，对于同一个操作的函数方法定义也许也各不相同。对于上层的用户和程序员来说很麻烦，所以操作系统需要向上层提供统一标准的系统调用接口。
虚拟文件系统

下图为虚拟文件系统，用户程序可以通过VFS提供的统一调用函数（如open()等）来操作不同文件系统的文件，而无须考虑具体的文件系统和实际的存储介质。

虚拟文件系统采用了面向对象的思想，它抽象出一个通用的文件系统模型，定义了通用文件系统都支持的接口。新的文件系统只要支持并实现这些接口，即可安装和使用。

特点：
- ①向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
- ②VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求（其实就是规定了每个函数的参数数量和作用，你必须要有，没有的话就不给你用我的文件系统）
- ③每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。注意：每次打开文件是先把inode调入内存，再把inode信息复习到vnode里面去了。所以vnode只在主存，而inode主存和外存里面都有
VFS在系统启动时建立，在系统关闭时消亡

为了实现VFS，Linux主要抽象了四种对象类型。每个VFS对象都存放在一个适当的数据结构中，其中包括对象的属性和指向对象方法（函数）表的指针。
- 虚拟文件系统VFS所定义的对象类型
  
  （1）超级块对象：表示一个已安装（或称挂载）的特定文件系统。超级块对象对应于磁盘上特定扇区的文件系统超级块，用于存储已安装文件系统的元信息。其操作方法包含一系列可在超级块对象上调用的操作函数，主要有分配inode、销毁inode、读inode、写inode等。
  （2）索引节点对象：表示一个特定的文件。索引节点和文件是一对一的关系。只有当文件被访问时，才在内存中创建索引节点对象，每个索引节点对象都会复制磁盘索引节点包含的一些数据。索引节点对象还提供许多操作函数，如创建新索引节点、创建硬链接、创建新目录等。
  （3）目录项对象：表示一个特定的目录项。目录项对象是一个路径的组成部分，它包含指向关联索引节点的指针，还包含指向父目录和指向子目录的指针。不同于前面两个对象，目录项对象在磁盘上没有对应的数据结构，而是VFS在遍历路径的过程中，将它们逐个解析成目录项对象的。
  
  （4）文件对象：表示一个与进程相关的已打开文件。可以通过调用openO打开一个文件，通过调用closeO关闭一个文件。文件对象和物理文件的关系类似于进程和程序的关系。文件对象仅是进程视角上代表已打开的文件，它反过来指向其索引节点。文件对象包含与该文件相关联的目录项对象，包含该文件的文件系统、文件指针等，还包含在该文件对象上的一系列操作函数。当进程发起一个面向文件的系统调用时，内核调用VFS中的一个函数，该函数调用目标文件系统中的相应函数，将文件系统请求转换到面向设备的指令。以在用户空间调用writeO为例，它在VFS中通过sys_writeO函数处理，sys_writeO找到具体文件系统提供的写方法，将控制权交给该文件系统，最后由该文件系统与物理介质交互并写入数据。
进程与VFS对象之间的交互如下图所示。

三个不同的进程已打开了同一个文件，其中两个进程使用同一个硬链接。

在这种情况下，每个进程都使用自己的文件对象，但只需要两个目录项对象，每个硬链接对应一个目录项对象。这两个目录项对象指向同一个索引结点对象, 这个索引结点对象标识的是超级块对象及随后的普通磁盘文件。

4.3.5 文件系统安装/挂载

第二点的函数地址列表就是vnode里面的函数功能指针所指的地方

UNIX本身是一个固定的目录树，只要安装就有，但是如果不给它分配存储空间，就不能对它进行操作，所以首先要给根目录分配空间，这样才能操作这个目录树。

4.4 本章疑难点

1、文件的物理分配方式的比较

2、文件打开的过程描述

检索目录，要求打开的文件应该是已经创建的文件，它应登记在文件目录中，否则会出错。在检索到指定文件后，就将其磁盘iNode复制到活动iNode表中。
将参数mode所给出的打开方式与活动iNode中在创建文件时所记录的文件访问权限相比较，如果合法，则此次打开操作成功。
当打开合法时，为文件分配用户打开文件表表项和系统打开文件表表项，并为后者设置初值，通过指针建立表项