[6.S081]journal-design论文翻译 原文journal-designIntroduction文件系统是任何现代操作系统的核心部分，人们期望它们既快速又极其可靠。然而，问题仍然会发生，机器可能会因为硬件、软件或电源故障而意外宕机。在意外重启之后，系统可能需要一段时间才能将其文件系统恢复到一致状态。随着磁盘容量的增长，这段时间可能成为一个严重问题，导致系统下线一小时甚至更长时间，因为磁盘需要进行扫描、检查和修复。尽管磁盘驱动器每年都在变得更快，但与它们巨大的容量增加相比，这种速度增长是适度的。不幸的是，每个磁盘容量翻倍都会导致使用传统文件系统检查技术时恢复时间翻倍。在系统可用性至关重要的情况下，这可能是无法割舍的时间，因此需要一种机制来避免每次机器重启时都需要昂贵的恢复阶段。What’s in a filesystem?任何文件系统都需要满足一定的功能要求，这些要求通常由文件系统所服务的操作系统所决定。文件系统在应用程序中的表现方式是其中之一，操作系统通常要求文件名遵循特定的约定，并且文件具有特定的属性，这些属性以特定的方式进行解释。然而，文件系统的许多内部方面并没有受到如此严格的限制，文件系统的实现者可以在一定程度上自由设计。数据在磁盘上的布局（或者在非本地文件系统的情况下，可能是网络协议）、内部缓存的详细信息以及用于调度磁盘I/O的算法，这些都是可以在不必违反文件系统应用程序接口规范的情况下进行更改的事项。我们选择一种设计而不是另一种设计的原因有很多。与旧文件系统的兼容性可能是一个问题：例如，Linux提供了UMSDOS文件系统，它在标准的MSDOS磁盘文件结构之上实现了POSIX文件系统的语义。在尝试解决Linux上长时间文件系统恢复时间的问题时，我们牢记了一些目标：使用新文件系统不应严重影响性能；不得破坏与现有应用程序的兼容性；文件系统的可靠性不得以任何方式受损。Filesystem Reliability在谈论文件系统可靠性时，有许多问题需要考虑。针对这个特定项目，我们主要关注在文件系统崩溃时能够可靠地恢复内容的可靠性，我们可以确定以下几个方面：保护性：在崩溃之前在磁盘上稳定的数据绝不能受到损坏。显然，正在写入磁盘的文件在崩溃时不能保证完全完好，但是任何已经安全保存在磁盘上的文件都不能被恢复系统触及。可预测性：我们需要可预测的故障模式，以便可靠地进行恢复。原子性：许多文件系统操作需要完成大量单独的IO操作。一个很好的例子是将文件从一个目录重命名为另一个目录。如果这种文件系统操作在磁盘上完全完成或在恢复完成后完全撤销，那么恢复就是原子的。（例如，在重命名示例中，恢复应该在崩溃后将旧文件名或新文件名提交到磁盘，但不应同时存在两者。）Existing implementationsLinux的ext2fs文件系统提供了保护性恢复，但是它是非原子的且不可预测的。实际上，可预测性是一个比表面看起来更复杂的属性。为了能够可靠地在崩溃后清理，恢复阶段必须能够确定在磁盘上遇到不一致性的情况下文件系统当时正在尝试做什么。一般来说，这需要文件系统在单个更新操作更改多个磁盘块时以可预测的顺序将其写入磁盘。有许多实现磁盘写入顺序的方法。最简单的方法是在提交下一个写入设备驱动程序之前等待第一个写入完成，即“同步元数据更新”方法。这是BSD快速文件系统采用的方法，它出现在4.2BSD中，启发了许多后来的Unix文件系统，包括ext2fs。然而，同步元数据更新的主要缺点是其性能。如果文件系统操作需要等待磁盘IO完成，那么我们就无法将多个文件系统更新批量写入单个磁盘。例如，如果我们在同一个目录块上创建了十几个目录条目，那么同步更新要求我们将该块分别写回磁盘十几次。有几种方法可以解决这个性能问题。一种保持磁盘写入顺序的方法，而不必等待IO完成，是在内存中维护磁盘缓冲区之间的顺序，并确保当我们最终写回数据时，直到所有前置块都安全地写入磁盘后，我们才写入一个块，即“延迟有序写入”技术。延迟有序写入的一个复杂之处在于很容易陷入缓存缓冲区之间存在循环依赖的情况。例如，如果我们试图在两个目录之间重命名文件，并同时将另一个文件从第二个目录重命名到第一个目录，则最终会出现两个目录块互相依赖的情况：在另一个目录块写入磁盘之前，不能将任何一个目录块写入磁盘。Ganger的“软更新”机制巧妙地避开了这个问题，如果在我们第一次尝试将缓冲区写入磁盘时，仍存在未解决的依赖关系，则有选择地回滚缓冲区内特定的更新。一旦所有依赖关系都得到满足，缺失的更新将稍后恢复。这使我们能够按任意顺序写出缓冲区，即使存在循环依赖。软更新机制已被FreeBSD采用，并将作为其下一个主要内核版本的一部分提供。然而，所有这些方法都存在一个共同的问题。尽管它们确保整个文件系统操作过程中磁盘的状态是可预测的，但恢复过程仍然需要扫描整个磁盘才能找到并修复任何未完成的操作。恢复变得更可靠，但不一定更快。然而，可以通过不牺牲可靠性和可预测性来加速文件系统恢复。这通常是由保证文件系统更新原子完成的文件系统来实现的（在这些系统中，单个文件系统更新通常称为事务）。原子更新背后的基本原理是，文件系统可以将一整批新数据写入磁盘，但是这些更新在进行最终提交更新之前不会生效。如果提交涉及将单个块写入磁盘，则崩溃只能导致两种情况：要么已经将提交记录写入磁盘，此时可以假定所有已提交的文件系统操作在磁盘上都是完整和一致的；要么提交记录丢失，在这种情况下，我们必须忽略由于崩溃时尚未提交的部分不完整更新而导致的任何其他写入。这自然需要文件系统更新将更新数据的旧版本和新版本都保留在磁盘上的某个地方，直到提交时刻。实现这一点有多种方法。在某些情况下，文件系统将更新数据的新副本保存在与旧副本不同的位置，并且一旦更新被提交到磁盘，就会最终重新使用旧空间。Network Appliance的WAFL文件系统采用了这种方法，它通过维护一个可以通过简单地将树节点复制到新位置并然后在树的根部更新一个磁盘块来以原子方式更新树形文件系统数据。日志结构文件系统通过将所有文件系统数据（包括文件内容和元数据）连续写入磁盘流（“日志”）来实现相同的目的。使用这种方案查找数据的位置可能比传统文件系统更复杂，但是日志具有一个很大的优势，即相对容易在日志中放置标记，以指示在某个点之前所有数据都已提交并且在磁盘上一致。由于日志的性质使得大多数写入以连续的流进行且无需磁盘寻道，因此写入这样的文件系统特别快。许多文件系统都是基于这种设计编写的，包括Sprite LFS和Berkeley LFS。Linux上也有一个原型LFS实现。最后，还有一类原子更新的文件系统，其中未完成更新的旧版本和新版本通过将新版本写入磁盘上的不同位置来保留，直到更新提交为止。提交后，文件系统可以将更新后的磁盘块的新版本写回磁盘上的原位置。这就是“日志”（有时称为“日志增强”）文件系统的工作方式。当更新磁盘上的元数据时，更新将记录在保留用作日志的磁盘的单独区域中。完成的文件系统事务将在日志中添加一个提交记录，只有在提交安全写入磁盘后，文件系统才能将元数据写回其原始位置。事务是原子的，因为在崩溃后我们总是可以根据日志是否包含事务的提交记录来撤消事务（丢弃日志中的新数据）或重做事务（将日志副本复制回原始副本）。许多现代文件系统都采用了此设计的变体。Designing a new filesystem for Linux这种针对Linux的新文件系统设计的主要动机是消除崩溃后长时间的文件系统恢复时间。因此，我们选择了文件系统日志记录方案作为工作的基础。日志记录通过始终记录磁盘上潜在不一致的所有数据到日志中，实现了快速的文件系统恢复。因此，文件系统恢复可以通过扫描日志并将所有已提交的数据复制回主文件系统区域来实现。这样做是快速的，因为日志通常远小于完整的文件系统。它只需要足够大的空间来记录几秒钟的未提交更新。选择日志记录还有另一个重要优势。与传统文件系统不同，日志记录文件系统将临时数据保存在新位置，与磁盘上的永久数据和元数据无关。因此，这种文件系统不要求永久数据以任何特定方式存储。特别是，可以在新文件系统中使用ext2fs文件系统的磁盘结构，并将现有的ext2fs代码用作日志记录版本的基础。因此，我们并不是为Linux设计一个新的文件系统。相反，我们正在向现有的ext2fs添加一个新功能——事务性文件系统日志记录。Anatomy of a transaction在考虑日志记录文件系统时的一个核心概念是事务，对应于文件系统的单个更新。每个应用程序发出的单个文件系统请求都会导致一个事务，其中包含由该请求产生的所有已更改的元数据。例如，对文件的写入将导致对磁盘上文件inode中的修改时间戳的更新，并且如果写入扩展了文件，则可能还会更新长度信息和块映射信息。如果为文件分配了新的块，那么配额信息、空闲磁盘空间和已使用块位图都必须更新，并且所有这些都必须记录在事务中。在事务中还有另一个隐藏的操作，我们必须意识到。事务还涉及读取文件系统的现有内容，这就对事务之间的顺序产生了约束。修改磁盘上的块的事务不能在读取该新数据并根据读取的内容更新磁盘的事务之后提交。即使这两个事务永远不会尝试将相同的块写回，依赖关系仍然存在——想象一下一个事务从目录中的一个块中删除一个文件名，另一个事务将相同的文件名插入到不同的块中。这两个操作可能不会在它们写入的块中重叠，但是第二个操作仅在第一个操作成功后才有效（违反此规则会导致重复的目录条目）。最后，还有一个超出元数据更新顺序的排序要求。在我们可以提交为文件分配新块的事务之前，我们必须确保该事务创建的所有数据块实际上已经被写入磁盘（我们将这些数据块称为依赖数据）。忽略此要求实际上不会损害文件系统的元数据的完整性，但可能导致在崩溃恢复后新文件仍然包含之前的文件内容，这既是安全风险也是一致性问题。Merging transactions许多日志记录文件系统中使用的术语和技术都来自数据库领域，在那里，日志记录是确保复杂事务的原子提交的标准机制。然而，传统数据库事务与文件系统之间存在许多差异，其中一些差异使我们能够大大简化事务处理。最大的两个差异之一是文件系统没有事务中止，而且所有文件系统事务都相对短暂。在数据库中，有时我们希望在事务进行到一半时中止事务，放弃我们到目前为止所做的任何更改，但是在ext2fs中并非如此——在我们开始对文件系统进行任何更改之前，我们已经检查了更改是否可以合法完成。在开始写入更改之前中止事务（例如，如果创建文件操作发现同名文件已存在，则可能中止事务）并不会造成问题，因为在这种情况下，我们可以简单地提交没有更改的事务并达到相同的效果。第二个差异——文件系统事务的短生命周期——很重要，因为它意味着我们可以极大地简化事务之间的依赖关系。如果我们必须处理一些非常长期的事务，那么我们需要允许事务以任何顺序独立提交，只要它们不互相冲突，否则单个搁置的事务可能会拖慢整个系统。然而，如果所有事务都足够快，则我们可以要求事务以严格的顺序顺序提交到磁盘，而不会显著影响性能。有了这个观察结果，我们可以对事务模型进行简化，从而大大减少实现的复杂性，同时提高性能。与其为每个文件系统更新创建一个单独的事务，我们简单地每隔一段时间创建一个新事务，并允许所有文件系统服务调用将它们的更新添加到该单一的系统级合并事务中。这种机制有一个很大的优点。因为合并事务中的所有操作将一起提交到日志中，所以我们不必为非常频繁更新的任何元数据块编写单独的副本。特别是对于创建新文件等操作，通常每次对文件的写入都会导致文件被扩展，从而连续更新相同的配额、位图块和inode块。在合并事务的生命周期内多次更新的任何块只需要提交一次到磁盘即可。关于何时提交当前合并事务并启动新事务的决定是一项策略决策，应该由用户控制，因为它涉及影响系统性能的权衡。提交等待时间越长，日志中就可以合并更多的文件系统操作，因此长期来说需要的IO操作就越少。然而，较长的提交会占用更多的内存和磁盘空间，并且在发生崩溃时留下更大的丢失更新的时间窗口。它们还可能导致磁盘活动风暴，使文件系统的响应时间不太可预测。On-disk representation日志记录的ext2fs文件系统在磁盘上的布局将完全与现有的ext2fs内核兼容。传统的UNIX文件系统通过将每个文件与磁盘上的唯一编号的inode关联来存储数据，并且ext2fs设计已经包含了一些预留的inode编号。我们使用其中一个保留的inode来存储文件系统的日志，除此之外，在所有其他方面，文件系统将与现有的Linux内核兼容。现有的ext2fs设计包括一组兼容性位图，其中的位可以设置为指示文件系统使用某些扩展功能。通过为日志记录扩展功能分配一个新的兼容性位，我们可以确保即使旧内核能够成功挂载新的、带有日志记录的ext2fs文件系统，它们也将被禁止以任何方式对文件系统进行写入。Format of the filesystem journal日志文件的工作很简单：在我们提交事务的过程中，它记录文件系统元数据块的新内容。日志的唯一其他要求是我们必须能够以原子方式提交其中包含的事务。我们向日志中写入三种不同类型的数据块：元数据块、描述符块和头部块。日志元数据块包含一个事务更新后文件系统元数据单个块的完整内容。这意味着无论我们对文件系统元数据块进行多么小的更改，我们都必须写入一个完整的日志块以记录更改。然而，出于以下两个原因，这实际上相对廉价：日志写入通常很快，因为大多数写入日志的操作都是顺序的，并且我们可以轻松地将日志IO批处理成大型簇，以便磁盘控制器有效处理；通过将来自文件系统缓存的更改的整个元数据缓冲区的内容写入日志，我们避免了在日志记录代码中进行大量的CPU工作。Linux内核已经为我们提供了一种非常高效的机制，用于将缓冲区缓存中现有块的内容写入到磁盘的其他位置。每个缓冲区在缓冲区缓存中都由一个称为buffer_head的结构描述，其中包括有关将缓冲区的数据写入的磁盘块的信息。如果我们想要将整个缓冲区块写入到新位置而不干扰buffer_head，我们只需创建一个新的临时buffer_head，将描述从旧缓冲区块复制到其中，然后编辑临时buffer_head中的设备块编号字段，以指向日志文件内的一个块。然后，我们可以直接将临时buffer_head提交给设备IO系统，并在IO完成后丢弃它。描述符块是描述其他日志元数据块的日志块。每当我们要将元数据块写入日志时，我们都需要记录元数据通常位于的磁盘块，以便恢复机制可以将元数据复制回主文件系统。在日志中的每组元数据块之前都会写入一个描述符块，其中包含要写入的元数据块数以及它们的磁盘块编号。描述符块和元数据块都按顺序写入日志，每当我们到达日志末尾时，就重新从日志开头开始写入。始终保持日志的当前头（最后一个写入的块的块编号）和尾部（日志中未被取消固定的最旧块，如下所述）。每当我们用完日志空间时（即日志的头已经循环回到尾部并赶上尾部），我们会暂停新的日志写入，直到日志的尾部已经清理并释放更多空间。最后，日志文件包含一些位于固定位置的头部块。这些记录了日志的当前头和尾部，以及一个序列号。在恢复时，将扫描头部块以找到具有最高序列号的块，并且在恢复过程中扫描日志时，我们只需从记录在该头部块中的尾部到头部的所有日志块。Committing and checkpointing the journal在某个时刻，要么是因为距上次提交已经等待了足够长的时间，要么是因为日志空间不足，我们将希望将未处理的文件系统更新作为一个新的复合事务提交到日志中。一旦复合事务完全提交，我们还没有完成它。我们需要跟踪记录在事务中记录的元数据缓冲区，以便我们可以注意到它们何时被写回到磁盘上的主要位置。回想一下，当我们提交一个事务时，新的更新后的文件系统块位于日志中，但尚未同步回它们在磁盘上的永久位置（我们需要保持旧块未同步，以防在提交日志之前崩溃）。一旦日志已提交，磁盘上的旧版本就不再重要了，我们可以在自己方便的时候将缓冲区写回其主位置。然而，在我们完成同步这些缓冲区之前，我们不能删除日志中的数据副本。要完全提交和完成事务的检查点，我们需要经历以下阶段：关闭事务。此时，我们创建一个新的事务，在其中记录将来开始的任何文件系统操作。任何现有的、未完成的操作仍将使用现有的事务：我们不能将单个文件系统操作分割成多个事务！开始将事务刷新到磁盘。在单独的日志写入内核线程的上下文中，我们开始写入由事务修改的所有元数据缓冲区到日志中。在这个阶段，我们还必须写入任何相关的数据（参见上文中的事务解剖）。当一个缓冲区被提交时，将其标记为固定在事务中，直到它不再是脏的（它已通过常规的写回机制写回到主存储中）。等待此事务中所有未完成的文件系统操作完成。我们可以在所有操作完成之前安全地开始写入日志，并且允许这两个步骤在某种程度上重叠会更快。等待所有未完成的事务更新完全记录在日志中。更新日志头块以记录日志的新头和尾部，将事务提交到磁盘。写入事务的更新缓冲区到日志时，我们标记它们为在日志中固定该事务。只有当缓冲区被同步到其磁盘上的主位置时，它们才会变为未固定。只有当事务的最后一个缓冲区变为未固定时，我们才能重新使用事务占用的日志块。当发生这种情况时，再次写入一组日志头，记录日志尾的新位置。现在释放的空间可以被稍后的事务重用。Collisions between transactions为了提高性能，在提交事务时，我们并不完全暂停文件系统更新。相反，我们创建一个新的复合事务，用于记录在提交旧事务时到达的更新。这就引出了一个问题：如果一个更新要访问已经由另一个正在提交的较旧事务拥有的元数据缓冲区，该怎么办呢？为了提交旧事务，我们需要将其缓冲区写入日志，但我们不能在该写入中包含任何不属于该事务的更改，因为这将允许我们提交不完整的更新。如果新事务只想读取相关缓冲区，那么就没有问题：我们已经在两个事务之间创建了一个读/写依赖关系，但由于复合事务始终按严格的顺序提交，我们可以安全地忽略这种冲突。如果新事务想要写入缓冲区，则情况就更复杂了。我们需要旧缓冲区的副本来提交第一个事务，但我们又不能让新事务在修改缓冲区时继续进行。解决方案是在这些情况下制作缓冲区的新副本。一个副本提供给新事务进行修改。另一个副本仍由旧事务拥有，并将像往常一样提交到日志中。一旦该事务提交，这个副本就会被简单地删除。当然，我们不能在这个缓冲区安全地记录到文件系统其他位置之前回收旧事务的日志空间，但由于该缓冲区必须被提交到下一个事务的日志记录中，这是自动处理的。Project status and future work这仍然是一个正在进行的工作。最初实现的设计稳定且简单，我们不认为需要进行重大的设计修订才能完成实现。上文描述的设计相对直接，除了处理日志文件管理、缓冲区与事务之间的关联以及在非正常关闭后恢复文件系统的代码外，对现有的 ext2fs 代码需要进行的修改很少。一旦我们有一个稳定的代码库进行测试，我们可以在许多可能的方向上扩展基本设计。其中最重要的是调整文件系统性能。这将需要我们研究日志系统中的任意参数对性能的影响，如提交频率和日志大小。这还将涉及研究瓶颈，以确定通过对系统设计进行修改是否可能改进性能，并且已经提出了几个可能的扩展设计。一个研究领域可能是考虑压缩日志更新。当前的方案要求我们将整个元数据块写入日志，即使只修改了块中的一个位也是如此。我们可以通过仅记录缓冲区中的更改值而不是完全记录缓冲区来轻松压缩这样的更新。然而，目前尚不清楚这是否会带来任何重大的性能优势。当前的方案对于大多数写操作不需要进行内存到内存的复制，这在CPU和总线利用率方面是一个很大的性能优势。由于写出整个缓冲区产生的IO操作是廉价的 - 更新是连续的，在现代磁盘IO系统上，它们直接从主存储器传输到磁盘控制器，而无需通过缓存或CPU。另一个重要的可能的扩展领域是支持快速 NFS 服务器。NFS 设计允许客户端在服务器崩溃时优雅地恢复：客户端将在服务器重新启动时重新连接。如果发生这样的崩溃，则服务器尚未安全写入磁盘的任何客户端数据都将丢失，因此 NFS 要求服务器在将客户端的文件系统请求提交到服务器的磁盘之前不得确认其完成。这对于支持通用目的的文件系统来说可能是一个尴尬的特性。NFS 服务器的性能通常是通过对客户端请求的响应时间来衡量的，如果这些响应必须等待文件系统更新同步到磁盘，那么整体性能将受到在磁盘上的文件系统更新延迟的限制。这与文件系统的大多数其他用途相反，在这些用途中，性能是根据缓存更新的延迟而不是磁盘上的更新延迟来衡量的。有一些文件系统专门设计来解决这个问题。WAFL 是一种基于事务的树型文件系统，可以在磁盘的任何位置写入更新，但是 Calaveras 文件系统通过使用类似于上文提出的日志的方式达到相同的目标。区别在于 Calaveras 为每个应用程序文件系统请求在日志中记录一个单独的事务，从而尽快在磁盘上完成单个更新。提议的 ext2fs 日志记录中的提交批处理牺牲了快速提交以获得吞吐量，而代价是延迟（磁盘上的延迟被缓存的影响隐藏了）。ext2fs 日志记录可能使其更适合用于 NFS 服务器的两种方法可能是使用较小的事务和记录文件数据以及元数据。通过调整提交到日志的事务的大小，我们可能能够大幅改进提交单个更新的回转时间。NFS 还要求将数据写入磁盘尽快提交，原则上没有理由不扩展日志文件以涵盖普通文件数据的写入。最后，值得注意的是，这个方案中没有任何阻止我们将单个日志文件共享给几个不同的文件系统。在一个单独的完全为此目的保留的磁盘上允许多个文件系统记录日志几乎不需要额外的工作，而在有许多经历重负的日志文件系统的情况下，这可能会带来显著的性能提升。这个独立的日志磁盘几乎完全是顺序写入的，因此可以维持高吞吐量，而不会影响主文件系统磁盘上可用的带宽。Conclusions本文中概述的文件系统设计应该相对现有的 Linux 上的 ext2fs 文件系统提供显著优势。它应该通过使文件系统在崩溃后更可预测地和更快速地恢复来提高可用性和可靠性，并且在正常操作期间不会造成太大的性能损失。日常性能的最显著影响是，新创建的文件将需要迅速同步到磁盘，以便将创建操作提交到日志，而不是允许内核通常支持的数据延迟写回。这可能使得日志文件系统不适合在 /tmp 文件系统上使用。该设计应该对现有的 ext2fs 代码库需要进行最少的更改：大部分功能由一个新的日志机制提供，该机制将通过简单的事务缓冲区 IO 接口与主要的 ext2fs 代码进行交互。最后，这里提出的设计是基于现有的 ext2fs 磁盘文件系统布局的，因此可以向现有的 ext2fs 文件系统添加一个事务日志，利用新功能，而无需重新格式化文件系统。

