15-410 Homework 2

This homework assignment is due Friday, December 5th at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, turn your solutions in on time.

If you wish to turn in your homework on paper, you may do so, but due to the lack of a timestamped drop-box, you will need to bring the paper portion of it to 3503 Wean Hall by 17:00.

Homework must be submitted 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.

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 - Kernel stack size

When we gave out an exam question on how to compute (or approximate) the kernel stack size required by a particular kernel, we received many answers of the form "pick a size and see what happens".

Measuring the behavior of a system on a particular set of inputs is dangerous, because if the inputs you choose don't cover the worst case then your answer will be inadequate. That said, measuring the typical case is often easier than computing the worst case, or at least it can be more fun.

To that end, take your group's Project 3 kernel and instrument it to measure the maximum amount of kernel stack actually used by a process during a single boot.

1. Ensure that your kernel fills fresh kernel stacks with some known value (various values are possible, and you may find that your kernel behaves differently depending on which value you choose...oops!).
2. When freeing a kernel stack, scan it to see how much of it was modified.
3. Record in a global variable the maximum-observed stack depth so far.
4. Use lprintf() to print this variable, either each time it grows or when halt() is called.
5. Run five test programs (yours or ours) and report the maximum values observed due to each one. Try to choose your test programs to exhibit a wide range of kernel stack usage. If you use some of your own test programs, please place a copy of the source for each in your hw2 directory.

Please note that althrough Project 3 was a group project this homework is not, so you should work by yourself with a private copy of your group's sources.

Question 3 - IPC

(a) On slide 14 of the IPC/RPC lecture, I presented a brief code example and claimed there was "a problem" with it. Draw a "system resource-allocation graph" (as presented in the text and in class) depicting a deadlock situation that can arise from running this code. Your graph must depict both processes and resources, and should do so in an accurate way. For example, it should be "sensible" for the particular resource type(s) in question. Also, assume that the send() operation is buffered, i.e., most of the time the send() system call allows a sender to queue a message for a receiver and returns essentially immediately.

1. Process 1:

   send(P2, &p1-my-status, sizeof (p1-my-status));
   receive(P2, &p1-peer-status, sizeof(p1-peer-status));
   

2. Process 2:

   send(P1, &p2-my-status, sizeof (p2-my-status))
   receive(P1, &p2-peer-status, sizeof(p2-peer-status))
   

(b) How should an operating system deal with this sort of problem? Suggest a design and briefly defend it.

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

[Last modified Saturday January 10, 2004]