Name:

SE552 final exam: Winter 2000-2001

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Dictionaries

Some questions will refer to an ImmutableDictionary interface and a MutableDictionary interface. They are defined:

public interface ImmutableDictionary {

    public Object lookup (Object key);
    public ImmutableDictionary add (Object key, Object value);
    public int size ();
    public Iterator keys ();
    
    public static final ImmutableDictionary empty = new Empty ();

}

abstract class DictImpl implements ImmutableDictionary {
    
    public ImmutableDictionary add (Object key, Object value) {
        return new Node (key, value, this);
    }

    public Iterator keys () {
        return new DictIterator (this);
    }

    protected abstract Object key ();
    
    protected abstract Object value ();
    
    protected abstract DictImpl rest ();        
    
}

class Empty extends DictImpl {

    public Object lookup (final Object key) { 
        throw new NoSuchElementException (); 
    }

    public int size () {
        return 0;
    }

    protected Object key () { throw new NoSuchElementException (); }
    
    protected Object value () { throw new NoSuchElementException (); }
    
    protected DictImpl rest () { throw new NoSuchElementException (); }
    
}

Dictionaries cont.

class Node extends DictImpl {

    protected final Object key;
    protected final Object value;
    protected final DictImpl rest;
    protected final int size;

    Node (final Object key, final Object value, final DictImpl rest) {
        this.key = key; this.value = value; this.rest = rest;
        this.size = rest.size () + 1;
    }


    public Object lookup (final Object key) { 
        if (this.key.equals (key)) {
            return value; 
        } else {
            return rest.lookup (key);
        }
    }

    public int size () {
        return size;
    }

    protected Object key () { return key; }
    
    protected Object value () { return value; }
    
    protected DictImpl rest () { return rest; }
    
}

class DictIterator implements Iterator {

    protected DictImpl contents;

    DictIterator (final DictImpl contents) {
        this.contents = contents;
    }

    public boolean hasNext () {
        return this.contents.size () > 0;
    }

    public Object next () {
        final Object result = contents.key ();
        contents = contents.rest ();
        return result;
    }

    public void remove () { throw new UnsupportedOperationException (); }

}

Dictionaries cont.

public interface MutableDictionary {

    public Object lookup (Object key);
    public void add (Object key, Object value);
    public int size ();
    public Iterator keys ();
    
    public static final MutableDictionaryFactory factory = new MutableDictionaryFactoryImpl ();

}

interface MutableDictionaryFactory {
    
    public MutableDictionary build ();

}

class MutableDictionaryFactoryImpl implements MutableDictionaryFactory {

    public MutableDictionary build () { 
        return new MutableDictionaryImpl ();
    }

}

class MutableDictionaryImpl implements MutableDictionary {

    protected ImmutableDictionary contents = ImmutableDictionary.empty;

    public Object lookup (Object key) { return contents.lookup (key); }
    public void add (Object key, Object value) { contents = contents.add (key, value); }
    public int size () { return contents.size (); }
    
    
}

Question 1 (5 points)

a) Three failure modes for concurrent programs are baulking, guarding and timeout. Explain each of these.

b) Two possible strategies for ensuring thread-safety are optimistic and pessimistic. Explain each of these.

Question 2 (20 points)

The MutableDictionary class is not thread-safe. Make it thread safe, by providing a pessimistic, guarding implementation:

public interface GuardingDictionary extends MutableDictionary {

    // This method should block if the key is not in the dictionary
    public Object lookupGuarding (Object key) throws InterruptedException;

    public static final GuardingDictionaryFactory factory = new GuardingDictionaryFactoryImpl ();

}

interface GuardingDictionaryFactory {

    public GuardingDictionary build ();

}

class GuardingDictionaryFactoryImpl implements GuardingDictionaryFactory {

    public GuardingDictionary build () { 
        return new GuardingDictionaryImpl ();
    }

}

class GuardingDictionaryImpl implements GuardingDictionary {

    protected ImmutableDictionary contents = ImmutableDictionary.empty;
    // Your code goes here...

Question 2 continued

Question 3 (20 points)

The MutableDictionary class is not thread-safe. Make it thread safe, by providing a optimistic, baulking implementation:

import java.util.Iterator;

public interface OptimisticDictionary extends MutableDictionary {

    public static final OptimisticDictionaryFactory factory = new OptimisticDictionaryFactoryImpl ();

}

interface OptimisticDictionaryFactory {

    public OptimisticDictionary build ();

}

class OptimisticDictionaryFactoryImpl implements OptimisticDictionaryFactory {

    public OptimisticDictionary build () { 
        return new OptimisticDictionaryImpl ();
    }

}

class OptimisticDictionaryImpl implements OptimisticDictionary {

    // Your code goes here

Question 3 continued

Question 4 (15 points)

a) What is an IVar?

b) What is deferred synchronous invocation?

c) Explain how IVars (or futures) can be use to implement deferred synchronous invocation.

Question 4 continued

Question 5 (15 points)

Complete the following implementation of an IVar:

  public interface Channel {
    public void put (Object x) throws InterruptedException;
    public Object get () throws InterruptedException;
  }
  class IVar implements Channel {
    protected final Object lock = new Object ();
    protected Object contents = null;

Question 6 (15 points)

a) What is a worker pool?

b) Give two reasons why a program might use a worker pool, rather than creating new threads directly.

c) Give an outline of how a worker pool can be implemented.

Question 7 (10 points)

a) What is polling I/O?

b) What is blocking I/O?

c) Explain why, under normal circumstances, blocking I/O is preferable to polling I/O.

d) Explain why, under special circumstances, polling I/O may be preferable to blocking I/O.

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.