Computer Science 161

Midterm Exam

March 12, 2013

82 minutes/82 points

Instructions

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 margo@eecs.harvard.edu. 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.
  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.
  3. Base and bounds addressing is able to reduce internal fragmentation relative to static relocation.
  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).
  5. A protection boundary crossing is always accompanied by a context switch.
  6. The operating system presents the abtraction of an MMU to processes.
  7. A spinlock can be implemented with TAS or CAS, but not LL/SC.
  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.
  9. In a microkernel architecture, critical pieces of the operating system, such as the file system, run in user-mode.
  10. The threading structure of the kernel dictates whether it is possible to implement user-level threads.

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.
  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.
  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?
  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.
  5. Why does modern virtual memory support require hardware support?
  6. Why on earth does the MIPS have a Random register? How would you use it?
  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?

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

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
1
pg # (3)
offset (4)
Mapped address
0
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?
  2. What is the maximum size of a single virtual address space?
  3. How large is a page?
  4. In what range of virtual addresses would it be easiest to implement the operating system?
  5. To what physical address would you map the virtual address 0x63?
  6. Would a NULL pointer generate a fault?
  7. Are the addresses 0x3C and 0x40 contiguous in physical memory (they are contiguous in virtual memory)?
  8. What range of physical addresses are always valid translations of virtual addresses?