University of California Berkeley College of Engineering Computer Science Division EECS Fall 2007 John Kubiatowicz Midterm 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 1 15 2 17 3 25 4 25 5 18 Total 100 Page 1 18 Score CS 162 Fall 2007 Midterm Exam I October 10 2007 This page left for 3 141592653589793238462643383279502884197169399375105820974944 Page 2 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 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 Page 3 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 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 Page 4 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 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 for i 0 i 5 i x x 1 Thread B 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 Page 5 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 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 Page 6 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 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 Lock Create new Lock public void Acquire Acquire Lock public void Release Release Lock public class CondVar public CondVar Lock lock Creates a condition variable associated with Lock lock public void Wait Block on condition variable public void Signal 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 Page 7 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 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 sleeping threads Give at least 3 reasons why the following implementation of wait and signal is incorrect wait CVSemi p signal CVSemi v Page 8 18 CS 162 Fall 2007 Midterm Exam I October 10 2007 Problem 3e 3pts Explain why we need an additional semaphore to implement signal under Hoare scheduling as you describe in problem 3a Hint when a waiting thread T1 is signaled by another thread T2 something special must happen immediately and something else must happen when this signaled thread either releases the monitor lock or executes wait Problem 3f 6pts Given your answer to 3e show how to implement the Lock class for a Hoarescheduled monitor using Semaphores Let us call the additional semaphore from 3e the SDefer semaphore If if helps you think
View Full Document
Unlocking...