Name:

SE552 final exam: Winter 2001-2002

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Sequence collection

Some questions will refer to a Sequence interface. It implements a binary tree data structure for storing collections of objects, and is defined:

interface Sequence {
    public Sequence add (Object s);
    public int size ();
    public Object get (int index);
    public static final Sequence empty = new SequenceEmpty ();
}

class SequenceEmpty implements Sequence {
    public Sequence add (Object x) { return new SequenceOne (x); }
    public int size () { return 0; }
    public Object get (int index) { throw new NoSuchElementException (); }
}

class SequenceOne implements Sequence {
    final Object contents;
    SequenceOne (Object contents) { this.contents = contents; }
    public Sequence add (Object x) { return new SequenceMany (this, new SequenceOne (x)); }
    public int size () { return 1; }
    public Object get (int index) { 
        if (index == 0) { return this.contents; }
        else { throw new NoSuchElementException (); }
    }
}

class SequenceMany implements Sequence {
    final Sequence left;
    final Sequence right;
    final int size;
    SequenceMany (Sequence left, Sequence right) {
        this.left = left; this.right = right; this.size = left.size () + right.size ();
    }
    public Sequence add (Object x) {
        if (left.size () > right.size ()) {
            return new SequenceMany (left, right.add (x));
        } else {
            return new SequenceMany (this, new SequenceOne (x));
        }
    }
    public Object get (int index) {
        if (index < left.size ()) { return left.get (index); }
        else { return right.get (index - left.size ()); }
    }
    public int size () { return size; }
}

Array

Some questions will refer to an Array interface. It uses the Sequence data structure to provide a simplified implementation of arrays.

interface Array {
    public void add (Object x);
    public int size ();
    public Object get (int index);
    public static ArrayFactory factory = new ArrayFactoryImpl ();
}

interface ArrayFactory {
    public Array build ();
}

class ArrayFactoryImpl implements ArrayFactory {
    public Array build () { return new ArrayImpl (); }
}

class ArrayImpl implements Array {
    Sequence contents = Sequence.empty;
    public void add (Object x) { 
        contents = contents.add (x); 
    }
    public int size () {
        return contents.size ();
    }
    public Object get (int index) {
        return contents.get (index);
    }
}

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 (15 points)

A simple program which uses the Array data structure is:

        Array array = Array.factory.build ();
        array.add ("A");
        array.add ("B");
        array.add ("C");
        array.add ("D");
        for (int i=0; i<array.size (); i++) {
            System.out.println (array.get (i));
        }

a) What is printed out by this program?

b) Draw an object diagram showing the contents of the array object after this program has executed.

Question 3 (20 points)

Currently, the Array data structure is not thread-safe. Make changes to the ArrayImpl class which make it thread-safe, using pessimistic safety, and guarding failure mode.

interface Array {
    public void add (Object x);
    public int size ();
    public Object get (int index) throws InterruptedException;
    public static ArrayFactory factory = new ArrayFactoryImpl ();
}

class ArrayImpl implements Array {


    Sequence contents = Sequence.empty;
    final Object lock = new Object ();


    public void add (Object x) { 




        contents = contents.add (x); 




    }

    public int size () {




        return contents.size ();




    }

    public Object get (int index) throws InterruptedException {




        return contents.get (index);




    }

}

Question 3 continued

Question 4 (20 points)

Make changes to the ArrayImpl class which make it thread-safe, using optimistic safety, and baulking failure mode. In the case where the commit method fails, you should throw a ConcurrentModificationException and not retry the method.

interface Array {
    public void add (Object x);
    public int size ();
    public Object get (int index);
    public static ArrayFactory factory = new ArrayFactoryImpl ();
}

class ArrayImpl implements Array {


    Sequence contents = Sequence.empty;
    final Object lock = new Object ();


    public void add (Object x) { 




        contents = contents.add (x); 




    }

    public int size () {




        return contents.size ();




    }

    public Object get (int index) {




        return contents.get (index);




    }

}

Question 4 continued

Question 5 (20 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 reentrant locks.

d) Give one disadvantage of using a mutex object rather than Java's built-in reentrant locks.

Question 5 continued

Question 6 (15 points)

a) What is a worker pool?

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

c) Describe a program which does not deadlock if there are an aribitrary number of worker threads, but which may deadlock if there is a fixed number of worker threads. (You only need to provide an English description, or pseudocode, not a full implementation.)

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.