Computer Science 161

Instructions

Exam Policy Statement

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)

• Counting semaphore
• Binary semaphore
• Lock
• Lock and condition variable

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