Computer Science 161
March 12, 2013
82 minutes/82 points
The points allocated to each problem correspond to how much time
we think the problem should take.
Please send your answers to me in a PLAIN TEXT file named your-lastname.txt
as an attachment - with the string "your-lastname" replaced with your
(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, open notes, and open
course web site. 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 documentation, or to examine your notes or the
course web site).
You must complete the exam on your own, without assistance.
Exam Policy Statement
At the end of your exam, assuming you have followed the rules of the 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 I have not used any disallowed materials in the completion of this exam."
1. True False (20 points)
Answer true if the statement is always true; otherwise answer false.
- The realization that human time is valuable was a significant
motivation for timesharing.
T: The motivation was that they wanted to use
people's time more efficiently.
- On the MIPS processor, virtual addresses that begin with the bits 100
map to exactly the same range of physical addresses as those that begin
with the bits 101.T, see vm-mips.pdf notes, slide 8
(2/28) -- one of those
regions run uncached for device memory and such; the other runs cached.
- Base and bounds addressing is able to reduce internal fragmentation
relative to static relocation.
T, you get to "bound" the size of the segment,
which we didn't have a way to do with the static version we discussed.
- If you do not have interrupts, then the only option you have
for scheduling is to run each process to completion (or until the
process blocks for I/O).
F, you can reschedule processes on system calls.
- A protection boundary crossing is always accompanied by a context switch.
F, It turns out that the staff was using the
term context switch to mean something very precise, and the book
uses the term to mean something much more general. The book uses
the term context broadly -- including procedures, threads, user
space, etc. With that definition, this statement becomes true.
So, we are giving credit for all answers. The idea that we were
trying to convey is that you can change protection domains, but
still be executing the same thread. That is, when you make a system
call, you switch into kernel mode, you switch onto the kernel stack,
but you are still executing in the same thread of control.
- The operating system presents the abtraction of an MMU to processes.
F, The MMU isn't an abstraction; the abstraction is
that of virtual addresses.
- A spinlock can be implemented with TAS or CAS, but not LL/SC.
F, All are fine primitives from which to construct
- Kimi the cat is rolling around with her catnip stuffed mouse; Fuzzer
the bully comes over and takes the mouse away and begins to play with it.
The mouse is a preemptible resource.
T, even if Kimi can't take it away from Fuzzer, he
has demonstrated that it is possible to take it away from a processor (cat).
- In a microkernel architecture, critical pieces of the operating
system, such as the file system, run in user-mode.
T, That is one of the key ideas behind microkernels.
- The threading structure of the kernel dictates whether it is
possible to implement user-level threads.
F, you can implement user level threads (or not)
regardless of what the OS is doing.
2. Short Answer (26 points)
Answer the following questions in a few sentences as necessary.
- Typically a system call returns exactly once from an invocation.
Name two os/161 system calls that violate this behavior, and
explain briefly how they violate the behavior.
The most common examples are fork (returns twice),
exec (doesn't return at all), and exit (doesn't return at all).
- Let's assume you have exactly three page frames and they contain the
pages A, B, and C. Construct a page reference sequence of 10 page
accesses, including A, B, C and any other pages you want demonstrating
that MIN produces a better hit rate than does LRU. Include the hit rates
for each algorithm.
The easiest pattern is: (A B C given), then D A B C D A B C D A, which is pessimal for LRU (and, in fact, MRU works particularly well),
producing 0% hit rate, while MIN produces a 60% hit rate.
- A system is designed with the condition that
no thread holding lock A can acquire lock B. What
problem is this system designed to prevent?
- A MIPS instruction stores a value from a general purpose register
into memory. List as many different ways as possible that this instruction
could cause an exception.
This one tripped a lot of people up. First, you have
to realize that reading the instruction itself is a memory read, so you
could get TLB, page, or permission faults while accessing the instruction.
Then, you could get TLB, page, or permission faults while accessing the
data. In the case of the instruction, you would need read/execute
permission; for the data write permission.
And of course, either the instruction of the address might be completely
invalid addresses, which would result in faults as well.
- Why does modern virtual memory support require hardware support?
Without hardware, you'd be forced to do the
translation in software and that would require multiple instructions
to be executed per instruction in the program and that would be
- Why on earth does the MIPS have a Random register? How would you
It is specifically designed for use during TLB
replacement; it should not be used as a general source or randomness.
- We often evaluate schedulers in terms of their efficiency and
fairness. How might we quantify each of these? Which of the schedulers
that we studied perform especially well at each of these metrics?
Efficiency could mean 1) allocate as much time as possible running processes
instead of switching among them -- FIFO, where we let jobs run to completion,
would be most efficient in this sense. 2) getting the best response time,
in which case STCF would just great, because it produces the minimum average
response time. 3) Responsiveness could be another way to measure efficiency.
In that case, we might be thinking of interactive response time, which
would favor things like MLFQ or fairshare (not necessarily STCF, because
if you type a character, but the response requires both echoing it back
and then computing, I don't think you will necessarily get what you want
with STCF although that's debatable).
Fairness could mean 1) Each process gets the same amount of time in which
case Round Robin might be just fine, 2) to each according to its needs;
from each according to its ability, in which case CFS, FairShare or MLFQ
could be considered fair.
3. Synchronization (20 points)
For each synchronization problem described below, select the best
synchronization primitives to solve the problem. Select the synchronization
primitive from the following list:
- Counting semaphore
- Binary semaphore
- Lock and condition variable
- All CS161 students want to sit at the middle table in the front of
the room, but Mean Old Professor Seltzer (MOPS for short) says that only
four people can sit at any table. It is important that a student who
is not allowed to sit at the desired table be able to sit at some
other table during class.
Lock -- you can't use a counting semaphore here, because if you
did, the 5th student would block and end up standing the entire class
waiting for someone to leave, and that was explicitly not allowed.
- The Town of Lincoln, MA frequently has a coyote problem, but it turns
out that coyote and deer populations are cyclic, and coyotes are masters of
synchronization. The coyotes cannot move into town until the deer population
is sufficiently high to support the coyote population. What synchronization
primitive should our wily coyotes use to prevent them from moving into town
before the deer population is sufficiently large to support them?
Lock+CV -- the coyotes would wait until the deer population reaches an
appropriate level, at which point a broadcast would let all the coyotes
move in (however, as someone points out, no right thinking deer would
ever broadcast on that CV).
- Imagine that you are building a virtual memory system for a
multiprocessor. You could have two user-level threads in the same
address space running on different processors. When you handle a page
fault, how will you synchronize access to your page table?
Either a lock or binary semaphore (used for exclusive access) would be
- You've been hired by Bouncy Houses R Us for the summer.
It turns out that the key part of your job will be to make sure
that you never allow more than twelve children into a bouncy house
at once. This sounds like a classic synchronization problem to you,
so you need to select the appropriate mechanism to use to manage
a single house full of bouncy children.
This is a classic use of a counting semaphore.
- You need to synchronize two kernel threads.
They must never run at the same time.
One is responsible for writing dirty memory pages
to disk and the other can begin running when there are no dirty
memory pages and runs until it notices a dirty page.
How would you synchronize them?
Although I gave credit for lock and CV, I was trying to construct a case of
using a binary semaphore for scheduling (where the threads would ping pong
back and forth on the semaphore).
4. Virtual Memory (16 points)
The Simple architecture has an 8-bit virtual address space.
If the high order bit is 0, then the address is mapped through the MMU,
but if it is 1, then it is not mapped - instead the corresponding physical
address consists of the low 7 bits of the virtual address.
Of the remaining 7 bits, the next 3 bits of the VA represent a page
number and the bottom four bits are the offset as shown:
The hardware also supports a page table and its contents are shown below.
Each PTE entry has 9 bits, a valid bit followed
by an 8-bit physical page number.
| 1 || 0xFF |
| 0 || 0x00 |
| 0 || 0xA0 |
| 1 || 0x08 |
| 1 || 0xB0 |
| 1 || 0xEE |
| 1 || 0xDD |
| 0 || 0xFF |
- Based on what you see in the page table, what is the maximum size
of physical memory this architecture supports?
12 bits => 4 KB
- What is the maximum size of a single virtual address space?
- How large is a page?
- In what range of virtual addresses would it be easiest to
0x80 - 0xFF
implement the operating system?
- To what physical address would you map the virtual address 0x63?
- Would a NULL pointer generate a fault?
- Are the addresses 0x3C and 0x40 contiguous in physical memory
(they are contiguous in virtual memory)?
- What range of physical addresses are always valid translations
of virtual addresses?