Computer Science 161 (2015)

Instructions

All questions should be directed to me (Margo) via email. I will check mail periodically, but do not expect an instant response. I strongly encourage you to read through the exam and fire off any questions that immediately come to mind. I will check mail regularly, but will not be watching constantly. When in doubt, document assumptions.

Here is my advice on how to complete this exam:

• Read through the entire exam. Send me any questions.
• Go to lunch or dinner or take a walk and think about the exam.
• Spend a couple of hours on the first day/evening writing up answers to the questions that you know. Sketch our your thoughts about some of the longer design problems.
• Get a good night's sleep.
• Spend another couple of hours on day 2 working on the remaining problems and fleshing out the details of your designs.
• Read over your answers.
• Email them to me at margo@eecs.harvard.edu.
• On Wednesday, May 6, show up MD 119 at 7:00 PM to consume ice cream, pick up your T-shirt, and optionally iron on a team patch.

• in a PLAIN TEXT file, named LASTNAME.txt,
• in 80 character lines,
• with answers labelled clearly so it is obvious what answers correspond to what questions, and
• with space between each question.

Exam Policy Statement

At the end of your exam, please write the following statement and then place your name after it, asserting that you have followed the rules of the exam. "I have neither given nor received help on this exam and have followed the rules as stated." If this statement is absent, you will hear from me.

I. Multiple Choice (42 points)

Questions with one answer are worth 3 points; those with the potential for multiple answers are worth 5.

1. (Pick 1) Suppose we have a file system that has 10 direct block pointers and 5 indirect block pointers. Blocks are 8 KB and a block pointer is 4 bytes. Every file in the system uses the same block map structure, with unused pointers directed at null. Eliminating the indirect pointers while supporting the same maximum file size would be:
   1. Beneficial - The new block map will save significant space storing small files.
   2. Beneficial - The new block map will save significant space storing large files.
   3. Detrimental - The new block map will waste significant space storing small files.
   4. Detrimental - The new block map will waste significant space storing large files.
   5. I am not familiar with this terminology / I don't know.
2. (Pick as many as you like) On a MIPS or x86 processor, software running in supervisor mode:
   1. May be able to execute instructions that software running in user mode cannot.
   2. Runs faster
   3. Has exactly the same capabilities as software running in user mode.
   4. May obtain different behavior from instructions than software running in user mode does.
   5. Can turn off interrupts.
   6. Can directly modify registers running on other cores.
   7. Can change the value of all hardware registers.
3. (Pick 1)A Hypervisor is most like
   1. UNIX
   2. Linux
   3. CTSS
   4. VM/370
   5. MacOS
   6. Windows
4. (Pick as many as you like) The Operating System may schedule a new process whenever:
   1. A user program issues an illegal instruction
   2. An I/O operation completes
   3. A user program makes a system call
   4. A timer interrupt occurs
5. (Pick as many as you like) Which of the following parts of an operating system must run in supervisor mode?
   1. The scheduler
   2. The virtual memory system
   3. Process management
   4. The file system
6. (Pick 1) The fundamental difference between a semaphore and a lock is:
   1. A lock can only be unlocked by the thread that locked it.
   2. A semaphore can only be V'd by the thread that P'd it.
   3. A lock provides mutual exclusion.
   4. A semaphore would not work in conjunction with a condition variable.
7. (Pick as many as you like) A system call invocation in OS161 entails:
   1. A domain crossing
   2. A process switch
   3. A thread switch
   4. A stack switch
   5. A trap
   6. An interrupt
8. (Pick as many as you like) Which of the following are metrics for which you might want a process scheduler to optimize?
   1. Throughput
   2. Latency
   3. Fairness
   4. Synchronization
   5. Taste
9. (Pick 1) Round Robin is (blank1) but has poor (blank2).
   1. Unfair, latency
   2. Unfair, throughput
   3. Fair, latency
   4. Fair, throughput
10. (Pick as many as you like) Virtual memory
    1. Makes your system run faster
    2. Lets you run processes that exceed the size of memory.
    3. Uses your I/O system more efficiently than systems without VM.
    4. Lets you run more processes than can actually fit in memory.
    5. Makes your system more predictable.

II. Short Answer (30 points)

Answer each of the following in a sentence or two.

1. What is the difference between a wait channel and a condition variable in OS161?
2. Give an example of how file system implementation details can affect security.
3. Give an example of how virtual machine implementation details can affect security.
4. Why is trap.c in the architecture dependent directory?
5. Give one argument in support of hardware managed page tables and one argument in support of software managed page tables.
6. Imagine that you have a direct mapped TLB, suggest some things that could be done to avoid thrashing the TLB. (You cannot change the hardware -- you must suggest things you can do in software.)

III. Stupid or Clever (50 points)

Each of the following is an example of a design decision made in a real system. For each one, decide if it's stupid or clever and provide a one or two sentence explanation to justify your opinion.

1. Early versions of Linux ran only on uniprocessors and therefore turned interrupts off to protect critical sections. Initial work at making Linux multiprocessor capable did so by introducing a mechanism to turn interrupts off on all processors.
2. The Mach virtual memory system, developed in the 80's, was divided into a machine dependent (pmap) layer and a machine independent layer. The machine independent layer implements a logical virtual memory system with a logical page size (that must be a multiple of the physical page size) and the machine dependent layer translates the logical structure into the physical structures of a particular machine, updating hardware mappings.
3. Barrelfish is a new operating system designed for multiprocessors that treats a multiprocessor like a distributed system, essentially running a small operating system on each processor.
4. A researcher was building a prototype transaction system and decided to create a separate log for each different type of data element that needed to be stored in the log.
5. ZFS is a tree-based, no-overwrite storage system such that when you modify a block in a file, you write a new copy of the block, which requires a new copy of the file meta-data, which requires writing a new copy of the dataset to which that object belongs, which requires rewriting all data structures up to the root of the tree (superblock).

IV. File system design for new hardware (38 points)

• Reads are infinitely fast, but destructive, which means that when you read the data, it disappears from the drive.
• The minimum unit you can read/write is 1 MB.
• Due to parallelism in the device, write bandwidth is terrific: 1 TB/second, but the latency for any individual request is not so great: a 1 MB write takes 100 microseconds.
• The drives have amazing capacity -- a single drive can hold an exabyte (2^60).

In this question, you will be designing a file system for the drive. The file system should support the workload imposed on a data center machine that has multiple terabytes of memory and many processors and supports tens of virtual machines simultaneously (you might have many more VMs than that, but only tens of them will be running simultaneously). The VMs are running today's operating systems with today's file systems, and workloads typical of today's workloads. Your job will be to design a file system for the hypervisor. The hypervisor gives each machine its own virtual disk, which will map to a file on the quantum drive.

1. How much parallelism is there in the drive?
2. As you begin to think about building a file system for this device, what are three challenges you will need to address?
3. Design a data structure to represent files in your file system (i.e., your inode structure). Give a brief justification for the structure you selected.
4. Describe your allocation policy (not the mechanisms, e.g., bitmaps, but the approach you will take towards placing data on the drive). Again, give a brief justification for it.
5. What will your robustness and recovery strategy be for the file system?

V. Elastic Operating Systems (80 points)