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?
- What is the role of "volatile?"  What problem does it solve?
- What is the difference between a concurrent data structure, like
  ConcurrentHashMap, and a synchronized one, like that created by
  Collections.synchronizedMap()?
- Why doesn't client-side locking work with ConcurrentHashMap?
- Assuming 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?

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)

  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)

- 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?

- 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; 
  } 
}

- 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.

- 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<T> {
  private List<T> vec;
  private int max;
  public SizedList(int max) {
    this.vec = Collections.synchronizedList(new ArrayList<T>(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);
  }
}

- 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();
    }
}

B) 

public class StuffIntoPublic {
    public Holder holder;
    public void initialize() {
        holder = new Holder(42);
    }
}

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
    ...
  }
}

D) 

public class RandomList implements Runnable {
  private static final ArrayList<Integer> nums = new ArrayList<Integer>();
  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);
  }
}


- 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<T> {
  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<Integer> buf;
    public void initialize() {
        buf = new MyBlockingQueue<Integer>(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());
    }
}

- 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<List<Integer>> 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).

- 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.

- 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.