Name:

SE552 Example midterm exam

Answer all questions.

Time allowed: 2 hours

Total number of points: 100


Hash tables

Some questions will refer to a SimpleHashTable class. It is defined:

  public class SimpleHashTable {

    private Object[] keys = new Object[2];
    private Object[] values = new Object[2];

    public void add (Object key, Object value) {
      int hash = key.hashCode () % keys.length;
      if (keys[hash] == null) {
        keys[hash] = key;
        values[hash] = value;
      } else if (keys[hash].equals (key)) {
        values[hash] = value;
      } else {
        grow ();
        add (key, value);
      }
    }

    public Object get (Object key) {
      int hash = key.hashCode () % keys.length;
      if (keys[hash] != null && keys[hash].equals (key)) {
        return values[hash];
      } else {
        throw new NoSuchElementException ();
      }
    }

    private void grow () {
      Object[] newKeys = new Object[keys.length * 2 - 1];
      Object[] newValues = new Object[newKeys.length];
      for (int i=0; i<keys.length; i++) {
        if (keys[i] != null) {
          int hash = keys[i].hashCode () % newKeys.length;
          newKeys [hash] = keys[i];
          newValues [hash] = values[i];
        }
      }
      keys = newKeys;
      values = newValues;
    }

  }

Question 1 (5 points)

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


Question 2 (5 points)

What is the difference between a thread, a process and a processor?


Question 3 (15 points)

Consider the following code:

  SimpleHashTable example = new SimpleHashTable ();
  example.add ("one", "fred");
  example.add ("three", "wilma");
  System.out.println (example.get ("one"));

a) What is printed by this code?

b) What is the size of example.keys after executing this code?

c) What is the contents of example.keys after executing this code?

For the purpose of these questions, you can assume that the hash code of "one" is 1, the hash code of "two" is 2 and so on.


Question 4 (15 points)

Consider the following code:

  SimpleHashTable example = new SimpleHashTable ();
  Thread t1 = new Thread () { public void run () { example.add ("one", "fred"); } };
  Thread t2 = new Thread () { public void run () { example.add ("three", "wilma"); } };
  t1.start (); t2.start ();
  t1.join (); t2.join ();
  System.out.println (example.get ("one"));

Explain how it is possible for this code to print the result "wilma":


Question 4 (15 points)

Write a subclass of SimpleHashTable which uses synchronization in order to make the class safe for use in a concurrent setting.


Question 5 (10 points)

a) What is the difference between a safety property and a liveness property?

b) Give an example safety property, and an example liveness property.


Question 6 (5 points)

a) What is an immutable class?

b) Why are immutable classes useful in concurrent programming?


Question 7 (15 points)

Consider the following program:

  class Foo { int a = 0; }
  Foo foo = null;
  Thread t1 = new Thread () { public void run () {
    Foo bar = new Foo (); bar.a = 1; foo = bar;
  } };
  Thread t2 = new Thread () { public void run () {
    if (foo != null) {
      System.out.println ("foo.a = " + foo.a);
    }
  } }
  t1.start ();
  t2.start ();

a) What is SMP?

b) Briefly explain the SMP memory model (your answer should mention processors, cache and main memory).

c) Explain why the SMP memory model makes it possible for the above program to print "foo.a = 0".


Question 8 (15 points)

Consider the interface:

  public interface Pointless { 
    public int get (); // should always return 0 
    public void inc (); 
  } 

For each of the following programs, say:

a) Whether delegate escapes from class Outer or not.

b) Whether get and inc have to be synchronized in class Inner or not.

1.

  public class Outer {
    public final Pointless delegate = new Inner ();
    public synchronized int get () { return delegate.get (); }
    public synchronized void inc () { delegate.inc (); }
  }
  class Inner implements Pointless {
    int a; int b; // Invariant: a == b
    public synchronized int get () { return a-b; }
    public synchronized void inc () { a++; b++; }
  }

2.

  public class Outer {
    protected final Pointless delegate = new Inner ();
    public synchronized int get () { return delegate.get (); }
    public synchronized void inc () { delegate.inc (); }
  }
  class Inner implements Pointless {
    int a; int b; // Invariant: a == b
    public synchronized int get () { return a-b; }
    public synchronized void inc () { a++; b++; }
  }

Question 8 cont.

3.

  public class Outer {
    protected final Pointless delegate = new Inner ();
    public synchronized Pointless get () { return delegate; }
  }
  class Inner implements Pointless {
    int a; int b; // Invariant: a == b
    public synchronized int get () { return a-b; }
    public synchronized void inc () { a++; b++; }
  }

4.

  public class Outer {
    protected final Pointless delegate = new Inner ();
    public synchronized Pointless get (Callback c) { c.do (delegate); }
  }
  class Inner implements Pointless {
    int a; int b; // Invariant: a == b
    public synchronized int get () { return a-b; }
    public synchronized void inc () { a++; b++; }
  }

5.

  public class Outer {
    protected final Pointless delegate = new Inner ();
    public synchronized Pointless get (Callback c) { c.do (delegate.get ()); }
  }
  class Inner implements Pointless {
    int a; int b; // Invariant: a == b
    public synchronized int get () { return a-b; }
    public synchronized void inc () { a++; b++; }
  }