@menu
* Project 4 Background::
+* Project 4 Suggested Order of Implementation::
* Project 4 Requirements::
* Project 4 FAQ::
@end menu
can use the Unix @command{tar} program to examine them. The tar file
for test @var{t} is named @file{@var{t}.tar}.
+@node Project 4 Suggested Order of Implementation
+@section Suggested Order of Implementation
+
+To make your job easier, we suggest implementing the parts of this
+project in the following order:
+
+@enumerate
+@item
+Buffer cache (@pxref{Buffer Cache}). Implement the buffer cache and
+integrate it into the existing file system. At this point all the
+tests from project 2 (and project 3, if you're building on it) should
+still pass.
+
+@item
+Extensible files (@pxref{Indexed and Extensible Files}). After this
+step, your project should pass the file growth tests.
+
+@item
+Subdirectories (@pxref{Subdirectories}). Afterward, your project
+should pass the directory tests.
+
+@item
+Remaining miscellaneous items.
+@end enumerate
+
+You can implement extensible files and subdirectories in parallel if
+you temporarily make the number of entries in new directories fixed.
+
+You should think about synchronization throughout.
+
@node Project 4 Requirements
@section Requirements
not suffer from external fragmentation (as does the extent-based file
system we provide).
-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
+You can assume that the file system partition will not be larger than
+8 MB. You must
+support files as large as the partition (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.
must allow this.
There should be no predetermined limit on the size of a file, except
-that a file cannot exceed the size of the disk (minus metadata). This
+that a file cannot exceed the size of the file system (minus metadata). This
also applies to the root directory file, which should now be allowed
to expand beyond its initial limit of 16 files.
We have also provided @command{pwd}, which is not so straightforward.
The @command{shell} program implements @command{cd} internally.
-The @code{pintos} @option{put} and @option{get} commands should now
+The @code{pintos} @option{extract} and @option{append} commands should now
accept full path names, assuming that the directories used in the
paths have already been created. This should not require any significant
extra effort on your part.
Modify the file system to keep a cache of file blocks. When a request
is made to read or write a block, check to see if it is in the
cache, and if so, use the cached data without going to
-disk. Otherwise, fetch the block from disk into cache, evicting an
+disk. Otherwise, fetch the block from disk into the cache, evicting an
older entry if necessary. You are limited to a cache no greater than 64
sectors in size.
-Be sure to choose an intelligent cache replacement algorithm.
-Experiment to see what combination of accessed, dirty, and other
-information results in the best performance, as measured by the number
-of disk accesses. For example, metadata is generally more valuable to
-cache than data.
+You must implement a cache replacement algorithm that is at least as
+good as the ``clock'' algorithm. We encourage you to account for
+the generally greater value of metadata compared to data. Experiment
+to see what combination of accessed, dirty, and other information
+results in the best performance, as measured by the number of disk
+accesses.
You can keep a cached copy of the free map permanently in memory if you
like. It doesn't have to count against the cache size.
@func{filesys_done}, so that halting Pintos flushes the cache.
If you have @func{timer_sleep} from the first project working, write-behind is
-an excellent application. If you're still using the base
-implementation of @func{timer_sleep}, be aware that it busy-waits, which
-is not acceptable here (or elsewhere). 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}).
+an excellent application. Otherwise, you may implement a less general
+facility, but make sure that it does not exhibit busy-waiting.
You should also implement @dfn{read-ahead}, that is,
automatically fetch the next block of a file
Operations on different directories should take place concurrently.
Operations on the same directory may wait for one another.
+Keep in mind that only data shared by multiple threads needs to be
+synchronized. In the base file system, @struct{file} and @struct{dir}
+are accessed only by a single thread.
+
@node Project 4 FAQ
@section FAQ
30 files changed, 2721 insertions(+), 286 deletions(-)
@end verbatim
-@item Can @code{DISK_SECTOR_SIZE} change?
+@item Can @code{BLOCk_SECTOR_SIZE} change?
-No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
-of IDE disk hardware.
+No, @code{BLOCK_SECTOR_SIZE} is fixed at 512. For IDE disks, this
+value is a fixed property of the hardware. Other disks do not
+necessarily have a 512-byte sector, but for simplicity Pintos only
+supports those that do.
@end table
@menu
@table @b
@item What is the largest file size that we are supposed to support?
-The disk we create will be 8 MB or smaller. However, individual files
-will have to be smaller than the disk to accommodate the metadata.
-You'll need to consider this when deciding your inode organization.
+The file system partition we create will be 8 MB or smaller. However,
+individual files will have to be smaller than the partition to
+accommodate the metadata. You'll need to consider this when deciding
+your inode organization.
@end table
@node Subdirectories FAQ
copies of inodes would subvert the 64-block limitation that we place
on your cache.
-You can store a pointer to inode data in @struct{inode}, but it you do
+You can store a pointer to inode data in @struct{inode}, but if you do
so you should carefully make sure that this does not limit your OS to 64
simultaneously open files.
You can also store other information to help you find the inode when you
projects / pintos-anon / blobdiff