5. Project 4: File Systems#

在前两个任务中，您广泛使用了文件系统而不必担心它的实现方式。在最后一次作业中，您将改善文件系统的实现。您将主要在“filesys”目录中工作.

您可以在项目2或项目3的基础上构建项目4。在任何一种情况下，项目2所需的所有功能都必须在文件系统提交中起作用。如果在项目3上构建，则所有项目3的功能也必须工作，并且需要编辑“`filesys /Make.vars”以启用VM功能。

5.1 Background#

5.1.1 New Code#

以下是一些您可能不熟悉的文件。这些都在“filesys”目录中，除非另有说明:

“fsutil.c”
可从内核命令行访问的文件系统简单实用程序。

“filesys.h”
“filesys.c”
文件系统的顶级接口。参见 3.1.2 使用文件系统.

“directory.h”
“directory.c”
将文件名转换为inode。目录数据结构存储为文件。

“inode.h”
“inode.c”
管理代表磁盘上文件数据布局的数据结构。

“file.h”
“file.c”
将文件读取和写入转换为磁盘扇区读取和写入。

“lib/kernel/bitmap.h”
“lib/kernel/bitmap.c”
位图数据结构以及用于将位图读写到磁盘文件的例程.

我们的文件系统具有类似Unix的界面，因此您可能还希望阅读Unix手册页，其中包括“create”，“open”，“close”，“read”，“write”，“seek”和“unlink”。我们的文件系统具有与此类似但不完全相同的调用。文件系统将这些调用转换为磁盘操作。

上面的代码中提供了所有基本功能，因此从一开始就可以使用文件系统，就像在前面两个项目中看到的那样。但是，它具有严格的限制，您将删除这些限制。

尽管您的大部分工作将在“filesys”中进行，但您应该准备好与之前的所有部分进行交互。

5.1.2 Testing File System Persistence#

到目前为止，您应该已经熟悉了运行Pintos测试的基本过程。如有必要，请参阅1.2.1 测试。

到目前为止，每个测试仅调用一次Pintos。但是，重要的是文件系统的目的是确保仍然可以从一个引导到另一个。因此，文件系统中的测试项目第二次调用Pintos。第二轮将所有文件系统中的文件和目录合并为单个文件，然后进行复制该文件从Pintos文件系统移入主机（Unix）文件系统.

评分脚本根据第二次运行中复制出的文件内容来检查文件系统的正确性。这意味着您的项目将无法通过任何扩展的文件系统测试，直到文件系统实现得足够好以支持tar为止。tar程序的要求很高（它需要可扩展的文件和子目录支持），因此这将需要一些工作。在此之前，您可以忽略“make check”中与提取的文件系统有关的错误。

顺便提一句，您可能已经猜到，用于复制文件系统内容的文件格式是标准的Unix “tar”格式。您可以使用Unixtar程序来检查它们。测试t的tar文件名为“t.tar”。

5.2 Suggested Order of Implementation#

为了使您的工作更轻松，我们建议按以下顺序实施该项目的各个部分：

Buffer cache (see section 5.3.4 Buffer Cache). 实现缓冲区高速缓存并将其集成到现有文件系统中。此时，来自项目2（以及项目3，如果您正在构建的项目）的所有测试仍应通过。
可扩展文件(请参阅5.3.2 索引文件和可扩展文件)。此步骤之后，您的项目应通过文件增长测试。
子目录（请参见5.3.3 子目录）。之后，您的项目应通过目录测试。
剩余的杂项。

如果临时固定新目录中的条目数，则可以并行实现可扩展文件和子目录。

您应该始终考虑同步。

5.3 Requirements#

5.3.1 Design Document#

在上交项目之前，必须将project 4设计文档模板复制到源代码树中，名称为“pintos/src/filesys/DESIGNDOC”并填写我们建议您在开始进行项目之前阅读设计文档模板。请参阅[D. 项目文档]，以获得与虚拟项目一起提供的示例设计文档。

5.3.2 Indexed and Extensible Files#

基本文件系统将文件分配为单个扩展区，从而使其容易受到外部碎片的影响，也就是说，即使 n ，也可能无法分配 n 块文件块是free的。通过修改磁盘上的inode结构消除此问题。实际上，这可能意味着使用具有直接，间接和双重间接块的索引结构。欢迎您选择其他方案，只要您在设计文档中解释了方案的基本原理，并且方案不会受到外部碎片的影响（就像我们提供的基于扩展的文件系统一样）。

您将在最后一个任务的基础上建立此任务。测试程序项目2中的内容也应与项目3中的内容一起使用。开始进行之前，请先修复您的Project2提交中的所有错误项目3，因为这些错误很可能会在项目3引起相同的问题。

您可以假设文件系统分区不会大于8MB。你必须支持与分区一样大的文件（减去元数据）。每个索引节点是存储在一个磁盘扇区中，限制了它的块指针数量可以包含。支持8MB的文件将需要您实施二次间接块。

基于扩展盘区的文件只有在其后跟空白空间时才能增长，但是只要有可用空间，索引索引节点就可以使文件增长成为可能可用。实现文件增长。在基本文件系统中，文件创建文件时指定大小。在最现代的文件中系统，最初创建的文件大小为0，然后展开每次从文件末尾进行写操作。您的文件系统必须允许这一点。

文件的大小应该没有预定的限制，除非文件不能超过文件系统的大小（减去元数据）。这也适用于根目录文件，现在应该允许它扩展到超过其初始限制的16个文件。

允许用户程序查找超出当前文件结尾（EOF）的范围。搜索本身不会扩展文件。在超出EOF的位置进行写入会将文件扩展到要写入的位置，并且先前EOF与写入开始之间的任何间隙都必须用零填充。从EOF之后的位置开始的读取不返回任何字节。

写入超出EOF可能导致许多块完全为零。一些文件系统为这些隐式分配和写入实际数据块调零的块。其他文件系统根本不分配这些块直到明确编写它们为止。据说后者是文件系统支持“稀疏文件”。您可以采用以下任一种分配策略您的文件系统。

5.3.3 Subdirectories#

实现一个分层的名称空间。在基本文件系统中，所有文件位于单个目录中。修改它以允许目录指向文件或其他目录的条目。

确保目录可以像其他任何文件一样扩展超出其原始大小。

基本文件系统的文件名限制为14个字符。您可以选择保留单个文件名组件的此限制，也可以扩展该限制。您必须允许完整路径名长于14个字符。

为每个进程维护一个单独的当前目录。在启动时，将根目录设置为初始进程的当前目录。当一个进程通过exec系统调用启动另一个进程时，子进程将继承其父进程的当前目录。之后，两个进程的当前目录是独立的，因此更改其自己的当前目录不会对另一个进程产生影响。（这就是为什么在Unix下cd命令是内置的Shell，而不是外部程序的原因。）

更新现有的系统调用，以便在调用方提供文件名的任何地方，都可以使用绝对或相对路径名。目录分隔符为正斜杠（“/”）。您还必须支持特殊文件名“.”和“..”，它们的含义与Unix中的含义相同。

更新open系统调用，以便它也可以打开目录。在现有的系统调用中，只有close才需要接受目录的文件描述符。

更新remove系统调用，以便它除常规文件外还可以删除空目录（除根目录外）。如果目录不包含任何文件或子目录（“.”和“..”除外），则只能将其删除。您可以决定是否允许删除由进程打开或用作进程当前工作目录的目录。如果允许，则必须禁止尝试打开文件（包括“.”和“..”）或在已删除目录中创建新文件。

实施以下新的系统调用：

System Call: bool chdir (const char *dir)
将进程的当前工作目录更改为dir，该目录可以是相对的也可以是绝对的。如果成功，则返回true，失败则返回false。

System Call: bool mkdir (const char *dir)
创建名为dir的目录，该目录可以是相对的也可以是绝对的。如果成功，则返回true，失败则返回false。如果 dir已经存在，或者dir中除最后一个目录之外的任何目录名都不存在，则失败。也就是说，仅当“/a/b”已经存在而“/a/b/c”不存在时，“mkdir(“/a/b/c”)`才会成功。

