Re: WaitForSingleObject() will not deadlock

See below...
On Wed, 04 Jul 2007 11:03:57 -0500, "Doug Harrison [MVP]" <dsh@xxxxxxxx> wrote:

On Wed, 04 Jul 2007 01:15:31 -0400, Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:

Actually, all I found in the Butenhof reference was a quote from Alice in Wonderland, and
the next page is 97, thus skipping everything in between.

Oh well, I was skeptical the Google Books link would work, and now I know
it doesn't. (I was really surprised to find the whole text of the book
available to me; it must be a great comfort to the publisher/author that
it's not linkable.) Anyway, here is what I was trying to link to:

"Programming with POSIX Threads", page 89
<q>
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.
*****
Seems an odd specification. Essentially, it means that threads cannot share variables
when they are running.
*****

2. Whatever memory values a thread can see when it unlocks a mutex (leaves
a synchronized method or block in Java), either directly or by waiting on a
condition variable (calling wait in Java), can also be seen by any thread
that later locks the same mutex. Again, data written after the mutex is
unlocked may not necessarily be seen by the thread that locks the mutex,
even if the write occurs before the lock.
*****
I find this truly unbelievable. How can a mutex know what values were accessed during the
thread, so that it can ensure the values are going to be consistent if that same mutex is
locked? This strikes me as requiring immensley complicated bookkeeping on the part of the
mutex implementation. It seems so much easier to follow the semantics of most hardware
and just make sure that locking guarantees all pipes and caches are coherent across all
processors. While I first find it hard to imagine how it is possible to create a
situation of this nature on any closely-coupled MIMD architecture, I can imagine how it
can exist in a distributed MIMD architecture, but in that case, the mutice have to keep
track of every variable that is accessed within their scope, and ensure that an attempt to
lock a mutex can ensure that all remotely-cached data is sent back and all locally-cached
data is distributed out. An awesome task.
*****

3. Whatever memory values a thread can see when it terminates, either by
cancellation, returning from its run method, or exiting, can also be seen
by the thread that joins with the terminated thread by calling join on that
thread. And, of course, data written after the thread terminates may not
necessarily be seen by the thread that joins, even if the write occurs
before the join.
*****
This implies that the notion of "join" exists as a fundamental concept. Most operating
systems that have threads do not seem to have this concept any longer; it seems to have
been more of a high-level concept when threads were implemented above the operating
system.

I wonder what bizarre era of programming this specification represents.
****

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.
*****
This seems to imply that it is possible to have locally cached copies of the values that
are not written back. Strangely enough, this would take a massive effort to implement,
and in hardware, the effort is trivial and built-in by the manufacturer, at least in
closely-coupled MIMD systems. In distributed systems, the problems are sufficiently
complex that these specifications are going to be very expensive to implement (note that
Transputers, the most popular distributed MIMD system, had very complicated rules for
low-level synchronization, and these were abstracted away by the OCCAM language).
*****
</q>

No surprises there. The MSDN link indicates this applies to other sync
objects plus CRITICAL_SECTION. It's nice for it to be stated, but for all
the reasons we've talked about, it couldn't be any other way. For Windows,
I expect you could add:

5. Whatever memory values a thread can see when it calls PostMessage or
SendMessage can also be seen by the thread that retrieves or processes the
message.
*****
Essentially, in Windows, any value in an memory location that can be seen by one thread
can be seen by any other thread at any time for any reason. So the only issue is whether
or not the COMPILER has done something that keeps some local cache somewhere. The
conservative optimizer of Microsoft C ensures this by essentially implementing "volatile"
semantics against any variable that is potentially modifiable by an arbitrary function
call. A C compiler is not required to do this, and it can still be a conforming C
compiler.
*****

I don't recall seeing any explicit statement of this, but again, I don't
see how it could be otherwise.

Memory ordering (which I would not have thought of as "memory visibility guarantees") is
an ancient topic.

In this context of using synchronization objects such as mutexes,
"visibility" subsumes "ordering".
*****
I would think they are the same problem, as far as the hardware is concerned.
*****
Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: WaitForSingleObject() will not deadlock
    ... Whatever memory values a thread can see when it creates a new thread can ... data written after the mutex is ... standardized multithreading library designed to run efficiently on existing ... A C compiler is not required to do this, and it can still be a conforming C ...
    (microsoft.public.vc.mfc)
  • Re: WaitForSingleObject() will not deadlock
    ... Whatever memory values a thread can see when it creates a new thread can ... and after the clause, "However, if you were to uncomment the line that sets ... data written after the mutex is ... No, you have to lock the same mutex, and reflects that. ...
    (microsoft.public.vc.mfc)
  • Re: WaitForSingleObject() will not deadlock
    ... Whatever memory values a thread can see when it creates a new thread can ... and after the clause, "However, if you were to uncomment the line that sets ... data written after the mutex is ... No, you have to lock the same mutex, and reflects that. ...
    (microsoft.public.vc.mfc)
  • Re: Emulating PTHREAD_MUTEX_RECURSIVE - recursive mutex implementation...
    ... turned out to be non-recursive mutex deadlock - and that was not the ... found non-recursive mutex to lead to more complex code in general. ... In my memory allocator, there is a possibility to get memory profile ...
    (comp.programming.threads)