Carnegie Mellon
SCS logo
Computer Science Department
home
syllabus
staff
schedule
lecture
projects
homeworks
 
 

15-410 HW2 solutions (Fall, 2004)



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 - Nuts & Bolts

Part A

How could the second output happen?

The compiler (or the link editor) was implementing what is sometimes called a "shared string pool", meaning that each string constant (e.g., "abc", "def") occurs only once in the executable file even if it is present multiple times in the source code. This can save non-trivial amounts of space, especially in comparison to the amount of memory available on older machines. For example, many programs contain many occurrences of "%s\n".

When editstr() ran, it changed the sole copy of "fred" (oops!).

Part B

How could you arrange for this program to crash even though the Unix kernel you're running on doesn't have the concept of an rodata region?

The straightforward solution, which was implemented on some systems, was to teach the link editor about read-only data, which doesn't require changing the kernel. As one of its final steps the link editor would place all data marked as read-only into the text segment of the executable. This worked ok on most systems because nobody would ever jump to those "instructions".

In the old Unix tradition this was sometimes done semi-automatically after compilation using a small script called :rofix (read-only fix).

By the way, this approach was impractical for some versions of the PDP-11 which tried to reduce the harshness of the 64 kilobyte address space limit (!!) through a technique called "split instruction and data spaces" or "split I & D", a charming bit of computing history which you will not be expected to explain on the exam.


Question 3 - Platform Issues

On a multiprocessor, now matter how hard one processor turns off interrupts, that won't stop other processors from executing instructions. In other words, one instruction stream can't achieve mutual exclusion from other streams by disabling interrupts. On a uniprocessor, interleaving comes only from voluntary context switching (e.g., yield()) or from interrupt handlers which voluntarily invoke something yield()-like. So if a code sequence doesn't call yield() and can't be interrupted by anybody who would then it's easily atomic with respect to all other code sequences. But on a multiprocessor interleaving is an inescapable fact of life.

What to do? Use some mutual-exclusion protocol to make threads running on different processors take turns entering each critical section. There are lots of options, which we covered long ago before Project 2--atomic exchange (XCHG), compare-and-swap, fetch-and-add, the i960 magic lock bit, and so on. And it's probably a good idea to encapsulate the particular method best for your machine inside an appropriate abstraction, so most of your code will move easily to a machine with a different instruction set. C-callable pseudo-functions are a lot easier to swap in and out than #ifdef, asm(), __volatile__, and other unsightly incantations.

By the way, on many multiprocessor systems it's possible for code on one processor to arrange for another processor to receive an interrupt. You can imagine that if all processors run the same interrupt-handling code it would be possible to attain mutual exclusion by having processors interrupt each other into submission. But it would probably not be advisable.


For further reading...

Here is last semester's homework page.


[Last modified Wednesday December 07, 2005]