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 8, 10, 11, and 15, and the slides
on the Fork-Join framework, with an emphasis on material we covered in
class.  You are also responsible for the material covered in class on
Erlang (through November 15), and in the two papers (by Jim Larson and
Joe Armstrong, respectively) and code examples linked on-line.

I also expect you to be familiar with solutions to project 3, and
basic strategies that work.  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:

-Latency
-Throughput
-Scalability
-Deadlock (what are the necessary conditions)
-Livelock
-Starvation
-Lock contention
-Open call
-Spinlock
-Nonblocking algorithm
-Lock-free algorithm

***Short answer:

- What are some of the costs that are incurred by using threads?  What
  are ways to avoid some of these costs?

- It is recommended that when using Executors the tasks be
  independent.  Why is this?  The ForkJoin framework does allow
  dependencies among tasks --- describe more precisely how this is
  so.  Explain why such dependencies are OK in this context.

- How does the example program we gave in class, involving bank
  account transfers, prevent deadlock.  The solution appears to be
  pretty complicated --- the root of the complication is that the
  program does not know how many bank accounts there are.  If you did
  know that there was a fixed number of bank accounts (say, 2), how
  could your solution be made simpler?

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

- Name three ways to reduce lock contention

- Nonblocking synchronization are often referred to as "optimistic"
  compared to blocking (i.e., lock-based) synchronization, which is
  referred to as "pessimistic".  Explain this.

- Under what circumstances would you expect a non-blocking algorithm
  to outperform a blocking algorithm, e.g., a counter implemented with
  non-blocking synchronization vs. one implemented with blocking
  synchronization?  When would you expect you expect the reverse
  situation?

- Explain what the CAS (compare-and-swap) operator does.  Provide
  pseudocode, if you wish.

- Give the definition of Amdahl's Law, explaining the parts of the
  equation you show.  When/how do you use this law?

- Erlang uses message passing to coordinate actions among concurrent
  tasks, while Java uses shared memory.  How do these two styles
  relate?  What are the advantages of one vs. the other?

- Erlang variables are "assign once".  Explain what this means.  Give
  a code example that shows how "assign once" is useful for verifying
  results.

- Can Erlang programs have atomicity violations?  If so, give an
  example.

***Java Programming:

- Write a parallel mergesort using the fork/join framework.  You can
  start from the MaxSolver.java and Maxproblem.java classes that we
  provided.  Use Arrays.sort() to perform the sequential work of
  sorting the array; you will have to write the merge() routine
  yourself (you can find code that does this on the Internet).  You
  could also make the problem a little simpler by merging the two
  classes and eschewing the separate notion of a SortProblem akin to
  MaxProblem.

- If you have not done so already, implement the Maze solving
  algorithm using the puzzlesolving framework from Chapter 8.  This
  boilds down to changing the Maze class to implement the Puzzle
  interface (p. 183) and then using the code already provided with
  project 3 to execute the solving process.  Implement it as part of
  your project so you can confirm that the solution is correct.

- Recall the basic formula for implementing a non-blocking algorithm:
  read the current value of the state, make a change, and then try to
  write the change using CAS to make sure that the original value has
  not changed.  Using this idea, implement the add() and remove() below.

public class NonBlockingLinkedList { 
  private static class Node { 
    public final int item; 
    public Node next; 
    public Node(int item) { 
      this.item = item; 
    } 
  } 
  public void add(int item) { 
    // FILL IN
  }

  public void remove() {
    // FILL IN
  }
}

  (check your work by looking at the SyncStack.java example we provided).

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

- In class we went over the program processes.erl, which created N
  processes in Erlang, and measured the time to do so.  Write a
  similar program in Java and run both it and the Erlang program on
  your machine.  How much does the task creation time differ?  What
  are the ramifications of this difference on how you do programming
  in each language?

***ERLANG Programming

- Write a ring benchmark in Erlang.  Create N processes in a ring.
Send a message round the ring M times so that a total of N * M
messages get sent.  Time how long this takes for differernt values of
N and M.  Look at the example processes.erl file to see how timing is
done.  Otherwise, you should be able to use the standard spawn, send
(using !) and receive operations.

- Implement a countdown latch in Erlang in the same style as the
  semaphore.erl implementation.  Recall: a countdown latch starts with
  a particular number, and has two functions: decrement() and
  await().  The latter blocks until the count reaches 0, while the
  former decrements the count (no blocking).

