@chapter Project 4: File Systems
In the previous two assignments, you made extensive use of a
-filesystem without actually worrying about how it was implemented
+file system without actually worrying about how it was implemented
underneath. For this last assignment, you will fill in the
-implementation of the filesystem. You will be working primarily in
+implementation of the file system. You will be working primarily in
the @file{filesys} directory.
You should build on the code you wrote for the previous assignments.
However, if you wish, you may turn off your VM features, as they are
-not vital to making the filesystem work. (You will need to edit
+not vital to making the file system work. (You will need to edit
@file{filesys/Makefile.vars} to fully disable VM.) All of the
functionality needed for project 2 (argument passing, syscalls and
multiprogramming) must work in your filesys submission.
On the other hand, one of the particular charms of working on
operating systems is being able to use what you build, and building
full-featured systems. Therefore, you should strive to make all the
-parts work together so that you can run VM and your filesystem at the
+parts work together so that you can run VM and your file system at the
same time. Plus, keeping VM is a great way to stress-test your
-filesystem implementation.
+file system implementation.
Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
@file{constants.h} (@pxref{Conditional Compilation}).
@menu
* File System New Code::
-* Problem 4-1 Large Files::
+* File System Synchronization::
+* Problem 4-1 Indexed Files::
* Problem 4-2 File Growth::
* Problem 4-3 Subdirectories::
* Problem 4-4 Buffer Cache::
* File System Design Document Requirements::
-* File System FAQ::
+* File System FAQ::
@end menu
@node File System New Code
@table @file
@item fsutil.c
-Simple utilities for the filesystem that are accessible from the
+Simple utilities for the file system that are accessible from the
kernel command line.
@item filesys.h
file system translates these calls into physical disk operations.
All the basic functionality is there in the code above, so that the
-filesystem is usable right off the bat. In fact, you've been using it
+file system is usable right off the bat. In fact, you've been using it
in the previous two projects. However, it has severe limitations
which you will remove.
@node File System Synchronization
@section Synchronization
-The file system as provided requires external synchronization, that is,
+The provided file system requires external synchronization, that is,
callers must ensure that only one thread can be running in the file
-system code at once. Your submission should use a more finely granular
-synchronization strategy. You will need to consider synchronization for
-each type of file system object. The provided code uses the following
-strategies:
+system code at once. Your submission should use a finer-grained
+synchronization strategy. You will need to consider synchronization
+issues for each type of file system object. The provided code uses the
+following strategies:
@itemize @bullet
@item
@item
Inodes are immutable in the provided file system, that is, their content
-never changes between creation and deletion, and furthermore only one
-copy of an inode's data is maintained in memory at once, even if the
-file is open in multiple contexts.
+never changes between creation and deletion. Furthermore, only one copy
+of an inode's data is maintained in memory at once, even if the file is
+open in multiple contexts.
@item
File data doesn't have to be consistent because it's just not part of
write has completed. (However, after the write system call returns to
its caller, all subsequent readers must see the change.) Similarly,
when two threads write to the same part of a file at the same time,
-their data may be arbitrarily interleaved.
-
-External synchronization of the provided file system ensures that reads
-and writes are fully serialized, but your file system doesn't have to
-maintain full serialization as long as it follows the rules above.
+their data may be interleaved. External synchronization of the provided
+file system ensures that reads and writes are fully serialized, but your
+file system doesn't have to maintain full serialization as long as it
+follows the rules above.
@end itemize
-@node Problem 4-1 Large Files
-@section Problem 4-1: Large Files
+@node Problem 4-1 Indexed Files
+@section Problem 4-1: Indexed Files
+
+The basic file system allocates files as a single extent, making it
+vulnerable to external fragmentation. Eliminate this problem by
+modifying the inode structure. In practice, this probably means using
+an index structure with direct, indirect, and doubly indirect blocks.
+(You are welcome to choose a different scheme as long as you explain the
+rationale for it in your design documentation, and as long as it does
+not suffer from external fragmentation.)
-Modify the file system to allow the maximum size of a file to be as
-large as the disk. You can assume that the disk will not be larger
-than 8 MB. In the basic file system, each file is limited to a file
-size of just under 64 kB. Each file has a header called an index node
-or @dfn{inode} (represented by @struct{inode}) that is a table of
-direct pointers to the disk blocks for that file. Since the inode is
-stored in one disk sector, the maximum size of a file is limited by
-the number of pointers that will fit in one disk sector. Increasing
-the limit to 8 MB will require you to implement doubly-indirect
-blocks.
+You can assume that the disk will not be larger than 8 MB. You must
+support files as large as the disk (minus metadata). Each inode is
+stored in one disk sector, limiting the number of block pointers that it
+can contain. Supporting 8 MB files will require you to implement
+doubly-indirect blocks.
@node Problem 4-2 File Growth
@section Problem 4-2: File Growth
to perform better than on the original file system implementation, and
demonstrate the performance improvement.
-Note that write-behind makes your filesystem more fragile in the face
+Note that write-behind makes your file system more fragile in the face
of crashes. Therefore, you should
periodically write all cached blocks to disk. If you have
@func{timer_sleep} from the first project working, this is an
-excellent application for it.
+excellent application for it. (If you're still using the base
+implementation of @func{timer_sleep}, be aware that it busy-waits, which
+is not an acceptable solution.) If @func{timer_sleep}'s delays seem too
+short or too long, reread the explanation of the @option{-r} option to
+@command{pintos} (@pxref{Debugging versus Testing}).
Likewise, read-ahead is only really useful when done asynchronously.
That is, if a process wants disk block 1 from the file, it needs to
pintos -ex "shell"
@end example
-If you don't change the filesystem interface, then this should already
+If you don't change the file system interface, then this should already
be implemented properly in @file{threads/init.c} and
@file{filesys/fsutil.c}.
``similar'' to a block of disk data, such as a @struct{inode_disk}
without the @code{length} or @code{sector_cnt} members.
+You can keep a cached copy of the free map in memory permanently if you
+like. It doesn't have to count against the cache size.
+
That means you'll have to change the way the inode implementation
accesses its corresponding on-disk inode right now, since it currently
just embeds a @struct{inode_disk} in @struct{inode} and reads the
projects / pintos-anon / blobdiff