15-410 Homework 2

This homework assignment is due Friday, May 2nd 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

Suppose that our Simics PC configuration were extended to add a disk device and that we gave you a simple disk device driver. This hardware could be used to virtualize RAM, i.e., to use physical memory frames as a cache for a larger, virtual, memory system.

The x86 hardware mapping unit defines "present" bits in both the page-directory entry and the page-table entry. As we discussed in class, a "not present" page-directory entry can be used to cheaply mark a large part of an address space as invalid. However, in a kernel using a paging disk, when a particular page table entry is marked "not present" this may indicate either that the address is invalid or that the indicated page has been evicted to disk. Likewise, a "not present" page directory entry may indicate that an address range is permanently invalid or temporarily unavailable due to a "miss in the RAM cache".

Part A

Imagine that a program successfully stores a value into some memory page but later receives a page fault while trying to retrieve that value. Consider the case where the page fault exception is raised because the "present" bit is turned off in the relevant page directory entry. Assume that the address is still logically valid, i.e., the program is entitled to fetch from that address, the kernel will fix the problem without intervention from the program, and the instruction will eventually succeed when retried.

This situation strongly suggests that the kernel embodies a particular feature, design decision, or practice. Explain--why was it sensible for this fault to happen?

Part B

Briefly sketch the sequence of operations the kernel will take in response to this fault. Try to provide roughly the level of detail given in "Another story about read()" in the "Hardware" lecture or the "I/O Completion Example" in the "Yield" lecture.

Question 3 - Non-blocking send()

Consider the example presented on slide 20 of the "IPC/RPC" lecture. Note that the send() operation in this example is "non-blocking", meaning that it is not defined as blocking until a matching receive() operation is posted (for those of you doing Project 4, this is not the same send() operation as the one you are implementing).

Part A

Draw a picture of a deadlock which may result in this scenario. You may wish to make explicit assumptions about the number of objects in the system (e.g., assume a certain number of processes).

Part B

Which deadlock management approach would you suggest be applied to this system? Why?

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

[Last modified Monday April 28, 2008]