Programming assignment #6 (a.k.a. Grand Finale) - File System and Disk I/O

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.

Part I: The Base File System

For this assignment, you will build your Nachos executable in the filesys/ subdirectory. In this assignment, you must supply a disk profile (using -dp option) when running nachos. For 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 file 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 n concurrent 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 n 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 the option -f to do so.

Keep in mind that you are also encouraged to design your own test programs when you feel necessary.

Part II: Prefetching and Performance Evaluation

You are asked to implement file system prefetching. You can use a fixed prefetching size 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 test program 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, IBM.xml and 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?

Part III: Disk Scheduling and Performance Evaluation

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?

Administrative policies

Turn-in:
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.

Grading guideline:
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.