15-410 HW2 solutions (Spring, 2006)

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.

Question 2 - Virtual Memory

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.

1. Don't page out the page-fault handler. That would clearly be bad.
2. Don't page out the device driver for the disk.
3. Since you'd better do something useful while you're waiting for a faulted page to come in from the disk, you'd better not page out your scheduler and context-switch infrastructure
4. Paging out your timer device driver wouldn't be super-wise either. Actually, the same is true of all of your interrupt and exception handlers.
5. Also, don't page out the data that any of those things need (basically, queues).

Part B

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

To some extent it depends on your kernel. You might think of paging out large kernel data structures related to user processes which have been substantially paged out... some operating systems page out page tables. For Pebbles-like kernels an attractive target is probably kernel stacks, though you would probably want to be a little careful about exactly when to page them out and back in (page faults in certain parts of context switch might not be so fun).

Question 3 - Scheduling

Part A

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.

Probably the simplest way would be for the assembly-language wrappers to set a thread-specific flag on the way in and clear it on the way out. Howver, that would require the scheduler to search around for high-priority threads, so some linked-list action might be better.

Part B

Is the proposed scheduling design wise?

Any process able to spend lots of time running in the kernel (as opposed to blocked in the kernel) would deny service to all threads trying to get work done in user space (e.g., mandelbrot). Since we generally buy machines to run user applications, a system which spent all its time busily in the kernel would be bad. What kind of program would spend essentially all of its time in the kernel running busily away? How about fork_bomb? A loop around gettid() wouldn't be as good, because such a program would spend a greater proportion of its time in user mode... though you could probably have some fun by hand-coding a long string of INT instructions back-to-back.

Part C

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

One approach would be a form of priority inheritance: acquiring a lock would raise a thread's priority until the lock were relinquished. Another, cruder, approach would be for lock acquisition to disable interrupts. Either way it would be important to not hold that kind of lock for a long time while doing work, or else a practice designed to stop other threads from being delayed would act to delay them!

For further reading...

Here is last semester's homework page.

[Last modified Friday December 07, 2007]