文件系统管理和优化

1. 磁盘空间管理

几乎所有文件系统都把文件分割成固定大小的块来存储，各块之间不一定相邻。

1. 块大小

   拥有大的块尺寸意味着小的文件会浪费大量磁盘空间。小的块尺寸意味着大多数文件会跨越多个块，即需要多次寻道与旋转延迟才能读出它们，浪费了时间。

2. 记录空闲块

   有两种方法被广泛采用。

   1. 磁盘块链表

      每个块中包含尽可能多的空闲磁盘块号，对于1KB大小的块和32位的磁盘块号，空闲表中每个块包含有255个空闲块的块号(32位 = 4字节，1KB = 1024字节，1024/4 = 256,还需要一个位置存放指向下一个块的指针，所以是255)。对于一个500G的磁盘，需要190万个块才能存放这些地址。所以通常情况下，将这些空闲表存放在空闲块中，该方法比较适合磁盘快满时使用。

   2. 位图

      n个块的磁盘需要n位位图，每一位用1表示该块空闲，0表示已分配。对于500G硬盘，只需要60000个1KB的块。

   

2. 文件系统备份

将磁盘备份有两种方案：物理转储和逻辑转储

1. 物理转储

   从磁盘的第0块开始，将全部的磁盘块按需输出，直到最后一块复制完毕。对于未使用的磁盘块不需要备份，如果转储程序能够访问管理空闲块的数据结构，就可以避免备份未使用的磁盘块。要注意的是原磁盘和得到备份的磁盘块并不是一一对应的，所以应该在每个磁盘块前写上磁盘块号码。

   另一方面需要关注的是坏块的转储。可以通过建立一个包含所有坏块的“文件”来解决，以确保这些坏块不会被使用和分配。所以在转储时，需要跳过这些块。

   物理存储的优点是简单，快速，但是不能跳过选定的目录，也不能增量转储。

2. 逻辑转储

   从一个或几个指定的目录开始，递归地转储其自给定基准日期(如最近一次转储的日期)后所更改的全部文件和目录。在逻辑存储中，得到转储的磁盘会有一连串被标识过得目录和文件，可以按要求恢复特定文件或目录。

3. 逻辑转储算法

如图，树中方框代表目录，圆圈代表文件。被阴影覆盖的项目代表在基准日期后被修改过，需要转储。到达修改过文件的所有目录也应该被转储，因为这样方便对文件的整体恢复。

该算法需要维持一个以i结点号为索引的位图。随着算法的执行，位图中的一些位会被设置或清除，算法分为四个阶段。

1. 从起始目录开始(本例中为根目录)检查所有目录项，对每个修改过的文件在位图中标记，并递归标记所有目录(包括未被修改的)。
   

2. 再次递归遍历目录树，并去掉目录书中所有不含被修改过的文件或目录的目录上的标记(这一阶段结束后所有被标记的文件和目录就是最后必须被转储的)。
   

3. 以节点号为序，扫描i节点，并转储步骤2中所有标记的目录，并为这些目录添加目录属性前缀。
   

4. 转储步骤2中所有标记的文件，并为这些文件添加文件属性前缀。
   

4. 文件系统一致性

使用程序检验文件系统一致性，包括：块的一致性检查和文件一致性检查。

1. 块的一致性

   程序构造两张表，每张表为每一个块设立一个计数器，初始为0，第一个表中的计数器跟踪该块在文件中出现的次数，第二个表中的计数器跟踪该块在空闲表中出现的次数。

   接着检验程序使用原始设备读取全部i结点，从0开始。由i节点开始，可以建立相应文件中采用的全部块的块号表。每当读到一个块时，该块在第一个表中计数器加1。然后，程序检查空闲表或空闲位图，每当一个块未使用时，在第二张表中加1。

   检查完成后可能出现结果如下：

   1. 一致，即每一块要么在第一个表计数器为1，要么在第二个表计数器为1。

   2. 如果一个磁盘块在任何一张表中都是0，那么就称该块块丢失。解决方法是，检验程序将该块加入到空闲表中。

   3. 一个块在空闲表中出现了两次，即一个块在第二张表中数字为2。解决方法是，重新建立空闲表。

   4. 两个或多个文件中出现同一个数据块，即一个块在第一张表中数字为2。解决方法是，先分配一空闲块，将这个重复块的内容复制到空闲块中，然后把它插入到其中一个文件中。

2. 文件一致性

   检验程序检查目录系统，同样创建一张计数表，但每个文件而不是一个块对应一个计数器。程序从根目录开始检验，沿着目录树递归，检查文件系统中的每个目录。对每个目录中的每个文件，将文件使用计数器加1。遇到硬连接，同样加一，但是符号连接不计数。

   检验完成后，会得到一张由i节点号索引的表，说明每个文件被多少个目录包含。然后，检验程序将这些数字与存储在文件i节点中的连接数目比较。

   最终可能得到的结果如下：

   1. i节点连接数与计数器相等，则说明文件系统一致

   2. i节点连接数大于计数器个数，说明即使所有该文件都被删除，计数仍是非0，i节点不会被删除。解决方法是，将i节点的值更新为计数器的值。

   3. i节点连接数小于计数器个数。可能导致一个目录指向错误i节点。解决方法同样是更新i节点值。

5. 文件系统性能

三种主要的优化措施

1. 高速缓存

   常用算法为检查全部读请求，并检查高速缓存中是否有所需要的块。如果存在，可以直接执行读操作而无需访问磁盘。如果不存在，则将它读入到高速缓存，然后再复制到所需地方。为了快速确定所需块是否存在，通常使用散列表将设备和磁盘地址散列。

   为避免一致性遭到破坏(如一个块读进了高速缓存并进行过修改，但是在崩溃前没有写回磁盘)，如果一个块关系到文件系统一致性且被修改，那应该立即将该块写回磁盘。该方法被称为通写高速缓存。

2. 块提前读

   在需要用到块之前，提前将其写入高速缓存。对于许多顺序读的文件，预读操作很适合。但是对于随机存取文件，提前读策略并不好。

3. 减少磁盘臂运动。

   把有可能顺序存取的块放在一起，最好是一个柱面上，以减少磁盘臂的移动次数。对于位图保存空闲块的系统来说，可以很简单的找到最近的空闲块。

   对于使用空闲表的系统，需要使用块簇技术。即不用块，而是连续块簇来跟踪存储区。例如，一个扇区512字节，一个块为两个扇区即1KB，但是按每两块即4个扇区来分配存盘存储区。不同于直接使用2KB的块，在高速缓存中依然使用1KB的块，磁盘与内存之间的数据传送也还是以1KB为单位进行，但在一个空闲的系统上顺序读取文件，寻道的次数可以减少一半。

   另一方面，在使用i节点的系统中，读取文件需要两次磁盘访问：一次访问i节点，一次访问块。为减少寻道时间，可以避免把磁盘开始处存放i节点，而是将磁盘凤城多个柱面组，每个组有自己的i结点、数据块和空闲表。

参考书目：现代操作系统第三版