Re: WaitForSingleObject() will not deadlock

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.

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

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 mechanisms required to make it actually work right become more and more
complex.

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.

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.
joe

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
.

Relevant Pages

  • 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)
  • [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)
  • [PATCH 4/8] adaptive real-time lock support
    ... The Real Time patches to the Linux kernel converts the architecture ... compromising the integrity of critical sections protected by the lock. ... while retaining both the priority inheritance protocol as well as the ... the RT Mutex has been ...
    (Linux-Kernel)
  • Re: WaitForSingleObject() will not deadlock
    ... You could easily add a thread id member, which you set when you lock it. ... you can use non-recursive mutexes that have ... deadlock detection -- instead of locking they return EDEADLK if you ... try to recursively lock the mutex. ...
    (microsoft.public.vc.mfc)