Name:

SE552 midterm exam: Autumn 2000-2001

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Bank Accounts

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

class BankAccount {

    protected TransactionList transactions = TransactionList.empty;
    protected int balance = 0;

    public int getBalance () { return balance; }

    public TransactionList getTransactions () { return transactions; }

    public void deposit (final int amount) {
        balance = balance + amount;
        transactions = transactions.cons (new Transaction (amount));
    }

    public void withdraw (final int amount) {
        balance = balance - amount;
        transactions = transactions.cons (new Transaction (-amount));
    }

    public String toString () {
        return "BankAccount ( balance = " + balance +", transactions = " + transactions + ")";
    }

}

class Transaction {

    protected final int amount;

    public Transaction (final int amount) { this.amount = amount; }

    public int getAmount () { return amount; }

    public String toString () { 
        if (amount > 0) {
            return "deposit " + amount;
        } else {
            return "withdraw " + (-amount);
        }
    }

}

Bank Accounts

The BankAccount class refers to a TransactionList interface. A partial implementation is:

interface TransactionList {

    // Return the head of the list
    public Transaction head ();

    // Return the tail of the list
    public TransactionList tail ();

    // Build a new list by adding hd onto the front of this list
    public TransactionList cons (Transaction hd);

    // Return the number of transactions in the list
    public int size ();

    // Return the total of all of the transaction amounts in the list
    public int total ();

    // An empty list
    public final static TransactionList empty = new Empty ();

}

class Empty implements TransactionList {

    public Transaction head () { throw new NoSuchElementException (); }
    public TransactionList tail () { throw new NoSuchElementException (); }
    public TransactionList cons (final Transaction hd) { return new Cons (hd, this); }
    public int size () { your code goes here }
    public int total () { your code goes here }
    public String toString () { return "empty"; }

}

class Cons implements TransactionList {

    protected final Transaction hd;
    protected final TransactionList tl;

    public Cons (final Transaction hd, final TransactionList tl) {
         this.hd = hd; this.tl = tl;
    }

    public Transaction head () { return hd; }
    public TransactionList tail () { return tl; }
    public TransactionList cons (final Transaction hd) { return new Cons (hd, this); }
    public int size () { your code goes here }
    public int total () { your code goes here }
    public String toString () { return "cons (" + hd + ", " + tl + ")"; }

}

Question 1 (5 points)

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

Question 2 (5 points)

What is the difference between concurrent programming, parallel programming, and distributed programming?

Question 3 (10 points)

Consider the following program:

        final BankAccount account = new BankAccount ();
        account.deposit (500);
        account.withdraw (300);
        account.withdraw (100);
        System.out.println (account);

What is printed by this program?

Question 4 (10 points)

Complete the TransactionList implementation by providing implementations for:

a) Empty.size ().

b) Empty.total ().

c) Cons.size ().

d) Cons.total ().

Question 5 (15 points)

a) What is an invariant?

b) Give one invariant which should hold for the BankAccount class.

c) Show that the following program can break your invariant:

        final BankAccount account = new BankAccount ();
        account.deposit (500);
        Thread t1 = new Thread () { public void run () { account.withdraw (300); } };
        Thread t2 = new Thread () { public void run () { account.withdraw (100); } };
        t1.start (); t2.start ();

Question 6 (15 points)

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

Question 7 (10 points)

Which of the following classes require synchronization? In each case, give a one-sentence justification for your answer.

a) BankAccount.

b) Transaction.

c) Empty.

d) Cons.

Question 8 (15 points)

a) What is deadlock?

b) What is the dining philosophers problem?

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

d) Outline one possible change to the dining philosophers which avoids deadlock.

Question 9 (15 points)

Consider the interface:

  public interface Counter {
    public void inc ();
    public int get ();
  }

For each of the following programs, say:

i) Whether delegate escapes from class Outer or not.

ii) Whether inc has to be synchronized in class Inner or not.

a)

  public class Outer {
    public final Counter delegate = new Inner ();
    public synchronized void inc () { delegate.inc (); }
    public synchronized int get () { return delegate.get (); }
  }
  class Inner implements Counter {
    int contents = 0;
    public void inc () { contents++; }
    public int get () { return contents; }
  }

b)

  public class Outer {
    protected final Counter delegate = new Inner ();
    public synchronized void inc () { delegate.inc (); }
    public synchronized int get () { return delegate.get (); }
  }
  class Inner implements Counter {
    int contents = 0;
    public void inc () { contents++; }
    public int get () { return contents; }
  }

Question 9 cont.

c)

  public class Outer {
    protected final Counter delegate = new Inner ();
    public synchronized void inc () { delegate.inc (); }
    public Counter get () { return delegate; }
  }
  class Inner implements Counter {
    int contents = 0;
    public void inc () { contents++; }
    public int get () { return contents; }
  }

d)

  public class Outer {
    protected final Counter delegate = new Inner (0);
    public synchronized void inc () { delegate.inc (); }
    public synchronized Counter get () { return delegate.getCounter (); }
  }
  class Inner implements Counter {
    int contents;
    Inner (int contents) { this.contents = contents; }
    Inner (Counter other) { this.contents = other.contents; }
    public void inc () { contents++; }
    public int get () { return contents; }
    public Counter getCounter () { return new Inner (this); }
  }

e)

  public class Outer {
    protected final Counter delegate = new Inner (0);
    public synchronized void inc () { delegate.inc (); }
    public synchronized Counter get () { return delegate.getCounter (); }
  }
  class Inner implements Counter {
    int contents;
    Inner (int contents) { this.contents = contents; }
    Inner (Counter other) { this.contents = other.contents; }
    public void inc () { contents++; }
    public int get () { return contents; }
    public Counter getCounter () { return this; }
  }

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.