15-410 Homework 2

This homework assignment is due Friday, December 7th 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, XyWrite, 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 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 - Virtual Memory

Suppose our Simics PC configuration were extended to add a disk device and that we gave you a simple disk device driver. This hardware could be used to virtualize RAM, i.e., to use physical memory frames as a cache for a larger, virtual, memory system. It is common for operating systems to evict pages holding user memory which hopefully will not be needed for the near future. But some systems go further and page out parts of the kernel as well.

Part A

Identify four specific kinds or areas of kernel code or data which could not safely be paged out, describing briefly why each would be unsafe. Sort your list so that the most unsafe entries come first.

Part B

What one kind of kernel code or data do you think would be most attractive to page out? Explain briefly.

Question 3 - Scheduling

Consider the following argument.

Threads executing in the kernel frequently must acquire locks in order to do their jobs. Any time a thread executing in kernel mode is preempted while holding a lock this means that no other thread will be able to acquire that lock--this includes threads belonging to other tasks, whom it is "not fair" to delay. Therefore, it is to the benefit of all threads in the system for threads executing kernel code to quickly finish their work and return to user mode.

Now consider this proposal for a Project 4 assignment: re-work the scheduling infrastructure of your kernel so that runnable threads executing system calls, and runnable threads executing the page-fault handler, are run before all other threads. This can be thought of as a two-level scheduler, with round-robin scheduling within each level and strict priority between levels.

Part A

There is an interesting conceptual issue associated with this assignment: any time a scheduler is considering which thread to run, candidate threads are by definition not running, and are thus by definition "in kernel mode". Describe briefly how a scheduler can determine which threads in kernel mode are there "for real" versus having been forced into the kernel by an interrupt.

Part B

Is the proposed scheduling design wise? If so, explain. If not, briefly describe a program which would make your objection clear. Code or pseudo-code is acceptable if brief, but is not required.

Part C

Briefly suggest an alternate scheduling strategy which would be sensitive to the argument described above.

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

[Last modified Wednesday December 05, 2007]