These are some sample problems to help you prepare for the exam. They are not meant to be comprehensive. Many problems on the exam will have the same flavor as these. Some of these problems are deliberately harder than those that will appear on the exam, but they should be useful study material. This practice is not meant to be comprehensive! You are responsible for all material in JCIP, chapters 1-8, with an emphasis on material we covered in class. I will also expect you to be familiar with the project descriptions and implementations (projects 1 and 2), and may ask questions about these. If there's some part of the project you didn't get working or your partner did and you don't understand, make sure you remedy your understanding by test time. ---------------------------------------------------------------------- - Definitions/Short answer Define the following: Thread-safe class Check-then-act data race Read-modify-write data race Guarded By (as in "Field f is guarded by lock L") Immutable class Effectively immutable class Thread confinement Atomicity Intrinsic lock Reentrant lock Mutual exclusion Deadlock Visibility Safety vs. liveness Happens-before relation Client-side locking (definition, and purpose) Short answer: - What are the two problems that synchronization helps to solve? Answer: atomicity (or mutual exclusion) and visibility - What is the role of "volatile?" What problem does it solve? Answer: it solves the visibility problem my ensuring that all reads/writes to the variable will be ordered between threads. - What is the difference between a concurrent data structure, like ConcurrentHashMap, and a synchronized one, like that created by Collections.synchronizedMap()? Answer: both kinds of datastructures are thread-safe, but only the first permits truly parallel operations (such that more than one thread may be operating on a the same datastructure at the same point in time). - Why doesn't client-side locking work with ConcurrentHashMap? Answer: Client-side locking only works for synchronized data structures such that all operations that access the datastructure first acquire the structure's intrinsic lock. ConcurrentHashMap is not synchronized in this way (it doesn't use locks) so client-side locking is inappropriate. - Assuming a you want your CPUs to be fully utilized, you have 8 cores, and your tasks have a ratio of 4 units of waiting time to every unit of compute time, how many threads should you allocate to execute the tasks? Answer: Nthreads = Ncpu * Ucpu * (1 + W/C) = 8 * 1 * (1 + 4) = 40 (equation on p. 171 in the text) Long answer: - Draw a happens-before graph of the following thread execution. In particular, each node of the graph will be an operation (read, write, lock, unlock, etc.) in the execution, and there is an edge between each node such that the source "happens before" the target. Transitivity corresponds to reachability in the graph, so you do not need to draw transitive edges. write(T1,x,1); read(T2,x,0); write(T2,y,0); write(T1,y,2) Answer: +----------+ +----------+ | T1:x = 1 +--->| T1:y = 2 | +----------+ +----------+ +-----------+ +----------+ | T2:x == 1 +--->| T2:y = 0 | +-----------+ +----------+ write(T1,z,0); lock(T1,y); write(T1,x,1); unlock(T1,y); write(T1,z,1); lock(T2,y); read(T2,x,1); unlock(T2,y) Answer: T1:z = 0 | v T1:lock(y) ---> T1:x = 1 ---> T1:unlock(y) ---> T1:z = 1 | +--------------------------------+ | v T2:lock(y) ---> T2:x == 1 ---> T2:unlock(y) - Suppose we extend the second execution trace above with a read-event on variable z by thread T2, i.e., having the form read(T2,z,_) where the _ is the value actually read. According to the interpretation of visibility under the happens-before relation, what value, or values, will z take on? Answer: Both read(T2,z,0) and read(T2,z,1) would be legal, since both writes to z precede the read in the trace, where z=0 is the most recent that happens-before the read, and z=1 does not happen before it, and thus is also a possibility. - Given the following class, indicate all possible values that could be printed when running the program (the key here is to understand what is allowed by "visibility" rules): public class setValue { private static boolean ready; private static int number; private static class ReaderThread extends Thread { public void run() { while (!ready) {} System.out.println(number); } } public static void main(String[] args) throws InterruptedException { new ReaderThread().start(); number = 42; ready = true; } } Answer: it could print 42 (as expected), print 0, or loop forever. See p. 34 in the text for an explanation. - In the intuitive definition of a data race we say that two threads might access a memory location "at the same time". This will never literally happen on a machine with a single processor. Can there still be data races on such machines? If so, give an execution trace that demonstrates the data race and explain why it is still a race. Answer: Yes. A data race is technically two accesses by different threads to the same location where at least one of the accesses is a write, and the access are not ordered by happens-before. Here is an example trace (taken from an earlier question): write(T1,z,0); lock(T1,y); write(T1,x,1); unlock(T1,y); write(T1,z,1); lock(T2,y); read(T2,x,1); unlock(T2,y); read(T2,z,_) The data race is between the write(T1,z,1) and the read(T2,z,_) which are unordered according to the happens-before definition. - Is there a data race in the following class? If so, explain how it could happen. Is the class thread-safe? If so, explain why. If not, give an example run that breaks thread safety, and show how to fix it to make it thread-safe. public class SizedList { private List vec; private int max; public SizedList(int max) { this.vec = Collections.synchronizedList(new ArrayList(max)); this.max = max; } public void add(T obj) { if (vec.size() == max) return; vec.add(obj); } public T get(int idx) { return vec.get(idx); } } Answer: There is no data race---all accesses to the internal fields of vec are ordered by synchronization operations (added by teh Collections.synchronizedList factory method). There is, however, an atomicity violation such that the class is not thread-safe. In particular, the add() method could be called by two threads where the operations are interleaved. For example, suppose thread T1 calls o.add(X) and thread T2 calls o.add(Y) for some X and Y. Further suppose that o.vec.size() != max prior to both calls. Then the operations of the call to add() could be interleaved as follows: T1 : vec.size() != max vec.add(X) T2 : vec.size() != max vec.add(Y) At the end, the vector gets both X and Y added, and thus exceeds its size restriction, breaking its specification. - The next three classes have various problems that make them not thread-safe. Indicate what kind of problem(s) they have from the choices data race, deadlock, atomicity violation, visibility problem. Then add in code to fix the problem. If you decide to use synchronization, be sure not to oversynchronize. A) public class LazyInit { private ExpensiveObject instance = null; public ExpensiveObject getInstance() { if (instance == null) instance = new ExpensiveObject(); return instance; } } class ExpensiveObject { public void use() { ... } } class Client { public void doit(LazyInit x) { ExpensiveObject o = x.getInstance(); o.use(); } } Answer: This class has a data race: the read of instance in getInstance in the expression instance == null could race with the write to instance, instance = new ExpensiveObject(). This is a check-then-act data race. To fix the problem we have two choices. The simplest is to change the LazyInit class as follows, to use synchronization: public class LazyInit { private ExpensiveObject instance = null; public synchronized ExpensiveObject getInstance() { if (instance == null) instance = new ExpensiveObject(); return instance; } } A trickier solution is to do the following: public class LazyInit { private volatile ExpensiveObject instance = null; public synchronized ExpensiveObject getInstance() { if (instance == null) { synchronized (this) { if (instance == null) instance = new ExpensiveObject(); } } return instance; } } For the first null check, we avoid synchronization. This way, after the object is initialized we won't have to pay the cost of synchronization for every call to getInstance(). On the other hand, for this to work, we have to make the field volatile, so that after one thread assigns the field, subsequent threads will see that assignment without having to synchronize. Within the synchronized block, we have to recheck that instance has not been assigned to in the meantime. See http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html for an interesting history of this "double-checked locking" paradigm. B) public class StuffIntoPublic { public Holder holder; public void initialize() { holder = new Holder(42); } } Answer: This class has a visibility problem. Assuming that initialize() will only be called once, so that only one object is ever stored in holder, the problem is that other threads may not see that store, and still read holder as null. In short, a write to holder via initialize() called from thread T1 does not happen-before a read of holder from thread T2. To fix this problem, we must make the holder field volatile. C) public class DualCounter { private AtomicInteger i = new AtomicInteger(0); private AtomicInteger j = new AtomicInteger(0); public void inc() { i.inc(); j.inc(); } public void use() { if (i.get() != j.get()) throw new IllegalStateException(); // should never happen ... } } Answer: This class has an atomicity violation (but no data races). The problem is that one thread could call DualCounter.inc(), but only get as far as calling i.inc() before another thread calls use() on the same object, thus discovering that i.get() != j.get(). To solve this problem, we need to make the two calls i.inc() and j.inc() execute atomically. The easiest way to do this is to use the monitor pattern, making DualCounter.inc() and DualCounter.use() both synchronized methods. Once we do this, there is no need for i and j to be AtomicIntegers any more, so we might as well make them normal integers, as follows: public class DualCounter { private int i = 0; private int j = 0; public synchronized void inc() { i++; j++; } public synchronized void use() { if (i != j) throw new IllegalStateException(); // should never happen ... } } D) public class RandomList implements Runnable { private static final ArrayList nums = new ArrayList(); private static final Random rand = new Random(); public void run() { for (int i = 0;i<100; i++) { synchronized (nums) { nums.add(rand.nextInt(1000)); } } } public static void main(String args[]) { Thread[] ts = new Thread[10]; for (int i = 0; i<10; i++) { ts[i] = new Thread(new RandomList()); ts[i].start(); } for (int i = 0; i<10; i++) { try { ts[i].join(); } catch (InterruptedException e) { } System.out.println(nums); } System.out.println(nums); } } Answer: This program has a data race, which could result in a ConcurrentModificationException. The nums field's contents could be read during the call to System.out.println() at the bottom (which is implicitly iterating through the arraylist when it is constructing the string to print), at the same time another thread is writing to those contents during the call to nums.add() in the run() method. The latter call is made with the intrinsic lock on nums held, but the latter calls are not. To fix this problem, we could rewrite the class as follows: public class RandomList implements Runnable { ... public static void main(String args[]) { ... for (int i = 0; i<10; i++) { try { ts[i].join(); } catch (InterruptedException e) { } synchronized (nums) { System.out.println(nums); } } System.out.println(nums); } } Notice that we do not need to synchronize the last println call, because the calls to ts[i].join() ensure that all the threads that were writing to the array have completed, and that all those writes will be properly ordered with the reads that take place when converting to a string. - Show how to implement a BlockingQueue using a Semaphore and some means to store the objects. Here is the interface you must implement (you only need to worry about the two methods shown, not the entirety of the actual Java collections interface), along with a constructor that takes an integer N as the maximum queue size: public interface BlockingQueue { void put(T object) throws InterruptedException; T take() throws InterruptedException; ... } - The following is a MTC test case for a blocking queue. This test intends for the first thread to block on the call to buf.put(17). Will this happen, as it is written now? If not, how would you fix it? class MTCBoundedBufferTest extends MultithreadedTestCase { MyBlockingQueue buf; public void initialize() { buf = new MyBlockingQueue(1); } public void thread1() throws InterruptedException { buf.put(42); buf.put(17); // test case should ensure this blocks assertTick(1); } public void thread2() throws InterruptedException { waitForTick(0); assertEquals(Integer.valueOf(42), buf.take()); assertEquals(Integer.valueOf(17), buf.take()); } public void finish() { assertTrue(buf.isEmpty()); } } Answer: the waitForTick(0) should be waitForTick(1). This is because the tick starts at 0, so waiting for 0 will not force thread2() to wait until thread 1 has blocked, which should happen when thread 1 makes the second call to buf.put(). As such, thread 2 could end up running first, blocking on buf.take() and thus ensuring that thread 1 never actually blocks at all. - The PrimeParallel.java class (at http://www.cs.umd.edu/class/fall2010/cmsc433/examples/PrimeParallel.java) computes prime numbers by dividing the range into sub-ranges, and having each compute chunk produce a list of prime numbers. A Future> is stored in the results[] array for each worker executed by a thread pool, and each result is combined into a single array at the end. Rewrite the main() method of this program to use a CompletionService instead in the style of the method computeMTCompletion in http://www.cs.umd.edu/class/fall2010/cmsc433/examples/ArrayAverageParallel.java (look at computeMTFut in this file and see how it differs from computeMTCompletion; make the same change to ArrayAverageParallel). Answer: I leave it to you to do this and test the answer yourself! - Consider the following class: public class Service extends Thread { private volatile boolean canceled; public void run() { while (!canceled) { doSomeWork(); } } private void doSomeWork() throws InterruptedException { ... } public void cancel() { canceled = true; } } We want other threads to be able to call a Service's cancel() method to cause it to halt, but this implementation has a problem. What is it? Rewrite it so that it no longer has this problem. Answer: The problem is that the doSomeWork() call could block, and thus it may never notice that the cancel variable has been set. (We know that doSomeWork() could block by the fact that it declares it could throw InterruptedException.) To fix this problem, we should use interruption to cancel the service, as follows: public class Service extends Thread { public void run() { while (!isInterrupted()) { try { doSomeWork(); } catch (InterruptedException e) { interrupt(); // need to re-interrupt the thread } } } private void doSomeWork() throws InterruptedException { ... } public void cancel() { interrupt(); } } Two things to notice here. First, notice that we must catch interrupted exception in the run() method because the method does not declare that it throws this exception. (This was a mistake in the initial code given above!) Second, in the catch block, we reinterrupt the thread. This is because when InterruptedException is thrown, the interruptedness of the thread is reset. By re-setting it, the condition in the while loop (!isInterrupted()) will be true, and the loop will exit. Second, Service extends Thread. If Service extended Runnable, the calls to interrupt(), and isInterrupted(), wouldn't work because they are inherited from the thread class. You'd have to change Service to know what thread is running it so that the thread can be properly interrupted. For example: public class Service implements Runnable { private volatile Thread runningThread; public void run() { runningThread = Thread.currentThread(); while (!Thread.currentThread().isInterrupted()) { try { doSomeWork(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); // need to re-interrupt the thread } } } private void doSomeWork() throws InterruptedException { ... } public void cancel() { runningThread.interrupt(); } } - Starting with the single-threaded WordCount program on the web site, follow the design recipe for parallelizing a program to produce a multi-threaded version. Produce each of the intermediate versions, and compare your answers against those we went over in class.