Recursive mutexes
notme
operating
system doesn't provide one (it only provides ordinary mutexes and critical
sections)
So far, I have done this:
void my_mutex::acquire() {
EnterCriticalSection();
if (m_owner == thread_id) {
++m_count;
}
else {
m_mutex->wait();
m_count = 1;
m_owner = thread_id;
}
ExitCriticalSection();
}
void my_mutex::release() {
EnterCriticalSection();
--m_count;
if (m_count == 0)
m_mutex->signal();
ExitCriticalSection();
}
I guess the variable's names are self-explanatory. Is this implementation
ok? I'd like to hear from the experts here
any comment or advice about corrections, performance changes, etc. Remember
that I can only use
these primitives.
Thanks!
Chris Thomasson
> operating
> system doesn't provide one (it only provides ordinary mutexes and critical
> sections)
CRITICAL_SECTION's are recursive.
Mikhail Polatov
Why do you need a recursive mutex in the first place?
You can always refactor your code not to use them plus you'll get the
faster code.
--
Mikhail Polatov
notme
mensaje news:Ke-dnaV0w7R...@comcast.com...
Not in my system. Why you assume I'm using windows? :-) (In fact, AFAIK,
windows does support
recursive mutexes). No, in my case they're implemented with a semaphore, so
calling it twice in a row
in the same thread would deadlock. This is an embedded system, and the
synchronization support
isn't very good. It's quite minimal. This is why I need to do it by myself.
Thanks.
notme
"Mikhail Polatov" <mpol...@meta-comm.com> escribió en el mensaje
news:uvf7hv...@meta-comm.com...
> Why do you need a recursive mutex in the first place?
> You can always refactor your code not to use them plus you'll get the
> faster code.
Thanks for your suggestion, but I can't discuss that :-) I was asked to do
it this way. Besides, is for
adding to existing code, which is quite big, so I presume the decision is
based on that. Refactoring
would take a huge effort.
So, could somebody critique/correct my implementation?
Thanks!
Alexander Terekhov
regards,
alexander.
notme
Thank you Alexander. I looked into this and it seems very similar to what
I did. Your code pointed me to correct to reset the owner after releasing
the
mutex, which I didn't. Only concern is what "tsd flag key" mean?
Specifically
TSD..?
And your comment about "posix safety", does it refer to destroying the mutex
without releasing it previously (in case it were locked)?
This is your quote:
"Note that if you need "posix safety" with respect to
unlock/destroy of this lock, "tsd::set(&key, false);"
shall be done before "lock.release();" (and of course
the underlying nonrecursive lock itself shall be safe
with respect to unlock/destroy)."
Thanks again.
Alexander Terekhov
notme wrote:
[...]
> TSD..?
Thread-specific data.
> And your comment about "posix safety", does it refer to destroying the mutex
> without releasing it previously (in case it were locked)?
No.
http://lists.boost.org/MailArchives/boost/msg67633.php
http://lists.boost.org/MailArchives/boost/msg08526.php
regards,
alexander.
notme
>> mutex
>> without releasing it previously (in case it were locked)?
>
> No.
Thank you for your kind help. I'll see if I get into this problem.
Chris Thomasson
DOH!
I instantly thought windows because you used EnterCriticalSection. I failed
to see the call to ExitCriticalSection. Windows has
EnterCriticalSection/LeaveCriticalSection API's. Thats what confuused me.
>(In fact, AFAIK, windows does support recursive mutexes).
Yes it does.
> No, in my case they're implemented with a semaphore, so calling it twice
> in a row
> in the same thread would deadlock. This is an embedded system, and the
> synchronization support
> isn't very good. It's quite minimal. This is why I need to do it by
> myself.
Ok, you can do it like this:
void my_mutex::acquire() {
if (m_owner == thread_id) {
++m_count;
return;
}
EnterCriticalSection();
m_owner = thread_id;
}
void my_mutex::release() {
if (m_count) {
--m_count;
if ( m_count ) { return; }
}
m_owner = 0;
ExitCriticalSection();
}
David Schwartz
"notme" <a@b.c> wrote in message news:3aeb79F...@individual.net...
> void my_mutex::acquire() {
> EnterCriticalSection();
> if (m_owner == thread_id) {
> ++m_count;
> }
> else {
> m_mutex->wait();
Why are you waiting for the mutex while holding the critical section?
How will the thread that holds the mutex release it?
> m_count = 1;
> m_owner = thread_id;
> }
> ExitCriticalSection();
> }
Also, your code won't work unless thread IDs are unique in the sense
that the same thread can't have more than one of them. This is true on most
platforms unless you are using thread handles instead of thread identifiers.
DS
notme
>
> DOH!
>
> I instantly thought windows because you used EnterCriticalSection. I
> failed to see the call to ExitCriticalSection. Windows has
> EnterCriticalSection/LeaveCriticalSection API's. Thats what confuused me.
No problem :-)
> Ok, you can do it like this:
>
>
> void my_mutex::acquire() {
> if (m_owner == thread_id) {
> ++m_count;
> return;
> }
>
> EnterCriticalSection();
> m_owner = thread_id;
> }
Interesting approach! So it seems this can be done with just one synch
object!?
> void my_mutex::release() {
> if (m_count) {
> --m_count;
> if ( m_count ) { return; }
> }
>
> m_owner = 0;
> ExitCriticalSection();
> }
Any advantages if enforcing the if with "&& m_owner == thread_id" ? In any
case,
it should be expected the code not being ill behaved. Or I could add this
check and
display an error, right?
Thank you very much for your help. Very enlightening.
notme
>> EnterCriticalSection();
>> if (m_owner == thread_id) {
>> ++m_count;
>> }
>> else {
>> m_mutex->wait();
>
> Why are you waiting for the mutex while holding the critical section?
Because I'm newbie with this :-)
> How will the thread that holds the mutex release it?
Well, after being elegible to run again. I see, that's not good. Any other
thread
trying to acquire it will be blocked in the critical section... well, in
case if it's the
same thread, that shouldn't be a problem, because when it tries to
re-acquire
it's assumed the mutex was hold. And if it's another thread, it will be
blocked
not in the mutex, but in the critical section. Is it too bad?
So the way to go is using Chris' approach I see.
>> m_count = 1;
>> m_owner = thread_id;
>> }
>> ExitCriticalSection();
>> }
>
> Also, your code won't work unless thread IDs are unique in the sense
> that the same thread can't have more than one of them. This is true on
> most platforms unless you are using thread handles instead of thread
> identifiers.
Yes, I'm using id's.
Thanks for the comments.
doug
"Chris Thomasson" <_no_damn_spam_cristom@_no_damn_comcast.net_spam> wrote in
message news:HMadndFiKdm...@comcast.com...
>> Not in my system. Why you assume I'm using windows? :-)
>
> DOH!
>
> I instantly thought windows because you used EnterCriticalSection. I
> failed to see the call to ExitCriticalSection. Windows has
> EnterCriticalSection/LeaveCriticalSection API's. Thats what confuused me.
>
>
>
>
>>(In fact, AFAIK, windows does support recursive mutexes).
>
> Yes it does.
>
>
>> No, in my case they're implemented with a semaphore, so calling it twice
>> in a row
>> in the same thread would deadlock. This is an embedded system, and the
>> synchronization support
>> isn't very good. It's quite minimal. This is why I need to do it by
>> myself.
>
> Ok, you can do it like this:
>
>
> void my_mutex::acquire() {
> if (m_owner == thread_id) {
> ++m_count;
> return;
> }
will not work on a multi-CPU system. There is no memory barrier op before
the read of m_owner, so a cpu could read an out of date value from its
cache.
Bug would manifest itself as a thread recursively acquiring mutex (i.e. has
not called ExitCriticalSection() - the barrier which 'writes' the value of
m_owner), but on different cpu, seeing an old value of m_owner, skipping the
increment of m_count and (according to your description of the behaviour)
hanging on EnterCriticalSection.
doug
void my_mutex::acquire() {
EnterCriticalSection();
if (m_owner == thread_id) {
++m_count;
}
else {
do
* {
* ExitCriticalSection();
m_mutex->wait();
* EnterCriticalSection();
* } while (m_count > 0);
m_count = 1;
m_owner = thread_id;
}
ExitCriticalSection();
}
void my_mutex::release() {
EnterCriticalSection();
--m_count;
if (m_count == 0)
* {
* m_owner = 0;
m_mutex->signal();
* }
ExitCriticalSection();
}
The * lines are new. The second set is just the bug fix for resetting
owner, already pointed out by someone in this thread.
The first set will give you what you want and it's multi-cpu safe (provided
your OS is). It also demonstrates the cardinal rule of coding with mutexes,
signal semphores, etc - "test it before acquiring, and test it again
afterwards" - hence the do..while loop, since we have to drop the mutex crit
section around wait().
Doug
Marcin 'Qrczak' Kowalczyk
> void my_mutex::acquire() {
> EnterCriticalSection();
> if (m_owner == thread_id) {
> ++m_count;
> }
> else {
> do
> * {
> * ExitCriticalSection();
> m_mutex->wait();
> * EnterCriticalSection();
> * } while (m_count > 0);
> m_count = 1;
> m_owner = thread_id;
> }
> ExitCriticalSection();
> }
It should be while (m_count > 0) {...}, not do {...} while (m_count > 0).
Alternatively m_count should be tested at the beginning, so the common
case of the mutex being free is faster.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
doug
news:87psxl6...@qrnik.zagroda...
> "doug" <no...@nowhere.co.uk> writes:
>
>> void my_mutex::acquire() {
>> EnterCriticalSection();
>> if (m_owner == thread_id) {
>> ++m_count;
>> }
>> else {
>> do
>> * {
>> * ExitCriticalSection();
>> m_mutex->wait();
>> * EnterCriticalSection();
>> * } while (m_count > 0);
>> m_count = 1;
>> m_owner = thread_id;
>> }
>> ExitCriticalSection();
>> }
>
> It should be while (m_count > 0) {...}, not do {...} while (m_count > 0).
>
> Alternatively m_count should be tested at the beginning, so the common
> case of the mutex being free is faster.
Indeed it should!
This is what you get for making it up on the fly on a Sunday morning after a
heavy night out.
doug
"Marcin 'Qrczak' Kowalczyk" <qrc...@knm.org.pl> wrote in message
news:87psxl6...@qrnik.zagroda...
> "doug" <no...@nowhere.co.uk> writes:
>
>> void my_mutex::acquire() {
>> EnterCriticalSection();
>> if (m_owner == thread_id) {
>> ++m_count;
>> }
>> else {
>> do
>> * {
>> * ExitCriticalSection();
>> m_mutex->wait();
>> * EnterCriticalSection();
>> * } while (m_count > 0);
>> m_count = 1;
>> m_owner = thread_id;
>> }
>> ExitCriticalSection();
>> }
>
> It should be while (m_count > 0) {...}, not do {...} while (m_count > 0).
>
> Alternatively m_count should be tested at the beginning, so the common
> case of the mutex being free is faster.
>
Indeed it should!
This is what you get for making it up on the fly on a Sunday morning after a
heavy night out.
I broke my own rule - I didn't test *before*!
Chris Thomasson
> will not work on a multi-CPU system. There is no memory barrier op before
> the read of m_owner, so a cpu could read an out of date value from its
> cache.
Yes, you are correct. It was a simple sketch. I believe the barriers would
be extra overhead. If the target OS provides fast access to TLS then Alex's
simple solution would be better.
Chris Thomasson
> case,
> it should be expected the code not being ill behaved. Or I could add this
> check and
> display an error, right?
Yes. You can display an error. I use a very simple mutex error checking
algorithm for my AppCore library. It uses TLS so you don't have to worry
about extra memory barriers which can hamper performance. However, you do
have to check the performance of pthread_self(). Generally I try to minimize
calls to pthread_self() by including a pointer to TLS in the synchronization
object's interface. Here is a snippet of code that implements the simple
error checking on a per-thread basis. Its fairly generic so you should be
able to use its logic for your custom locks:
/* recurse bucket */
typedef struct
ac_thread_shared_recurse_
{
void *lock;
ac_intword_t count;
} ac_thread_shared_recurse_t;
/* thread local storage */
struct
ac_thread_
{
...
/* zero out array on init */
ac_thread_shared_recurse_t recurse[MAX_RECURSE_DEPTH];
/* init to -1 */
ac_intword_t recurse_index;
...
};
/*
api call parameters
_this = pointer to TLS
lock = pointer to synchronization object
ac_sys_thread_recurse_whatever
( ac_thread_t *_this,
void *lock );
return values:
0 = don't access sync object, recurse instead
non-zero = need to access sync object
*/
/* You would call this function before _this
trys to acquire the synchronization object */
int ac_sys_thread_recurse_inc
( ac_thread_t *_this,
void *lock )
{
ac_intword_t recurse = _this->recurse_index;
if ( recurse > -1 && _this->recurse[recurse].lock == lock )
{
++_this->recurse[recurse].count;
return 0;
}
return 1;
}
/* You would call this function after _this
has acquired the synchronization object */
void ac_sys_thread_recurse_locked
( ac_thread_t *_this,
void *lock )
{
ac_intword_t recurse = ++_this->recurse_index;
assert( ! _this->recurse[recurse].count );
_this->recurse[recurse].lock = lock;
}
/* You would call this function before _this
releases the synchronization object */
int ac_sys_thread_recurse_dec
( ac_thread_t *_this,
void *lock )
{
ac_intword_t recurse = _this->recurse_index,
count = _this->recurse[recurse].count;
if ( _this->recurse[recurse].lock != lock )
{
assert( _this->recurse[recurse].lock == lock );
return ac_sys_error( AC_ECORRUPTED );
}
if ( count )
{
_this->recurse[recurse].count = count - 1;
return 0;
}
_this->recurse_index = recurse - 1;
return 1;
}
--
http://appcore.home.comcast.net/
(portable lock-free data-structures)