JavaMemoryModel: Ordering of volatile and monitor actions

From: Bill Pugh (pugh@cs.umd.edu)
Date: Wed Jun 27 2001 - 22:01:02 EDT


Once again, please correct me if I get any of this wrong:

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

In other words, all volatile/monitor pairs except for:
        volatile write followed by a monitor enter
        monitor exit followed by a monitor enter
        volatile write followed by a volatile read
        monitor exit followed by a volatile read

You can get deadlock if you allow the following re-orderings:

        volatile write followed by a monitor enter
        monitor exit followed by a monitor enter

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

We haven't yet seen any examples where you get into trouble by
allowing the reordering of:

        monitor exit followed by a volatile read

However, to keep the semantics symmetric, I think we should prohibit
any _observable_ reordering of a monitor exit followed by a volatile
read.

This translates into a requirement that all lock and volatile actions
should observe a sequentially consistent order (or possibly a
processor ordering).

One issue still being considered is whether the ordering should be SC
(sequentially consistent) or PO (processor ordering).

At 7:33 AM -0800 11/21/00, Hudson, Rick wrote:
>The difference of interest between SC and PO is that if two processors
>perform multiple writes then all processors will observe the writes of each
>of these processors in the order written (just as with SC) but the
>interleaving of the writes may appear different to different processors.

Note that it is impossible to observe the difference between SC and
PO in any scenario involving only two threads/processors. You can
only see the difference in scenarios involving three or more
processors, at least two of whom are writing.

Comments?

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