Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Assignment 2: Caching and File I/O

In this assignment, you’ll gain experience with caching by writing your own buffered I/O library.

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://code.seas.harvard.edu/cs61/cs61-psets.git

Then run git pull handout master. This will merge our Assignment 2 code with your previous work. If you have any “conflicts” from Assignment 1, resolve them before continuing further. Run git push to save this merge back to code.seas.

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. Make sure you update the grading server.

Goal

We’ve released a very simple IO61 I/O library, in io61.c. Our version of IO61 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.

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 madvise or 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:

We will grade your work based on how much you speed up sample executions of the handout programs—and other secret tests—with points deducted for incorrect results.

All your code should fit in io61.c.

Evaluation

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-cat61, stdio-blockcat61, and so forth).

Run 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 will also measure your code’s performance against that of other students in class. :)

We may update the tests during the pset release period.

Roadmap

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.

Hints

You are allowed to make a couple assumptions.

Building

If you want to compile with gcc, rather than clang, run make PREFER_GCC=1. 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. The makefiles will remember your setting for PREFER_GCC until you run make clean.

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 pipeexchange61.c?

Turnin

You will turn in your code by pushing your git repository to code.seas.harvard.edu. Inform us on the grading server if you have changed partner or repository from pset 1.

Don’t forget to fill out README.txt.

We are requiring an intermediate checkin for this problem set. Your grade on the intermediate checkin will be replaced with your final grade on the pset. The intermediate checkin is due 10/3 at midnight for college students, one day later for extension. By 10/3, you should roughly equal stdio’s performance on all sequential I/O tests. (It’s OK for your code to be broken on non-sequential tests.)


This pset was originally created for CS61.