15-410 Homework 2

This homework assignment is due Friday, December 6, 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

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

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 - Interrupts

A major concern for P3 has been preemptibility, i.e., how quickly the kernel can receive a device interrupt and switch to another thread if appropriate. If your P3 were extended to run on a multi-processor machine, which in fact has been done in previous semesters for P4, the result would be multiple processors, each one able to react quickly to incoming device interrupts. And in a sense this is the typical state of affairs.

But there are some kernels that take a very different approach. If this different approach were used on a two-processor machine, one processor would run kernel code designed to respond nimbly to device interrupts, such as timer ticks, keystrokes on a USB keyboard, mouse events from a USB mouse, etc. That processor would have interrupts enabled almost all of the time. But in a system following this different approach the other processor would do something very different. The second processor would always have interrupts disabled (!!) and would spin in a tight loop polling certain hardware devices (for example, an Ethernet device). Those devices would be configured so that they wouldn't generate interrupts when they had something to say; instead, they would just set a flag bit (perhaps one flag bit would be "packet available in receive buffer" and another flag bit would be "ready to transmit packet"). The second processor would, fairly quickly since it's running a short polling loop, see the flag bit set, and would run an I/O-event handler routine for the device. The I/O-event handler routine would be a trivial rewrite of what would normally be the interrupt handler for that device: it would examine the device state, determine what the device wants, perhaps awaken blocked threads, etc. But the end of the I/O-event handler routine would not involve dismissing the in-progress interrupt from the device, because the device wouldn't have raised an interrupt.

Overall, one processor would process interrupts normally, thus alternating between running regular application/kernel code and handling some I/O events, while the other processor would process other I/O events without any interrupts. Thus the second processor would be running only completely non-preemptible code (!!).

Part A

Briefly explain (or at least speculate about) why this approach might be used. Why would people go to the trouble of writing framework code, and editing device-driver code, to build such an architecture? It is reasonable to assume that the devices that will be configured to generate interrupts are relatively slow, i.e., do not generate many interrupts per second (as is true for keyboards and mice), while the devices that are handled via the special interrupt-free approach are high-throughput, such as an Ethernet controller (100,000 packets received and/or sent per second).

Part B

What kinds of computer would this approach be good or bad for? For example, would this approach be good for a cellular phone?

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

[Last modified Wednesday December 04, 2024]