Name:

SE552 final exam: Autumn 2000-2001

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Sorted lists

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

  public interface SortedList {
    public int size ();
    public Comparable head ();
    public SortedList tail ();
    public SortedList insert (Comparable x);
    public static SortedList empty = new Empty ();
  }
  class Empty implements SortedList {
    public int size () { return 0; }
    public Comparable head () { throw new NoSuchElementException (); }
    public SortedList tail () { throw new NoSuchElementException (); }
    public SortedList insert (Comparable x) { return new Cons (x, this); }
  }
  class Cons implements SortedList {
    final Comparable hd; final SortedList tl; final int sz;
    Cons (final Comparable hd, final SortedList tl) {
      this.hd = hd; this.tl = tl; this.sz = sz;
    }
    public int size () { return sz; }
    public Comparable head () { return hd; }
    public SortedList tail () { return tl; }
    public SortedList insert (Comparable x) {
      if (x.compareTo (hd) < 0) {
        return new Cons (x, this);
      } else {
        return new Cons (hd, tl.insert (x));
      }
  }

Priority queues

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

  public interface PriorityQueue {
    public int size ();
    public Comparable get () throws InterruptedException;
    public void put (Comparable x) throws InterruptedException;
    public static void PriorityQueueFactory factory =
      new PriorityQueueFactoryImpl ();
  }
  public interface PriorityQueueFactory {
    public PriorityQueue build ();
  }
  class PriorityQueueFactoryImpl implements PriorityQueueFactory {
    public PriorityQueue build () { return new PriorityQueueImpl (); }
  }
  class PriorityQueueImpl implements PriorityQueue {
    SortedList contents = SortedList.empty;
    final Object lock = new Object ();
    public int size () { 
      your code goes here 
    }
    public Comparable get () throws InterruptedException {
      your code goes here 
    }
    public void put (Comparable x) throws InterruptedException {
      your code goes here 
    }
    your code goes here 
  }

Question 1 (5 points)

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

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

Question 2 (20 points)

Complete the implementation of PriorityQueueImpl using pessimistic safety, and guarding failure mode.

  class PriorityQueueImpl implements PriorityQueue {
    SortedList contents = SortedList.empty;
    final Object lock = new Object ();

Question 2 continued

Question 3 (20 points)

Complete the implementation of PriorityQueueImpl using optimistic safety, and baulking failure mode.

  class PriorityQueueImpl implements PriorityQueue {
    SortedList contents = SortedList.empty;
    final Object lock = new Object ();

Question 3 continued

Question 4 (10 points)

a) What is a mutex?

b) What is the difference between a mutex and a reentrant lock?

c) Give one reason why a programmer might use a mutex object rather than Java's built-in locks?

Question 5 (15 points)

Complete the following code for a mutex:

  public interface Sync {
    public void acquire () throws InterruptedException;
    public void release ();
  }
  class Mutex implements Sync {
    final Object lock = new Object ();
    boolean acquired = false;    
    your code goes here

Question 6 (10 points)

For each of the following programs, say whether or not the field delegate can escape, and whether or not it suffers from the nested monitor problem:

a)

  class Outer {
    public final Inner delegate = new Inner ();
    public synchronized void foo (final boolean b) throws InterruptedException {  delegate.bar (b); }
  }
  class Inner {
    public synchronized void bar (final boolean b) throws InterruptedException {
      if (b) { notifyAll (); } else { wait (); }
    }
  }

b)

  class Outer {
    protected final Inner delegate = new Inner ();
    public synchronized void foo (final boolean b) throws InterruptedException {  delegate.bar (b); }
  }
  class Inner {
    public synchronized void bar (final boolean b) throws InterruptedException {
      if (b) { notifyAll (); } else { wait (); }
    }
  }

c)

  class Outer {
    protected final Inner delegate = new Inner ();
    public synchronized Inner foo (final boolean b) throws InterruptedException { return delegate.bar (b); }
  }
  class Inner {
    public synchronized Inner bar (final boolean b) throws InterruptedException {
      if (b) { notifyAll (); } else { wait (); }
      return this;
    }
  }

d)

  class Outer {
    protected final Inner delegate = new Inner ();
    public synchronized void foo (final boolean b) throws InterruptedException { 
      if (b) { notifyAll (); } else { wait (); } delegate.bar (b); 
    }
  }
  class Inner {
    public synchronized void bar (final boolean b) throws InterruptedException {
      return;
    }
  }

Question 7 (20 points)

Complete the following implementation of a worker pool, which uses the following rules:

You can assume that the insert method of PriorityQueue cannot block indefinitely.

  interface Task extends Comparable {
    public void run ();
    public void cancel ();
  }
  interface Executor {
    public void execute (Task t) throws InterruptedException;
  }
  class WorkerPool implements Executor {
    final Object lock = new Object ();
    final PriorityQueue queue = PriorityQueue.factory.build ();
    your code goes here    

Question 7 continued

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.