These are some sample problem ideas to help you as you prepare for 
the exam.  The list is not meant to be comprehensive.  Some problems 
on the exam will have the same flavor as these, but some of these
are here more to help you think about types of things the exam might
address.  You are also responsible for the material covered in class, 
in the slides, in the projects, and the posted code examples.



Definitions:
===========
- Deadlock
- Starvation
- Latency
- Throughput
- Scalability
- Graceful degredation
- Lock contention
- Spinlock
- Non-blocking algorithm
- Data Parallel
- Task Parallel



Short answer:
============
- Why is the purpose of Threadlocal<T>?  What problem does it generically
  solve in many cases?  How does the use of thread pools break this?

- Why use a thread pool rather than spawn each task off in a new thread?

- Why did our MergeSort algorithm in class deadlock if the threadpool
  was fixed at size 4?  Would making it size 8 have solved the problem?

- Improving performance by parallelization can actually increase the
  total work performed by all threads while reducing the latency of
  performing the work by all threads in parallel.  More specifically,
  some optimizations that could make a single-threaded program go
  faster could actually slow down a parallel program.  Can you give an
  example of such a situation?

- Non-blocking synchronization are often referred to as "optimistic"
  compared to blocking (i.e., lock-based) synchronization.  Why is 
  the term "optimistic" used?  What is it hoping will happen?

- Explain what the CAS (compare-and-swap) operator does.  Provide
  pseudocode to show how a "++" operator could be written using this
  approach without the use of any locks.

- What is the difference between shutdown() and shutdownNow()?  Is it
  possible for threads to ever continue running in a pool after each
  of these is called?  

- If you submit tasks to a threadpool, how can you have a line of code
  wait until the result is ready before using it without introducing
  new things like semaphores or latches or blocking queues?

- When is the CopyOnWriteArrayList a good concurrent structure to use?

- Are there ever cases where you would need to use locks to guard
  a list that was turned into a synchronizedList using the 
  Collections.synchronizedList method?

- When writing a Java program you have the option of using one of two
  styles of thread-safe collection: a concurrent collection, like 
  ConcurrentHashMap, or a synchronized collection, like one returned 
  from Collections.synchronizedMap. Give a benefit of each.

- What is a straight-forward approach for turning a recusive algorithm
  into a multi-threaded algorithm?  If there are any dangers to this
  approach, explain them and how they might be avoided.

- How can a CompletionService be used to grab the results of tasks as
  they complete by a single consumer?



Java Programming:
================
- Write a program that spawns producers and consumers so that at most
  60 things are produced (each one requiring some random amount of time
  to be produced), exactly 50 things are consumed, and the program 
  terminates once 50 things have been consumed.  You must use semaphores
  in a meaningful way.

- Write a program that spawns producers and consumers so that at most
  60 things are produced (each one requiring some random amount of time
  to be produced), exactly 50 things are consumed, and the program 
  terminates once 50 things have been consumed.  You must NOT use any
  semaphores or waits or notifies but rather must use a blocking data 
  structure in a meaningful way.

- Write a program that will use a countdown latch to allow 10 taks
  to run simultaneously on a 12-processor machine such that the program
  will take only marginally longer than the slowest task to complete.

- Suppose your application needs to keep an accurate count of the
  number of threads using a resource. You decide to use an
  AtomicInteger to maintain this count.  Fill in the code below to
  implement this strategy when a thread starts and stops using the
  resource.  You may not add any synchronized blocks or other locking
  mechanisms beyond that provided by AtomicInteger. For operations on
  AtomicIntegers you may only use the get() and compareAndSet(int
  expect, int update) methods.

     public class CustomerTracking { 
       public AtomicInteger numCust = new AtomicInteger(0); // the count 
       public void enter() { 
           //FILL IN 
       } 
       public void exit() {
           //FILL IN 
       } 
     } 

- For the specific input used below the main() method should print out,
  "Starting Stats" and "(0,4)". However, as written, it currently
  will not. Explain in detail why it does not print the expected output. 
  What can you do to fix the problem?

public class ExecutorStats implements Callable<Bounds> {
  private ExecutorService executor = Executors.newSingleThreadExecutor();
  private List<Integer> data = new ArrayList<Integer>(Arrays.asList(0, 3, 4, 2, 1));

  public Bounds call() throws Exception {
    Future<Integer> maxComputation = executor.submit(new Callable<Integer>() {
       public Integer call() throws Exception { return Collections.max(data); }});
    Future<Integer> minComputation = executor.submit(new Callable<Integer>() {
       public Integer call() throws Exception { return Collections.min(data); }});
    return new Bounds(minComputation.get(), maxComputation.get());
  }


  public static void main(String[] args) throws Exception {
     ExecutorStats stats = new ExecutorStats();
     System.out.println("Starting Stats");
     Future<Bounds> result = stats.executor.submit(stats);
     System.out.println(result.get());
     stats.executor.shutdown();
  }

}