System Call: bool readdir (int fd, char *name)
+ 从文件描述符fd中读取目录条目，该描述符必须代表目录。如果成功，则将以空值结尾的文件名存储在name中，该文件名必须具有“READDIR_MAX_LEN + 1”字节的空间，并返回true。如果目录中没有任何条目，则返回false。

“readdir”不应返回“.”和“..”。
如果目录在打开时发生更改，则可以完全不读取或多次读取某些条目。否则，每个目录条目应以任何顺序读取一次。
READDIR_MAX_LEN是在lib/user/syscall.h中定义的。如果文件系统支持的文件名比基本文件系统长，则应将此值从默认值14增加。

System Call: bool isdir (int fd)
如果fd代表目录，则返回true；如果它代表普通文件，则返回false。

System Call: int inumber (int fd)
+ 返回与fd关联的inode的inode号，它可以表示普通文件或目录。

索引节点号永久标识文件或目录。在文件存在期间，它是唯一的。在Pintos中，索引节点适合用作索引节点号。

我们提供了ls和mkdir用户程序，一旦实现了上述syscall，它们就很简单。我们还提供了“pwd”，它不是那么简单。shell程序在内部实现cd。

现在，假设已经创建了路径中使用的目录，那么“ pintos”“提取”和“附加”命令应该接受完整的路径名。您无需为此付出任何额外的努力。

