15-410 Homework 2

This homework assignment is due Friday, May 4th at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, please turn your solutions in on time.

Homework must be submitted (online) in either PostScript or PDF format (not: Microsoft Word, Word Perfect, Apple Works, LaTeX, XyWrite, WordStar, etc.). Except as otherwise directed (in the crypto question), turn in your answers as either .../$USER/hw2/$USER.pdf or .../$USER/hw2/$USER.ps. If you use another filename, there is some risk that your solutions will not be credited to you.

As usual, you may discuss this assignment with others, but you must then go off by yourself to write up the solution.

Question 1 - Public Key Practicum

This question is not hard, but it does take some time to do it right. Please don't leave this question to the last minute, and think carefully about what the various steps accomplish.

Follow the directions in gpg.html to generate a PGP key ring, containing public and private keys for digital signature and encryption purposes. Do not turn the key ring in to your hw2 directory. Instead, follow the directions on how to export the public key information from the key ring into a file, hw2/$USER.asc. Then create a secret message for the course staff, in hw2/$USER.secret.asc.

Question 2 - Virtual Memory

Part A

Consider a CALL instruction, e.g.,

CALL printf

Assuming the kernel has "plenty of memory" (i.e., is not forcing pages out to the swap disk), how many page faults might a single CALL instruction encounter? Explain. You may find it helpful to disassemble some code using simics and/or gdb.

Part B

How many page faults could a single RET instruction "reasonably" (non-pathologically) encounter? Explain. If you wish, you may give and explain a number for the pathological case as well as the "reasonable" case.

Part C

In general, if you counted the number of page faults encountered by all CALL instructions in one run of a program and compared that to the number of page faults encountered by RET instructions in the same run of the same program, would the CALL number be noticeably greater than, about the same as, or noticeably less than, the RET number? Explain.

Question 3 - File System Performance

Before beginning to work on Project 5 (the file system project, which will be due on the last day of the final-exam period), you decide to do some simple performance investigation of the file system on a handy nearby Linux machine. In particular, /tmp happens to be an ext2 file system stored on the "hda7" partition of a Seagate Barracuda 7200.10 200 gigabyte disk.

You write a program called timeseek which opens a file and then repeatedly times how long it takes to execute a function randread(int fd), which selects a random 4-kilobyte block of the file, uses the lseek() system call to set the file descriptor's cursor position to the start of the selected block, and then uses the read() system call to read the block's data into memory.

Because the Seagate data sheet for your disk says the average time for a 1-sector transfer is 4.16 milliseconds, you expect that most invocations of the randread() function will take roughly that long--or a little longer, maybe 5 milliseconds, since the file system presumably transfers 4-kilobyte blocks rather than individual sectors. But you are surprised to see that, even on an idle system, the time per randread() varies wildly--a plot of the times shows a cluster around 5 milliseconds, but also smaller clusters centered on 10 milliseconds and 15 milliseconds. Intrigued, you run timeseek on files of various sizes. It appears that larger files exhibit more of the surprisingly slow seek times, though you can't see a more-detailed pattern.

While you are silently pondering what might explain this phenomenon, your project partner reminds you that Unix kernels provide a file interface to raw disk partitions. That is, by opening /dev/hda7, your program can do random I/O within a "file" larger than any which could fit inside the /tmp file system, since the device file represents not only the data sectors of /tmp but also the sectors used to store metadata. Imagine your surprise when random-block reads out of /dev/hda7 cluster nicely around 5 milliseconds.

Part A

Please explain this seeming paradox. Why is random I/O within this largest-possible file reliably faster than I/O within medium-sized files?

Part B

If you can, explain the odd clustering of seek times within files in /tmp.

Notes

We're just kidding--there is no Project 5. If you wish there were... you might give serious consideration to 15-412 and/or 15-610.
On a Linux system, you need superuser privileges to run the timeseek program on /dev/hda7. It is not polite to beg the Wean Hall CCon to tell you the root password for the cluster machines.

Helpful Hint

By the way, if you think you are having AFS permission problems, try running the program located at
% /afs/cs.cmu.edu/academic/class/15410-s07/pub/access_hw2

[Last modified Friday April 27, 2007]