Re: WaitForSingleObject() will not deadlock

No, recursive mutex WILL solve the problem, as should be obvious from the nature of
circular list detection. If you hit a node which has the visited-bit set, then you have
done a circular walk. In the case of mutexes, if you try to lock the object to inspect
the bit, and you already own the mutex, then you are able to acquire the lock
(recursively), and you can legitimately inspect the visited bit. If it is set, you
release the mutex and you now know you have a circular structure. If you are a thread
other than the thread that owns the object, you will block, and therefore when the lock is
finally released, and the waiting thread acquires it, the visited bit will NOT be set
because the thread could not have previously walked into the node.

This is a rather elementary data structure algorithm, and it seems obvious that it cannot
work without a recursively-acquirable lock of some sort.
joe

On Mon, 02 Jul 2007 11:57:44 -0700, Frank Cusack <fcusack@xxxxxxxxxxx> wrote:

Neither does a recursive mutex since a thread other than the one that
acquired the first lock cannot acquire a lock either.
-frank

On Mon, 02 Jul 2007 10:47:10 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
No, trylock and its equivalents only say that the object is locked.
It does not guarantee that you can lock an object and examine it, so
it won't do the job of walking a circular structure when there are
potentially concurrent walkers.
joe

On Sun, 01 Jul 2007 23:47:50 -0700, Frank Cusack <fcusack@xxxxxxxxxxx> wrote:

On Mon, 02 Jul 2007 01:37:50 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
I was not aware that anyone would design a non-recursive mutex,
since this has been an integral part of lock design for at least 20
years, if not longer.

I haven't known our good friend the mutex for so long, but I would
hazard a guess that posix mutexes have ALWAYS had recursion as
an option. Because posix has a non-recursive mutex (by default)
doesn't mean it hasn't also always had a recursive mutex.

I was using recursive-acquisition locks in the late 1980s and they
were a well-known technology at the time I was using them. A
non-recursive mutex is not usable for doing things like traversing
circular lists trying to detect circularity, for example.

Sure it is, use trylock() instead of lock().

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

Relevant Pages

  • Re: recursive mutexes
    ... > 1) You don't know the mutex is being used recursively. ... > lock it since you know it's already locked anyway. ... Unlock mutex ... If it is already locked by this thread then recursion ...
    (comp.unix.programmer)
  • Re: WaitForSingleObject() will not deadlock
    ... But the issue is how can you lock and traverse a potentially circular list with "node has ... circular lists, and it wasn't easy. ... The cost of supporting recursion led to the Kernel concept of a "fast mutex" which is used ...
    (microsoft.public.vc.mfc)
  • Re: WaitForSingleObject() will not deadlock
    ... acquired the first lock cannot acquire a lock either. ... I haven't known our good friend the mutex for so long, ... doesn't mean it hasn't also always had a recursive mutex. ... circular lists trying to detect circularity, ...
    (microsoft.public.vc.mfc)
  • Re: Recursive mutex that can be waited upon (pthread)
    ... While you can use a mutex to avoid that data is changed, for me having a mutex does not mean that data is not changed, it only means that data is not changed by a different thread. ... My own thread may of course change the data, hence functions I call may want to change the data and if they do so, they must be sure that these changes are atomically, hence they must lock the object and they simply can't rely that I locked the object before -> thus I need recursive locks. ... Then I could as well throw out threads of my code and just use a single thread going through an event queue. ... you have a predicate condition on an invariant. ...
    (comp.programming.threads)
  • [patch 6/8] mutex subsystem, core
    ... mutex implementation, core files: just the basic subsystem, no users of it. ... straightforward mutexes with strict semantics: ... + * Block on a lock - add ourselves to the list of waiters. ...
    (Linux-Kernel)