让文件系统正常工作是一回事，让文件系统高效稳定地工作又是另一回事。让我们讨论一下文件系统的管理和优化。1、磁盘空间管理文件通常存储在磁盘上，因此如何管理磁盘空间是操作系统设计者需要考虑的问题。有两种存储文件的策略：“分配n字节的连续磁盘空间；或者将文件拆分为多个不一定连续的块”。在存储管理系统中，主要有分段管理和分页管理两种方式。正如我们所见，将文件存储为连续的字节序列存在一个明显的问题，这可能需要随着文件的增长在磁盘上四处移动。内存分段也有同样的问题。不同之处在于，移动内存中的段比将文件从磁盘上的一个位置移动到另一个位置要快得多。因此，几乎所有的文件系统都将文件分成固定大小的块进行存储。1、块大小一旦文件被分成固定大小的块存储，就会出现一个问题。块大小是多少？根据“磁盘组织法”，扇区、磁道、柱面显然可以作为分配单位。在分页系统中，页面大小也是一个主要因素。具有大块大小意味着每个文件，即使是1字节文件，也会占用一个柱面空间，这意味着小文件会浪费大量磁盘空间。另一方面，小块意味着大多数文件将跨越多个块，因此需要多次查找和旋转延迟才能读取它们，从而降低性能。因此，分配太大的块会浪费空间；如果分配的块太小，就会浪费时间。2.跟踪空闲块一旦指定了块大小，下一个问题就是如何跟踪空闲块。有两种方法被广泛使用，如下图所示。第一种方法是使用磁盘块链表，链表的每个块包含尽可能多的空闲磁盘块号。对于1KB的块和32位的磁盘块号，空闲列表中的每个块包含255个空闲块号。考虑一个1TB的硬盘，大约有十亿个磁盘块。要存储所有地址块号，如果每个块可以容纳255个块号，则需要将近400万个块。通常，空闲块用于保存空闲列表，因此存储基本上是免费的。另一种可用空间管理技术是位图。具有n个块的磁盘需要n位位图。在位图中，空闲块用1表示，已分配块用0表示。以1TB硬盘为例，需要10亿位表示，即需要大约130000个1KB块存储。显然，位图比32位链表模型需要更少的空间，因为每个块使用1位。仅当磁盘快满时，链表才需要比位图更少的块。如果空闲块是长期连续的，则可以将空闲列表更改为记录连续的块而不是单个块。每个块都会用8位、16位、32位的计数与每个块相关联，记录连续空闲块的个数。最好的情况是一个空闲块可以用两个数字表示：“第一个空闲块的地址和空闲块的计数”。另一方面，如果磁盘严重碎片化，则跟踪连续块的效率低于跟踪单个块的效率，因为不仅要存储地址，还要存储数量。这种情况说明了操作系统设计者经常遇到的一个问题。有许多数据结构和算法可以用来解决问题，但选择最佳解决方案需要设计者无法事先拥有的数据。只有在系统部署并实际使用后才会获得。现在，回到空闲列表方法，只有一个指针块保存在内存中。创建文件时，从指针块中获取所需的块。当它用完时，从磁盘读取一个新的指针块。类似地，当一个文件被删除时，该文件的块被释放并添加到主内存中的指针块中。当块已满时，它被写回磁盘。在某些特定情况下，这种方法会导致不必要的磁盘IO。如下图所示，上面内存中的指针块只有两个空闲块。如果一个包含三个磁盘块的文件被释放，指针块就会溢出，必须写入磁盘，那么这就会导致如下图的情况。如果现在写了一个三块的文件，就得重新读入全指针，又会回到上图a的情况。如果一个包含三个块的文件仅作为临时文件写入，当它被释放时，需要另一个磁盘写操作将完整的指针块写回磁盘。简而言之，当指针块几乎为空时，一系列短暂的临时文件会“导致大量磁盘I/O”。避免大部分磁盘I/O的另一种方法是拆分整个指针块。这样当三个block被free后，变化就不再是a-b，而是a-c了，如下图。现在，系统可以在不进行任何磁盘I/O的情况下处理一系列临时文件。如果内存中的指针块已满，则写入磁盘，半满的指针块则从磁盘读取。这里的想法是让磁盘上的大部分指针块保持完整（以减少磁盘使用），但在内存中保留一个半满的指针块。这样，文件创建和文件删除都可以在没有磁盘I/O到空闲列表的情况下处理。对于位图，只有一个块保留在内存中，只有当块已满或为空时才从磁盘中取出另一个块。通过在位图的单个块上进行所有分配，磁盘块紧密地堆积在一起，减少了磁盘臂的移动。由于位图是固定大小的数据结构，如果内核进行了分页，则可以将位图放在虚拟内存中，需要时调用位图的页。2、磁盘配额为了防止某些用户占用过多的磁盘空间，多用户操作通常会提供一种强制执行磁盘配额的机制。系统管理员为每个用户分配“最大文件和块分配”，操作系统确保用户不超过他们的配额。我们将在下面讨论这个机制。当用户打开文件时，操作系统找到文件属性和磁盘地址，并将它们发送到内存中的打开文件表。其中一个属性告诉文件的所有者是谁。对文件的任何添加都计入所有者的配额。第二个表包含每个用户当前打开的文件的配额记录，即使其他人打开了该文件。如上所示，该表的内容是从打开文件的所有者的磁盘配额文件中提取出来的。当所有文件都关闭时，该记录将写回配额文件。当在打开文件表中创建一个新条目时，将生成一个指向所有者的配额记录的指针。每向文件添加一个块，文件所有者使用的数据块总数就会增加，硬限制和软限制检查都会增加。可以超过软限制，但不能超过硬限制。在达到硬限制时添加到文件将引发错误。同样，对文件数量也存在类似的检查。什么是硬限制和软限制？“硬限制是软限制的上限。”软限制是实际对会话或进程强制执行的限制。这允许管理员（或用户）设置硬限制以允许他们希望允许的最大使用上限。然后，其他用户和进程可以使用软限制来根据需要自行将其资源使用限制在较低的上限。当用户尝试登录时，系统会检查配额文件以查看用户是否超过了文件或磁盘块数的软限制。如果违反了任何限制，则显示警告并将保存的警告计数减1，警告计数为0表示用户已多次忽略该警告，并且不允许用户登录。为了要获得再次登录的权限，需要与系统管理员协商。如果用户在注销时清除超出部分，他们可以在终端会话期间超过软限制，但“在任何情况下都不会超过硬限制”。3、文件系统备份文件系统的损坏比计算机的损坏要严重得多。无论是硬件故障还是软件故障，只要是电脑文件系统损坏，都极难甚至无法恢复。因为文件系统无法抵抗损坏，所以我们需要在文件系统损坏之前备份数据，但是备份并不是那么容易。让我们在下面讨论备份过程。很多人认为做文件系统备份不值得而且浪费时间，直到有一天他们的磁盘出现故障，他们才意识到事情的严重性。相对而言，公司在这方面做得很好。磁带备份主要需要处理以下两个潜在问题之一：从意外灾难中恢复：这个问题主要是由外部条件引起的，例如磁盘破裂、洪水和火灾。从错误中恢复：第二个问题通常是由于用户不小心删除了应该恢复的文件。这种情况经常发生，以至于Windows设计者为删除命令设计了一个特殊的目录。这就是回收站（recyclebin）。消失，而是放在这个特殊的目录中，以后需要的时候可以恢复。文件备份主要是指这种情况，可以让几天前或者几周前的文件从原来的备份盘中恢复出来。进行文件备份既费时又浪费空间，这可能会导致一些问题。首先，你想“备份整个文件还是只备份其中的一部分”？一般来说，只备份特定目录及其下的所有文件，而不是整个文件系统。其次，备份上次没有修改的文件很浪费，于是产生了增量转储（incrementaldumps）的想法。增量转储最简单的形式就是定期做一次全面备份，每天增量转储完成后只对发生变化的文件做一次备份。周期性：例如一周或一个月稍微好一点的方法是只备份自上次转储以来更改过的文件。当然这种方式大大减少了dump的时间，但是恢复起来比较复杂，因为“必须先完全恢复最近的fulldump，然后倒序递增dump”。为了便于恢复，人们倾向于使用更复杂的转储模式。第三，由于要转储的数据往往是海量的，因此在将文件写入磁带之前需要对其进行压缩。但是，如果文件在备份过程中损坏，它可能会破坏压缩算法并使整个磁带无法读取。因此，备份前是否进行文件压缩需要慎重考虑。第四，很难对正在使用的文件系统进行备份。如果在转储过程中添加、删除和修改文件和目录，转储结果可能会不一致。因此，晚上下线备份是很有必要的，因为转储过程需要几个小时，但这种方法并没有被广泛接受。因此，人们修改了转储算法来对文件系统进行即时快照，即复制关键数据结构，然后需要将以后对文件和目录的修改复制到块中，而不是到处更新。磁盘转储到备份磁盘有两种选择：“物理转储和逻辑转储”。物理转储从磁盘的块0开始，依次将所有磁盘块写入输出磁盘，复制完最后一个磁盘时停止。这个程序是绝对可靠的。第二个考虑是“转储坏块”。大盘不可能没有瑕疵，所以会有一些坏块。有时在低级格式化后，会检测到并标记坏块。解决这种情况的方法是用磁盘末尾的一些空闲块替换它们。但是，某些块在格式化后会损坏，在这种情况下操作系统可以检测到它们。通常，它通过创建一个包含所有坏块的文件来解决问题，确保它们不会出现在空闲池中并且永远不会被分配。“那么这个文件是完全不可读的”。如果磁盘控制器重新映射所有坏块，物理转储仍然有效。Windows系统有分页文件和休眠文件。它们在文件恢复中不起任何作用，一开始就不应该备份。物理转储和逻辑转储的主要优点是简单且速度极快（基本上以磁盘的速度运行）。缺点是是全量备份，不能跳过指定目录，也不能增量转储，也不能恢复个人文档。因此，句子“在大多数情况下不使用物理转储，但使用逻辑转储”。逻辑转储（logicaldump）从一个或几个指定的目录开始，递归地转储自指定日期以来发生变化的文件和目录。因此，在逻辑转储中，转储磁盘上有一系列经过仔细识别的目录和文件，这使得根据请求恢复特定文件或目录变得容易。既然逻辑转储是最常用的方法，那么我们就来研究一下逻辑转储的一般算法。该算法广泛用于UNIX系统。待转储的文件系统如下图所示，方框代表目录，圆圈代表文件。以黄色列出的项目自上次转储以来已修改。每个目录和文件都标有其inode编号。该算法出于两个原因转储已修改文件或目录路径上的所有目录（以及未修改的目录）。第一个是在不同计算机的文件系统中恢复转储文件的能力。这样，转储和恢复程序可用于在两台计算机之间传输整个文件系统。第二个原因是能够执行单个文件的增量恢复。逻辑转储算法需要维护一个由inode索引的位图（bitmap），每个inode包含若干位。随着算法的进行，位图中的这些位被设置或清除。算法的执行分为四个阶段。第一阶段从起始目录（本例中为根目录）开始，检查其中的所有目录条目。对于每个修改过的文件，算法都会在位图中标记它的索引节点。该算法还标记并递归检查每个目录（修改或未修改）。在第一阶段结束时，所有被修改的文件和所有目录都被标记在位图中，如下图所示。理论上，第二阶段会再次递归遍历目录树，并删除目录树中任何不包含修改的文件。已删除的文件或目录的标记。该阶段的执行结果如下注意，inode号为10、11、14、27、29、30的目录因为内容没有被修改，所以没有被标记。他们也不倾倒。相反，索引节点编号为5和6的目录本身会被转储，即使它们没有被修改，因为需要此信息来恢复新机器上当天的修改。为了提高算法的效率，目录树遍历的两个阶段可以合二为一。现在我们知道了哪些目录和文件必须转储，这就是上图b中标记的内容。第三阶段算法将按照节点号的顺序扫描这些inode，并转储所有标记为转储的目录。为了如下所示的恢复目的，每个转储目录都以目录的属性（所有者、时间）为前缀。最后，在第四阶段，上面标记的文件也被转储，同样以它们的文件属性为前缀。至此，转储结束。从转储磁盘恢复文件系统非常简单。最初，需要在磁盘上创建一个空文件系统。然后恢复最近的完整转储。由于目录首先出现在磁带上，因此首先恢复目录，给出文件系统的框架，然后恢复文件系统本身。完整存储之后是第一次增量存储，然后是第二次重复该过程，依此类推。逻辑存储虽然很简单，但是也有一些棘手的问题。首先，由于空闲块列表不是文件，因此需要在所有转储文件恢复后从头开始重建。另一个问题是关于链接。如果一个文件链接了两个或多个目录，而该文件只能恢复一次，那么指向该文件的所有目录都必须恢复。另一个问题是UNIX文件实际上包含许多漏洞。打开一个文件，写入几个字节，在文件中找到偏移一定距离的地址，写入更多的字节是合法的。但是中间的这些块不属于文件本身，因此不应该在文件上转储和恢复。最后，“特殊文件、命名管道等”不应该被转储，无论它们属于哪个目录。四、文件系统的一致性影响可靠性的一个因素是文件系统的一致性。许多文件系统读取磁盘块，修改磁盘块，然后将它们写回磁盘。如果系统在写入所有块之前崩溃，文件系统将处于不一致状态。如果一些没有被写回的块是inode块、目录块或包含空闲列表的块，这个问题会很严重。为了处理文件系统一致性问题，大多数计算机都有检查文件系统一致性的应用程序。比如UNIX有fsck；Windows有sfc，它可以在系统启动时运行（尤其是在崩溃后）。可以进行两种一致性检查：“块一致性检查和文件一致性检查”。为了检查块的一致性，应用程序构建了两个表，每个块包含一个计数器，初始设置为0。第一个表中的计数器跟踪块在文件中出现的次数，第二个表中的计数器记录每个块出现的频率块出现在空闲列表中，空闲位图。然后验证器使用原始设备读取所有索引节点，忽略文件的结构，并简单地返回从零开始的所有磁盘块。从inode开始，很容易找到文件中的块数。每当读取一个块时，第一个表中的块计数器为+1，应用程序检查空闲块或位图以找到未使用的块。空闲列表中的每个块都会导致其在第二个表中的计数器递增。如果文件系统是一致的，那么每个块要么在第一个表中的计数器为1，要么在第二个表中的计数器为1，如下图所示。但是当系统崩溃时，这两个表可能看起来像下面这样。其中，Diskblock2没有出现在任何一个表中，称为缺失块。虽然块丢失并没有真正的危害，但它确实会浪费磁盘空间并减少磁盘容量。丢失块的问题很容易解决，文件系统验证器只是将它们添加到空闲列表中。还有一种可能的情况是block4在freelist中出现了2次。这个解决办法也很简单，只要重新建立freelist即可。最坏的情况是同一个数据块出现在两个或多个文件中，如下图，比如上图中的磁盘块5，如果其中一个文件被删除，块5会被添加到空闲列表中，导致一个块同时处于使用和空闲两种状态。如果删除这两个文件，那么这个磁盘块就会在空闲列表中出现两次。文件系统检查器首先分配一个磁盘块，将块5的内容复制到一个空闲块中，然后将其插入到其中一个文件中。文件的内容没有改变。虽然内容肯定是错误的，但至少保证了文件的一致性。这个错误应该报告给用户，用户可以检查情况。除了检查每个磁盘块计数的正确性外，文件系统还检查目录系统。这个时候会用到一个计数器表，但是这个时候一个文件（不是块）对应一个计数器。该程序从根目录开始检查并沿着目录树向下走，检查文件系统中的每个目录。对于目录中的每个文件，使其计数+1。请注意，由于硬链接，一个文件可能会出现在两个或多个目录中。但是遇到符号链接是不计数的，目标文件的计数器不会+1。验证程序完成后，会得到一个由inode索引的表，表示每个文件和目录的包含关系。验证器将这些数字与存储在文件inode中的链接数进行比较。如果inode节点的链接数大于目录项数，即使删除了目录中的所有文件，计数仍然不为0，inode也不会被删除。这种错误并不严重，但是由于存在不属于任何目录的文件而浪费磁盘空间。另一种错误是潜在的风险。如果同一个文件链接了两个目录项，但inode链接计数仅为1，则删除任何一个目录项，对应的inode链接计数变为0。当inode计数达到0时，文件系统将inode标记为未使用并释放所有块。这将导致其中一个目录指向一个未使用的inode，其块很可能会立即分配给其他文件。5、文件系统性能访问磁盘的效率比内存慢很多。是时候再次展示这张图了。从内存中读取一个32位的字大约需要10ns，从硬盘读取速率大约为100MB/S。对于32位字，效率会慢四倍。此外，还会增加其他损失，例如5-10毫秒的寻道时间。如果只访问一个字，内存将比磁盘快数百万个数量级。因此，磁盘优化是必要的。下面我们将讨论几种优化方法1.缓存减少磁盘访问次数最常用的技术是使用块缓存或缓冲区缓存。缓存是指逻辑上属于磁盘但实际上出于性能原因保留在内存中的一系列块。有不同的算法来管理缓存。常用的算法是：检查所有的读请求，看需要的块是否在缓存中。如果存在，则无需访问磁盘即可执行读取操作。如果校验块已经不在缓存中，则先将其读入缓存，再复制到需要的地方。之后，对同一个块的请求都通过缓存完成。缓存的操作如下图所示。由于缓存中有很多块，因此需要一些方法来快速判断所需的块是否存在。一种常见的方法是对设备和磁盘地址进行哈希处理，然后在哈希表中查找结果。具有相同哈希值的块在一个链表中链接在一起（这个数据结构看起来是不是很像一个HashMap？），这样就可以沿着冲突链查找其他块。如果缓存已满，此时需要传输新的块，则必须将原块传输出缓存。如果要传输的块自上次传输以来已被修改，则需要将其写回磁盘。这种情况与分页非常相似。我们之前已经介绍了所有常用的页面替换算法。不熟悉的可以参考https://mp.weixin.qq.com/s/5-k2BJDgEp9symxcSwoprw。比如“FIFO算法、SecondChance算法、LRU算法、时钟算法、老化算法等”。它们都适用于缓存。2.块预读文件系统性能的第二个明显改进是尽量在需要块之前将块提前写入缓存，从而提高命中率。许多文件是顺序读取的。如果请求文件系统在文件中生成块k，文件系统执行操作，完成后检查缓存以查看块k+1是否已经在缓存中。如果不是，文件系统会安排k+1次预读，因为文件希望在使用该块时直接从缓存中读取该块。当然，块预读策略只适用于真正顺序读取的文件。对于随机访问的文件，预读无效。甚至可能成为障碍。3.减少磁盘臂运动缓存和块预读并不是提高文件系统性能的唯一途径。另一个重要的技术是“将可能被顺序访问的块放在一起，最好放在同一个柱面上，以减少磁盘臂移动的次数”。写入输出文件时，文件系统必须根据需要一次分配一个磁盘块。如果使用位图来记录空闲块，并且整个位图都在内存中，那么很容易选择离前一个块最近的空闲块。如果使用空闲链表，并且链表的一部分存储在磁盘上，那么分配相邻的空闲块就会困难得多。然而，块聚类技术甚至可以用于空闲列表。也就是说，不使用块，而是使用连续块的簇来跟踪磁盘存储。如果一个扇区有512字节，有可能系统使用了1KB的块（2个扇区），却以2个块（4个扇区）为单位分配磁盘存储。这与2KB磁盘块不同，因为它仍然在缓存中使用1KB块，磁盘和内存之间的数据传输也以1KB完成，但在空闲系统上，文件是顺序读取的，寻道次数可以减少了一半，大大提高了文件系统的性能。如果考虑旋转定位，可以获得此类方法的变体。分配块时，系统会尝试将连续的块存储在同一柱面上的文件中。使用inode或任何类似于inode的系统的另一个性能瓶颈是读取一个非常短的文件还需要两次磁盘访问：“一次用于inode，一次用于块”。通常情况下，inode的放置如下图所示，所有的inode都靠近磁盘的开头放置，所以一个inode和它指向的block的平均距离是柱面组的一半，这会花费很长时间求时间。一个简单的改进是将inode存储在磁盘的中间而不是开头，在这种情况下，inode和第一个块之间的寻道时间减半。另一种做法是：将磁盘分成多个柱面组，每个柱面组有自己的inode、数据块和空闲链表，如上图b所示。当然，只有当磁盘中有磁盘臂时，讨论寻道时间和自旋时间才有意义。如今，越来越多的计算机使用固态硬盘(SSD)。对于这些硬盘，由于采用了与闪存相同的制造技术，随机存取和顺序存取的传输速度比较接近，传统硬盘的很多问题都消失了。.但它也提出了新的问题。4、磁盘碎片整理操作系统初始安装后，会不断地创建和清除文件，因此磁盘会产生大量的碎片。创建文件时，它使用的块会分散在整个磁盘上，降低性能。删除文件后，回收磁盘块可能会造成空洞。可以通过移动文件使它们彼此相邻并将所有或至少大部分可用空间放在一个或多个大的连续区域中来恢复磁盘性能。Windows有一个程序碎片整理，正是这样做的。Windows用户会大量使用它，除了SSD。磁盘碎片整理程序将在文件系统上运行良好。Linux文件系统（尤其是ext2和ext3）由于选择磁盘块的方式，通常不像Windows那样难以进行碎片整理，因此很少需要手动进行碎片整理。此外，固态硬盘不受磁盘碎片的影响。其实对固态硬盘做磁盘碎片整理是画蛇添足，不仅不能提升性能，反而会磨损固态硬盘。所以碎片整理只会缩短SSD的寿命。
