Name:

SE552 final exam: Winter 2002-2003

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (10 points)

a) Three failure modes for concurrent programs are baulking, guarding and timeout. Give a one- or two-sentence explaination for each of these.

b) Two possible strategies for ensuring thread-safety are optimistic and pessimistic. Give a one- or two-sentence explaination for each of these.

Question 2 (30 points)

A wrapper class which turns an immutable dictionary into a mutable dictionary is defined:

  interface IDictionary {
    IDictionary add (Object key, Object value);
    Object get (Object key);
    Iterator iterator ();
    static final IDictionary empty = ...;
  }
  interface MDictionary {
    void add (Object key, Object value);
    Object get (Object key);
    Iterator iterator ();
  }
  interface Iterator {
    boolean hasNext ();
    Object next ();
  }
  class MDictionaryImpl implements MDictionary {
    IDictionary contents = IDictionary.empty;
    void add (Object key, Object value) { 
      contents = contents.add (key, value); 
    }
    Comparable get (Object key) {
      return contents.get (key);
    }
    Iterator iterator () {
      return contents.iterator ();
    }
  }

Question 2 continued

a) Make this class thread-safe using an pessimistic strategy.

  class MDictionaryImpl implements MDictionary {
    IDictionary contents = IDictionary.empty;
    final Object lock = new Object ();
    void add (Object key, Object value) { 










    }
    Comparable get (Object key) {









    }
    Iterator iterator () {









    }
  }

Question 2 continued

b) Make this class thread-safe using an optimistic strategy. Any error conditions caused by concurrent simultaneous access to the list should cause a ConcurrentModificationException to be thrown.

  class MDictionaryImpl implements MDictionary {
    IDictionary contents = IDictionary.empty;
    final Object lock = new Object ();
    void add (Object key, Object value) { 










    }
    Comparable get (Object key) {









    }
    Iterator iterator () {









    }









  }

Question 3 (30 points)

a) What is an IVar?

b) What is an MVar?

c) Why might a programmer wish to use one of these classes?

d) Give one advantage and one disadvantage of an IVar compared to an MVar.

Question 3 continued

e) What is deferred synchronous method invocation?

f) Discuss how one of these classes could be used to implement deferred synchronous invocation.

g) Should an IVar or an MVar be used to implement deferred synchronous invocation?

Question 3 continued

h) Edit the following code sample which implements an MVar, and change it to implement an IVar.

  class MVarImpl {

    final Object lock = new Object ();

    Object contents = null;

    public void put (Object x) {


      synchronized (lock) {


        if (contents = null) { contents = x; }


        else { throw new RuntimeException ("MVar is full!");


        lock.notifyAll ();


      }


    }


    public Object get () throws InterruptedException {


      synchronized (lock) {


        while (contents == null) { lock.wait (); }


        Object result = contents;


        contents = null;


        return result;


      }


    }


  }

Question 4 (15 points)

a) What is a worker pool?

b) Why might a programmer use a worker pool rather than calling new Thread directly?

c) Why might a worker pool need to limit the total number of worker threads?

d) Under what circumstances should a new worker thread be created?

e) Under what circumstances should an existing worker thread die?

Question 4 continued

Question 5 (15 points)

a) What is the difference between concurrent programming and parallel programming?

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

c) How can a Java programmer implement a divide-and-conquer algorithm as a parallel program?

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