Computer Science 61 and E61
Systems Programming and Machine Organization
Assignment 3: Caching and File I/O
In this assignment, you’ll gain experience with caching by writing your own buffered I/O library.
- Due Fri 10/21 at 11:59pm for college students (1 day later for extension)
- EXTENDED to Mon 10/24 at 11:59pm for college students (1 day later for extension)
- This assignment may be completed in pairs.
- Reminder: You may not use code or solutions from previous years.
Get the code
Our code is released in the
cs61-psets repository. To update it, run
git remote show handout
If this reports an error, run
git remote add handout git://github.com/cs61/cs61-psets.git
git pull handout master
This will merge our Assignment 3 code with your previous work. If you have any “conflicts” from Assignment 1 or 2, resolve them before continuing further. Run
git push to save this merge back to your private repository.
Use an explicit merge. If you copy code by hand, our automated scripts will have trouble analyzing your code, and it’ll be harder for you to incorporate our updates.
You may also create a new
cs61-psets repository for this assignment. However, you will need our help: some issues with our use of GitHub Classroom make it difficult for you to create a new repository yourself. Write
email@example.com for help. Tell us (1) your GitHub username and (2) the name of the repo you want to create. Once the repo is ready, make sure you update the grading server.
We’ve released a simple library, IO61, to perform I/O to/from files. You will find the code in the pest directory in the file
io61.c. Our version of IO61 is pretty stupid—it uses character-at-a-time system call I/O and is thus quite slow. Your goal is simple: speed it up using caching.
We also distribute several programs that use IO61. (The grading server has some secret extra programs too!)
cat61reads a file sequentially one character at a time and writes it to standard output.
cat61, but reads the file sequentially one block at a time. Its
-b BLOCKSIZEargument sets the block size.
blockcat61, but it chooses a random block size for each read and write. It still reads and writes sequentially (only the block sizes are random). The
-bargument is the maximum possible block size. This may very well stress your caching solution.
reverse61reads a file a character at a time in reverse and writes the result to standard output.
stride61reads its input file using a strided access pattern, writing the data it reads sequentially. By strided, we mean that it begins at offset 0, reads BLOCKSIZE bytes, seeks to position STRIDE, reads another bloc, seeks to position (2 * STRIDE), etc. When it gets to the end of the file, it jumps back to the first bytes not yet read and repeats the pattern. The
-sarguments set the block size and stride length, respectively.
reordercat61reads its input file one block at a time in random order and writes each block to the output file at the correct position. The result is a copy of the input file, but created non-sequentially.
gather61can take two or more input files. It reads blocks from them in round-robin order to create its single output file. This will test your ability to handle multiple input files.
scatter61can take two or more output files. It reads blocks from a single input file, then writes them to the output files in round-robin order. This will test your ability to handle multiple output files.
Introduce buffering (that is, caching) to the
io61_file abstraction and use them to speed up IO61 operations.
We’re giving you tons of freedom to implement the file caches as you like. You may even use memory-mapped I/O, prefetching system calls like
posix_fadvise, or multiple threads or processes (although none of these are required). But you may not use another buffered I/O library or caching I/O library.
Your library should:
- Return correct results for all access patterns and file types, including multiple files, very large files, non-seekable files, mixtures of calls (for instance, alternating
io61_readc), and random accesses.
- Perform as well as stdio on sequential reads and writes for any files, including very large files (such as files that don’t fit in memory) and non-seekable files.
- Improve on stdio’s performance for some non-sequential access patterns, such as simple strides or reverse access.
All your code should fit in
We will evaluate you based on your code’s performance relative to a version of IO61 that uses stdio. That version is provided for you for testing in
stdio-io61.c (and the makefile builds
stdio-blockcat61, and so forth).
make check to see how your current implementation is doing on a battery of tests. This will also print summary statistics at the end. Run
make check-TESTNUMBERS (e.g.,
make check-9 or
make check-5-10 or
make check-1,2,3) to run selected tests.
We may update the tests during the pset release period. We may also run additional tests during grading. In all instances, correctness counts -- that is, a program that runs quickly but incorrectly is worse than a program that runs slowly!
It’s easy in this problem set to design something too complex and get yourself stuck. Avoid that problem by tackling the simple cases first. Here’s a possible roadmap.
- First, you can improve the way
io61_writework without introducing a cache. Use
straceto investigate the operation of
blockcat61. Look at the
blockcat61code; what system calls do you think it should make? Then run
strace -o strace.out ./blockcat61 blockcat61.c. (That command line tells
straceto write its output to
strace.out, so examine
strace.outwith a command like
less strace.out.) What system calls does
- This will improve your performance on the block I/O tests (e.g.,
- This will improve your performance on the block I/O tests (e.g.,
- Then, implement a single-slot cache buffer for reading. This will hold bytes [N, N+B) of the file, where B is some largish number (try different numbers). Any read request that lies within that range of bytes can be satisfied without making a system call. In the book’s terminology, this is a single-slot cache. Check your work by examining
straceoutput. Don’t worry about seeks yet. (This means your code will stop working on the “reverse order,” “stride order,” and “random seek order” tests.)
- This will improve your performance on character I/O tests.
- Then, implement a single-slot cache buffer for writing. This is like the cache buffer for reading, but it absorbs writes instead of prefetching reads.
- This will improve your performance on character I/O tests. If you do this well, you should now match or beat stdio’s performance on all sequential I/O tests!
- Then, fix your code to handle seeks correctly (but not necessarily in a high-performance way). This is actually pretty easy.
- This should make your code produce correct results for all tests.
- Then, fix your code to handle seeks correctly, but with good performance for
reverse61. For ideas, try running
stdio-reverse61variant. What does it look like stdio is doing?
- This should make your code roughly equal stdio’s performance on all tests.
- Then, if you feel ambitious, you might try changing your code to use memory-mapped I/O when this is possible. Note: Memory-mapped I/O is not always possible, though, so keep your old block cache around for pipe files and other non-mappable files. (Mmap is not required; it is optional.)
- This should make your code beat stdio on some non-sequential I/O tests!
- Then, if you have additional time and feel even more ambitious, implement an associative cache that works for non-mappable files or for very large memory-mapped files.
- Something like this will get the highest performance.
- It is difficult and rewarding to implement an associative cache. You’ll learn a lot! But design carefully so you don't make your other code more difficult to read and maintain. In fact, you might try working on a separate branch initially.
- Read our file descriptors notes.
- Write code to handle sequential I/O first. This isn’t so hard and covers many important cases.
- Some of our tests, particularly on shorter files, are noisy, and can produce different timing results when run multiple times.
- You will likely need to change most of the functions in
- To handle reordered I/O and particularly stride I/O, you will need to be clever and implement more complex cache algorithms.
- Stdio is a well-written package! It is OK if you can’t always beat it.
- Write your own tests! This will help you shake out bugs in your code, particularly correctness bugs. What diabolical things can you think of to try? You can add new tests pretty easily; just edit
- You can run the tests on their own, too.
make checkcreates some useful input files for testing and puts them in
You are allowed to make a couple assumptions.
- You may assume that any file descriptor passed to
io61_fdopenhas its file pointer set to 0 (the beginning of the file).
- You don’t need to set the file pointer after every call to
If you want to compile without optimization (which might help you debug), run
make O=0 or edit the GNUmakefile to set
O = 0 by default. Your code should work safely with sanitizers turned on; try
make SANITIZE=1 check.
Extra credit: Deadlock
We also release a program,
pipeexchange61, that demonstrates a problem with conventional blocking I/O. The
pipeexchange61 program forks two copies of itself. One copy, the requester, sends requests to the other copy, the responder. The requester can send many requests back-to-back and only then wait for responses (a form of batching). When you run
pipeexchange61, the program appears to get stuck! Why? Can you construct an I/O library that unsticks
pipeexchange61, without modifying
You will turn in your code by pushing your git repository to github.com and updating the grading server with your repository.
Don’t forget to fill out
README.txt. But don’t put your name there.
This pset was originally created for CS61.