Name:

SE552 midterm exam: Winter 2001-2002

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

String collections

Some questions will refer to a Strings interface and a UnsafeStringCollection class. They are defined here:

interface Strings {

    public int size ();
    public String get (int index);
    public Strings append (String s);
    public Strings append (Strings s);
    public static final Strings none = new StringsNone ();

}
abstract class StringsAbst implements Strings {

    public Strings append (String s) { return this.append (new StringsOne (s)); }
    public Strings append (Strings s) { 
      if (s.size () == 0) { return this; } 
      else if (this.size () == 0) { return s; } 
      else { return new StringsMany (this, s); } 
    }

}
class StringsNone extends StringsAbst {

    public int size () { return 0; }
    public String get (int index) { throw new NoSuchElementException (); }
    public Strings append (Strings s) { return s; }

}
class StringsOne extends StringsAbst {

    final String contents;
    StringsOne (String s) { contents = s; }
    public int size () { return 1; }
    public String get (int index) { 
        if (index == 0) { return contents; } 
        else { throw new NoSuchElementException (); } 
    }

}
class StringsMany extends StringsAbst {

    final int sz;
    final Strings left;
    final Strings right;
    StringsMany (Strings l, Strings r) { left = l; right = r; sz = l.size () + r.size (); }
    public int size () { return sz; }
    public String get (int index) { 
        if (index < left.size ()) { return left.get (index); } 
        else { return right.get (index - left.size ()); } 
    }

}

String collections continued


public class UnsafeStringCollection {

    Strings contents = Strings.none;

    public void add (String s) { contents = contents.append (s); }
    public boolean contains (String s) {
        for (int i=0; i<contents.size (); i++) {
            if (contents.get (i).equals (s)) {
                return true;
            }
        }
        return false;
    }

}

Question 1 (10 points)

What are the three components of the Java concurrent programming model?

Give a one- or two-sentence description of each component.

Question 2 (20 points)

Consider the following program:

	Strings test1 = Strings.none;
	Strings test2 = test1.append ("hello").append ("world");
	Strings test3 = test2.append (test2);
	for (int i=0; i<test3.size (); i++) {
	    System.out.println (test3.get (i));
	}

a) What is printed by this program?

b) Draw an object diagram for the objects created by this program.

c) Draw a class diagram for the Strings interface and all of its subclasses, and for the UnsafeStringCollection class.

Question 2 continued

Question 3 (20 points)

Consider the following program:

	final UnsafeStringCollection coll = new UnsafeStringCollection ();
	Thread thread1 = new Thread () { public void run () {
	    coll.add ("Wilma");
	    if (coll.contains ("Wilma")) {
		System.out.println ("YES!");
	    } else {
		System.out.println ("NO!");
	    }
	}};
	Thread thread2 = new Thread () { public void run () {
	    coll.add ("Fred");
	}};
	thread1.start ();
	thread2.start ();

a) What should be printed out by this program in a thread-safe execution?

b) Show that UnsafeStringCollection is not thread-safe, by describing an unsafe execution of this program where NO is printed out.

Question 3 continued

Question 4 (20 points)

One way to build a thread-safe StringCollection class is as follows:

public class MaybeSafeStringCollection {

    final UnsafeStringCollection contents = new UnsafeStringCollection ();
    final Object lock = new Object ();
    
    public void add (String s) { synchronized (lock) { contents.add (s); } }
    public boolean contains (String s) { synchronized (lock) { return contents.contains (s); } }

}

a) Does the contents field escape from the MaybeSafeStringCollection class? If so, why? If not, why not?

b) Is the MaybeSafeStringCollection class thread-safe? If so, why? If not, why not?

c) What is an aggregate?

d) Explain how aggregates can be used in reducing the number of locks required in a thread-safe program.

Question 4 continued

Question 5 (10 points)

Are the Strings interface and its subclasses thread-safe? If so, why? If not, why not?

Question 6 (20 points)

a) What is deadlock?

b) What is the dining philosophers problem?

c) Explain how the dining philosophers problem can exhibit deadlock.

d) Explain how resource ordering can be used to avoid deadlock in the Dining Philosophers.

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

Worksheet

You can use this sheet as scrap paper.