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.
The best message was Mark Hairgrove's; the second best was Mike Kasick's. The wisest was probably Zoe Ouyang's. No, of course we're not going to reveal the messages--they're secret!
Question 2 - Nuts & Bolts
The ELF file format specifies addresses for the text, data, rodata, and bss regions, but not the stack region.
Briefly explain why it is ok for this information to be missing from the executable file.
This is acceptable because the compiled instructions forming the program text don't depend on where in the address space the stack is located. Accesses to the stack are relative to the stack pointer (or the base pointer, in stack disciplines which have one)--this includes pushes, pops, fetches, and stores.
Since the program doesn't care where the stack is located as long as it "works" (implements these relative operations), there is no reason for the executable file to (over)specify an address. This means that the kernel has substantial freedom about where the stack is placed.
The fact that the executable file doesn't specify the address range used by the stack allows interested kernels the freedom to deploy a mild optimization for some programs. Briefly explain, referring to the Pebbles environment if you wish to use a specific example.
Consider slide 45 of the first VM lecture. Observe that the upper page table is required only because the stack is at the far end of the address space from everything else. This is often done so the stack and heap have "enough" room to grow toward each other without colliding, but how much "enough" do we really need? If a kernel decided to fit a whole program (text, rodata, data, bss, heap, and stack) into four megabytes, then mapping all of user space could be done with one page table.
How practical is that? Consider these section sizes for the Pebbles shell (excerpted from the output of size --format=SysV shell):
So an important program like the shell, if allowed a megabyte of heap and a megabyte of stack, could easily be mapped by a single page table. In fact, the Minix OS uses a similar approach.
Question 3 - VM
On the IA32 platform, we have two ways to remove entries from
the TLB, namely setting
Explain how to implement
The job of
Explain how to implement
flushing the whole TLB in terms of
This problem, as stated, is significantly more painful.
Without a way to inspect the contents of the TLB, it will be necessary
to perform 4,194,304
However, some processors have special instructions which allow the kernel to read (or even update) particular slots in the TLB, or to request the index of the TLB slot mapping a particular page. On such processors (including certain flavors of PowerPC) a mass-invalidate instruction may not be necessary.
Now imagine you can purchase a version of the IA32 processor family which implements one TLB-removal method or the other, but not both. Which would you choose, and why?
Strictly speaking, this depends on how often the kernel
must invalidate one page versus invalidate an entire
and how large address
spaces typically are (if you know that the VM range from
1 gigabyte to 3 gigabytes is not used by any process in
the system, then there is no need to
Practically speaking, I believe most people would regard mass-invalidate as a necessity and invalidate-one as a performance enhancement.
For further reading...
Here is last semester's homework page.
[Last modified Saturday May 06, 2006]