Thanks, Victor.
And great questions. It is very encouraging that you have been able to get
to the point to ask these questions. Yes, I have spent most of my energy on
the read discontinuity, and you bring up good points about the write
discontinuity. I will spend some more thought on that. Meanwhile, both of
your examples are allowed at the moment, but here are some ways to change
that/issues to consider:
>
> 1. I assume that the model is intended to generalize to more than two
> competing writes: in that case, a subsequent read can return any of
> the values written by those writes. Is this true?
Correct.
> If so, how does
> this work for three writes, two of which compete with the third, but
> not with each other? For example,
>
> Initially, X == 0
>
> Thread 1 Thread 2
>
> X = 1 X = 2
> X = 3 r2 = X
> r1 = X
>
> What values may each of r1 and r2 get? Or more to the point, what
> "special write" replaces "X = 2" so that we cannot get r1 == 1?
I don't think there will be an argument that this should happen. So the fix:
a race write obliterates any values previously deposited by its own thread.
(Since we have SC semantics, "previous" is well-defined.)
>
> 2. Should a value be allowed to "oscillate"? That is, suppose two
> competing writes write 1 and 2 into x. Can another thread see 1
> and then 2 and then 1 again (assuming 1 and 2 are never written
> by any other instruction instance)? Is this allowed even if there
> are synchronization operations intervening between the reads?
> Consider for example
>
> Initially, X == 0, V == 0 (V is volatile)
>
> Thread 1 Thread 2 Thread 3
>
> X = 1 X = 2 r3 = V; V = r3+1
> r1 = V r2 = V ra = X
> V = r1+1 V = r2+1 r4 = V; V = r4+1
> rb = X
> r5 = V; V = r5+1
> rc = X
>
> Can we get r1 == 0, r2 == 1, r3 == 2, r4 == 3, r5 == 4 and
> ra == 1, rb == 2, rc == 1?
>
> (I could put in while loops before reading V to make sure it
> got the right values.)
>
I can fix this too, but the solution that comes immediately to mind is a tad
more complex (requiring keeping track of happens-before and a separate set
of values for each thread). Let me go back and see what CnC does, and I'll
come up with something no stronger.
Of course, in the philosophy of "weaker is better," I can think of one
scenario (albeit far-fetched) where the above result may actually occur, and
it is unclear to me if we do want to fix it. Think of a distributed system
where thread 1 and 2 didn't get acks back from thread 3 because the ack was
lost in the network. The threads send their data again, and because thread 3
does some optimization for races, it ends up applying the data update all
over again. Yeah, may sound far-fetched, but who can predict the future?
Again, I am not pushing for this, just bringing the options on the table.
Also, regarding your comment:
> I was going to suggest that she could go a bit
> further and simply allow the program to execute as though with
> sequential consistency, except that reads in data races can be
> replaced by any value that they are allowed to read (by Jeremy and
> Bill's definition) in that execution,
First, it is great that you had the same intuition. Second, I would love to
push SC- down to restrict reads to return values allowed by Jeremy and Bill.
Unfortunately, with the prohibited reads stuff, I do not know how to do that
yet...
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:47 EDT