CSC 2/456 File System Assignment

For this assignment you will write an I/O intensive application based on conventional, asynchronous, and memory-mapped file system interfaces. You will compare and discuss the performance of the different versions.

256 version

You are to build three versions of an external merge-sort application. Your input and output will consist of lines of ASCII text. Each line is to be taken as a record. The lines of the output should appear in lexicographic order.

The first version of your program will use the conventional read/write or printf/scanf file interface (your choice). The initial program pass will read its input in chunks no larger than 10 kilobytes (this is an artificially small number) to be sorted internally and written to a pair of temporary files. These files will then be merged to produce a pair of files whose chunks are twice as large. Successive rounds of merging will eventually result in a pair of sorted files that can be merged in a final round to produce the desired output. For more details on external merge-sort, see any algorithms textbook.

The second version of your program will use asynchronous I/O to (hopefully) overlap computation and disk access. During the initial pass of your program, you will sort a given chunk of your input file while simultaneously writing out the previous chunk and reading in the next chunk. Read the man pages for aioread, aiowrite, and aiowait, or see the tutorial from SunWorld on-line. (There's also a version at Sun's own site, but it's significantly harder to read.) Note that because Solaris caches the contents of recently-accessed files, you may not see the advantages of user-level double-buffering unless your input file is very large.

The third version of your program will use memory-mapped files in place of read/write or printf/scanf. See the man page for mmap.

Please review the General Guidelines for all Assignments regarding the contents of your write-up (README) file. In addition to the usual textual information, include a quantitative comparison of the performance of the three versions of your program, with an explanation of any differences observed.

Important notice:

The TA will create some sample input files for you to use (watch the newsgroup). Please do not create copies of these, or leave your temporary files lying around. This assignment has the potential to chew up a lot of disk space. If we fill the partitions on the UG servers, everyone will suffer.

456 version

Your assignment consists of the 256 assignment plus an additional binary search program. The input consists of the name of a sorted file (as output by the 256 assignment) and a character string. The output consists of any lines beginning with that string. Think of this as an electronic phone book: if every line of the file is a name and phone number, when you provide the name (prefix of the line), you get the entire line as output.

You are to create two versions of this program, one of which uses conventional file I/O, the other of which uses memory-mapped files. Again, your write-up should include a quantitative and qualitative comparison of the two.

Extra Credit Suggestions

  1. If you're in 256, try the 456 assignment.
  2. In place of the aio calls, write the second version of the 256 assignment using multiple threads, each of which performs blocking I/O. Is this easier or harder to write than the aio version? Does it run faster or slower?
  3. Investigate the implementation of the streams library (printf/scanf). These use read and write system calls internally. Under what circumstances do they actually make a system call? How much overhead do they induce?

Trivia assignment

By the date shown below, send e-mail to cs456 containing answers to the following:

  1. Who are the members of your team? (They need not necessarily be the same as last time.)
  2. Why might an application use SIGIO instead of aiowait?
  3. If two processes mmap the same file at the same time, do they see each other's changes?
  4. What is the principal difference between mmap and the various shmop calls? (See the shmop man page.)

DUE DATE:

Remember: No extensions.


Back to the assignments and grading page

Back to the course home page

Last Change: 13 March 2000 / Michael Scott's email address