Stanford Operating Systems Quals

2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

2002 Problem Set

Dawson Engler

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. Problem 1 — Code is Data (25 Points) 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.)


Problem 2 — Yes, We Have No Chaos (20 points) 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.


Problem 3 — Would you like to Crash my Computer? (10 points) Downloading code is fun, so you want to let applications add new code to your network controller.
  1. (3 points) Give a two (potentially) compelling uses of such handlers.
  2. (7 points) How could you safely run untrusted code in an interrupt handler? As part of your answer list some of the most important abilities that these message handlers would probably need and how you can provide it.

Maintained by Gurmeet Singh Manku