Stanford CS Department 2010 OS Quals

This is the page describing the OS quals requirements for Spring 2010. It is the only page describing the OS quals for Spring 2010. More importantly, it describes the OS quals only for Spring 2010.

To take the 2010 OS quals, do all of the following:

1. Get an A- or higher in any 100-, 200-, or 300- level class while enrolled as a graduate student at Stanford.
2. Read the following paper (an electronic copy of which may be found here):
   Jochen Liedtke. Improving IPC by kernel design. In Proceedings of the 14th ACM Symposium on Operating Systems Principles, pages 175-88, Asheville, NC, USA, December 1993.
3. Build an OS or add a feature to any existing OS to support fast inter-process communication (IPC) between processes with different address spaces on a modern CPU. Write a simple benchmark that ping-pongs between user-level code in different address spaces. Carefully evaluate your feature using your benchmark on real hardware (not a virtual machine), paying particular attention to the minimum number of TLB misses you can achieve for an IPC.
4. Describe your IPC feature and evaluation in a write-up of not more than 3 pages, in a font size no smaller than 11 points. Email your write-up and source code with subject "2010 OS Qual entry" to David Mazières by May 17, 2010, and ask to schedule a one-hour oral examination for the week of May 24. I can't over-emphasize how important it is that the subject of your email contain the string "OS Qual".
5. Take the oral exam, in which you will be asked about the Liedtke paper and your own write-up. Be prepared to answer questions about your hardware (e.g., cache and TLB size and configuration, cost of TLB and cache misses, etc.) as well as your methodology for determining these things. You must bring both your marked-up copy of the Liedtke paper and a copy of your unofficial Stanford transcript (to get credit for your class).

Possible questions:

• How will the examination be graded?
  You will be assigned a score as follows: You get 15 points for having gotten an A- or higher in a 100-, 200- or 300-level class. You will get up to 15 points for getting good IPC performance compared to existing OSes and other people taking the exam. You will get up to 15 points for doing a thorough and convincing evaluation of your performance (which, in particular, requires you to quantify the effects of TLB misses). You will get up to 15 points for your performance on the oral examination. If your total points are 40 or higher, then you pass the exam. If your total points are 30-39, then you conditionally pass.
• What hardware and operating system should I use for this test?
  Whatever you want, so long as the OS has virtual memory and protection. Probably most people will want to use a PC. You are free to use an open-source commodity OS such as Linux or OpenBSD. You can also use an instructional OS (such as PintOS or xv6) or any research OS you feel like hacking on. On the x86, you can use long mode or not, whichever you feel is most interesting. Note that if you are modifying an existing OS and not writing your own, your performance evaluation should also include base-line numbers measured on the unmodified OS.
• Should I make use of hyper-threading or multiple cores?
  You are free to use these features to speed up your IPC time. However, it is also okay to use just a single core in a machine and to compete for the best single-core IPC number.
• Can I use superpages?
  You must not waste more than 2 Megabyte of physical memory per process to internal fragmentation, plus an extra 2 Megabytes of system-wide space used by the kernel for the IPC optimization. Under memory pressure, you must shatter superpages to make effective use of physical memory, and should not waste excessive amounts of time writing clean pages to disk. Subject to those constraints, feel free to use superpages if they can be helpful.
• Must my OS support paged virtual memory and memory-mapped files?
  If you are modifying an OS that has these features, you must preserve them. If you are building your own OS from scratch, you do not need to implement paging to disk, a file system, or any disk I/O. However, it should be the case that your IPC mechanism is not fundamentally incompatible with standard OS features and optimizations. You should be prepared to answer questions about how you would add such features during the oral exam.
• Can I use segmentation, sandboxing, or other tricks to avoid running in user mode or to avoid changing address spaces in hardware?
  The OS must not allow malicious benchmark code to crash or hang the machine. It is okay to modify the OS's default linker script or to change ld.so, but you cannot change the C compiler. Moreover, linker/ld.so changes must not break existing portable software, so, for example, you cannot severely reduce the virtual address space available to applications, nor assume a priori that a process's stack will remain small. (It is okay if you break programs that make non-portable assumptions about the underlying OS.) Your kernel may dynamically enable optimizations when it notices desirable properties in running programs (e.g., that a process is using only a small portion of its virtual address space, or that most of two processes' pages are identical). If the property for which you optimize is one that real programs might exhibit, then it's fine if your benchmark also happens to exhibit it.
• Can the processes engaged in IPC trust each other?
  You may assume at most uni-directional trust. For instance, a client that IPCs to a server may trust the server to use the IPC mechanism correctly. The server must distrust the client, however. In particular, the client must not be able to crash the server or violate the confidentiality or integrity of the server's data. (The server's code need not be kept secret, however.)
• I want to add special features to a CPU (e.g., the open-source Leon SPARC) to make context switching super fast. Can I do this exam using my own hardware?
  Absolutely! In this case, since your FPGA will obviously be a lot slower than commodity CPUs, your performance will be judged on a relative, not absolute basis. You should include some base-line numbers for what context switches cost without your new feature.
• Can I just use existing IPC functions in an existing kernel?
  You can. If your performance is not good, you will not get the 15 points for performance. However, if what you turn in is essentially a detailed evaluation of IPC performance and TLB behavior on an existing operating system, you can still pass the exam (as long as you do well on the oral exam and have satisfied the class requirement). If you compare multiple ways of doing IPC on multiple unmodified OSes and get good performance, then you can even potentially get some points for performance in addition to evaluation.
• What happens if I can't figure out how to email you my Qual entry?
  You fail the exam.
• Can I take the exam if I haven't taken any classes?
  Sure, but you will have to be nearly perfect on all other aspects of the exam to pass.
• Why are you making it so much harder to pass the Qual for people who have not taken classes?
  Stanford is a fantastic school with lots of amazing classes on offer. By not taking any graduate classes while you are here, you are shortchanging yourself. The increased difficulty of the OS Qual is just one more disadvantage of not taking classes, but not the principal disadvantage.
• What if I am taking my first class this Spring quarter?
  When you bring your transcript to the exam, show me that you are registered for credit and a letter grade. Then ask your instructor to email me on Tuesday, June 1, stating that your performance thus far in the class is on track for a final grade of A- or higher. If your instructor emails me that day, I will revise your score upwards by 10 points (effectively giving you 10 out of the 15 available class points).
• What happens if my instructor can't figure out how to email you?
  Then you can't get the extra 10 points. (However, you are free to email both of us so that the instructor can just "reply to all", which should work for all faculty members except Don Knuth.)
• Can I pass the exam if I run all my code in a virtual machine?
  No. Virtual machines (especially bochs and qemu) may be useful for debugging your code, but an important part of the exam is evaluating the performance of your solution, which can only be done on raw hardware.
• How do I flush the TLB on an x86 CPU?
  Really I should be asking you this kind of question during the oral exam. However, the answer is that you first have to clear the PGE bit in %cr4, then load %cr3, then set the PGE bit in %cr4. Yup, it's expensive. (You should understand how this works if you are using an x86 CPU for your exam.)