Name:

SE552 midterm exam: Winter 2002-2003

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Mutable Points

Some questions will refer to an MPoint interface and an MPointImpl class. They are defined here:

interface MPoint {

    public double getX ();
    public double getY ();
    public double distance (MPoint other);
    public void move (double dX, double dY);
    public static final MPointFactory factory = new MPointFactoryImpl ();

}

interface MPointFactory {

    public MPoint build (double x, double y);

}

class MPointFactoryImpl implements MPointFactory {

    public MPoint build (double x, double y) { return new MPointImpl (x, y); }

}

class MPointImpl implements MPoint {

    double x; 
    double y;
    MPointImpl (double x, double y) { this.x = x; this.y = y; }

    public double getX () { return this.x; }
    public double getY () { return this.y; }
    public double distance (MPoint other) {
        double dX = this.x - other.getX (); double dY = this.y - other.getY (); return Math.sqrt (dX*dX + dY*dY);
    }
    public void move (double dX, double dY) {
        this.x = this.x + dX; this.y = this.y + dY;
    }

}

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

Consider the following program:

	MPoint p = MPoint.factory.build (0, 0); p.move (2, 3);
	MPoint q = MPoint.factory.build (0, 0); q.move (5, 7);
	System.out.println ("Distance between p and q = " + p.distance (q));
	System.out.println ("Distance between p and p = " + p.distance (p));

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 MPoint interface and all of its associated classes.

Question 2 continued

Question 3 (10 points)

The distance between a point p and itself should always be zero, so we expect p.distance (p) to always return 0.0.

Consider the following program:

        final MPoint p = MPoint.factory.build (0, 0);
        Thread thread1 = new Thread () { public void run () {
            p.move (2, 3);
        }};
        Thread thread2 = new Thread () { public void run () {
   	    System.out.println ("Distance between p and p = " + p.distance (p));
        }};
        thread1.start ();
        thread2.start ();

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

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

Question 3 continued

Question 4 (15 points)

One way to make the point classes thread-safe is to make them immutable.

What changes need to be made to the following code for MPoint to produce an immutable IPoint version?

interface IPoint {

    public double getX ();

    public double getY ();

    public double distance (IPoint other);

    public void move (double dX, double dY);

    public static final IPointFactory factory = new IPointFactoryImpl ();

}
interface IPointFactory {

    public IPoint build (double x, double y);

}
class IPointFactoryImpl implements IPointFactory {

    public IPoint build (double x, double y) { return new IPointImpl (x, y); }

}
class IPointImpl implements IPoint {

    double x; 

    double y;

    IPointImpl (double x, double y) { this.x = x; this.y = y; }


    public double getX () { return this.x; }


    public double getY () { return this.y; }


    public double distance (IPoint other) {

        double dX = this.x - other.getX (); double dY = this.y - other.getY (); return Math.sqrt (dX*dX + dY*dY);

    }


    public void move (double dX, double dY) {

        this.x = this.x + dX; this.y = this.y + dY;

    }

}

Question 4 continued

Question 5 (15 points)

An alternate strategy for making mutable points thread-safe is to add locks:

Complete the following thread-safe implementation of mutable locks by indicating which methods need synchronization. In each case give a one- or two-sentence justification for your answer.

interface MPoint {

    public double getX ();
    public double getY ();
    public double distance (MPoint other);
    public void move (double dX, double dY);
    public static final MPointFactory factory = new MPointFactoryImpl ();

}
interface MPointFactory {

    public MPoint build (double x, double y);

}
class MPointFactoryImpl implements MPointFactory {

    public MPoint build (double x, double y) { return new MPointImpl (x, y); }

}
class MPointImpl implements MPoint {

    double x; 
    double y;
    final Object lock = new Object ();
    MPointImpl (double x, double y) { this.x = x; this.y = y; }

    public double getX () { 
        synchronized (lock) {  // a) NECESSARY?
            return this.x; 
        }
    }
    public double getY () { 
        synchronized (lock) {  // b) NECESSARY?
            return this.y; 
        }
    }
    public double distance (MPoint other) {
        Object otherLock = ((MPointImpl)other).lock;
        synchronized (lock) {  // c) NECESSARY?
            synchronized (otherLock) {  // d) NECESSARY?
                double dX = this.x - other.getX (); double dY = this.y - other.getY (); return Math.sqrt (dX*dX + dY*dY);
            }
        }
    }
    public void move (double dX, double dY) {
        synchronized (lock) {  // e) NECESSARY?
            this.x = this.x + dX; this.y = this.y + dY;
        }
    }

}

Question 5 continued

Question 6 (15 points)

Consider the distance method from the previous question:

    public double distance (MPoint other) {
        Object otherLock = ((MPointImpl)other).lock;
        synchronized (lock) {
            synchronized (otherLock) {
                double dX = this.x - other.getX (); double dY = this.y - other.getY (); return Math.sqrt (dX*dX + dY*dY);
            }
        }
    }

a) Show that this implementation of mutable points suffers from deadlock by completing the following program which can deadlock:

class CanDeadlock {
    public static void main (String args[]) {
        // SOME CODE GOES HERE









        Thread thread1 = new Thread () { public void run () {
            // SOME CODE GOES HERE









        }};
        Thread thread2 = new Thread () { public void run () {
            // SOME CODE GOES HERE









        }};
        thread1.start ();
        thread2.start ();
    }
}

Question 6 continued

b) Give a one-paragraph description of why your program deadlocks.

Question 7 (25 points)

a) Give a one-paragraph description of the resource ordering solution to deadlock.

b) Give a one-paragraph description of the token pool solution to deadlock.

c) Give one advantage and one disadvantage of resource ordering compared to token pools.

d) In the case of the distance method from the previous question, is resource ordering or a token pool a more appropriate solution?

e) Give a one-paragraph outline of how you would implement your proposed solution (you do not need to supply Java code, just an English description).

Question 7 continued

Question 7 continued

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.