> Perhaps a better way to capture the main case I've been hitting on is
> to resurrect the idea of "scoped volatile": This applies in cases
> where you cannot have a lock (for the sake of liveness), or do not
> want one (for the sake of performance), and you can live with looser
> coupling among threads, yet do need the memory effects associated with
> synchronization in order to bound otherwise infinitely stale reads or
> infinitely unflushed writes. My first idea about this (long ago) was a
> syntactic extension:
A bound on infinitely stale reads and infinitely unflushed writes
would not be too hard to define into the semantics without the need
for any syntax changes. The simplest example of the problem comes up
with the following example:
initially, quit = false
Thread 1: Thread 2:
quit = true; while (!quit) do_something();
exit();
Under all of the current proposed semantics, thread 2 might loop
forever. The problem occurs because there is no guarantee that the
write by thread 1 is EVER seen by thread 2. I'd like to propose the
following semantics that will handle this problem:
For every write action W to a variable V, no thread can perform an
infinite number of reads from V, all of which return a value from
some write before W (for some definition of "before").
If we assume coherence, then defining "before" is easy, because we
only need to define "before" on a per-variable basis, and writes to a
single variable are totally ordered. Defining "before" can be a bit
more tricky without coherence, but models like LC and Bill Pugh's
strawman model have a roughly equivalent notion.
For the given example, the write "quit = false" is before "quit =
true", so thread 2 cannot read the false value indefinitely.
As far as I know, all SMP platforms have this property. It is
possible that some DSMs violate it, but it probably wouldn't be too
hard a property to add, by flushing caches periodically, for example.
The implications of this property for the compiler are a bit more
interesting. Reads can in general be reordered and coalesced as
before, but the compiler must be sure to leave at least one read for
each variable in every potentially infinite path through the code
(both unbounded loops and recursion). Writes can be reordered and
coalesced as well, but they cannot be postponed indefinitely, so they
can't be moved after a potentially infinite loop, recursion, or a lock
acquire.
Of all of these constraints, the only one that worries me is the fact
that at least one read must be left in each potentially unbounded
loop. This restriction means that some code hosting opportunities
might me missed. Not a huge deal, but enough that we might want to
think about how important it is to have this property.
-Keith
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:23 EDT