Computer Science 161
March 10, 2015
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 (email@example.com)
in a PLAIN TEXT file named your-lastname.txt
as an attachment - with the string "your-lastname" replaced with your
Please do not put your name at the top of your exam (as you'll
see below I would like your name at the bottom).
In a perfect world, your text file will not have lines longer than 80
characters, but I'll reformat it if it does, albeit sadly.
Label the answers clearly so it is
obvious what answers correspond to what questions. Please place
your answers in order in the file. When you have completed the
exam, please email it 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.
If you feel that there is ambiguity and that affects your answer, feel
free to explain your logic.
- A uniprocessor with only single-threaded processes does not need
- Threads waiting on a CV will be granted the CV lock on a FIFO basis.
- If a processor supports virtual memory, then it must have a TLB.
- A drum served the same purpose as modern day harddrives.
- The job of the operating system has always been to allow the
hardware to be used as efficiently as possible.
- Operating systems as an area of intellectual investigation arose in
the 60's when it was an open question whether one could construct a layer
of software that allowed hardware to be used efficiently.
- Most of the types of problems identified in early operating systems
have been solved today.
- Loadable kernel modules are the modern-day solution to extensible
operating systems, providing all the features that were desired by
the extensible OS community.
- The transition from user mode to supervisor mode requires hardware support.
- It is possible to handle page faults without hardware support.
2. Short Answer & Multiple Choice (24 points)
Answer the following questions in as few sentences as necessary.
- (5 points) On a trap, what information must the kernel save or figure out.
- (5 points) You have been asked to design a TLB for a new processor. Your
like to understand the tradeoffs involved in deciding whether to implement
a 2-way set associative TLB or a 16-way set associative TLB. What do you tell
him/her? Which would you advise selecting for the design. (Assume that both
TLBs will hold exactly the same number of mappings.)
- (5 points) Jack and Jill are arguing about page replacement schemes.
One of them
claims that MRU -- replacing the most recently used page would be a
monumentally stupid replacement policy. The other argues that if you
focus only on data pages, then there are
workloads for which it would be optimal. What do you think?
- (5 points) You are writing a C program and you've created a nice
clean design with a reasonably short main program and a small library
implemented in a separate file.
You want functions in both files to share a common, global debug
parameter, so you put:
extern int debug;
in both files. Each file compiles cleanly by itself, but when you go to
build your program, you get the error:
Undefined symbols for architecture x86_64:
"_debug", referenced from:
_main in foo.o
Why are you getting this error? Explain this first in high level terms
and then in lower level detail referring to the various segments in
which the debug variable is/is not defined.
- (2 points) Which is true of a modern operating system kernel
(select only one):
- The kernel code is always executing.
- The kernel only stores resource state, it does not execute code.
- The kernel code executes when the kernel process is scheduled.
- The kernel code executes in response to hardware interrupts and system calls.
- None of the above
- (2 points) You have a bunch of CS161 students who are frantically
writing code and periodically compiling it while the CS205 students
are running a bunch of long simulations.
Which scheduling algorithm would be best for the workload described?
(select only one):
- Lottery Scheduling
- Round Robin
3. Synchronization (20 points)
For each synchronization problem described below, select the best
synchronization primitives to solve the problem. You may use each
primitive as many times as you need to. Briefly (1-2 sentences),
explain why you chose the primitive you did. Select the synchronization
primitive from the following list:
- Counting semaphore
- Binary semaphore
- Lock (w/out a CV)
- Lock and condition variable
- A common problem in soccer collisions between players jumping for
headers (this often leads to concussions). They've decided that clever
CS161 students could easily solve this problem with a synchronization
primitive that would arbitrate which player got to jump up for the header
(such primitives would have to be very high performance). Which primitive
would you suggest?
- Professor Seltzer was making pancakes for hungry teenagers. The pancakes
come out in batches of three. She'd like a synchronization primitive that
would allocate pancakes to teenagers without fighting. (There is no need
to worry about leftovers between batches -- all pancakes are consumed
pretty much instantly.) Suggestions?
- You are competing in a new Olympic event called a distributed relay.
One team member has to run one lap at the Harvard track. The next team
member must run a lap at the Yale track. The third team member runs a lap
at Brown track and the last team member runs a lap at the Columbia track.
Each runner must not start until the previous runner has completed
his/her lap. Natually, the traditional passing of the baton or slapping of
the hands won't work, so they've turned to you, as a savvy CS161 student, to
provide the proper synchronization. What mechanism do you use?
- Competition for parking in Cambridge has become brutal due to the
massive quantities of snow accumulating on our streets. The traditional
use of space-savers (things like cones or lawn chairs that mark a spot
as being "owned" because someone invested the physical labor in shoveling
it out) has become too contentious and the Cambridge Department of Public
Works is looking for a better solution. They've decided to have neighborhoods
hand out parking tokens and any car without a visible token will be towed
to the far reaches of the universe. Each neighborhood has a token checkin
point and cars must drive to the checkin point to obtain a token for a
specific spot and return a token when they leave a spot (cars that do
not return tokens within seven minutes of leaving a spot are subject
to enormous fines). They would like the checkin points to operate as
efficiently as possible, allocating and deallocating spots in parallel
as much as possible. What synchronization primitive(s) should they use?
- It is well known that graduate students (as well as many others) are
motivated by free food. After the first couple of years (once classes
are complete), a graduate student's day consists mostly of doing research
and periodically checking email to determine if anyone has announced any
free food lately.
Unfortunately, the better research is going, the less likely students
are to check email, and by the time they get to the location of the free
food, it's often gone. (While they could configure their mail to alert
them every time a new message comes in, most messages do not concern free
food, so this would be quite distracting.)
There must be a better way -- can you propose use of a synchronization
primitive that would let them receive/see messages only when they
concerned free food?
4. Virtual Memory (18 points)
Open RISC is a specification for a family of open-source, synthesizable RISC
microprocessor cores. The OpenRISC 1000 MMU supports:
32-bit address translation takes place as follows (depicted below):
- Both 32-bit and 64-bit address spaces.
- Multiple page sizes.
- Hardware support for page tables.
- Context IDs (CID) that allow multiple processes to be translated by the
hardware without changing hardware registers.
- We form a 36-bit address by prepending the process's address with
a four bit context ID.
- The top 23 bits of the 36-bit address form the virtual page number.
- The low 13 bits are the page offset.
- The CID and level 1 page index are used to index into an L1
- The physical page number from the L1 Page Directory is added to the
level 2 page index to form an index into the L2 Page Table.
- The physical page number from the L2 PTE is concatenated with the page
offset to form a phyiscal address
A page table entry is as shown:
- Bits 0-3 indicate cache behavior (you can ignore them)
- Bit 4 is an accessed (use) bit.
- Bit 5 is a dirty bit.
- Bits 6-8 indicate the page protection.
- Bit 9 is a link bit and can be ignored for now.
- Bits 10-31 are the physical page number.
- (2 points) What is the smallest page this architecture supports?
- (2 points) The hardware allows for treating this as a segmented
architecture by ignoring the L2 page tables. In such a configuration,
how large are segments?
- (2 points) What is the largest physical address you can construct
- (4 points) There are only 4 bits of Context ID -- is it possible to run
more than 16 processes on this architecture? If so, how?
- (4 points) Although OpenRISC provides hardware support for page
tables, it also allows software management. Name one thing that you
could do using software management that you cannot do in the hardware.
- (4 points) Knowing only what you know about this architecture, how
would you propose dealing with the operating system's memory management?
Would you run it mapped? Unmapped? Why?