Name:

SE552 final exam: Autumn 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 sorted collection into a mutable sorted collection is defined:

  interface ISortedCollection {
    ISortedCollection insert (Comparable x);
    Comparable get (int index);
    int size ();
    static final ISortedCollection empty = ...;
  }
  interface MSortedCollection {
    void insert (Comparable x);
    Comparable get (int index);
    int size ();
  }
  class MSortedCollectionImpl implements MSortedCollection {
    ISortedCollection contents = ISortedCollection.empty;
    void insert (Comparable x) { 
      contents = contents.insert (x); 
    }
    Comparable get (int index) {
      return contents.get (index);
    }
    int size () {
      return contents.size ();
    }
  }

Question 2 continued

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

  class MSortedCollectionImpl implements MSortedCollection {
    ISortedCollection contents = ISortedCollection.empty;
    final Object lock = new Object ();
    void insert (Comparable x) { 










    }
    Comparable get (int index) {










    }
    int size () {










    }









  }

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 MSortedCollectionImpl implements MSortedCollection {
    ISortedCollection contents = ISortedCollection.empty;
    final Object lock = new Object ();
    void insert (Comparable x) { 










    }
    Comparable get (int index) {










    }
    int size () {










    }









  }

Question 3 (15 points)

a) What is a Mutex?

b) What is a Read/Write lock?

c) What is the advantage of using a Read/Write lock over a Mutex?

d) When implementing a Read/Write lock, the designer has to decide whether to implement a readers beat writers policy or a writers beat readers policy. Describe these policies and give one advantage of each.

Question 3 continued

Question 4 (20 points)

a) What is deferred synchronous invocation?

b) Give an example of when deferred synchronous invocation is useful.

c) Explain how callbacks can be used to implement deferred synchronous invocation.

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

e) Give one advantage of callbacks and one advantage of futures.

Question 4 continued

Question 5 (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 waiting tasks?

d) When a task has to be cancelled, should the pool cancel a newly arrived task, or an old task? Give a one- or two-sentence justification for your answer.

Question 5 continued

Question 6 (10 points)

a) What is an event loop?

b) One strategy for implementing an event loop is to use a worker pool with only one worker thread (the event handling thread). Give a one- or two-sentence example of this strategy.

c) Give one advantage and one disadvantage of using an event handling thread to implement an event loop.

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.