Name:

SE552 midterm exam: Autumn 2002-2003

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Doubly-linked lists

Some questions will refer to a DLList interface and a DLListImpl class. They are defined here:

public interface DLList {

    public void pushFront (Object x);
    public void pushBack (Object x);
    public Object popFront ();
    public Object popBack ();
    public Iterator iterator ();

}

class DLListImpl implements DLList {

    Cell front = null;
    Cell back = null;

    public void pushFront (Object x) {
        this.front = new Cell (null, x, this.front);
        if (this.back == null) { this.back = this.front; }
	else { this.front.next.prev = this.front; }
    }
    
    public void pushBack (Object x) {
        this.back = new Cell (this.back, x, null);
        if (this.front == null) { this.front = this.back; }
	else { this.back.prev.next = this.back; }
    }
    
    public Object popFront () {
        if (this.front == null) { throw new NoSuchElementException (); }
        Object result = this.front.contents;
        this.front = this.front.next;
        if (this.front == null) { this.back = null; }
        else { this.front.prev = null; }
        return result;
    }

    public Object popBack () {
        if (this.back == null) { throw new NoSuchElementException (); }
        Object result = this.back.contents;
        this.back = this.back.prev;
        if (this.back == null) { this.front = null; }
        else { this.back.next = null; }
        return result;
    }

    public Iterator iterator () { return new DLListIterator (this, this.front); }

}

Doubly-linked lists continued

class Cell {

    Cell prev;
    Object contents;
    Cell next;

    Cell (Cell prev, Object contents, Cell next) {
        this.prev = prev; this.contents = contents; this.next = next;
    }

}

class DLListIterator implements Iterator {

    DLListImpl list;
    Cell cell;
    
    DLListIterator (DLListImpl list, Cell cell) {
        this.list = list; this.cell = cell;
    }

    public boolean hasNext () { 
        return this.cell != null; 
    }

    public Object next () {
        Object result = this.cell.contents;
        this.cell = this.cell.next;
        return result;
    }

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

}

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 (15 points)

Consider the following program:

        DLList list = new DLListImpl ();
        list.pushFront ("fred");
        list.pushFront ("wilma");
        for (Iterator i=list.iterator (); i.hasNext ();) {
            System.out.println (i.next ());
        }

a) What is printed by this program?

b) Draw an object diagram for the objects created by this program (assume that none of them are garbage-collected).

c) Draw a class diagram for the DLList interface and all of its associated classes.

Question 2 continued

Question 3 (15 points)

Consider the following program:

        DLList list = new DLListImpl ();
        Thread thread1 = new Thread () { public void run () {
            list.pushFront ("fred");
            System.out.println (list.popFront ());
        }};
        Thread thread2 = new Thread () { public void run () {
            list.pushFront ("wilma");
            System.out.println (list.popFront ());
        }};
        thread1.start ();
        thread2.start ();

a) What should be printed out by this program in a thread-safe execution? (Hint: there are two possible printouts, you should give both.)

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

Question 3 continued

Question 4 (15 points)

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

public class SyncedDLListImpl extends DLListImpl {

    final Object lock = new Object ();
    
    public void pushFront (Object x) {
        synchronized (this.lock) { super.pushFront (x); }
    }
    
    public void pushBack (Object x) {
        synchronized (this.lock) { super.pushBack (x); }
    }
    
    public Object popFront () {
        synchronized (this.lock) { return super.popFront (); }
    }

    public Object popBack () {
        synchronized (this.lock) { return super.popBack (); }
    }

    public Iterator iterator () {
        synchronized (this.lock) { return super.iterator (); }
    }

}

a) Do the front and back fields escape from the SyncedDLListImpl class? If so, why? If not, why not?

b) Is the SyncedDLListImpl 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 (15 points)

a) What is an iterator?

b) What is a snapshot iterator?

c) What is a fast-fail iterator?

d) Why is a fast-fail iterator more appropriate than a snapshot iterator for the DLList classes?

Question 5 continued

Question 6 (15 points)

Complete the following implementation of a fast-fail iterator for the DLList classes. You should throw a ConcurrentModificationException in the fast-fail case.

public class FastFailDLListImpl extends DLListImpl {

    final Object lock = new Object ();
    int version = 0;
    
    public void pushFront (Object x) {
        synchronized (this.lock) { this.version++; super.pushFront (x); }
    }
    
    public void pushBack (Object x) {
        synchronized (this.lock) { this.version++; super.pushBack (x); }
    }
    
    public Object popFront () {
        synchronized (this.lock) { this.version++; return super.popFront (); }
    }

    public Object popBack () {
        synchronized (this.lock) { this.version++; return super.popBack (); }
    }

    public Iterator iterator () {
        synchronized (this.lock) { return new FastFailDLListIterator (this, this.front, this.version); }
    }

}

Question 6 continued

class FastFailDLListIterator implements Iterator {

    DLListImpl list;
    Cell cell;
    int version;
    
    DLListIterator (DLListImpl list, Cell cell, int version) {
        this.list = list; this.cell = cell; this.version = version;
    }

    public boolean hasNext () { 








        return this.cell != null; 








    }

    public Object next () {








        Object result = this.cell.contents;
        this.cell = this.cell.next;
        return result;








    }

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

}

Question 7 (15 points)

Consider a variant implementation of DLListImpl where every Cell object had its own lock, which was used to protect access to the fields:

class Cell {

    Cell prev;
    Object contents;
    Cell next;
    Object lock = new Object ();

    Cell (Cell prev, Object contents, Cell next) {
        this.prev = prev; this.contents = contents; this.next = next;
    }

}

For example, the code for popFront would become:

    
    public Object popFront () {
        if (this.front == null) { throw new NoSuchElementException (); }
        synchronized (this.front) {
            Object result = this.front.contents;
            this.front = this.front.next;
            if (this.front == null) { this.back = null; }
            else { synchronized (this.front) { this.front.prev = null; } }
            return result;
        }
    }

Explain how the above changes to DLListImpl can result in deadlock.

Hint: consider two threads, one which calls popFront and one which calls popBack simultaneously.

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