Due by 11:59pm, Friday, April 29.
The managing TA for this assignment is Christopher Stewart. 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. You will need
a new base Nachos package for this assignment, which can be found at
/u/cs256/nachos/nachos-3.4-urv2-fsbase.tar if you are in
the CSUG network; or at
if you are in the research (graduate students and faculty) network.
You must use the new Nachos package. The old package
does not have necessary disk simulator for this assignment.
This assignment contains three parts: (1) the base file system; (2) prefetching and performance evaluation; (3) disk scheduling and performance evaluation.
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.
For this assignment, you will build your Nachos executable in the
filesys/ subdirectory. You will find that two executables are
generated after the build:
You only need to be concerned with the
nachos executable in
this part of the assignment. If you want to save build time and you know
what you are doing, you can modify
Makefile to disable the
vesper for now. However, you must re-enable it for
later parts of this assignment.
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 default Nachos disk simulator uses arbitrarily
selected disk parameters (seek time, rotational delay, and sequential
transfer rate). We provide a new disk simulator Vesper that
can emulate a realistic disk drive with an input profile file. We
provide two such profile files,
Seagate.profile, which describe the performance characteristics
of an IBM 10KRPM SCSI drive and a Seagate 10KRPM SCSI drive respectively.
To use Vesper with an input profile file, specify the option
vesper -dp disk.profile. Note all Nachos options can be
specified in the same way for
vesper. In this assignment,
you are required to provide performance results for the default Nachos
disk simulator, Vesper with the IBM drive, and Vesper with the Seagate
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.