Computer Science 161

Midterm Exam

March 11, 2014

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. A trap causes a mode change from user mode to kernel node.
  2. Locks and binary semaphores provide identical functionality.
  3. Most operating systems use Shortest Time to Completion First (STCF) scheduling algorithms since STCF is the optimal scheduling algorithm.
  4. The operating system frequently insulates application programmers from changes in hardware.
  5. Trap handlers execute in supervisor mode.
  6. Thread (or threads) plus address space = process.
  7. (Students) Working on problem sets is a preemptible activity.
  8. Skydiving (once you've left the plane) is a preemptible activity.
  9. It is possible to switch threads at either user level or kernel level.
  10. Virtual memory allows processes larger than main memory to run.

2. Short Answer (24 points)

Answer the following questions in as few sentences as necessary.

  1. (5 points) What is the difference between a program (an executable file) and a process and how is a program transformed into a process?
  2. (3 points) Professor Seltzer is playing with kittens. She throws out a yarn ball and the kittens all race to fetch it, but only one succeeds. There are 12 kittens. After playing with the ball for a moment, the kitten brings the yarn ball back, returns it to Professor Seltzer and gets a treat. Which of deadlock, race condition, or starvation can occur? Please explain.
  3. (4 points) Explain, in terms of thread switches and domain crossings, what a process switch entails.
  4. (4 points) Explain how a scheduling algorithm could produce good throughput, but poor response time. Then explain how a scheduling algorithm could produce good response time, but poor throughput.
  5. (3 points) Why don't we typically allow user level processes to disable interrupts?
  6. (5 points) Explain how you would enhance a multi-level feedback queue scheduler to support user-specified process priorities. That is, a user has a way to indicate that some processes are more important than other processes.

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, explain why you chose the primitive you did. Select the synchronization primitive from the following list:
  1. Your dorm has 6 washing machines and you need to make sure there are no more users of the machines than there are machines.
  2. The dryers in your dorm operate for only ten minutes at a time. Everyone agrees that only one person's clothing should be in the dryer at any time and that you can only take someone's clothes out of a dryer if they are completely dry.
  3. Margo's cats like to sleep on her hip, but only one cat can do that at any one time. If too many cats are trying to sleep on her hip, then a cat fight ensues. How should the cats synchronize access to their favorite sleeping spot?
  4. A server process needs to block when there is no work to be done and run when there is work to be done.
  5. You are implementing a synchronization manager for a database. A process cannot access a record while another process is accessing it. When a process completes its work with a record, if there are multiple processes that next wish to access the record, the process relinquishing access may want to select a particular process to run next.

4. Virtual Memory (18 points)

The Stoopid architecture has a 12-bit, segmented, virtual address space. The top three bits of an address identify a segment. The next four identify a page number and the last five are offsets.

seg#(3)
pg # (4)
offset (5)

  1. (2 points) How large (in bytes) are pages in this architecture?
  2. (8 points) You are told that the architecture has a TLB, but that they haven't quite worked out the details of a) what each TLB entry looks like, and b) how many TLB entries they should include. Propose a TLB entry design; then make (and justify) a suggestion for how many TLB entries they should have (there is no a priori right answer for this second question -- we're looking for the thought process behind picking a number).
  3. (2 points) Assume that the architecture supports paging. How many entries would you expect to find in a page table?
  4. (6 points) Stoopid Inc. has asked you to come in and consult for them. They know that NULL pointers are an endless source of bugs. They are trying to decide whether they can/should make the hardware guarantee that NULL pointers always cause faults or leave it to the operating system to enforce that.
    1. Would it be possible for the hardware to guarantee that an access to the memory location referenced by a pointer whose value is NULL always generates faults? (How?)
    2. If the hardware designers either can't or don't provide that support, how would you design your operating system to make sure that accesses to the location referenced by a NULL pointer always generates a fault?