Re: WaitForSingleObject() will not deadlock

And in what way am I wrong about Windows mutexes?

I have been doing concurrent programming professionally for 32 years in a variety of
operating systems and environments, and I have considerable expertise in it. I suppose
you're next going to say years of experience don't qualify me either. On the other hand,
I was absolutely right about the semantics of mutexes (since I can give you quotes from
the documentation which are consistent with my statements of how mutexes work) and you
were wrong (because you said I didn't understand mutexes, even though I told you your
expectations would violate the *documented* mutex behavior). I started working with
concurrency shortly after Dijkstra's 1968 paper, but only worried about it between about
1968 and 1972, building only experimental systems (my first synchronization system was
written in 1968 as an interterminal chat system running on TSS/360, so as someone who has
actually written synchronization code, I've now been doing it for 39 years, with
considerable success, I might add). I wrote the P and V operations for our student
project on the IBM/360 computer. Between 1975 and 1977 I did a substantial amount of work
on a 16-processor multiprocessor system, and our problems included concurrent update of
objects, deadlock avoidance, and lock contention avoidance. I spent a fair amount of time
developing algorithms for analyzing deadlock in source code by doing static source
analysis and using Petri net simulations. The C.mmp/Hydra system (C.mmp was the
multiprocessor system, built from 16 PDP-11 computers, and Hydra was the capability-based
object-oriented operating system that ran on it) was one of the earliest mid-scale
multiprocessor systems. I was part of the Ada evaluation team and studied the Ada
rendezvous mechanism in some detail including the issues of implementing it, although we
did not publish any papers on this aspect.

Whatever you care to believe, I was right about mutexes. You were not.

More below...
*****
On Sun, 01 Jul 2007 18:45:05 -0700, Frank Cusack <fcusack@xxxxxxxxxxx> wrote:

On Sun, 01 Jul 2007 16:08:59 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
Two weeks ago, I taught my Systems Programming Course, in which we
use mutexes in the lab on Thursday. I also teach about critical
sections. Last week I taught our Device Driver course, in which I
taught what a mutex is. As well as spin locks, fast mutexes, and
executive resources. I suspect I actually understand what a mutex
is.

Teaching a subject does not qualify you as an expert in it. I have
had some very qualified and very good teachers, but like all of us I
have also had some poor ones. I'm not outright saying you are
unqualified, and I am not implying anything about your teaching skills
(after all, I have no idea), I'm simply saying that your assertion of
qualification or expert knowledge by teaching about it is meaningless.
Furthermore, unless you are talking about a 40 hour course, covering
the topic of synchronization primitives or device drivers in "a week"
is just introductory and again does not demonstrate expert knowledge.

For example, you asked a question which clearly shows you do not
undertand recursive acquisition semantics, one of the fundamental
properties of a mutex. I quote from your post:

if (WaitForSingleObject(mutex, INFINITE) == WAIT_OBJECT_0)
AfxMessageBox("acquired", ID_OK);
if (WaitForSingleObject(mutex, INFINITE) == WAIT_OBJECT_0)
AfxMessageBox("acquired", ID_OK);

You got two message boxes, which is EXACTLY what you should see happen!

Now, if I say :"this would violate the fundamental design of a mutex
to have this deadlock", and it is obvious that it does not deadlock,
it is almost certainly because I understand how mutexes work. You
are insisting that it *should* deadlock, and this shows you do *not*
understand how a mutex works.

Get it straight. I did not insist that it should deadlock, I asked
why it didn't. I didn't find documentation that Windows mutexes were
recursive, so I had to ask. And it's not obvious why it didn't
deadlock; there are 2 possible reasons.

1. The mutex is recursive.
2. WaitForSingleObject() knows that the object has already been
"signalled", and therefore returns success, WITHOUT again
locking the mutex.
*****
How is (2) different from (1)? Note that once a mutex is non-signaled, it is owned, and
would not be "locked" again. Instead, the reference count is is incremented, as is done
with all implementations of recursive mutexes I know of. Furthermore, the documentation
actually states that mutexes can be acquired recursively because it states that a WaitFor
will not block, and as many ReleaseMutex calls as successful WaitFor calls must be
performed.
*****

