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.
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.
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.
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.
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?
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?
By the date shown below, send e-mail to
cs456
containing answers to the following:
SIGIO
instead of
aiowait
?
mmap
the same file at the same time, do
they see each other's changes?
mmap
and the
various shmop
calls? (See the shmop
man page.)