The objective of this exam is to find out what you know about operating systems and to assess your ability to identify and develop solutions for problems that arise in operating systems. Note that the questions have many "right" answers, so be sure to justify your answers. In particular, state any assumptions you make. Point form answers are acceptable. Grammar optional.
You conceive of a get-rich scheme of retrofitting virtual memory onto old government computers. Unfortunately, the most prevalent computer in use, the Obsolete-3000K(and-beyond!)(tm), supports the following odd instruction:
mem_incr r # corresponds to: "mem[mem[r]++]++"
Part A (10 points). Explain why a program that executes this instruction may not work after you add virtual memory. You will have to make some assumptions about a reasonable way for VM to work. Please state these assumptions and be very concrete about what causes a problem and why.
Part B (10 points). You notice that the Obsolete also supports a typical load instruction:
ld r0, r1 # corresponds to: "r0 <- mem[r1]"
which reads the memory value pointed to by r1 into the
register r2 (which always contains the value "0").
In a few sentences, sketch how a program loader could use the
ld instruction and binary rewriting techniques (similar
to those used in the Lucco et. al.'s software fault isolation paper)
to fix programs containing "mem_incr" instructions so
that they work with virtual memory. Why might you have to modify the
scheduler?
Part C (5 points). Rather than hack the Obsolete OS you decide to implement a virtual machine monitor underneath it that transparently manages virtual memory. Unfortunately, the Obsolete has three privilege levels, and code at any level can execute the instruction:
privlev rdst
which will load the value "2" into rdst if it is running
at user level, "1" if running at supervisor level, and "0" if running
at kernel level.
What problem does this instruction create? How could your binary rewriter solve this problem? (Point out any corner cases that could cause this technique to break.)
Assume you have a spiffy new solid-state device (SSD) that can hold 60 GB of memory, costs about as much as a normal disk, and can be accessed in the same amount of time as a RAM reference. You buy it of course and immediately start porting your traditional Unix file system to it (i.e., your file system has directories, inodes, indirect blocks, etc.). The new SSD device can only be written one byte at a time with a "store byte" instruction. On crash, the last byte is either written in its entirety, or not at all.
Explain, concretely, the steps you have to take to create a new file in a directory, being sure to handle the case where you crash while doing so and how you would recover afterwards. You should only use the metadata structures that already exist, with possibly (very) minor modifications—i.e., do not add a log.
Downloading code is fun, so you want to let applications add new code to your network controller.