Computer Science 161
May 3, 2011 - May 4, 2011 5:00 PM
240 minutes/240 points
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:
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
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.
- 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 email@example.com.
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:
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:
- 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).
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:
- 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?)
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
- 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.
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.
Think about this problem and answer the following questions:
- There are 12 incoming lanes, each with a light.
- Each of the 12 incoming lanes feeds into one of the 6 outgoing lanes.
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 is this problem similar to scheduling on a multicore, multiprocessor system?
- How is this problem different?
- 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.
We talked about social ways to prevent something like Stuxnet from
happening, but in what follows, please focus only on technical
- 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.
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
- 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
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.data.
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:
Here is the suggestion for how we recommend you go about the analysis:
- 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.
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.
- 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
- 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.