15-410 Homework 2

This homework assignment is due Friday, May 3rd at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, please turn your solutions in on time. Late days are not available for this assignment.

Homework must be submitted (online) in either PostScript or PDF format (not: Microsoft Word, Word Perfect, Apple Works, LaTeX, XyWrite, WordStar, etc.). A plain text file (.text or .txt) is also acceptable, though it must conform to Unix expectations, meaning lines of no more than 120 characters separated by newline characters (note that this is not the Windows convention, and MacOS has two different conventions). Except as otherwise directed (in the crypto question), turn in your answers as .../$USER/hw2/$USER.pdf, .../$USER/hw2/$USER.ps, or .../$USER/hw2/$USER.text. If you use another filename, there is some risk that your solutions will not be credited to you. Please try not to submit your homework into your book-report directory or the other way around.

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

As you go through the steps of working on this question, try to think carefully about what each step is accomplishing in terms of underlying cryptography primitives.

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 Design

As you know, many operating systems "play tricks" using virtual memory hardware in order to improve performance for certain workloads. One such trick is "copy on write", in which the operating system simulates copying some read/write pages from one address space to another by instead marking the page-table entries read-only and then copying them to the target address space. The result is that both address spaces share the same frames as long as neither one tries to make any changes. The primary data structure necessary to implement copy on write is a reference count per frame: as each address space with a logical copy of some page receives a page fault, it makes a physical copy into a new frame, then decrements the reference count of the shared frame. Eventually there will be zero references to the shared frame and it can be freed. Because the reference count for each frame is much smaller than the frame and may enable the frame to be re-used many times, devoting some amount of RAM to reference counts is often considered to be a reasonable use of space.

Another thing operating systems typically do with virtual memory hardware is implement partial memory residence, i.e., treating RAM as a cache of the set of all pages, with pages which are not currently in RAM being stored on disk. Most VM hardware provides "dirty" and "reference" bits in each page-table entry; a "pager daemon" can inspect the reference bit of each page in each address space to decide when a particular page is no longer important enough to be backed by a RAM frame. If a page is judged to be unimportant, its contents can be stored to a disk frame (storing is non-optional if the "dirty" bit is on), the location of that disk frame can be recorded "somewhere", and the RAM frame can be given up for some more-urgent purpose. Aside from the "dirty" and "reference" bits, the main data structure necessary is a map from non-resident pages to disk locations. In some old-fashioned systems, that map was stored in the page-table entries: if the "present" bit of a page-table entry is off, then the other bits of the PTE can be used to store a disk block number.

Individually, neither the copy-on-write optimization nor paging to disk is particularly challenging. But, as is often the case in the real world, combining features results in non-linear implementation complexity. In this question we will investigate why designing a VM system that handles both copy-on-write and paging to disk might be challenging.

Part A

Imagine that we have a system which implements copy-on-write but not paging to disk (this is true of some Pebbles kernels). Imagine that we wish to add a paging daemon to the system. Explain why doing this in a straightforward fashion would undermine the effectiveness of the copy-on-write optimization.

Part B

Now imagine that we have a system that implements paging to disk but does not implement copy-on-write (imagine for concreteness that disk block numbers are stored in the unused bits of non-present page-table entries). In particular, imagine that in this system fork() is implemented using a page-copy loop, and that fork()ing an address space with some non-resident pages will result in those pages being brought into RAM so that they can be copied across to the new address space. Explain why adding copy-on-write to this system (which would include not bringing each paged-out page into RAM to copy it) would be challenging. Keep in mind that systems generally implement paging to disk so that the size of the virtual memory can be dramatically larger than the size of the physical memory (10X or maybe 100X).

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-s13/pub/access_hw2

[Last modified Monday April 29, 2013]