Computer Science 161

Final Exam

May 3, 2011 - May 4, 2011 5:00 PM

240 minutes/240 points

Instructions

The points allocated to each problem correspond to how much time we think the problem should take. Although you have 24 hours in which to take the exam, we do not recommend that you pull an all-nighter and spend 24 hours completing the exam. Here is Margo's advice on how to complete this exam:

Download the exam and read through the entire exam.
Go to dinner and think about the exam.
Spend 3-4 hours Tuesday evening writing up answers the questions that you know.
Get a good night's sleep.
Spend another couple of hours on Wednesday working on the remaining problems.
Read over your answers.
Email them to me at margo@eecs.harvard.edu.

Please send your answers to me in a PLAIN TEXT file as an attachment with your graphs in a separate PDF document (in a perfect world, your text file would not have lines longer than 80 characters, but I'll reformat it if it does). Label the answers clearly so it is obvious what answers correspond to what questions. Please place your answers in order in the file. Send your completed exam to margo@eecs.harvard.edu. This exam is open text book, open source code, and open notes. You may not use computers (cell phones, PDAs, or any other device that can talk to a network) during the exam (other than to record your answers, to view OS/161 or System/161 code, or to examine your notes or the course web site). You must complete the exam on your own.

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."

1. Virtualization (20 points)

Abel and Cain are having an argument about virtualization. Abel says that if we all used fully virtualizable processors, such as the AbelR3000, then there would be no need for paravirtualization. Cain says that even if all processors were fully virtualizable, it would still be beneficial to have paravirtualized hypervisors.

As Abel and Cain's manager, please expand on each of their points of view discussing both the pros and cons of each viewpoint.

2. Managing Data State (30 points)

You've been hired by a NoSQL startup to be part of a team building a distributed key/value store (KVstore). The KVstore holds data items that are accessed via keys, which are uninterpreted byte strings. It supports the following operations:

Add this key/data pair to the database.
Get me the data item associated with this key.
Delete this key/data pair.
Iterate over the entire KVstore obtaining batches of 100 items at a time (iteration is not guaranteed to be in-order, it just guarantees that you iterate over one copy, either a client or a master, of each set of data).

Keys are unique. The system does not support transactional updates (if you don't know what transactional updates are, you needn't worry about them). You are being hired to design the caching system. The KV store runs on a collection of 10's to 100's of nodes. Each node stores a master copy of part of the database and a read-only replica of another part of the database that is mastered on a different node. Clients using the system are typically web applications, such as shopping carts, user account mangement data, etc. There is client API that takes care of directing all write requests to a master copy and read requests to the `best' replica (you need not worry about how we define best). Clearly, the system will deliver the best performance when the items requested are in memory, so your manager knows that they need a caching layer so that both masters and replicas can keep recently used data in memory. She is not sure what approach to take and the approach will have implications on other parts of the system. She has posed the following questions, and asked your advice:

Should we guarantee that read requests to a replica always see the same value of an item as requests to the master? (That is, will you provide perfect consistency?)
When we iterate over the entire KVstore, will we get a consistent snapshot? (That is, if I am iterating and you insert 3 items while I'm doing that, is it possible that I will see some of those items, but not all of them?)

Take a position on each of those questions and justify your position in one to two sentences. Now, taking the answers to the two prior questions into account, explain how your caching system will work, being sure to include:

A discussion of when new or modified items will be written to stable storage on the master.
A discussion of when new or modified items will be propagated to replicas.
A discussion of how read requests will be processed on replicas (we assume reads on the master are trivial).
A discussion of what happens on failure.
A discussion of what happens when a node comes back up after failure.

Finally, state the guarantees that your system makes with respect to whether or not updates can ever be lost, if they can be lost, under what conditions, and what you guarantee about your response to a read.

3. Synchronization (30)

You've been hired by the city of San Francisco to help out with their light metering on the Bay Bridge. Twelve lanes of traffic approach and go through toll booths and must then merge into six lanes. To make this efficient during commute hours, there are metering lights in each of the 12 lanes. The metering light alternates between red and green. Each light allows one car to pass through each time it turns green. In summary:

There are 12 incoming lanes, each with a light.
Each of the 12 incoming lanes feeds into one of the 6 outgoing lanes.

Think about this problem and answer the following questions:

How is this problem similar to scheduling on a multicore, multiprocessor system?
How is this problem different?

Now, design a synchronization mechanism to implement the metering light, thereby scheduling the 12-lane merge into 6 lanes. The external interface to your mechanism should have a single API: car_approaches (id, lane), where id identifies the car and lane indicates in which of the 12 incoming lanes the car arrives. You should assume that two cars cannot enter into the same outgoing lane at the same time and that cars in the incoming lane must be handled in-order. You may use semaphores, locks, and/or condition variables.

How many instances of your primitive will you need?
Show the data structure you will use to implement your primitive.
Show the code that you will us to implement your primitive. (You need not make it compile, but it must be readable. Comments encouraged.)

4. Security (30)

The Stuxnet attack took advantage of many security vulnerabilities. For the purposes of this question, we are interested only in the technical vulnerabilities. For each thing listed below that Stuxnet did, indicate if it was a failure of authentication, authorization, or access control. Explain your reasoning behind your choice.

The ability to launch an admin process from a process that did not have administrator rights.
The ability to propagate across a LAN through the MS10-061 Print driver.

We talked about social ways to prevent something like Stuxnet from happening, but in what follows, please focus only on technical solutions.

If you were designing the programming environment for the programmable logic controllers and the software that runs on them, what safeguards would you put in place to prevent attacks such as Stuxnet from happening? Your answer should be on the order of 2-4 paragraphs.

5. Singularity (50)

For this question, you will need to read the first seven pages of this paper on the Singularity operating system. (You are, of course, free to read the entire paper, but I wanted to keep the portion necessary for the exam within reason.) Please answer the following questions.

In Section 2.1, the authors discuss "creating an entire operating system using SIPs." Discuss in one to two paragraphs the difference between such a system and a conventional microkernel.
What components of a Singularity system should be considered part of the trusted computing base? Please explain your answer with a few sentences for each component.
What is the mapping between application threads and kernel threads?
How would you implement a synchronization primitive, such as a lock between two SIPs in Singularity?

6. Performance (80)

A. The Design Phase (30)

In assignment 4 we asked you to design ways to make SFS recoverable. For the most part, groups chose their approach based on what they thought was simplest to implement (a good choice). However, let's assume that you are the fsRus company and your future depends on producing the best performing file system on the market. Being a well-funded, venture-backed startup, you have the luxury of dispatching two teams to build realizations of both a soft-update based system and a journaling one. Design a performance evaluation plan that you would use to help you select which system you will use for your cash cow. Your plan should include a list of benchmarks you will run, the data you'll collect for those benchmarks, and how you'll use the results that you obtain.

B. The Instrumentation Phase (10)

Imagine that you actually had to implement and compare two different scheduling algorithms for Assignment 2. Please list the statistics you might have wanted to add to your system to help you evaluate the performance of different schedulers. Explain what each statistic will tell you and how you will use the various statistics.

C. The Analysis Phase (40)

You are working on a paper with several co-authors. Up until now your co-authors have been fantastic and have been busily running tests, but now they are deep in the throes of finishing up CS161 (the year is 2013). They've dumped all the following data on you and you now need to write up an evaluation of it. You've been examining file system performance (what a surprise!). You are comparing a log-structured file system to an FFS-based file system. Unfortunately, not only did your co-authors leave you with a pile of unanalyzed data, they labeled their data sets FS1 and FS2, so you can't even figure out which is which! Fortunately, you know what benchmark they were running. For a given file size, they would create either 32 MB worth of data or 10 files, whichever is larger (create performance). Then they would read each file (in the same order) (read performance). Then they would overwrite each file (in order) (write performance). Finally, they would delete all the files. For the create, read, and write tests, the results are measured in throughput (MB/sec) and for deletes, the data is expressed in terms of files-deleted per second. In order to test out-of-memory behavior, the file system cache was significantly smaller than 32 MB, but you don't know how much smaller. In this directory, you will find the original four raw data files: FS[12].data[12]. In this directory, you will find some cooked versions of those files that we thought might be easier for you to plot. Your job is to:

Determine which of FS1 and FS2 is the log-structured system and which is the FFS-based systems.
Provide a performance analysis of the results that you have, providing whatever graphics you believe will illustrate the points you wish to make in the analysis.

Here is the suggestion for how we recommend you go about the analysis:

Before examining the data files, write down what you expect to see for each file system for each test.
Now start plotting the data, playing with it until your graphical representation really tells you something about the data. After you have graphs you like, make sure to label the data, graphs and axes appropriately.
Now compare your original predictions to the graphs. Where they match, explain how the graphs support your expectations and WHY. Where they differ, explain WHY the actual results are different from your expectations.

Your evaluation will undoubtedly have an introductory section followed by a section for each of the benchmarks. You need not explain LFS and FFS (assume your reader has already read the beginning part of your paper), but draw on what you know about these file systems to explain the results.