15-410 Homework 2

This homework assignment is due Friday, April 29th 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, XyWriter, 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 pgp.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

Consider this virtual-to-physical mapping data structure, which could be used for an x86-like processor instead of the traditional x86 page-directory/page-table structure.

1. The map descriptor register (MDR) contains two fields.
   • (MDR & 0xFFFFF000) is the base address of a hash table in physical memory.
   • (MDR & 0x00000FFF) is the number of hash table buckets in the table.
2. Each hash table bucket consists of four page-map entries located sequentially in memory.
3. Each 8-byte page-map entry contains these fields:

   User Flags (4 bits)

   Valid, Read, Write, Execute

   Kernel Flags (4 bits)

   Valid, Read, Write, Execute

   Access Flags (2 bits)

   Referenced, Dirty

   Other Flags (14 bits)

   Cache control, I/O bus control, coherency control, kernel-defined

   Page Address

   High-order 20 bits of virtual address.

   Frame Address

   High-order 20 bits of physical address.

When the translation unit needs to translate from a virtual address to a physical address, it applies a (documented) hash function H() to the upper 20 bits of the virtual address, divides the resulting hash by the number of hash table buckets, and uses the remainder as a bucket index. The translation unit then checks, in order, to see if any page-map entry in the bucket represents a translation for the page.

In particular, the TU compares the virtual page address being translated to the virtual page address field in the zeroth PME of the bucket. If they match and at least one of the two valid bits in the PME is on, the PME represents the translation for this page. The frame address, permission bits, and flags are then checked, applied, and updated as appropriate. If the virtual page address doesn't match PME[0].vpn, or if neither valid bit is on, the check is performed against PME[1], etc.

If the virtual address has a translation but the permission bits are inappropriate, a permission fault occurs. If the virtual address does not have a translation, a translation fault occurs. If the number-of-buckets field in the MDR is zero, your manager will yell at you.

Part A

In what circumstances do you believe the x86 mapping structure is superior to this one? Explain your reasoning.

Part B

Can you argue that this mapping structure is superior to the x86's? Explain.

Question 3 - Storage

Imagine you are interviewing for a summer internship at Seagate Research in downtown Pittsburgh. Your hiring manager asks you to explore two possible modifications to their well-known Barracuda line of disks:

1. Spin the platters twice as fast, or
2. Add an ultra-capacitor (basically, a solid-state electricity buffer) which can meet all of the disk's power needs for five seconds in the event of a power failure.

Your interviewer asks you to suggest which application market segments would be most receptive to disks with each of these modifications and to suggest which one you think Seagate should pursue. Your answer should be approximately three to five paragraphs.

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

[Last modified Saturday April 23, 2005]