Name:

SE552 midterm exam: Winter 2000-2001

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Token Pools

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

public interface TokenPool {

    public Token buildToken ();
    public Token getToken () throws InterruptedException;
    public void returnToken (Token t);
    public static final TokenPoolFactory factory = new TokenPoolFactoryImpl ();

}

interface Token { }

interface TokenPoolFactory { public TokenPool build (); }

class TokenImpl implements Token {

    protected final int tokenNum;

    TokenImpl (final int tokenNum) { this.tokenNum = tokenNum; }

    public String toString () { return "Token " + tokenNum; }

}

class TokenPoolFactoryImpl implements TokenPoolFactory {

    public TokenPool build () { return new TokenPoolImpl (); }

}

class TokenPoolImpl implements TokenPool {

    protected final Stack contents = Stack.factory.build ();
    protected final Object lock = new Object ();
    protected int numTokens = 0;

    public Token buildToken () { return new TokenImpl (++numTokens); }

    public Token getToken () throws InterruptedException {
        if (contents.size () == 0) { 
            synchronized (lock) { lock.wait (); }
        }
        return (Token)(contents.pop ());
    }

    public void returnToken (final Token t) {
        contents.push (t);
        synchronized (lock) { lock.notifyAll (); }
    }
    
}

Stacks

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

public interface Stack {

    public void push (Object element);
    public Object pop ();
    public int size ();

    public final static StackFactory factory = new StackFactoryImpl ();

}

public interface StackFactory {

    public Stack build ();

}

class StackFactoryImpl implements StackFactory {

    public Stack build () { return new StackImpl (); }

}

class StackImpl implements Stack {

    protected List contents = List.empty;

    public void push (final Object element) {
        contents = contents.cons (element);
    }

    public Object pop () {
        final Object result = contents.head ();
        contents = contents.tail ();
        return result;
    }

    public int size () {
        return contents.size ();
    }

}

Lists

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

interface List {

    public Object head ();
    public List tail ();
    public int size ();
    public List cons (Object hd);

    public static final List empty = new ListEmpty ();

}

class ListEmpty implements List {

    public Object head () { throw new NoSuchElementException (); }
    public List tail () { throw new NoSuchElementException (); }
    public int size () { return 0; }
    public List cons (final Object hd) { return new ListCons (hd, this); }

}

class ListCons implements List {

    final Object hd; final List tl; final int size;

    ListCons (final Object hd, final List tl) {
        this.hd = hd; this.tl = tl; this.size = tl.size () + 1;
    }

    public Object head () { return hd; }
    public List tail () { return tl; }
    public int size () { return size; }
    public List cons (final Object hd) { return new ListCons (hd, this); }

}

Question 1 (5 points)

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

Question 2 (10 points)

Consider the following program:

        final TokenPool pool = TokenPool.factory.build ();
        final Token a = pool.buildToken ();
        System.out.println ("a = " + a);
        pool.returnToken (a);
        final Token b = pool.getToken ();
        System.out.println ("b = " + b);
        pool.returnToken (b);
        final Token c = pool.getToken ();
        System.out.println ("c = " + c);
        pool.returnToken (c);

What is printed by this program?

Question 3 (20 points)

Consider the following program:

        final TokenPool pool = TokenPool.factory.build ();
        final Thread threadA = new Thread (new Runnable () { public void run () {
            final Token a = pool.buildToken ();
            System.out.println ("a = " + a);
            pool.returnToken (a);
        } } );
        final Thread threadB = new Thread (new Runnable () { public void run () {
            try {
                final Token b = pool.getToken ();
                System.out.println ("b = " + b);
                pool.returnToken (b);
            } catch (final InterruptedException ex) {
            }
        } } );
        final Thread threadC = new Thread (new Runnable () { public void run () {
            try {
                final Token c = pool.getToken ();
                System.out.println ("c = " + c);
                pool.returnToken (c);
            } catch (final InterruptedException ex) {
            }
        } } );
        threadA.start ();
        threadB.start ();
        threadC.start ();

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

b) Show that TokenPool is not thread-safe, by describing an unsafe execution of this program.

Question 3 continued

Question 4 (20 points)

Describe four changes which need to be made to the TokenPoolImpl class in order to make it thread-safe. In each case, give a one-sentence description of why the change is necessary.

class TokenPoolImpl implements TokenPool {


    protected final Stack contents = Stack.factory.build ();


    protected final Object lock = new Object ();


    protected int numTokens = 0;


    public Token buildToken () { return new TokenImpl (++numTokens); }


    public Token getToken () throws InterruptedException {


        if (contents.size () == 0) { 


            synchronized (lock) { lock.wait (); }


        }


        return (Token)(contents.pop ());


    }


    public void returnToken (final Token t) {


        contents.push (t);


        synchronized (lock) { lock.notifyAll (); }


    }

    
}

Question 4 continued

Question 5 (15 points)

a) Is the Stack class thread-safe? If so, why? If not, why not?

b) Does the contents field escape from the TokenPoolImpl class? If so, why? If not, why not?

c) Does the Stack class need to be thread-safe in order for TokenPoolImpl to be thread safe? If so, why? If not, why not?

Question 5 continued

Question 6 (10 points)

Is the List class thread-safe? If so, why? If not, why not?

Question 7 (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 the TokenPool can be used to avoid deadlock in the Dining Philosophers.

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.