15-410 HW2 solutions (Fall, 2003)

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. For the second semester in a row the appropriate quote from "Sneakers" was made.

Question 2 - Kernel stack size

Frankly, we have no real idea which test will use the most kernel stack--in good part it depends on how you wrote the code for the various system calls and on how interrupts happen to strike you. This is more a practicum question/thought inducer than a "right answer" situation. Hopefully when you look at your results you will be able to explain why they turned out the way they did.

Question 3 - IPC

(a) There are lots of ways for this to deadlock. For example, maybe your system has only one message buffer. Then P1 can seize it, fill up with a message, and send it. P2 will then be holding the message buffer when it tries to acquire it to fill it up and send it to P1.

Here is another possibility. Maybe the system has two message buffers, but an evil P3 has seized them:
send(P1, &msg, sizeof (msg));
send(P2, &msg, sizeof (msg));
Now both P1 and P2 are holding buffers (because they are not receiving their contents) while waiting for buffers.

(b) Some operating systems choose not to deal with this very much. With Unix pipes, the traditional rule was that a pipe was guaranteed to hold something like 4K of data before the next write() would stall. So two processes could send each other data via pipes as long as neither one would send more than 4K before read()'ing. The system would refuse to create a new pipe unless it could allocate 4K for it.

These days, pipes are really implemented via socketpair(), which, as far as I can tell, provides no guarantee at all.

Probably the best thing to do would be detection and recovery. Once in a while you could scan the global process list for anybody waiting for an IPC buffer allocation and paint them a certain color; if the next time you do a scan there are processes painted with the old color, choose one or all and have their send() calls return EDEADLOCK.

[Last modified Saturday January 10, 2004]