15-410 HW2 solutions (Spring, 2013)

Question 1 - Public Key Practicum

If you did this problem correctly, in a couple of hours your hw2 directory should contain a $USER.message.decrypted file. If not, check to see if there is a $USER.ERROR file. If not, a popular problem is that you used file names other than the ones specified in the assignment, the grading script wasn't able to guess what you meant, and the grader hasn't yet had the time to manually intervene.

By the way, your encrypted messages to us were read and, generally, appreciated.

The best inscrutable song lyrics were provided by Adrien Ghosn. The best potential exam question was provided by Damien Engels. Of course we're not going to reveal the messages--they're secret!

Question 2 - Virtual Memory Design

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.

The main problem with combining copy-on-write with paging is that the desirable data structures are different. In the case of copy-on-write, the key question we have is "How many people are referring to a particular frame?"; In the case of paging, we want to know "How has a particular program been using each of its pages recently?".

In the most straightforward sense, a copy-on-write kernel tracks a reference count per frame, but the virtual memory hardware tracks usage information per page. Imagine that some page has been "forked" into multiple address spaces by a copy-on-write operation and that the paging daemon, while scanning the universe of (address space, page) pairs, finds that a page's reference and dirty bits are both off. This page is a good candidate for eviction from RAM to disk... or is it? Since this frame is shared by other pages, maybe the reference bit is on in page-table entries in other address spaces. Obviously we can figure out which frame is backing this page, and we can even check the reference count to see how many other pages are pointed at the same frame, but there is no way to map back from the frame to the list of pages in the other address spaces---unless, of course, we add such a data structure (one way to do this would roughly double the amount of memory devoted to page tables). By adding a lot of complexity and space we could let multiple address spaces "vote" on whether this page should be evicted or retained. This general approach causes copy-on-write to keep working well despite paging, but will cause it to cost more space and time.

Another thing we could do is "shrug our shoulders" and split the page---in other words, allocate a new frame, copy the bits, decrement the original frame's reference count, and evict the newly-private page out to disk. According to this approach, paging directly attacks the utility of copy-on-write by shutting down the optimization when it's encountered.

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.

The problem we are considering here is how to "fork" a page which has already been evicted to disk. The location of the page's data on the disk is being stored in the page-table entry. At a high level of abstraction, forking the page is "easy": the new address space, like the old one, will get a page-table entry that has the "present" bit off and uses the rest of the bits to store the disk sector number. Because bringing the page in from disk is so expensive, we hope that neither address space will get around to using the page (for reading or writing) before that part of the address space is deleted. But even if we are lucky in this sense we still have a problem: now two address spaces, not one, "own" that disk sector, so somehow we will need to reference-count disk sectors! This is more troublesome than reference-counting frames: in the case of frames, we can argue that burning one word per frame for reference counts occupies only 0.1% of RAM and may vastly increase the utility of the remaining RAM. Unfortunately, it is usually true that our paging space will be much larger than our RAM, so storing disk-sector reference counts in RAM may not be feasible. Because disks are big, we could store disk-sector reference counts on disk, but this is either slow or messy depending on how we do it.

Discussion

How do real systems address these issues? It depends.

Linux's basic approach is to track more information about pages and frames. In particular, it is possible to map from a frame to a list of the address spaces that are using the frame. Further reading: Understanding The Linux Virtual Memory Manager (Gorman, 2007).

In contrast, Mach's approach is to think less about pages and frames and more about memory ranges. Contiguous hunks of memory are treated as objects, and each address space consists of a list of mappings of objects, e.g., "From 00000000 to 00008000 we refer to the first 8 pages of memory object 2412341". Each address has hardware page tables, but they can be deleted at any time; when a page fault occurs, the VM system consults the object list to determine which memory object is indicated and which page within that object is wanted; if the page is resident, an appropriate entry is made in a page table (which is allocated if necessary) and the instruction is re-run. When an address space is forked, the object list is duplicated (and each referenced object's reference count is increased). Meanwhile, paging to disk is a function of the underlying memory objects, not of the address spaces. Because the number of memory-range objects is relatively small, it isn't a burden to reference-count them; because each memory-range object evicts each page at most once, there is no need to reference-count disk sectors. This approach has many attractive features, but carrying it out involves many complexities. In particular, when a copy-on-write fault happens, the kernel creates a shadow object which sits in front of a pre-existing memory-range object and stores the changed pages, i.e., the ways that the address space generating the faults differs from the underlying memory-range object. Depending on the sequence of fork() and IPC operations and which pages are faulted on, it is possible for deep, bushy trees of shadow objects and "sharing maps" to be built up. Further reading: Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (Rashid et al., 1987).

Meta-discussion

This question will hopefully provide you with some sense of what a "design question" might be like. This question was focused on describing design problems rather than (as is more typical on exams) asking you to propose a solution to a problem. However, this question is like a "regular" design question in that answering it depends on your understanding of underlying issues and your ability to explain how they interact.

For further reading...

Here is last semester's homework page.

[Last modified Saturday May 04, 2013]