Re: WaitForSingleObject() will not deadlock

You keep talking about needing to know the reference count. Yet I have never seen an
algorithm that uses a recursive mutex that cares in the slightest what the reference count
is. Why do you keep insisting this matters?

more below...
joe
On Mon, 02 Jul 2007 14:41:28 -0700, Frank Cusack <fcusack@xxxxxxxxxxx> wrote:

On Mon, 02 Jul 2007 16:16:03 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
But how does the thread ID come into play? You can't lock the
mutex, so you can't legitimatey examine anything the mutex can set,
such as the thread ID.

True, sloppy thinking on my part.

Using a timeout does not prove that you have set the lock.

Right.

A lock which returns a different error code if the owning thread
attempts to lock appears to be isomorphic to a recursive lock,
except that you now have reference count problem as well, so the

No, with a recursive lock you have a reference counting problem,
with a non-recursive lock you merely need to know the locked state
and the owner. Both of which you need to know *anyway* because
in order to unlock a mutex you must be the owner.

mechanisms required to make it actually work right become more and
more complex.

Non-recursive lock is the simplest mechanism I can think of. I can't
imagine how you can think that a recursive lock is simpler.

There is no reason to assume that all searches are rooted in the
head of the list, and in fact there is no reason to assume the list
has an identifiable head. An example of this would be traversing
softlinks in a directory system, where any thread can start at any
point in the softlink chain.

True, but with locks any starting point (effective head, doesn't have
to be the "actual" head of a list) is the point at which all other
threads get locked out of a list. You can never release the lock at
the effective head, or any subsequent node, until you are done
traversing the entire list. So from the point at which you begin
cycle detection until you reach the end of the list (or find a cycle),
you necessarily lock out other threads. True, this might not be the
entirety of the list. Any part of the list earlier than the effective
head are accessible to other threads.

I'll note that symlink cycle detection is generally done by counting
the number of nodes visited, not by actually detecting the cycle.
*****
Hmmm....so how, exactly, does counting the nodes solve this problem? Oh, if I have a
count larger than the total number of directories, I must be in a cycle. In my
environment, I have something like 35,000 directories, so instead of detecting a cycle in
the three hops that generate the cycle, I have to first know how many directories I have,
then hope that the number of directories does not change during the massively long
traversal, then wait for that number of directories to be traversed. This is not a
feasible circularity algorithm (as was discovered back in 1968 when the IPL-V language was
ported from a 32K-word machine to an 8MB (2M-word) machine.

So please explain how counting the number of nodes visited solves this problem, either for
symbolic links or for any other list in memory.
*****

It is obvious how you know you've visited the node: you have an
is-visited bit. If it is set, and you can see it, it is because you
are the thread that has the node locked.

You don't need an is-visited bit. The mutex itself serves that purpose.
*****
How? The mutex locks in either case; if it locks, you have deadlocked the thread. If you
use a trylock, you have a non-atomic situation, and in that case you *do* need to track
the reference count, which is unnecessary with a recursive mutex.
*****

-frank

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

You could easily add a thread id member, which you set when you lock it.
If that's objectionable, you can use non-recursive mutexes that have
deadlock detection -- instead of locking they return EDEADLK if you
try to recursively lock the mutex. This would be equivalent to a
different version of pthread_mutex_trylock() (which doesn't actually
exist) which returns a different error based on whether the thread
is already locked by you, or if it is locked by someone else.

In any case, using a has-been-visited flag is generally considered
less good than using 2 different iterators with different strides.
Of course that method doesn't allow progress across the list with
multiple threads, although my guess would be that using a mutex
as a has-been-visited flag doesn't "really" allow multiple threads
to make progress either, since you can't release any mutexes until
you have walked the entire list, and presumably all threads would
start at the head node, so once a thread detecting cycles started,
all new threads traversing the list would stall.

Anyway the point is, this is certainly able to be accomplished with
non-recursive mutexes. With recursive mutexes, how do you know if
you've already visited the node? Does the Windows API tell you if
you've acquired a mutex again? Posix does not.

-frank

On Mon, 02 Jul 2007 10:49:40 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
Won't work. If you try to lock an object, and fail, then you can't
legitimately tell if you are the thread that originally locked it,
or some other thread has it locked, so you can't tell the validity
of the has-been-visited flag, so it requires that you would pass the
entire locking sequence around so that if a try failed, you have to
inspect the record of all outstanding locks in the thread to see if
there is an instance of the lock already present. This means you
have to deal with potentially unbounded sequences of locks in a data
structure, not a pleasant prospect. joe

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

On Mon, 02 Jul 2007 01:44:06 -0400 Joseph M. Newcomer <newcomer@xxxxxxxxxxxx> wrote:
But the issue is how can you lock and traverse a potentially
circular list with "node has been visited" detection without a
recursive mutex?

pthread_mutex_trylock()? or equivalent.
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
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
    ... extension required in a multithreaded environment is to provide the synchronization. ... is-visited bit if the mutex can be queried for the lock count. ... Because, as I stated, a lock count of>1 proves previous visitation. ... not by actually detecting the cycle. ...
    (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)
  • Re: [PATCH RFD] alternative kobject release wait mechanism
    ... There is no reason to hold reference to it. ... you grab the mutex excluding its removal and verified it's still there. ... It also wakes up all threads that are blocked trying to lock the ...
    (Linux-Kernel)
  • Re: WaitForSingleObject() will not deadlock
    ... is-visited bit if the mutex can be queried for the lock count. ... Because, as I stated, a lock count of>1 proves previous visitation. ... not by actually detecting the cycle. ... which is unnecessary with a recursive mutex. ...
    (microsoft.public.vc.mfc)
  • [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)