As a newcomer to Windows, the WaitForSingleObject() call is confusing
and has unclear semantics to me. In fact, the documentation for
CreateMutex() talks about the mutex being "signaled" and "unsignaled"
as opposed to acquired and released. That was confusing for me.
Hell, I had a hard time figuring out that the '0' at the end of
WAIT_OBJECT_0 was a '0' and not an 'O'.
*****
Objects are referred to as being signaled or non-signaled. Mutexes are a subset of the
general waitable object model, and therefore are either signaled or non-signaled just like
any other waitable object. Acquiring a mutex is a mutex-specific operation that converts
the mutex object from the signaled state to the non-signaled state, so it would not be
correct to talk about acquisition and release since that would limit the discussion to a
single type of object, and would not be applicable to file handles, waitable timers,
events, change notifications, job objects, processes, threads, or semaphores, none of
which have a concept of "acquisition". The only unifying concept is "signaled" and
"nonsignaled", and mutex acquisition is an operation that changes the state of a
particular kind of the waitable objects, a mutex, from signaled to non-signaled.
******

What you are asking violates the fundamental design of a mutex. I

Fundamental? ha. You mean fundamental to the design of a Windows
mutex.
****
This *is* a Windows newsgroup, and the behavior I described *is* fundamental to the design
of mutexes in Windows, so what is wrong with what I said? Your desires violate the
fundamental design of a mutex. In the context of a Windows newsgroup, that is the only
mutex that would be discussed.
****

would suggest that you are the one who doesn't understand them. Of

I agree, I do not understand Windows mutexes. Well, now I understand
them a bit more.
*****
So why did you presume I didn't understand them? I've been using synchronization
primitives for nearly 40 years, starting with the test-and-set instruction of the IBM 360
back in 1968.
*****

course, had you actually read the documentation on a mutex, you
would have seen the paragraph that says (and I have pasted this from
the MSDN documetation on CreateMutex):
================================
"The thread that owns a mutex can specify the same mutex in repeated
wait function calls without blocking its execution. Typically, you
would not wait repeatedly for the same mutex, but this mechanism
prevents a thread from deadlocking itself while waiting for a mutex
that it already owns. However, to release its ownership, the thread
must call ReleaseMutex once for each time that the mutex satisfied a
wait."
=================================

Thanks, I see that now. Wish I had seen it earlier, would have
answered my question right away.

So you are asking how to create a situation that violates the
fundamental *documented* design of a mutex, and I told you that your
suggestion violates the fundamental design of a mutex; your response
is that I have a limited understanding of what a mutex is, so please
explain exactly what part of a mutex I don't understand?

I will agree that you understand what a Windows mutex is (expert
knowledge even), but in my mind the jury is still out on whether or
not you understand more fundamentally about mutexes in general. Not
saying you don't have a solid grasp, just that your assumptions are
Windows-oriented.
*****
Gee, after 39 years of writing synchronization code, I probably have discovered SOMETHING
about synchronization, the basic principles,the high-level models, the formal models, and
a lot of other details. But when a question appears in a Windows group, showing an
example using the Windows API, I tend to assume that we are talking about Windows mutexes,
and not some general model of mutexes through history. If you ask a question about the
presidential candidate in a Republican blog, it is unlikely you are talking about the
office as it was in 1780, or about the presidential candidate of some South Pacific island
or of some company or social organization. So there is no reason to assume that we are
talking about POSIX semantics, or Dijkstra's P/V primitives, or Hoare monitors, or
discussing the Multics wait/wake problem, or Brinch-Hansens signaling mechanism.

With respect to my background, Per Brinch-Hansen's office was across the hall from mine;
one of Dijkstra's best students, Nico Habermann, was a professor at CMU and eventually
department head, and he taught the operating systems course there, which I sat in on. My
Software Systems PhD qualifier exam, which had several questions on synchronization, was
complimented by Nico as being the best answer he'd ever seen on the subject. I learned
initially about these issues from Dave Parnas, one of the creators of modular programming,
if not THE creator of modular programming. Have you read Jerry Salzer's work on
synchronization issues in Multics? Our first student exercise in operating systems was to
create P and V using ordinary instructions with the possiblity of context swap caused by
thread preemption between any two instructions, and the synchronization had to still work.
Let's see, have I amply demonstrated that I actually DO understand synchronization
primitives in general? But if you ask a question in a Windows newsgroup, expect to get a
Windows-oriented answer. If you need a general answer, go find some general newsgroup,
comp.something-dealing-with-synchronization. If you ask a Windows question in a Windows
newsgroup, expect a Windows-oriented answer.

