-@node Project 4--File Systems, References, Project 3--Virtual Memory, Top
+@node Project 4--File Systems
@chapter Project 4: File Systems
In the previous two assignments, you made extensive use of a
file system without actually worrying about how it was implemented
-underneath. For this last assignment, you will fill in the
+underneath. For this last assignment, you will improve the
implementation of the file system. You will be working primarily in
the @file{filesys} directory.
@file{filesys/Make.vars} to enable VM functionality. You can receive up
to 5% extra credit if you do enable VM.
+The tests for project 4 (and later projects) will probably run faster if
+you use the qemu emulator, e.g.@: via @code{make check
+PINTOSOPTS='--qemu'}.
+
@menu
* Project 4 Background::
* Project 4 Requirements::
-* Project 4 FAQ::
+* Project 4 FAQ::
@end menu
@node Project 4 Background
read the Unix man pages for @code{creat}, @code{open}, @code{close},
@code{read}, @code{write}, @code{lseek}, and @code{unlink}. Our file
system has calls that are similar, but not identical, to these. The
-file system translates these calls into physical disk operations.
+file system translates these calls into disk operations.
All the basic functionality is there in the code above, so that the
file system is usable from the start, as you've seen
which you will remove.
While most of your work will be in @file{filesys}, you should be
-prepared for interactions with all previous parts (as usual).
+prepared for interactions with all previous parts.
@node Project 4 Requirements
@section Requirements
@subsection Indexed and Extensible Files
The basic file system allocates files as a single extent, making it
-vulnerable to external fragmentation. Eliminate this problem by
+vulnerable to external fragmentation, that is, it is possible that an
+@var{n}-block file cannot be allocated even though @var{n} blocks are
+free. Eliminate this problem by
modifying the on-disk 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
+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.)
+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
doubly-indirect blocks.
An extent-based file can only grow if it is followed by empty space, but
-with indexed inodes file growth is possible whenever free space is
+indexed inodes make file growth possible whenever free space is
available. Implement file growth. In the basic file system, the file
-size is specified when the file is created. In UNIX and most other file
+size is specified when the file is created. In most modern file
systems, a file is initially created with size 0 and is then expanded
every time a write is made off the end of the file. Your file system
must allow this.
it, at your option. You must allow full path names to be
much longer than 14 characters.
-The current directory is maintained separately for each process. At
-startup, the initial process's current directory is the root directory.
+Maintain a separate current directory for each process. At
+startup, set the root as the initial process's current directory.
When one process starts another with the @code{exec} system call, the
child process inherits its parent's current directory. After that, the
two processes' current directories are independent, so that either
changing its own current directory has no effect on the other.
+(This is why, under Unix, the @command{cd} command is a shell built-in,
+not an external program.)
Update the existing system calls so that, anywhere a file name is
provided by the caller, an absolute or relative path name may used.
+The directory separator character is forward slash (@samp{/}).
Update the @code{remove} system call so that it can delete empty
directories in addition to regular files. Directories can only be
@end deftypefn
We have provided @command{ls} and @command{mkdir} user programs, which
-are straightforward once the above syscalls are implemented. In Unix,
-these are programs rather than built-in shell commands, but
-@command{cd} is a shell command.
+are straightforward once the above syscalls are implemented.
The @code{pintos} @option{put} and @option{get} commands should now
accept full path names, assuming that the directories used in the
@subsection Buffer Cache
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 stored in the
-cache, and if so, fetch it immediately from the cache without going to
+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
older entry if necessary. You are limited to a cache no greater than 64
sectors in size.
of these bounce buffers. Instead, copy data into and out of sectors in
the buffer cache directly.
-Your implementation should also include the following features:
-
-@table @b
-@item write-behind:
-Keep dirty blocks in the cache, instead of immediately writing modified
+Your cache should be @dfn{write-behind}, that is,
+keep dirty blocks in the cache, instead of immediately writing modified
data to disk. Write dirty blocks to disk whenever they are evicted.
Because write-behind makes your file system more fragile in the face of
crashes, in addition you should periodically write all dirty, cached
blocks back to disk. The cache should also be written back to disk in
@func{filesys_done}, so that halting Pintos flushes the cache.
-If you have @func{timer_sleep} from the first project working, this is
-an excellent application for it. If you're still using the base
+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 an acceptable solution. If @func{timer_sleep}'s delays seem too
+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}).
-@item read-ahead:
-Your buffer cache should automatically fetch the next block of a file
+You should also implement @dfn{read-ahead}, that is,
+automatically fetch the next block of a file
into the cache when one block of a file is read, in case that block is
about to be read.
-
Read-ahead is only really useful when done asynchronously. That means,
if a process requests disk block 1 from the file, it should block until disk
block 1 is read in, but once that read is complete, control should
return to the process immediately. The read-ahead request for disk
block 2 should be handled asynchronously, in the background.
-@end table
@strong{We recommend integrating the cache into your design early.} In
the past, many groups have tried to tack the cache onto a design late in
@command{diffstat} program. The final row gives total lines inserted
and deleted; a changed line counts as both an insertion and a deletion.
-This summary is relative to the Pintos base code, but we started from
-the reference solution to project 3. Thus, the reference solution runs
-with virtual memory enabled. @xref{Project 3 FAQ}, for the summary
-of project 3.
+This summary is relative to the Pintos base code, but the reference
+solution for project 4 is based on the reference solution to project 3.
+Thus, the reference solution runs with virtual memory enabled.
+@xref{Project 3 FAQ}, for the summary of project 3.
+
+The reference solution represents just one possible solution. Many
+other solutions are also possible and many of those differ greatly from
+the reference solution. Some excellent solutions may not modify all the
+files modified by the reference solution, and some may modify files not
+modified by the reference solution.
@verbatim
Makefile.build | 5
No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
of IDE disk hardware.
-
-@item What's the directory separator character?
-
-Forward slash (@samp{/}).
@end table
@menu
* Indexed Files FAQ::
-* Subdirectories FAQ::
* Buffer Cache FAQ::
@end menu
You'll need to consider this when deciding your inode organization.
@end table
-@node Subdirectories FAQ
-@subsection Subdirectories FAQ
-
-@table @b
-@item Why is @command{cd} a shell command?
-
-The current directory of each process is independent. A @command{cd}
-program could change its own current directory, but that would have no
-effect on the shell. In fact, Unix-like systems don't provide any way
-for one process to change another process's current working directory.
-@end table
-
@node Buffer Cache FAQ
@subsection Buffer Cache 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}, if you want,
-and you can store other information to help you find the inode when you
+You can store a pointer to inode data in @struct{inode}, but it 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
need it. Similarly, you may store some metadata along each of your 64
cache entries.
@func{byte_to_sector} in @file{filesys/inode.c} uses the
@struct{inode_disk} directly, without first reading that sector from
wherever it was in the storage hierarchy. This will no longer work.
-You will need to change @func{inode_byte_to_sector} so that it reads the
-@struct{inode_disk} from the storage hierarchy before using it.
+You will need to change @func{inode_byte_to_sector} to obtain the
+@struct{inode_disk} from the cache before using it.
@end table
projects / pintos-anon / blobdiff