# Name:

SE552 midterm exam: Winter 2002-2003

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 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);
p.move (2, 3);
}};
System.out.println ("Distance between p and p = " + p.distance (p));
}};
```

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

// SOME CODE GOES HERE

}};
// SOME CODE GOES HERE

}};
}
}
```

### 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).

### Worksheet

You can use this sheet as scrap paper.

### Worksheet

You can use this sheet as scrap paper.