But the other basic issue was that you were trying to use a synchronization primitive to
solve a non-synchronization problem, and the solution would have failed no matter what the
semantics were. With recursive acquisition, there is no synchronization, and without it,
the one-and-only GUI thread deadlocks itself, so both possible implementations of
synchronization primitives, the results are incorrect. You didn't have a synchronization
problem in the first place, just a problem of doing the same thing twice, in the same
thread.
******

I will submit that it was a mistake on my part to consider any mention
of a mutex in this newsgroup as meaning anything other than a Windows
mutex. Double dumbass on me.

Can you explain and/or point me to documentation on the memory
visiblity semantics of a Windows mutex? I am not trying to draw you
out; this is an honest question.
*****
What's "memory visibility semantics"? I've not heard that term applied to any
synchronization object, but if you explain what you mean, I can probably give you an
answer.

I tried a google search on "memory visibility semantics mutex" but didn't find anything
that seemed relevant.

Mutexes are not memory objects; they are represented by handles. So there is no memory to
be visible. But the handle can be visible across processes, and there are some
interesting protocols, such as using GUIDs for names, to prevent collision of these names
in the global namespace.

You cannot share a handle by placing the handle in shared memory, because the handle would
not be in the process handle table of the other processes. The usual technique of making
a mutex, semaphore, or event visible to another process is to have each process do

HANDLE mutex = CreateWhatever(NULL, otherparametershereasappropriate, MY_OBJECT_NAME);

where you do something like

#define MY_OBJECT_NAME _T("MyQueueMutex-{8D9BC3AE-A745-4513-B4D1-4AC600E62888}")

where you use the program GUIDGEN.EXE to create that GUID. This guarantees that no one,
anywhere, ever, will accidentally create a mutex of the same name you have. Actually, the
GUID is sufficient, but you use the readable name to communicate information to the person
using it (there are tools that can inspect the object space, for example).

The effect is to allow each process to create a new handle to a mutex. If the mutex is
named, and already exists, CreateMutex == OpenMutex. This means that it doesn't matter
what order the processes start up in; one gets to create the mutex and the rest get to use
it.

To use a handle, it must be in the handle table of the process. There are several ways
get a handle there, such as doing CreateMutex or the appropriate action for the type of
object whose handle you want, creating a duplicate handle using DuplicateHandle and
targeting the receiving process, or creating an inheritable handle which is inherited by a
child process. However, far and away the simplest method for synchronization objects is
to simply do the appropriate Create in the processes that wish to share.The other
techniques have problems in communicating the numerical value of the handle to the target,
and offer no serious advantages over the Create method.
joe
*****

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

Relevant Pages

  • Re: Thread synchronization
    ... sounds like mutexes might be the best ones to use then. ... I just wanted to use the fastest possible way of synchronization ... > try to perform an interlocked operation on the same variable concurrently, ... > thread releasing a Mutex and a blocked thread coming out its wait on the ...
    (microsoft.public.dotnet.languages.csharp)
  • RE: Thread synchronization
    ... try to perform an interlocked operation on the same variable concurrently, ... thread releasing a Mutex and a blocked thread coming out its wait on the ... > iv got a multithreaded program and need to use thread synchronization. ... > at current using mutexes but was wondering if there was something a bit ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: WaitForSingleObject() will not deadlock
    ... use mutexes in the lab on Thursday. ... I suspect I actually understand what a mutex ... I didn't find documentation that Windows mutexes were ... As a newcomer to Windows, ...
    (microsoft.public.vc.mfc)
  • Re: msleep() on recursivly locked mutexes
    ... Further the idea that holding a mutex "except for when we sleep" is a ... This is basically when I need to exit mutexes. ... I agree with the other comment that all drivers should be multi-thread ... lock a mutex again. ...
    (freebsd-hackers)
  • Re: msleep() on recursivly locked mutexes
    ... Further the idea that holding a mutex "except for when we sleep" is a ... release it during sleep you probably should invalidate all assumptions ... This is basically when I need to exit mutexes. ... it is not always possible to drop the blocking lock ...
    (freebsd-hackers)