5.3.4 Buffer Cache#

修改文件系统以保留文件块的缓存。当一个请求想读取或写入一个块时，检查它是否在缓存中，如果是，则使用缓存的数据即可，无需磁盘操作。否则，将磁盘中的块取到高速缓存中，如有必要的话淘汰缓存中较早的旧数据。您只能使用不超过64个扇区大小的缓存。

您必须实现的缓存替换算法至少不比“时钟”算法差。与数据相比，我们鼓励您考虑比数据数据价值更大的元数据。通过实验分析查看访问位、脏位和其他信息的组合如何影响性能，用磁盘访问次数作为衡量。

您可以根据需要将空闲映射表的缓存副本永久保留在内存中。它不必计入缓存大小。

所提供的inode代码使用分配有“malloc()”的“反弹缓冲区”将磁盘的逐个扇区接口转换为系统调用接口的逐字节接口。您应该摆脱这些反弹缓冲区。而是直接在缓冲区高速缓存中将数据复制进出扇区。

您的缓存应为“后写式”，即在缓存中保留脏块，而不是立即将修改后的数据写入磁盘。每次清除脏块时，将它们写入磁盘。由于回写使文件系统在崩溃时更加脆弱，因此，您还应定期将所有脏的，已缓存的块写回到磁盘。高速缓存也应该在filesys_done()中写回到磁盘，以便停止Pintos刷新高速缓存。

如果您在第一个项目中使用过“timer_sleep()”，那么“后写式”就是一个很好的应用程序。否则，您可以实施一种不太通用的工具，但是请确保该工具不会表现出忙等待状态。

您还应该实现read-ahead，即，在读取文件的一个块时自动将文件的下一个块提取到缓存中。预读仅在异步完成时才真正有用。这意味着，如果进程从文件中请求磁盘块1，则它应该阻塞直到读入磁盘块1，但是一旦读取完成，控制权应立即返回到该进程。磁盘块2的预读请求应在后台异步处理。

我们建议尽早将缓存集成到您的设计中。过去，许多组织都在设计过程的后期尝试将缓存添加到设计中。这很难。这些小组经常上交大多数或所有测试均未通过的项目。

5.3.5 Synchronization#

提供的文件系统需要外部同步，即，调用者必须确保文件中只能运行一个线程系统代码一次。您的提交必须采用更细粒度的,不需要外部同步的同步策略。对独立实体的操作应尽可能独立，这样他们就不必彼此等待。

不同缓存块上的操作必须是独立的。特别是，当特定块上需要I/O时，不需要I/O的其他块上的操作就应该继续进行，而不必等待I/O完成。

多个进程必须能够一次访问单个文件。一个文件的多次读取必须能够完成而不必等待彼此。当写入文件不扩展文件时，多个进程也应该能够一次写入一个文件。当一个文件正在被另一个进程写入时，一个进程对文件的读取被允许显示未完成，全部或部分写入。（但是，在“ write”系统调用返回到其调用者之后，所有后续阅读器都必须看到更改。）类似，当两个进程同时写入文件的同一部分时，它们的数据可能会交织。

另一方面，扩展文件并将数据写入新节必须是原子的。假设进程A和B都打开了给定的文件，并且都位于文件末尾。如果A读取并且B同时写入文件，则A可能会读取B写入的全部，部分或全部内容。但是，A可能不会读取B写入的数据，例如B写入的数据。如果B的数据都是非零字节，则不允许A看到任何零。

不同目录上的操作应同时进行。同一目录上的操作可能会彼此等待。

请记住，只有多个线程共享的数据才需要同步。在基本文件系统中，“结构文件”和“结构目录”仅由单个线程访问。

