October 9, 1997
There are five questions equally weighted at 20 points each, for a total of 100 points. Allocate your time carefully. Your answers will be graded on content, not style. For code answers, any kind of pseudocode is fine as long as its meaning is clear. For written answers to "essay" questions, please do not waste any words. You have 75 minutes.
-
Highway 110 is a two-lane north-south road that passes through a one-lane tunnel. A car can safely enter the tunnel if and only if there are no oncoming cars in the tunnel. To prevent accidents, sensors installed at each end of the tunnel notify a controller computer when cars arrive or depart the tunnel in either direction The controller uses the sensor input to control signal lights at either end of the tunnel.
Show how to implement the controller program correctly using mutexes and condition variables. You may assume that each car is represented by a thread that calls your Arrive() and Depart() functions, passing an argument indicating the direction of travel. You may also assume that Arrive() can safely stop the arriving car by changing the correct signal light to red and blocking the calling thread. Your solution should correctly handle rush hour, during which most cars approach the tunnel from the same direction. (Translation: your solution should be free from starvation.)
-
Tweedledum and Tweedledee are separate threads executing their respective procedures. The code below is intended to cause them to forever take turns exchanging insults through the shared variable X. The Sleep() and Wakeup() routines operate as discussed in class: Sleep blocks the calling thread, and Wakeup unblocks a specific thread if that thread is blocked, otherwise its behavior is unpredictable (like Nachos Scheduler::ReadyToRun).
a) The code shown above exhibits a well-known synchronization flaw. Briefly outline a scenario in which this code would fail, and the outcome of that scenario.
b) Show how to fix the problem by replacing the Sleep and Wakeup calls with semaphore P (down) and V (up) operations. No, you may not disable interrupts.
c) Implement Tweedledum and Tweedledee using a mutex and condition variable.
-
The kernel memory protection boundary prevents dangerous access to kernel data by user-mode threads. Similarly, mutexes prevent dangerous accesses to shared data by concurrent threads. However, kernel memory protection is mandatory, whereas the protection afforded by mutexes is voluntary. Explain this statement.
-
Round-robin schedulers (e.g., the Nachos scheduler) maintain a ready list or run queue of all runnable threads (or processes), with each thread listed at most once in the list. What can happen if a thread is listed twice in the list (e.g., by calling Wakeup() on a thread that is not asleep)? Explain how this could cause programs to break.
-
Birrell's paper describes a thread system (Taos/Topaz) that differs from Nachos threads in a fundamental way: threads are implemented in the kernel using new system calls for threads, rather than in a user-level library.
a) A multithreaded user program cannot disable interrupts in Taos/Topaz. What could go wrong if user programs were permitted to disable interrupts? How are user programs prevented from disabling interrupts? Why is it unnecessary for user programs to disable interrupts?
b) Briefly discuss the pros and cons of a kernel-based thread implementation, relative to a user-level library implementation like Nachos.
Thank you, have a safe and enjoyable Fall Break.