All processors will see writes made by a particular processor in the order
written, aka processor order. If processor W writes a value and then updates
the tail pointer then if processor R sees the updated tail pointer then
processor R will see a legal value. In a two processor scenario where only
one processor writes there is no interleaving so it is not interesting for
our purposes here.
In a two writer system (2 writers and n readers) the following interleavings
can be observed.
Write from processor 1 = W1
Write from processor 2 = W2
Tail Update from processor 1 = U1
Tail Update from processor 2 = U2
There are 6 possible interleavings, reading down.
W1 W1 W1 W2 W2 W2
W2 W2 U1 W1 W1 U2
U1 U2 W2 U1 U2 W1
U2 U1 U2 U2 U1 U1
Even if we have 6 readers and each saw a different interleaving they would
never read a bad value.
- Rick Hudson
-----Original Message-----
From: Jeremy Manson [mailto:jmanson@cs.umd.edu]
Sent: Tuesday, November 21, 2000 8:32 AM
To: javamemorymodel@cs.umd.edu
Subject: Re: JavaMemoryModel: Volatiles - where does SC work and PO
doesn'
>
> 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.
I'm
> looking for algorithms where observing different interleavings of writes
on
> different processors breaks the algorithm.
>
> Put another way, I'm trying to find useful algorithms where a total
ordering
> of stores is needed instead of a partial ordering of the stores.
What about a simple producer / consumer queue? A producer fills up a
buffer and a consumer removes data from it. There is a tail pointer,
and the buffer is stored in an array. The producer says write a new
value into the array and advance the tail pointer. The consumer reads
it by saying that if the tail pointer has advanced from where the
consumer last saw it, read the value out of the array. In this case,
the consumer doesn't delete the value. If writes can be seen in
different orders on different processors, then the consumer might see
the updated tail pointer without seeing the new value.
Or did I misunderstand your question?
Jeremy
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:28 EDT