5.4 FAQ 我需要编写多少代码？
+ 这是由diffstat程序生成的参考解决方案的摘要。最后一行给出了插入和删除的总行数；更改的行将同时算作插入和删除。

此摘要与Pintos基本代码有关，但是项目4的参考解决方案基于项目3的参考解决方案。因此，参考解决方案在启用虚拟内存的情况下运行。有关项目3的摘要，请参见[4.4 常见问题解答]。
参考解决方案仅代表一种可能的解决方案。许多其他解决方案也是可能的，其中许多解决方案与参考解决方案有很大不同。一些出色的解决方案可能不用修改所有参考解决方案修改的文件，有些可能修改参考方案里没有修改的文件。

 Makefile.build       |    5 
 devices/timer.c      |   42 ++
 filesys/Make.vars    |    6 
 filesys/cache.c      |  473 +++++++++++++++++++++++++
 filesys/cache.h      |   23 +
 filesys/directory.c  |   99 ++++-
 filesys/directory.h  |    3 
 filesys/file.c       |    4 
 filesys/filesys.c    |  194 +++++++++-
 filesys/filesys.h    |    5 
 filesys/free-map.c   |   45 +-
 filesys/free-map.h   |    4 
 filesys/fsutil.c     |    8 
 filesys/inode.c      |  444 ++++++++++++++++++-----
 filesys/inode.h      |   11 
 threads/init.c       |    5 
 threads/interrupt.c  |    2 
 threads/thread.c     |   32 +
 threads/thread.h     |   38 +-
 userprog/exception.c |   12 
 userprog/pagedir.c   |   10 
 userprog/process.c   |  332 +++++++++++++----
 userprog/syscall.c   |  582 ++++++++++++++++++++++++++++++-
 userprog/syscall.h   |    1 
 vm/frame.c           |  161 ++++++++
 vm/frame.h           |   23 +
 vm/page.c            |  297 +++++++++++++++
 vm/page.h            |   50 ++
 vm/swap.c            |   85 ++++
 vm/swap.h            |   11 
 30 files changed, 2721 insertions(+), 286 deletions(-)

可以修改BLOCk_SECTOR_SIZE吗? 不，BLOCK_SECTOR_SIZE固定为512。对于IDE磁盘，此值是硬件的固定属性。其他磁盘不一定具有512字节的扇区，但为简单起见，Pintos仅支持具有此功能的磁盘。

5.4.1 Indexed Files FAQ#

我们应该支持的最大文件大小是多少？
我们创建的文件系统分区将为8 MB或更小。但是，单个文件必须小于分区才能容纳元数据。在确定您的inode组织时，您需要考虑这一点。

5.4.2 Subdirectories FAQ#

应该如何解释“a//b”之类的文件名？
多个连续的斜杠等效于一个斜杠，因此此文件名与“a/b”相同。

像“/../x”这样的文件名怎么办？
根目录是其自己的父目录，因此等效于“/x”。

以“/”结尾的文件名应如何处理？
大多数Unix系统都允许在目录名的末尾使用斜杠，并拒绝其他类型以斜杠结尾。我们将允许这种行为，并且拒绝以“/”结尾的名称。

5.4.3 Buffer Cache FAQ#

我们可以在struct inode里面保留struct inode_disk吗？ + 64块限制的目标是限制高速缓存的文件系统数据量。如果您在内核内存中的任何位置保留磁盘数据块（无论是文件数据还是元数据），则必须将其计入64块限制。相同的规则适用于与磁盘数据块“相似”的任何事物，例如不包含“length”或“sector_cnt”成员的“struct inode_disk”。

这意味着您必须立即更改inode实现访问其相应的磁盘上inode的方式，因为它当前仅在instruct inode中嵌入一个struct inode_disk，并在创建磁盘时从磁盘读取相应的扇区。保留inode的额外副本将破坏我们在您的缓存上设置的64块限制。
您可以在struct inode中存储一个指向inode数据的指针，但是如果这样做，则应仔细确保这不会将OS限制为同时打开64个文件。您还可以存储其他信息，以帮助您在需要时找到索引节点。同样，您可以在64个缓存条目中的每个条目中存储一些元数据。
您可以根据需要将免费地图的缓存副本永久保留在内存中。它不必计入缓存大小。
“filesys/inode.c”中的“byte_to_sector()”直接使用“struct inode_disk”，而无需先从存储层次结构中的任何位置读取该扇区。这将不再起作用。您需要先更改inode_byte_to_sector()才能从缓存中获取struct inode_disk结构。