Problems understanding "visibility"

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Problems understanding "visibility"

Chris Purcell
I'm having problems understanding this word "visibility" that keeps
getting used. Is it possible to create a concurrent program that can
actually tell the difference between acquire/release having only
ordering constraints, and acquire/release having ordering + visibility
constraints? Moreover, what concurrent design idioms require visibility
for correctness?

Cheers,
Chris

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Problems understanding "visibility"

David Holmes
Chris,

> I'm having problems understanding this word "visibility" that keeps
> getting used.

Unless a write in one thread happens-before a read in another thread, then
the write need never be seen by that other thread. This is the conceptual
model. For simplicity assume a variable is kept in a thread-local-location
and unless two actions in two different threads are ordered by
happens-before, then writes to the variable only affect the thread's local
version of the variable.

Of course real hardware is unlikely to do this (in fact some cache
architectures pretty much guarantee that all writes go to main memory within
a bounded time). But the compiler could use a register to hold the local
value of a variable.

> Is it possible to create a concurrent program that can
> actually tell the difference between acquire/release having only
> ordering constraints, and acquire/release having ordering + visibility
> constraints?

I don't think it makes sense to talk about ordering without visibility as it
is the order in which writes are seen that is at issue.

> Moreover, what concurrent design idioms require visibility
> for correctness?

Pretty much all of them.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Problems understanding "visibility"

Jeremy Manson
In reply to this post by Chris Purcell
Chris Purcell wrote:
> I'm having problems understanding this word "visibility" that keeps
> getting used. Is it possible to create a concurrent program that can
> actually tell the difference between acquire/release having only
> ordering constraints, and acquire/release having ordering + visibility
> constraints? Moreover, what concurrent design idioms require visibility
> for correctness?
>

When you need visibility, you almost invariably need ordering, so
release and acquire provide both.

The distinction mostly exists so we can describe separate symptoms of
broken multithreaded code.  Here's an example of code with a data race
exhibiting strange behavior with visibility, but without ordering:

Initially, p = q, p.x = 0;

Thread 1:
r1 = p.x;
r2 = q.x;
r3 = p.x;

Thread 2:
p.x = 1;

Let's pretend there was some way of getting visibility without ordering.
  Somehow, we know that the write by Thread 2 will be seen by Thread 1.
  But we aren't guaranteeing ordering.  It would be possible for the
compiler to do the following:

Replacement Thread 1:
r1 = p.x;
r2 = q.x;
r3 = r1;

Let's say the write to p.x was scheduled between the read of p.x and the
read of q.x by Thread 1.  In this case, you would get the result r1 = r3
  0, r2 = 1.  In other words, the write was visible, but the results
were seen out of order.

You could equally construct situations where you get ordering without
visibility, but I think this illustrates the point.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Problems understanding "visibility"

Jeremy Manson
Jeremy Manson wrote:

> You could equally construct situations where you get ordering without
> visibility, but I think this illustrates the point.

I'll elaborate.  Here's an example where you can get ordering without
visibility:

boolean done = false;

Thread 1:
while (!done) {
  // do  stuff
}

Thread 2:
done = true;

Let's say a compiler sees that Thread 1 never changes the value of done,
and so changes Thread 1 to:

Thread 1:
while (true) {
   // do stuff
}

In the previous example, the order of operations had changed: the third
write was effectively moved to the beginning of Thread 1.

In this example, the order of operations has not changed; the write by
Thread 2 is just not visible to Thread 1.

Obviously, ordering and visibility are related, which is why acquires
and releases provide both.  I've said myself that there is a thin line
between the two.  The distinction can be useful when discussing these
issues, though.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest