Re: WaitForSingleObject() will not deadlock

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

CRITICAL_SECTIONs, however, *are* recursively acquirable. From the discussion of
CRITICAL_SECTION:
=================
"When a thread owns a critical section, it can make additional calls to
EnterCriticalSection or TryEnterCriticalSection without blocking its execution. This
prevents a thread from deadlocking itself while waiting for a critical section that it
already owns. To release its ownership, the thread must call LeaveCriticalSection one time
for each time that it entered the critical section."
==================
so it is not correct to compare the CRITICAL_SECTION and the pthread_mutex, because
CRITICAL_SECTION *does* have recursive acquisition semantics.

I also checked some Web sites. For example, in the discussion of HP POSIX, I find a page

http://h30097.www3.hp.com/docs/base_doc/DOCUMENTATION/HTML/AA-Q2DPC-TKT1_html/thrd0038.html

================
2.3.1.2 Recursive Mutex
A recursive mutex can be locked more than once by a given thread without causing a
deadlock. The thread must call the pthread_mutex_unlock routine the same number of times
that it called the pthread_mutex_lock routine before another thread can lock the mutex.
Recursive mutexes have the notion of a mutex owner. When a thread successfully locks a
recursive mutex, it owns that mutex and the lock count is set to 1. Any other thread
attempting to lock the mutex blocks until the mutex becomes unlocked. If the owner of the
mutex attempts to lock the mutex again, the lock count is incremented, and the thread
continues running. When an owner unlocks a recursive mutex, the lock count is decremented.
The mutex remains locked and owned until the count reaches zero. It is an error for any
thread other than the owner to attempt to unlock the mutex.

A recursive mutex is useful if a thread needs exclusive access to a piece of data, and it
needs to call another routine (or itself) that needs exclusive access to the data. A
recursive mutex allows nested attempts to lock the mutex to succeed rather than deadlock.

This type of mutex is called recursive because it allows you a capability not permitted by
a normal (default) mutex. However, its use requires more careful programming. A recursive
mutex should never be used with condition variables, because the unlock performed for a
pthread_cond_wait or pthread_cond_timedwait might not actually release the mutex. In that
case, no other thread can satisfy the condition of the predicate, and the thread waits
indefinitely. See Section 2.3.2 for information on the condition variable wait and timed
wait routines.
======================================

or from http://h30097.www3.hp.com/docs/posix/PCD1C_REV2/DOCU_009.HTM
======================================
11.3 Mutexes
11.3.1 Mutex Initialization Attributes
11.3.1.2 Description
The operating system supports the CAE "mutex type" extension attribute in a mutex
attributes object. This attribute determines a mutex's type when the mutex object is
created. Use the pthread_mutexattr_gettype() and pthread_mutexattr_settype() functions to
obtain and set this attribute, respectively. This attribute can take the values
[PTHREAD_MUTEX_NORMAL] (the default), [PTHREAD_MUTEX_RECURSIVE], or
[PTHREAD_MUTEX_ERRORCHECK].

The value [PTHREAD_MUTEX_NORMAL] indicates that the mutex object represents a normal
mutex. This type of mutex is locked exactly once by a thread. If a thread tries to lock
the mutex again without first unlocking it, the thread waits for itself to release the
lock and deadlocks. For more information, see the Guide to the POSIX Threads Library.

