Re: WaitForSingleObject() will not deadlock

See below...
On Thu, 05 Jul 2007 23:14:19 -0500, "Doug Harrison [MVP]" <dsh@xxxxxxxx> wrote:

On Thu, 05 Jul 2007 23:24:32 -0400, Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:

Yes, but you also said that there was an issue if the line was uncommented.

Because there *is* an issue.
****
I agree, but only because the code is erroneous
****

Since with
the line commented out, and assuming there is no other gratuitous assignment to x, then it
is completely deterministic

Then why did you say the code is "erroneous" and has a "race condition"?
Neither is true, as is clear when you read the explanation that came with
the example. Let me try once again:
*****
If I start the thread, there is no guarantee that the value represented by an address A
will be updated in one thread relative to its use in another thread.
*****

********************

It makes sense. Here's an illustration of what it's saying:

int x = 0; // global

***** Thread 1:

x = 2;
CreateThread;
// x = 3;

***** Thread 2:

if (x == 2)
puts("x == 2");

A. Rule (1) guarantees that when started, thread 2 observes x == 2, since
thread 1 set it to 2 before creating the second thread.
****
Yes, that would be true, if you don't have any other assignments possible in any other
thread. Essentially, there is an algorithmic guarantee of data stability in such a case,
and consequently, it would not make sense for the thread to see a value OTHER than 2,
because the language semantics would insist that the assignment has taken place at a time
before launching the thread. Any hardware, software, or compiler optimization that
violated this would represent an incorrect implementation of the language.
*****

B. However, if you were to uncomment the line that sets x to 3, thread 2
might not see that value, even if it were executed before thread 2 got
around to testing it. That is, thread 2 might still observe the value 2,
even though from thread 1's perspective, x contains 3, at the moment thread
2 tested it.
****
No, you would definitely see the value 3. The question is WHEN you would see it. Because
we no longer have a guarantee of data stability, the sequence could be

x=0
x=2
createthread
x=3

and the thread has the sequence
?=x

Now the issue is nondeterministic. Once the thread is launched, it MIGHT see the value 2,
if the assignment x=3 has not been performed, or it MIGHT see the value 3, if the
assignment x=3 has been performed. But there is no control of the temporal relationship
between the two threads, and consequently EiTHER situation could arise. A piece of code
that was depending on seeing either x==2 or x==3 inthe presence of the assignment x==3
would represent an overal structure that was erroneous, because it is not reasonable to
expect one or the other value of x; either could be true, and essentially it has nothing
to do with hardware, caches, pipelines, or synchronization; it only has to do with the
relative times at whcih the reads and writes are performed. Cache flushing will not
change the behavior, synchronization will not change the behavior, and a piece of code
that depended upon being able to see x==2 might or might not work, nondeterministically,
based on incidentals like the number of processor cores, the delta-T between the
assignments, the time taken to start the thread, the load on the scheduler, etc. And
therefore, by allowing the line x==3, the code has become erroneous, because it violates
any expectation of determinism. The variable is not cloned and given to the thread (e.g.,
the OpenMP concepts of variables local to a block that are initialized at the start of the
block but are essentially thread-local-storage), it is a truly shared location.
*****

********************

I've now split the discussion into parts (A) and (B). Part (A) is talking
about the example *as given*, with the line commented *out*. Part (B) is
talking about the example after *uncommenting* the line. Part (A) discusses
what Rule (1) guarantees. Part (B) discusses what it does not guarantee. I
don't see how I could more directly illustrate Rule (1), which is:

1. Whatever memory values a thread can see when it creates a new thread can
also be seen by the new thread once it starts. Any data written to memory
after the new thread is created may not necessarily be seen by the new
thread, even if the write occurs before the thread starts.
*****
No, that is what is confusing. If the write takes place, there is no reason the new
thread will not see it, because the write is taking place to the location where the
variable is found. The issue is merely the relative timings of when the write takes
place. The suggestion that the write would not be visible if it happened before the
thread starts seems odd, because that would suggest that the thread gets a local copy of
the variable, and that the implementation reserves the right to make the copy early (at
thread creation) or late (at thread startup). But why would a threaded implementation
feel any need to worry about the time a copy is made when the semantics of the language do
not require that a copy be made at all, and for that matter, would actually "teach
against" this practice?

A memory address is a memory address. Data written to that address appears in memory.
Caches are mechanisms to optimize performance while giving the illusion of those semantics
being maintained.
*****

Make sense?

Lacking the ability to see the pages, it was not obvious what was on them.

The point is, understanding what those pages discuss is not necessary to
understand the 4 rules which were phrased in terms of mutexes and condition
variables. Put another way, as long as you follow the 4 rules, you can get
by in pthreads having never heard of a memory barrier or cache consistency.
I posted the rules after you asked how to define "memory visibility". They
constitute one such definition, and if you limit yourself to thread
creation/join and mutexes, they apply equally well to Windows as they do to
POSIX. I also posted a link to an MSDN page that talked about the
lower-level concepts.
*****
4. Whatever memory values a thread can see when it signals or broadcasts a
condition variable (calling notify in Java) can also be seen by any thread
that is awakened by that signal or broadcast. And, one more time, data
written after the signal or broadcast may not necessarily be seen by the
thread that wakes up, even if it occurs before it awakens.

But why does it limit the value consistency to threads that are "awakened"? Why is the
value not known if the thread is already running? For example, if I wanted to wait on a
condition but the condition was already met, would the semantics be that the thread
"stopped and immediately was awakened" or would it mean that a thread that would have
blocked if the condition were not met is not considered to have been "awakened" if the
thread doesn't block in the first place? And why the limitation that the data is made
consistent at the time of the broadcast, instead of simply being there? Note that if the
data is changed after the broadcast, then either the existing data is seen because the
thread has already read it and the writes are not seen because the thread no longer will
read the data, or the writes will be seen because they have already been done before the
thread started. Coupling specific values to specific events seems to be overly
restrictive
joe

****
Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Loading