Computer Science 161

Midterm Exam

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 lastname. (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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. A spinlock can be implemented with TAS or CAS, but not LL/SC. F, All are fine primitives from which to construct spin locks.
  8. 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).
  9. 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.
  10. 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.

  1. 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).
  2. 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.
  3. 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? Deadlock!
  4. 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.
  5. 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 unacceptably slow.
  6. Why on earth does the MIPS have a Random register? How would you use it? It is specifically designed for use during TLB replacement; it should not be used as a general source or randomness.
  7. 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:
  1. 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.
  2. 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).
  3. 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 fine here.
  4. 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.
  5. 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:

Unmapped address
pg # (3)
offset (4)
Mapped address
pg # (3)
offset (4)

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
  1. Based on what you see in the page table, what is the maximum size of physical memory this architecture supports? 12 bits => 4 KB
  2. What is the maximum size of a single virtual address space? 256 bytes
  3. How large is a page? 16 bytes
  4. In what range of virtual addresses would it be easiest to 0x80 - 0xFF implement the operating system?
  5. To what physical address would you map the virtual address 0x63? 0xDD3
  6. Would a NULL pointer generate a fault? No
  7. Are the addresses 0x3C and 0x40 contiguous in physical memory (they are contiguous in virtual memory)? No
  8. What range of physical addresses are always valid translations of virtual addresses? 0x000-0x07F