The value [PTHREAD_MUTEX_RECURSIVE] indicates that the mutex object represents a recursive
mutex. This type of mutex can be locked more than once by a given thread without causing a
deadlock. Before another thread can lock an instance of this type of mutex, the locking
thread must call the pthread_mutex_unlock() routine the same number of times that it
called the pthread_mutex_lock() routine. Recursive mutexes have the notion of a mutex
owner. When a thread successfully locks a recursive mutex, it owns that mutex and the lock
count is set to 1. Any other thread attempting to lock the mutex blocks until the mutex
becomes unlocked. If the owner of the mutex attempts to lock the mutex again, the lock
count is incremented, and the thread continues running. When a recursive mutex's owner
unlocks it, the lock count is decremented. The mutex remains locked and owned until the
count reaches zero. It is an error for any thread other than the owner to attempt to
unlock a recursive mutex. For more information, see the Guide to the POSIX Threads
Library.
================================
From http://doc.trolltech.com/3.3/qmutex.html
================================
Member Function Documentation
QMutex::QMutex ( bool recursive = FALSE )
Constructs a new mutex. The mutex is created in an unlocked state. A recursive mutex is
created if recursive is TRUE; a normal mutex is created if recursive is FALSE (the
default). With a recursive mutex, a thread can lock the same mutex multiple times and it
will not be unlocked until a corresponding number of unlock() calls have been made.
================================
From HP's documentation of VMS (an operating system delivered with the first VAX systems,
back in the late 1970s) http://h71000.www7.hp.com/commercial/cplus/vax_doc/clv008.htm
================================
Chapter 6
Mutex Package
The Mutex package provides a way to synchronize access to user-defined objects. It
consists of a single class, Mutex , that manages the creation, locking and unlocking of
Mutex objects.

Construction of a Mutex object creates a recursive mutex that users can lock and unlock
using the appropriate member functions or parameterized manipulators. A recursive mutex is
a mutex that can be locked many times by the same thread without causing the thread to
enter a deadlock state. To completely unlock this kind of mutex, the thread must unlock
the mutex the same number of times that the thread locked the mutex. For more information
see the Guide to DECthreads manual.
==================================
From the DECthreads manual (which makes this information at least 9 years old, since DEC
was acquired by Compaq in 1998)
http://www.nacs.uci.edu/dcslib/digital_unix/digital-v40d/AQ2DPDTK/DOCU_004.HTM
==================================
When a thread first successfully locks a recursive mutex, it owns that mutex and the lock
count is set to 1. Any other thread attempting to lock the mutex blocks until the mutex
becomes unlocked. If the owner of the mutex attempts to lock the mutex again, the lock
count is incremented, and the thread continues running.

When an owner unlocks a recursive mutex, the lock count is decremented. The mutex remains
locked and owned until the count reaches zero. It is an error for any thread other than
the owner to attempt to unlock the mutex.
===================================
I have been seeing references to recursive acquisition of mutexes back to at least 1990,
when it appears to have been taken for granted rather than thought of as something
unusual.
joe

On Sun, 1 Jul 2007 17:01:07 -0700, "Alexander Grigoriev" <alegr@xxxxxxxxxxxxx> wrote:

I just checked pthread_mutex_lock description
(http://node1.yo-linux.com/cgi-bin/man2html?cgi_command=pthread_mutex_lock).
Sorry, this page comes on a lively gray (RGB=192) background. I wonder whay
not green on brown, that would be even cooler.

You won't believe me, but Posix mutex also provides non-recursive option,
which is an example of design by a commity (or design by a management). I
mean, there is even no reason to put it into the picture, because it still
posesses thread affinity (you should not unlock it from another thread), but
you cannot acquire it recursively (you'll deadlock). There is also
"error-checking" type, which checks agains recursive locking, or unlocking
by wrong thread. Anybody tell me, why any other variants besides a recursive
one were invented?

You also cannot use pthread_mutex across processes. This is just a
CRITICAL_SECTION rough equivalent.

"Joseph M. Newcomer" <newcomer@xxxxxxxxxxxx> wrote in message
news:hl1g83lpj6rdk46sonnc2gnigaobai4plr@xxxxxxxxxx
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.

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.

What you are asking violates the fundamental design of a mutex. I would
suggest that you
are the one who doesn't understand them. Of 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."
=================================
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?
joe

On Sun, 01 Jul 2007 01:40:28 -0700, Frank Cusack <fcusack@xxxxxxxxxxx>
wrote:

On Sat, 30 Jun 2007 23:05:58 -0400 Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:
You can't, it is impossible; it violates the fundamental design of a
mutex!!!!

You obviously are limited in your understanding of what a mutex is.

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

Loading