CMSC330 Fall 2009 Practice Problems 7 1. Multithreading, Data Races, and Deadlock a. For the following program, give two schedules under which the final value of i differs in the two schedules. Give the schedule as a list of line numbers, and in each case, also give the final value of i. l = new ReentrantLock(); m = new ReentrantLock(); i = 0 Thread 1 1. l.lock(); 2. i = 3; 3. l.unlock(); Thread 2 4. m.lock(); 5. i = i + 1; 6. m.unlock(); b. For the following program, give one schedule under which there will be a deadlock, and give one schedule under which there will not be a deadlock. Give the schedule as a list of line numbers. l = new ReentrantLock(); m = new ReentrantLock(); n = new ReentrantLock(); Thread 1 1. l.lock(); 2. m.lock(); 3. m.unlock(); 4. l.unlock(); Thread 2 5. m.lock(); 6. n.lock(); 7. n.unlock(); 8. m.unlock(); Thread 3 9. n.lock(); 10. l.lock(); 11. l.unlock(); 12. n.unlock();c. Using language notation similar to above, write a program that has no data races, but nonetheless may produce different output under different schedules. d. List all possible outputs from the following program. Indicate next to each possible output whether all threads complete at the end, or, if they do not, which threads remain blocked. l = new ReentrantLock(); c = l.newCondition() Thread 1 l.lock(); System.out.print("a "); c.await(); System.out.print("b "); l.unlock(); Thread 2 l.lock(); System.out.print("c "); c.signalAll(); System.out.print("d "); l.unlock(); 2. Multithreading Code a. Using Java Conditions, you must implement a synchronization construct called MyBarrier. A MyBarrier object is created with a certain value n. When a thread calls the method enter( ), it enters the barrier and blocks until a total of n threads have entered the barrier. When the nth threads enters the barrier, all the threads waiting at the barrier wake up and unblock, and the nth thread continues without blocking. When a thread calls the method reset( ), the barrier is reset so that it starts fresh in counting up to n (i.e., n more threads must enter the MyBarrier). You may start by modifying the following code fragment: public class MyBarrier { public void MyBarrier (int n) { … } public enter( ) { … } public reset( ) { … } } b. Implement MyBarrier using Ruby monitors. c. Write a Ruby program that creates a barrier for 2 threads, then creates 2 threads that each print out “hello”, enters the barrier, then prints out “goodbye”.3. Garbage collection Consider the following Java code. Object a, b, c; public foo( ) { a = new Object( ); // object 1 b = new Object( ); // object 2 c = new Object( ); // object 3 a = b; b = c; c = a; } a. What object(s) are garbage when foo( ) returns? Explain why. b. Describe the difference between mark-and-sweep &
View Full Document