Due by 11:59pm, Tuesday, May 1.
The managing TA for this assignment is Daniel Mullowney. All email inquiries about this assignment should be addressed to the TA and the instructor.
This is a group assignment. You should form a group of two or three to complete this assignment. Remember that you can NOT form the same group for all four Nachos assignments. In this assignment, you will build a small file system and explore some performance issues in disk I/O.
This assignment contains three parts: (1) the base file system; (2) prefetching and performance evaluation; (3) disk scheduling and performance evaluation.
For this assignment, you will build your Nachos executable in the
filesys/ subdirectory. In this assignment, you
must supply a disk profile
-dp option) when running
Part I of the assignment, you should use
nachos -dp Nachos.xml.
You will be using other disk profiles for later parts of this assignment.
The provided file system implementation in Nachos is incomplete. In particular, it does not support synchronization (only one thread can access the file system at a time), files have a very small maximum size, and there is no caching of file data. You task is to correct these three limitations in the provided Nachos file system implementation. Your main concern in this part of the assignment is correctness, not the performance. For caching, feel free to use FIFO replacement if that makes your life easier. For the total size of the file cache, we recommend you to set it to 512 blocks. For simplicity, you can assume files have a fixed size once created.
At the hardware level, we provide a disk simulator, which accepts "read
sectors" and "write sectors" requests and signals the completion of an
I/O operation via an interrupt. Please check the public part of
class disk in
machine/disk.h for the exact
APIs. The disk data is stored in a 128KB disk
DISK; read and write operations are performed using
normal UNIX file reads and writes. After the UNIX file is updated, we
calculate how long the simulated disk operation should have taken, and
set an interrupt to occur that far in the future. Read and write
operations return immediately at the hardware level; high level software
is responsible for waiting until the interrupt occurs.
We provide a concurrent read test program for this assignment:
fstest.cc. Note that this program runs in the Nachos kernel
(i.e., it is not a Nachos user program). The program initializes the
empty disk with
n files of 10000 bytes each (we enforce
n<=10 so the files would not exceed the available space on
the 128KB simulated drive). It then launches
threads to read these files. Each thread reads 10 bytes at a time until
it finishes reading the file it is assigned to.
To invoke the file system test program, you must specify the option
-t n when launching Nachos. Note that
indicates the number of files and threads (or the concurrency) of the
test. You might also want to format the Nachos disk before each test
to avoid filling up the disk after several tests. You can specify
-f to do so.
Keep in mind that you are also encouraged to design your own test programs when you feel necessary.
You are asked to implement file system prefetching. You can use a fixed
p. At each file read, the OS will read
p blocks ahead (unless the end-of-file is reached
prematurely). With a prefetching-capable file system, you are
required to conduct a set of performance experiments using the provided
fstest.cc. Use a fixed concurrency
n=10 for all your tests. You need to provide performance
results with varying prefetching sizes
1, 2, 4, 8, 16, 32, 64.
Additionally, you are required to provide performance results on
several disk drives. The original Nachos disk simulator uses arbitrarily
selected disk parameters (seek time, rotational delay, and sequential
transfer rate). We have incorporated a new disk simulator (called
Vesper) that can emulate a realistic disk drive with an input profile file.
We provide two such profile files,
Seagate.xml, which describe the performance characteristics
of an IBM 10KRPM SCSI drive and a Seagate 10KRPM SCSI drive respectively.
To use an input disk profile file, specify the option
nachos -dp disk.profile. Again, you can use the original
Nachos disk simulator through
nachos -dp Nachos.xml.
In this assignment, you are required to provide performance results for
the original Nachos disk simulator, Vesper with the IBM drive, and Vesper
with the Seagate drive.
Note that we are only interested in the time for the concurrent read phase.
You should not count the time of file creations in the test programs.
Luckily the test program
fstest.cc reports the
elapsed time for the concurrent read phase in an output statement like
"## The concurrent read phase takes 11720070 ticks or 11.7201sec".
Again note that the execution order of the
n concurrent threads
is randomized so you might see different performance at different runs,
even for the same configuration setting. It is important to conduct several
(e.g., 3) runs for each setting and calculate the average.
Please provide a simple analysis of your performance evaluation results. For instance, does prefetching improve the performance of concurrent read and why? What are the disk characteristics that might affect the benefit of prefetching?
You are asked to implement several disk scheduling algorithms (First-Come-First-Serve, Shortest-Seek-Time-First, and Cyclic-LOOK) into the operating system and compare their performance. Similar to part II, you are required to experiment with multiple disk drives. Also provide a simple analysis of your performance evaluation results. For instance, what disk scheduling algorithm has better or worse performance for concurrent read and why? What are the disk characteristics that might affect the performance difference among alternative scheduling algorithms?
You are asked to electronically turn in a copy of the complete Nachos source tree. Do not turn in any executables, object files, or things like that. Add enough comments in your code to make your changes easy to understand. You must also turn in a project report describing the performance results for Parts II and III of the assignment. If you want to illustrate the performance results in figures (which is encouraged), please produce the report in PDF or PostScript format. We will not be able to read any other format including Microsoft Word.
Below is a tentative grading guideline. Your turn-in will be graded on the correctness of your implementation, completeness and clarity of your comments, and validity of your performance results.
Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three-day late will be accepted.