[xv6]资源汇总 对xv6需要的资源做的集合

[xv6]Lab1-Utilities 开始6.S081的学习了，在这里记录下我对xv6的理解以及我的题解，这里我会尽可能详细的写。我写了我的代码实现，但是肯定是不完善的，所以你最好都自己写，你如果实在写不出来，可以评论一句 “看看代码”。{dotted startColor="#ff6c6c" endColor="#1989fa"/}环境安装这个照着官网的 教程 来就行，注意一下自己的linux版本（ubuntu20.04）。sleep (easy)因为不知道该怎么开始，所以这个我是直接看写好的，知道了怎么开始才能继续下边的任务对吧。就是调用提供的sleep接口就行。#include "kernel/types.h" #include "kernel/stat.h" #include "user/user.h" int main(int argc, char *argv[2]) { if (argc < 2) { fprintf(2, "usage sleep <ticks>\n"); exit(1); } sleep(atoi(argv[1])); exit(0); }pingpong (easy)这个任务要求我们利用管道在两个进程之间通信，最后实现这样的效果：{card-describe title="pingpong"}$ make qemu ... init: starting sh $ pingpong 4: received ping 3: received pong ${/card-describe}管道是一个小的内核缓冲区，它以文件描述符对的形式提供给进程，一个用于写操作，一个用于读操作。从管道的一端写的数据可以从管道的另一端读取。管道提供了一种进程间交互的方式。xv6中我们可以使用pipe()函数创建管道，提到这个我们要先了解一下文件描述符。具体请自行查阅xv6文档，简单来说就是在一个进程中一些读写等操作需要文件描述符来确定，比如read(0, buf,sizeof buf);这里的0就是代表从这个“0”处读取，或者说输入端是0绑定的文件（注意这个0是文件索引）。我们创建一个管道之后，这个管道也有他的文件描述符。例如int p[2];pipe(p);这个管道的文件描述符就被保存在了p数组中。p[0]是管道的读端口，p[1]是管道的写端口，有了管道的文件操作符我们就可以操作管道了。这个任务既可以用一个管道也可以用两个管道，两个管道更容易理清关系，记得关闭无用描述符，比如p1在process1只写那么就close(p1[1])等等，双管道双进程关系如图： 一个管道也可以做，我就是一个管道做的，这样做有没有什么风险我不知道，但是确实可以用。在我的理解中单管道是这样工作的：首先在process1中fork出process2。process2在read时如果p[0]没有接收到数据并且process1的p[1]也没有关闭，所以无论怎样process2都会等待接收process1的数据，process1传输ping之后close(p[1])，process2接收ping再输出，此时process1也会被read阻塞，直到process2传入pong，这样就保证了顺序即使只有一个管道也不会乱。隐藏内容，请前往内页查看详情primes (moderate)/(hard)这个任务是让我们写出素数筛，具体实现请思考这张图： 思考完了吗？那我来讲讲实现吧。 首先呢一个进程只会输出一个数，之后他会接收上一个进程中已经筛过数继续筛，上图的drop就是被筛掉的数，我们可以看到在输出2的进程中4、6、8...等所有2的倍数都被drop了，通过筛选的第一个数也就是3会进入新进程并输出，第二个数5因为不被3整除且是输出3的进程的第一个通过筛选的数所以他又进入了一个新进程并被输出...以此类推，就完成了素数筛选。 然后讲讲我的实现方法，我使用了一个id作为一个进程的标识，这个id代表通过了上一个进程筛选的第一个数也就是确认的素数。首先这个进程输出这个id，或者输出之后再创建进程随你，之后它接收通过了上一个进程的筛选的数并使用自己来筛选，比如2筛选4、6、8，3筛选9这些，如果这个数通过，那么就传给下一个进程，如果它是第一个通过的，那么优先为它创建新进程并以它命名id，这样的工作持续到上一个进程的管道的写端口关闭，那么我们就关闭进程，上边的进程wait之后也相继关闭。 这方面请了解read，write，wait等系统调用。 我的文字描述可能有点不清晰，那请看图，相信你可以看懂的（我是做的时候为了自己能理清所以画了这张图，第一次觉得流程图这么有用） {alert type="info"}写的时候请思考每个管道应该什么时候关闭，不然你可能会遇到许多想不明白的问题。{/alert}隐藏内容，请前往内页查看详情find (moderate)find 需要我们实现查找文件功能，但是会遍历给定文件夹的所有子孙文件夹（我自己起的名字），接着输出所有名称与给定名称的一样的文件。这个函数给出的提示是让我们看ls的实现源码，接下来我们就好好分析一下ls部分的源码。void ls(char *path) { char buf[512], *p; int fd; struct dirent de; struct stat st; if((fd = open(path, O_RDONLY)) < 0){ fprintf(2, "ls: cannot open %s\n", path); return; } if(fstat(fd, &st) < 0){ fprintf(2, "ls: cannot stat %s\n", path); close(fd); return; } switch(st.type){ case T_DEVICE: case T_FILE: printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size); break; case T_DIR: if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){ printf("ls: path too long\n"); break; } strcpy(buf, path); p = buf+strlen(buf); *p++ = '/'; while(read(fd, &de, sizeof(de)) == sizeof(de)){ if(de.inum == 0) continue; memmove(p, de.name, DIRSIZ); p[DIRSIZ] = 0; if(stat(buf, &st) < 0){ printf("ls: cannot stat %s\n", buf); continue; } printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size); } break; } close(fd); }这个是主体两个if里就是给文件描述符赋值并将文件的信息保存在stat中，在switch中如果给出的path不是文件夹那么就输出当前文件的一些信息，重点是在T_DIR中，while这里就是遍历了所有子文件。//通过while循环不断读取数据，我们可以看dirent的解释： Directory is a file containing a sequence of dirent structures. while(read(fd, &de, sizeof(de)) == sizeof(de)){ if(de.inum == 0) continue; memmove(p, de.name, DIRSIZ); p[DIRSIZ] = 0; if(stat(buf, &st) < 0){ printf("ls: cannot stat %s\n", buf); continue; } printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size); }知道了怎么遍历文件，剩下的就好做了，我们在遍历时候判断name是不是等于给定filename就行，当然如果是文件夹，那么我们进入这个文件夹再遍历，就是遇到文件就判断，遇到文件夹就递归，就完成了。隐藏内容，请前往内页查看详情xargs (moderate)这个我感觉比素数筛难，但是居然不带hard。首先呢，xargs就是执行它后边的程序也就是 xargs echo hello这样的，它接收管道的数据并加到hello之后，不过呢如果遇到换行\n，那就输出一行并继续执行相同操作，我这里描述的不太清晰，看个例子就明白了:echo hello\nworld | xargs echo say 这个不是很准确，因为\n会被识别成两个字符，但是我们假设这就是一个。程序是这样执行的：xargs echo say helloxargs echo say world看明白了吗？我们需要写一个字符串处理，就是把\n前和\n后的字符串分开，再用exec执行就行。通过分析，xargs的argv参数是这样的argv[0] = "xargs" argv[1] = "echo" argv[2] = "say"没有argv[3]，也就是说我们要使用read对文件操作符0进行读取，注意read读取一次只读取一个单词，所以我们还需要能读一整行的函数，不然还没读到\n就输出了不是？因为没有意识到read只读一个单词（或者说一直读到空格和换行）我这个做了很长时间但是找不到问题在哪，还有根据xv6book的描述，参数argv是根据argv==0结束的，在传参时候我们要注意这点。隐藏内容，请前往内页查看详情