Name:

SE552 Example final exam

Answer all questions.

Time allowed: 2 hours

Total number of points: 100


Immutable Lists

Some questions will refer to a ImmutableList interface. It is defined:

  public interface ImmutableList {
    public Object head ();
    public ImmutableList tail ();
    public int size ();
    public ImmutableList reverse ();
    public ImmutableList cons (Object hd);
    public static ImmutableList empty = new Empty ();
  }
  class Empty implements ImmutableList {
    public Object head () { throw new NoSuchElementException (); }
    public ImmutableList tail () { throw new NoSuchElementException (); }
    public int size () { return 0; }
    public ImmutableList reverse () { return this; }
    public ImmutableList cons (final Object hd) { return new Cons (hd, this); }
  }
  class Cons implements ImmutableList {
    final Object hd; final ImmutableList tl; final int sz;
    Cons (final Object hd, final ImmutableList tl) { this.hd = hd, this.tl = tl; this.sz = tl.size () + 1; }
    public Object head () { return hd; }
    public ImmutableList tail () { return tl; }
    public int size () { return sz; }
    public ImmutableList reverse () { return tl.reverse ().cons (hd); }
    public ImmutableList cons (final Object hd) { return new Cons (hd, this); }
  }

Queues

Some questions will refer to a Queue interface. It is defined:

  public interface Queue {
    public int size ();
    public Object get () throws InterruptedException;
    public void put (Object x);
    public static QueueFactory factory = new QueueFactoryImpl ();
  }
  public interface QueueFactory {
    public Queue build ();
  }
  class QueueFactoryImpl implements QueueFactory {
    public Queue build () { return new QueueImpl (); }
  }
  class QueueImpl implements Queue {
    final Object lock = new Object ();
    ImmutableList front = ImmutableList.empty;
    ImmutableList back = ImmutableList.empty;
    public int size () { synchronize (lock) { return front.size () + back.size (); } }
    public void put (final Object x) { synchronize (lock) { back = back.cons (x); } }
    public void get () throws InterruptedException { 
      synchronize (lock) {
        if (front.size () == 0) {
          front = back.reverse ();
          back = ImmutableList.empty;
        } 
        Object result = front.head ();
        front = front.tail ();
        return result;
      }
    }
  }

Question 1 (10 points)

a) Three failure modes for concurrent programs are baulking, guarding and timeout. Explain each of these.

b) Which failure mode does the QueueImpl class use?

c) Two possible strategies for ensuring thread-safety are optimistic and pessimistic. Explain each of these.

d) Which safety strategy does the QueueImpl class use?


Question 2 (15 points)

Rewrite the QueueImpl class so it uses a different failure mode.


Question 3 (20 points)

Rewrite the QueueImpl class so it uses a different safety strategy.


Question 4 (15 points)

a) What is the difference between an MVar and an IVar?

b) The following code implements an IVar. Rewrite it to implement an MVar.

  public interface Channel {
    public void put (Object x) throws InterruptedException;
    public Object get () throws InterruptedException;
  }
  class IVar implements Channel {
    protected final Object lock = new Object ();
    protected Object contents = null;
    public void put (final Object x) throws InterruptedException {
      if (contents == null) {
        synchronize (lock) {
          if (contents == null) { contents = x; lock.notifyAll (); return; }
        }
      }
      throw new IllegalAccessException ();
    }
    public Object get () throws InterruptedException {
      if (contents == null) {
        synchronized (lock) { while (contents == null) { lock.wait (); } }
      }
      return contents;
    }
  }

Question 5 (15 points)

a) What is a worker pool?

b) Give two reasons why a program might use a worker pool, rather than creating new threads directly.

c) Give an outline of how a worker pool can be implemented.


Question 6 (10 points)

a) What is synchronous method invocation?

b) What is asynchronous method invocation?

c) What is deferred synchronous method invocation?

d) Explain how futures can be used to implement deferred synchronous invocation.


Question 7 (15 points)

a) What is a divide-and-conquer algorithm?

b) Name an example divide-and-conquer algorithm?

c) Explain how Java's thread model can be used to exploit multiple processors for divide-and-conquer algorithms.

d) Give sample pseudo-code showing how your answer to part b) can be implemented using the technique in your answer to part c).