Page 1/18 University of California, Berkeley College of Engineering Computer Science Division ⎯ EECS Fall 2007 John KubiatowiczMidterm I October 10th, 2007 CS162: Operating Systems and Systems Programming Your Name: SID Number: Discussion Section: General Information: This is a closed book exam. You are allowed 1 page of hand-written notes (both sides). You have 3 hours to complete as much of the exam as possible. Make sure to read all of the questions first, as some of the questions are substantially more time consuming. Write all of your answers directly on this paper. Make your answers as concise as possible. On programming questions, we will be looking for performance as well as correctness, so think through your answers carefully. If there is something about the questions that you believe is open to interpretation, please ask us about it! Problem Possible Score 1 15 2 17 3 25 4 25 5 18 Total 100CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 2/18 [ This page left for π ] 3.141592653589793238462643383279502884197169399375105820974944CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 3/18Problem 1: Short Answer [15pts] Problem 1a[2pts]: Name two ways in which processes on the same processor can communicate with one another. If any of the techniques you name require hardware support, explain. Problem 1b[2pts]: What is an interrupt? What is the function of an interrupt controller? Problem 1c[3pts]: Suppose that we have a two-level page translation scheme with 4K-byte pages and 4-byte page table entries (includes a valid bit, a couple permission bits, and a pointer to another page/table entry). What is the format of a 32-bit virtual address? Sketch out the format of a complete page table.CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 4/18Problem 1d[2pts]: Which company was the first to develop a workstation with a mouse and overlapping windows? Problem 1e[2pt]: What is a thread-join operation? Problem 1f[2pts]: True or False: When designing a multithreaded application, you must use synchronization primitives to make sure that the threads do not overwrite each other’s registers. Explain. Problem 1g[2pts]: True or False: A system that provides segmentation without paging puts holes in the physical address space, forcing the operating system to waste physical memory. Explain.CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 5/18Problem 2: Multithreading [17 pts] Consider the following two threads, to be run concurrently in a shared memory (all variables are shared between the two threads): Thread A Thread B for (i=0; i<5; i++) { x = x + 1; } for (j=0; j<5; j++) { x = x + 2; } Assume a single-processor system, that load and store are atomic, that x is initialized to 0 before either thread starts, and that x must be loaded into a register before being incremented (and stored back to memory afterwards). The following questions consider the final value of x after both threads have completed. Problem 2a[2 pts]: Give a concise proof why x≤15 when both threads have completed. Problem 2b[4 pts]: Give a concise proof why x≠1 when both threads have completed. Problem 2c[3pts]: Suppose we replace ‘x = x+2’ in Thread B with an atomic double increment operation atomicIncr2(x) that cannot be preempted while being executed. What are all the possible final values of x? Explain.CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 6/18Problem 2d[3pts]: What needs to be saved and restored on a context switch between two threads in the same process? What if the two threads are in different processes? Be explicit. Problem 2e[2pts]: Under what circumstances can a multithreaded program complete more quickly than a non-multithreaded program? Keep in mind that multithreading has context-switch overhead associated with it. Problem 2f[3pts]: What is simultaneous multithreading (or “Hyperthreading”)? Name two ways in which this differs from the type of multithreading done by the operating system.CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 7/18Problem 3: Hoare Scheduling [25pts] Assume that you are programming a multiprocessor system using threads. In class, we talked about two different synchronization primitives: Semaphores and Monitors. In this problem, we are going to implement Monitors with Hoare scheduling by using Semaphores The interface for a Semaphore is as follows: public class Semaphore { public Semaphore(int initialValue) { /* Create and return a semaphore with initial value: initialValue */ … } public P() { /* Call P() on the semaphore */ … } public V() { /* Call V() on the semaphore */ } } As we mentioned in class, a Monitor consists of a Lock and one or more Condition Variables. The interfaces for these two types of objects are as follows: public class Lock { public class CondVar { public Lock() { public CondVar(Lock lock) { /* Create new Lock */ /* Creates a condition variable … associated with Lock lock. */ } … } public void Acquire() { public void Wait() { /* Acquire Lock */ /* Block on condition variable *’/ … … } } public void Release() { public void Signal() { /* Release Lock */ /* Wake one thread (if it exists) */ … … } } } } Problem 3a[3pts]: What is the difference between Mesa and Hoare scheduling for monitors? Focus your answer on what happens during the execution of Signal(). Hint: Mesa scheduling requires all conditional wait statements to be wrapped in “while” loops (see 3b).CS 162 Fall 2007 Midterm Exam I October 10, 2007 Page 8/18 Problem 3b[2pts]: When programming with a Mesa-scheduled monitor, the programmer must enclose all conditional wait operations with a while loop like this: while (condition unsatisfied) C.Wait(); What might happen if they did not do this? How might this happen? Problem 3c[2pts]: Explain why a Hoare-scheduled monitor allows the programmer to replace the “while” statement in (3b) with an “if”. Problem 3d[3pts]: Assume that we implement a Hoare-scheduled monitor with semaphores. Clearly, we will need one semaphore to implement mutual exclusion. Further, each condition variable will utilize a semaphore to hold its queue of
View Full Document
Unlocking...