- Extend the implementation of blockingqueue.erl provided with project
  4 to implement a priority queue.  The API should now be

take(Q) returns {ok,E} where E is the highest priority item in Q, or
  atom cancel if Q was canceled. 
put(Q,E,P) enqueues E with priority P (an integer) into Q.
cancel(Q) cancels Q, returns ok.

--The following ask you to write some standard functional programs in
Erlang.  Write them using recursion, and also try to use lists:map()
and lists:foldr().

-Write a function iter_n(N,F) that executes F(N), F(N-1), ..., F(0),
 and then returns ok.  If N < 0 the result is undefined (pattern match
 error).

-Write a function prod(list(integer())) -> integer() that returns the
 product of the elements of l. The function prod should return 1 if
 the list is empty.

-Write a function add_tail(list(X),Y) -> list(X|Y) that takes a list l
 and a single element e and returns a new list where e is appended to
 the back of l. For example, add_tail([1,2],3) = [1,2,3] (having type
 list(integer())), and add_tail([1,2],4.0] = [1,2,4.0] (having type
 list(integer()|float())).

-Write a function index(list(any()),any()) -> integer() that takes a
 list and a single element and returns the position of the last
 occurrence of that element in the list (indexed by zero). You should
 return -1 if the element is not in the list.

-Write a function app_int(fun(integer())->X,integer(),integer()) ->
 list(X) that returns the list [f(m); (f (m+1)); ...; f(n)] where f is
 the function passed to app_int, and m and n are the second and third
 arguments, respectively. It should return the empty list if n < m.
 

***Analysis:

- Here are three possible strategies for solving the maze in project
  3: one based on breadth-first search, one based on depth-first
  search (as in Sam Blitzstein's project solution, posted, that we
  discussed in class), and one based on bidirectional search, which
  starts from the entry and exit of the maze in parallel and tries to
  "meet in the middle".  Explain the basic idea of how each strategy
  might work, and describe why you think the strategy will produce a
  speedup compared to the sequential case for BFS, and why it might
  not.  Explain why your own project had a speedup, or didn't, as the
  case may be.

- The following program acquires locks on a set of resources. The
  acquire() method recursively acquires locks on each of the resources
  in the list, and then executes a Runnable command.  The main()
  method gives an example.  However, the ResourceMgr class could be
  used in a way that could lead to deadlock.  Produce an alternative
  main() method that will induce a deadlock (the main() method will
  have to spawn/use multiple threads).  Give an execution trace
  showing how it can lead to deadlock.

public class ResourceMgr { 
  Runnable comm; 
  ResourceMgr (Runnable comm) { 
    this.comm = comm; 
  } 
  public class Resource { 
    public synchronized void acquire(List<Resource> rest) { 
      if (rest.size() > 0) { 
        (rest.remove(0)).acquire(rest); 
      } else 
        comm.run(); 
    } 
  } 
  public static void main(String[] args) { 
    ResourceMgr bb = new ResourceMgr(new Runnable () {public void run () {}}); 
    // bb.new Resource() makes a new Resource inside bb 
    final ResourceMgr.Resource r1 = bb.newResource(); 
    final ResourceMgr.Resource r2 = bb.newResource(); 
    final ResourceMgr.Resource r3 = bb.newResource(); 
    List <Resource> resList = new ArrayList<Resource>(); 
    resList.add(r2); 
    resList.add(r3); 
    r1.acquire(resList); 
  } 
} 

- The following program can deadlock. Give an execution trace showing
how this can occur.  

public class Deadlock { 
  static class Friend { 
    public synchronized void bow(Friend bower) { 
      System.out.println("I bow to you"); 
        bower.bowBack(this); 
    } 
    public synchronized void bowBack(Friend bower) { 
      System.out.println("I bow back to you"); 
    } 
  } 
  public static void main(String[] args) { 
    final Friend f1 = new Friend(), f2 = new Friend(); 
    ExecutorService exec = Executors.newCachedThreadPool(); 
    exec.execute(new Runnable() {
      public void run() { while (true) {f1.bow(f2);}}}); 
    exec.execute(new Runnable() {
      public void run() { while (true) {f2.bow(f1);}}}); 
  } 
} 

- Look at WordCountParallelScale.java and WordCountParallel.java and
  examine the differences.  In both cases, identify the sequential
  bottlenecks of the program (i.e., the parts that, no matter how many
  threads we use, will always take the same amount of total time), and
  the parallel parts.  Which has a greater degree of parallelism?