RE: JavaMemoryModel: Ordering of volatile and monitor actions

From: Sarita Adve (
Date: Fri Jun 29 2001 - 18:31:33 EDT

> -----Original Message-----
> From:
> []On Behalf Of Bill Pugh
> Sent: Wednesday, June 27, 2001 9:01 PM
> To:
> Subject: JavaMemoryModel: Ordering of volatile and monitor actions
> 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

Yes, this is safe with finite number of reads.

(Some others are also safe due to special semantics of monitors, but may not
be useful; e.g., monitor exit --> volatile write.)

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

Not sure what this means. Any "observable" reordering should be prohibited.
The problem is that when we go down the path of these "system-centric"
semantics, we have to explicitly identify what's observable.

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

Bill asked me to comment on PO vs. SC for volatiles/locks and define PO. It
seems that PO is the name given to Intel's x86 model. It isn't well-defined,
so I won't try to define it here. There are other formally defined models in
the same class, so I'll use those. These are: IBM 370, SPARC TSO, and
Stanford processor consistency. These models all allow reordering of
write --> read, and differ in ways in which they preserve write atomicity.
The December'96 tutorial in Computer describes these differences. All of
these models break Dekker's algorithm due to the write --> read
optimization. The Computer paper also shows codes broken due to atomicity.
(I think the issue that Rick Hudson raised above concerns atomicity.)

To my knowledge, the codes broken by these models aren't commonly used.
Nevertheless, my opinion is that volatiles and monitors should have SC
semantics. The main reason is that it should be possible for anyone to write
any sequence of instructions and get SC results easily (i.e., by declaring
all as volatile); e.g., in less performance critical parts of the code where
you don't want to spend much time dealing with the memory model. If
volatiles are not SC, then there is no such "safety net" to rely on.

If people feel strongly about using PC/TSO instead, I can elaborate more on
those models if needed.


JavaMemoryModel mailing list -

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