15-410 Homework 2

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

While we hope you think through all the questions, for full credit on this assignment you need turn in only Question 1 and either Question 2 or Question 3.

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 - Being nice to users

Consider what happens in your kernel if physical memory is exhausted and a thread calls new_pages(). Hopefully, it should receive an error code and continue to run. But what if instead the thread had tried to grow its automatic stack region (by, for example, a PUSHL instruction)? There is no way to "return an error" for stack growth, nor can the thread continue user-mode execution before the stack has grown.

What should your kernel do in this case? One simple and popular solution would be to kill the "offending" thread. Aside from being easy, this might result in physical memory being freed, thus making the system less likely to kill other threads in the future.

Now consider a kernel architect who wishes to improve the service given to user programs, and decides to pursue the approach of temporarily suspending the execution of any thread which needs more automatic-stack memory until some memory becomes available.

Part A

Briefly but convincingly explain a horrible disaster that could result from a simplistic implementation of this approach.

Part B

What do you think should be done to address the issue of automatic stack growth when the system is out of memory? Briefly outline two options and then argue for one. Three medium-sized paragraphs should suffice.

Question 3 - O_APPEND

If you examine the documentation for the Unix open() system call, you will observe that there is an optional flag called O_APPEND which modifies the behavior of all write() system calls applied to the file descriptor returned by the open() call. Append-mode opens are often used when multiple programs wish to add records to system log file.

Part A

Imagine you were porting a program which was designed to use O_APPEND to a version of Unix which does not support that flag. Briefly sketch the implementation of a C function append_write() which has the same signature as write() (i.e., takes a file descriptor, buffer address, and length, and returns a length), and which simulates, to some degree, the behavior of write() applied to a file descriptor obtained via an O_APPEND call to open(). There are at least two reasonable answers to this question.

Part B

Of the concurrency control primitives you implemented for Project 2, which one(s) do you think a Unix-like kernel is most likely to employ internally while implementing O_APPEND? Explain, using a few sentences (or, if you wish, a few paragraphs, but a long answer should not be necessary).

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

[Last modified Sunday April 25, 2004]