Your Tasks
Task 0: Design Document
Download the project 4 design document template. Read through it to motivate your design and fill it in after you finish the project.
We recommend that you read the design document template before you start working on the project.
See section Project Documentation, for a sample design document that goes along with a fictitious project.
Task 1: Indexed and Extensible Files
Exercise 1.1
The basic file system allocates files as a single extent, making it vulnerable to external fragmentation, that is, it is possible that an n-block file cannot be allocated even though 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 rationale for it in your design documentation, and as long as it does not suffer from external fragmentation (as does the extent-based file system we provide).
Exercise 1.1
Modify inode structure to accommodate external fragmentation.
Some Important Notes
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.
An extent-based file can only grow if it is followed by empty space, but 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 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.
There should be no predetermined limit on the size of a file, except 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.
User programs are allowed to seek beyond the current end-of-file (EOF).
The seek itself does not extend the file.
Writing at a position past EOF extends the file to the position being written, and any gap between the previous EOF and the start of the write must be filled with zeros.
A read starting from a position past EOF returns no bytes.
Writing far beyond EOF can cause many blocks to be entirely zero.
Some file systems allocate and write real data blocks for these implicitly zeroed blocks.
Other file systems do not allocate these blocks at all until they are explicitly written. The latter file systems are said to support "sparse files."
You may adopt either allocation strategy in your file system.
Task 2: Subdirectories
Exercise 2.1
Implement a hierarchical name space.
In the basic file system, all files live in a single directory.
Modify this to allow directory entries to point to files or to other directories.
Exercise 2.1
Implement a hierarchical name space.
In the basic file system, all files live in a single directory.
Modify this to allow directory entries to point to files or to other directories.
Some Important Notes
Make sure that directories can expand beyond their original size just as any other file can.
The basic file system has a 14-character limit on file names.
You may retain this limit for individual file name components, or may extend it, at your option.
You must allow full path names to be much longer than 14 characters.
Exercise 2.2
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
execsystem 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, thecdcommand is a shell built-in, not an external program.)
Exercise 2.2
Update the system calls to support hierarchical file names.
Some Important Notes
Update the existing system calls so that:
Anywhere a file name is provided by the caller, an absolute or relative path name may be used.
The directory separator character is forward slash (/).
You must also support special file names
.and.., which have the same meanings as they do in Unix.
Update the open system call so that it can also open directories.
Of the existing system calls, only
closeneeds to accept a file descriptor for a directory.
Update the remove system call so that it can delete empty directories (other than the root) in addition to regular files.
Directories may only be deleted if they do not contain any files or subdirectories (other than
.and..).You may decide whether to allow deletion of a directory that is open by a process or in use as a process's current working directory. If it is allowed, then attempts to open files (including
.and..) or create new files in a deleted directory must be disallowed.
Exercise 2.3
Exercise 2.3
Implement the following new system calls:
System Call: bool chdir (const char *dir)
Changes the current working directory of the process to dir, which may be relative or absolute.
Returns true if successful, false on failure.
System Call: bool mkdir (const char *dir)
Creates the directory named dir, which may be relative or absolute.
Returns true if successful, false on failure.
Fails if dir already exists or if any directory name in dir, besides the last, does not already exist. That is,
mkdir("/a/b/c")succeeds only if /a/b already exists and /a/b/c does not.
System Call: bool readdir (int fd, char *name)
Reads a directory entry from file descriptor fd, which must represent a directory.
If successful, stores the null-terminated file name in name, which must have room for
READDIR_MAX_LEN + 1bytes, and returns true. If no entries are left in the directory, returns false..and..should not be returned byreaddir.If the directory changes while it is open, then it is acceptable for some entries not to be read at all or to be read multiple times. Otherwise, each directory entry should be read once, in any order.
READDIR_MAX_LENis defined inlib/user/syscall.h. If your file system supports longer file names than the basic file system, you should increase this value from the default of 14.
System Call: bool isdir (int fd)
Returns true if fd represents a directory, false if it represents an ordinary file.
System Call: int inumber (int fd)
Returns the inode number of the inode associated with fd, which may represent an ordinary file or a directory.
An inode number persistently identifies a file or directory. It is unique during the file's existence. In Pintos, the sector number of the inode is suitable for use as an inode number.
We have provided ls and mkdir user programs, which are straightforward once the above syscalls are implemented. We have also provided pwd, which is not so straightforward. The shell program implements cd internally.
The pintos extract and 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.
Task 3: Buffer Cache
Exercise 3.1
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 the cache, evicting an older entry if necessary.
You are limited to a cache no greater than 64 sectors in size.
Exercise 3.1
Implement buffer cache and cache replacement algorithm.
Some Important Notes
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.
The provided inode code uses a "bounce buffer" allocated with
malloc()to translate the disk's sector-by-sector interface into the system call interface's byte-by-byte interface.You should get rid of these bounce buffers.
Instead, copy data into and out of sectors in the buffer cache directly.
Your cache should be 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
filesys_done(), so that halting Pintos flushes the cache.If you have
timer_sleep()from the first project working, write-behind is 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 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.
Tips:
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 the design process. This is very difficult. These groups have often turned in projects that failed most or all of the tests.
Task 4: Synchronization
Exercise 4.1
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 must adopt a finer-grained synchronization strategy that does not require external synchronization.
To the extent possible, operations on independent entities should be independent, so that they do not need to wait on each other.
Exercise 4.1
Support finer-grained synchronization of file system.
Some Important Notes
Operations on different cache blocks must be independent. In particular, when I/O is required on a particular block, operations on other blocks that do not require I/O should proceed without having to wait for the I/O to complete.
Multiple processes must be able to access a single file at once.
Multiple reads of a single file must be able to complete without waiting for one another.
When writing to a file does not extend the file, multiple processes should also be able to write a single file at once.
A read of a file by one process when the file is being written by another process is allowed to show that none, all, or part of the write has completed. (However, after the
writesystem call returns to its caller, all subsequent readers must see the change.)Similarly, when two processes simultaneously write to the same part of a file, their data may be interleaved.
On the other hand, extending a file and writing data into the new section must be atomic.
Suppose processes A and B both have a given file open and both are positioned at end-of-file. If A reads and B writes the file at the same time, A may read all, part, or none of what B writes. However, A may not read data other than what B writes, e.g. if B's data is all nonzero bytes, A is not allowed to see any zeros.
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 fileandstruct dirare accessed only by a single thread.
Last updated