RE: JavaMemoryModel: Semantics of locks and volatiles

From: Sarita Adve (sadve@cs.uiuc.edu)
Date: Fri Jun 29 2001 - 17:53:32 EDT


> -----Original Message-----
> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu]On Behalf Of Bill Pugh
> Sent: Wednesday, June 27, 2001 8:59 PM
> To: javamemorymodel@cs.umd.edu
> Subject: JavaMemoryModel: Semantics of locks and volatiles
>
>
> The basic informal proposal for the semantics of locks and volatiles
> is release consistency, as well documented in a number of technical
> papers. Sarita or others can probably correct all the subtleties I am
> going to get wrong, but basically:

A couple of points:

First, the semantics are similar to, but weaker than, release consistency.
Here is an example of why they are weaker:

Initially all variables are 0
Thread 1
A = 1
Volatile1 = 2
tmp1 = Volatile2
B = 1

Thread 2
while (B != 1) {;}
Volatile3 = 3
tmp2 = Volatile4
tmp3 = A

Release consistency requires tmp3 to be 1 (assuming volatiles are SC). This
requirement implies that the following optimization isn't allowed.

> * volatile variables accessed from only a single thread can be
> treated as normal variables.

By this optimization, all four volatile variables above could be
eliminated/reordered, and tmp3 could return 0.

For similar reason, I suggest we avoid defining the semantics in terms of
"per-process" orderings that are imposed. Instead, we should define them in
terms similar to the happens-before terminology Bill used earlier. Then when
we want to interpret the semantics in terms of optimizations allowed, I
suggest we discuss safe reorderings rather than restricted orderings. More
concretely, I would like to suggest avoiding statements such as:

> The release/acquire semantics of volatiles and locks imposed the
> following orderings between volatile and monitor actions
>
> volatile read, followed by anything
> monitor enter, followed by anything
> anything followed by a volatile write
> anything followed by a monitor exit
>
> I think it should also be possible to implement Dekker's (sp?)
> algorithm using volatiles. That prohibits reordering:
>
> volatile write followed by a volatile read

The above statements imply that in the earlier example, tmp3 should have 1.
And so the local volatile variable optimization is restricted.

In other words, I suggest using statements such as:
The semantics imply the following [...] reorderings are allowed.

>
> * volatile writes and monitor exits are treated as
> synchronization releases.
>
> * volatile reads and monitor enters are treated as
> synchronization acquires.
>
> A synchronization release action and _a matching_ synchronization
> acquire action establish a "happens before" relationship between the
> two threads. Program order within a thread also establishes a happens
> before relationship, and "happens before" is transitive.
>
> If two threads access the same normal field or array element, and one
> of those accesses is a write, the accesses conflict. For any two
> conflicting accesses, there should be a "happens before" relationship
> between the two accesses. If all sequentially consistent executions
> of a program are correctly synchronized (i.e., all conflicting
> accesses are ordered), then the program is correctly synchronized and
> follows sequentially consistent semantics.

The above does not say anything about the ordering of volatiles and monitors
among themselves. The happens-before relation needs to be modified for that.
But I'll wait on that until we are decided on informal semantics of these
accesses.

Sarita

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:32 EDT