17.10 Example: Possible Swap

Consider a class that has class variables a and b and methods hither and yon: 


class Sample {
	int a = 1, b = 2;
	void hither() {
		a = b;
	}
	void yon() {
		b = a;
	}
}

Now suppose that two threads are created, and that one thread calls hither while the other thread calls yon. What is the required set of actions and what are the ordering constraints?

Let us consider the thread that calls hither. According to the rules, this thread must perform an use of b followed by an assign of a. That is the bare minimum required to execute a call to the method hither.

Now, the first action on variable b by the thread cannot be use. But it may be assign or load. An assign to b cannot occur because the program text does not call for such an assign action, so a load of b is required. This load action by the thread in turn requires a preceding read action for b by the main memory.

The thread may optionally store the value of a after the assign has occurred. If it does, then the store action in turn requires a following write action for a by the main memory.

The situation for the thread that calls yon is similar, but with the roles of a and b exchanged.

The total set of actions may be pictured as follows:

Here an arrow from action A to action B indicates that A must precede B.

In what order may the actions by the main memory occur? The only constraint is that it is not possible both for the write of a to precede the read of a and for the write of b to precede the read of b, because the causality arrows in the diagram would form a loop so that an action would have to precede itself, which is not allowed. Assuming that the optional store and write actions are to occur, there are three possible orderings in which the main memory might legitimately perform its actions. Let ha and hb be the working copies of a and b for the hither thread, let ya and yb be the working copies for the yon thread, and let ma and mb be the master copies in main memory. Initially ma=1 and mb=2. Then the three possible orderings of actions and the resulting states are as follows:

Thus the net result might be that, in main memory, b is copied into a, a is copied into b, or the values of a and b are swapped; moreover, the working copies of the variables might or might not agree. It would be incorrect, of course, to assume that any one of these outcomes is more likely than another. This is one place in which the behavior of a Java program is necessarily timing-dependent.

Of course, an implementation might also choose not to perform the store and write actions, or only one of the two pairs, leading to yet other possible results.

Now suppose that we modify the example to use synchronized methods:


class SynchSample {
	int a = 1, b = 2;
	synchronized void hither() {
		a = b;
	}
	synchronized void yon() {
		b = a;
	}
}

Let us again consider the thread that calls hither. According to the rules, this thread must perform a lock action (on the class object for class SynchSample) before the body of method hither is executed. This is followed by a use of b and then an assign of a. Finally, an unlock action on the class object must be performed after the body of method hither completes. That is the bare minimum required to execute a call to the method hither.

As before, a load of b is required, which in turn requires a preceding read action for b by the main memory. Because the load follows the lock action, the corresponding read must also follow the lock action.

Because an unlock action follows the assign of a, a store action on a is mandatory, which in turn requires a following write action for a by the main memory. The write must precede the unlock action.

The situation for the thread that calls yon is similar, but with the roles of a and b exchanged.

The total set of actions may be pictured as follows:

The lock and unlock actions provide further constraints on the order of actions by the main memory; the lock action by one thread cannot occur between the lock and unlock actions of the other thread. Moreover, the unlock actions require that the store and write actions occur. It follows that only two sequences are possible:

While the resulting state is timing-dependent, it can be seen that the two threads will necessarily agree on the values of a and b.