Re: WaitForSingleObject() will not deadlock

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
.

Relevant Pages

  • Re: WaitForSingleObject() will not deadlock
    ... mutex, so you can't legitimatey examine anything the mutex can set, ... attempts to lock appears to be isomorphic to a recursive lock, ... has an identifiable head. ... I'll note that symlink cycle detection is generally done by counting ...
    (microsoft.public.vc.mfc)
  • Re: WaitForSingleObject() will not deadlock
    ... legitimatey examine anything the mutex can set, ... Using a timeout does not prove that you have set the lock. ... to be isomorphic to a recursive lock, except that you now have reference count problem as ... you can use non-recursive mutexes that have ...
    (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)
  • [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)
Loading