condvar wait / signal on arbitrary object

25 views
Skip to first unread message

Michael B Allen

unread,
Jul 12, 2005, 2:46:25 PM7/12/05
to
I just had a thought and I'd like your opinion.

Instead of embedding a condition variable in each object one would want
to wait and signal on, the object could be used as a key to lookup a
condvar by it's address modulo the size of an array of convars. This has
the benifit of permitting one to wait on an arbitrary object (like Java
except you can specify the mutex to unlock). For example:

#define CONDVAR_ARRAY_SIZE 17

struct ctx {
pthread_cond_t array[CONDVAR_ARRAY_SIZE];
};

int
ctx_pthread_cond_wait(struct ctx *ctx, void *obj, pthread_mutex_t *mutex)
{
pthread_cond_t *cond = ctx->array[(size_t)obj % CONDVAR_ARRAY_SIZE];
return pthread_cond_wait(cond, mutex);
}
int
ctx_pthread_cond_signal(struct ctx *ctx, void *obj, pthread_mutex_t *mutex)
{
pthread_cond_t *cond = ctx->array[(size_t)obj % CONDVAR_ARRAY_SIZE];
return pthread_cond_broadcast(cond);
}

Of course depending on the table size there could be many spurious wakeups.

What do you think? Good idea or should I not bother?

Thanks,
Mike

Marcin 'Qrczak' Kowalczyk

unread,
Jul 12, 2005, 3:08:25 PM7/12/05
to
Michael B Allen <mba...@ioplex.com> writes:

> Instead of embedding a condition variable in each object one would
> want to wait and signal on, the object could be used as a key to
> lookup a condvar by it's address modulo the size of an array of
> convars.

Why not store condvars as fields of those objects which need them?

--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

Eric Sosman

unread,
Jul 12, 2005, 3:09:09 PM7/12/05
to

What problem are you trying to solve?

I've seen this technique used in a situation where there
were very many very short-lived objects created and destroyed
so rapidly that the overhead of pthread_cond_init()/destroy()
was undesirable. (One wonders why these transient objects
needed their own private condvars to begin with -- but strange
artifacts often creep in when existing single-threaded code is
"retrofitted" for multi-threading that wasn't envisioned in the
original design.) The drawback, as you note, is that signals
get replaced by broadcasts.

One other thing: Since a condvar can only be associated with
one mutex at a time, it'd be an error if two threads used two
different mutexes to wait on two different objects that just
happened to map to the same condvar. Perhaps an easy way to
dodge this would be to put the mutex in the `struct ctx' and
eliminate the `*mutex' argument from both functions. (In fact,
it serves no purpose in ctx_pthread_cond_signal() as things
now stand.)

--
Eric....@sun.com

Michael B Allen

unread,
Jul 12, 2005, 9:58:02 PM7/12/05
to
On Tue, 12 Jul 2005 15:09:09 -0400, Eric Sosman wrote:
> Michael B Allen wrote:
>> I just had a thought and I'd like your opinion.
>>
>> Instead of embedding a condition variable in each object one would want
>> to wait and signal on, the object could be used as a key to lookup a
>> condvar by it's address modulo the size of an array of convars. This has
>> the benifit of permitting one to wait on an arbitrary object (like Java
>> except you can specify the mutex to unlock). For example:
>>
>> #define CONDVAR_ARRAY_SIZE 17
>>
>> struct ctx {
>> pthread_cond_t array[CONDVAR_ARRAY_SIZE];
>> };
>>
>> int
>> ctx_pthread_cond_wait(struct ctx *ctx, void *obj, pthread_mutex_t *mutex)
>> {
>> pthread_cond_t *cond = ctx->array[(size_t)obj % CONDVAR_ARRAY_SIZE];
>> return pthread_cond_wait(cond, mutex);
>> }
>> int
>> ctx_pthread_cond_signal(struct ctx *ctx, void *obj, pthread_mutex_t *mutex)
>> {
>> pthread_cond_t *cond = ctx->array[(size_t)obj % CONDVAR_ARRAY_SIZE];
>> return pthread_cond_broadcast(cond);
>> }
>>
>> Of course depending on the table size there could be many spurious wakeups.
>>
>> What do you think? Good idea or should I not bother?
>
> What problem are you trying to solve?

No problem in particular. It's just a little be cleaner perhaps. This is
especially true during development because you're not modify structs and
their (de)constructors. When you have solidified the object model you can
then properly refit high-traffic objects with their own condvars. It also
tests the validity of your condvar conditions with the extra spurious
wakeups (although I would hardly call that a "feature" :-).

> I've seen this technique used in a situation where there
> were very many very short-lived objects created and destroyed
> so rapidly that the overhead of pthread_cond_init()/destroy()
> was undesirable. (One wonders why these transient objects
> needed their own private condvars to begin with -- but strange
> artifacts often creep in when existing single-threaded code is
> "retrofitted" for multi-threading that wasn't envisioned in the
> original design.) The drawback, as you note, is that signals
> get replaced by broadcasts.
>
> One other thing: Since a condvar can only be associated with
> one mutex at a time, it'd be an error if two threads used two
> different mutexes to wait on two different objects that just
> happened to map to the same condvar.

Ahh, good point.

> Perhaps an easy way to
> dodge this would be to put the mutex in the `struct ctx' and
> eliminate the `*mutex' argument from both functions. (In fact,
> it serves no purpose in ctx_pthread_cond_signal() as things
> now stand.)

Or (I'm not certain that this actually makes sense but ...) each condvar
could have its own mutex.

struct ctx {
pthread_cond_t condvars[CTX_ARRAY_SIZE];
pthread_mutex_t mutexes[CTX_ARRAY_SIZE];
};
...
int
ctx_pthread_cond_wait(struct ctx *ctx, void *obj)
{
int idx = (size_t)obj % CTX_ARRAY_SIZE;
pthread_cond_t *cond = ctx->condvars[idx];
pthread_mutex_t *mutex = ctx->mutexes[idx];
return pthread_cond_wait(cond, mutex);
}

Thanks,
Mike

Chris Thomasson

unread,
Jul 13, 2005, 1:47:59 AM7/13/05
to
> Or (I'm not certain that this actually makes sense but ...) each condvar
> could have its own mutex.
>
> struct ctx {
> pthread_cond_t condvars[CTX_ARRAY_SIZE];
> pthread_mutex_t mutexes[CTX_ARRAY_SIZE];
> };
> ...
> int
> ctx_pthread_cond_wait(struct ctx *ctx, void *obj)
> {
> int idx = (size_t)obj % CTX_ARRAY_SIZE;
> pthread_cond_t *cond = ctx->condvars[idx];
> pthread_mutex_t *mutex = ctx->mutexes[idx];
> return pthread_cond_wait(cond, mutex);
> }

You can get into potential deadlock situations here, if your not careful...


static ctx locks;


static obj a, b, c;


Thread A
----------

1: ctx_pthread_mutex_lock( &locks, &a );
2: ctx_pthread_mutex_lock( &locks, &b );
3: ctx_pthread_mutex_unlock( &locks, &b );
4: ctx_pthread_mutex_unlock( &locks, &a );

Thread B
----------

1: ctx_pthread_mutex_lock( &locks, &b );
2: ctx_pthread_mutex_lock( &locks, &c );
3: ctx_pthread_mutex_unlock( &locks, &c );
4: ctx_pthread_mutex_unlock( &locks, &b );


Lets say that the objects map to the following mutexs:

&a = mutex1
&b = mutex2
&c = mutex1

and the execution sequence happens to go like this:

A1
B1
A2 -- deadlocked!
...

?


;)


Eric Sosman

unread,
Jul 13, 2005, 10:51:27 AM7/13/05
to

Michael B Allen wrote:
> On Tue, 12 Jul 2005 15:09:09 -0400, Eric Sosman wrote:
>
>>Michael B Allen wrote:
>>
>>>I just had a thought and I'd like your opinion.
>>>
>>>Instead of embedding a condition variable in each object one would want
>>>to wait and signal on, the object could be used as a key to lookup a
>>>condvar by it's address modulo the size of an array of convars. This has
>>>the benifit of permitting one to wait on an arbitrary object (like Java
>>>except you can specify the mutex to unlock). For example:

>>> [...]

That seems to run counter to your "cleaner" goal: it would
require the user of the package to lock the proper mutex, meaning
the caller needs to be aware of the internal mapping between
addresses and mutexes ... All of a sudden, the fiddly details
of the internals have become part of your API and are leaking
out all over the place. Plus, as Chris Thomasson points out,
it's a deadlock waiting to happen. (I guess a deadlocked program
is at least doing no active harm, which is perhaps "cleaner"
than executing buggy code ;-)

To me, though, the most telling piece of dialogue in this
whole discourse is

>> What problem are you trying to solve?
>
> No problem in particular.

Permit me to suggest that if you have no problem in mind, you also
have no way to evaluate the goodness or badness of any particular
solution you may come up with. You've merely found a technological
way to re-frame the famous old riddle:

"What's the difference between a duck?"

--
Eric....@sun.com

Michael B Allen

unread,
Jul 13, 2005, 9:20:41 PM7/13/05
to
On Tue, 12 Jul 2005 22:47:59 -0700, Chris Thomasson wrote:

>> Or (I'm not certain that this actually makes sense but ...) each condvar
>> could have its own mutex.
>>
>> struct ctx {
>> pthread_cond_t condvars[CTX_ARRAY_SIZE];
>> pthread_mutex_t mutexes[CTX_ARRAY_SIZE];
>> };
>> ...
>> int
>> ctx_pthread_cond_wait(struct ctx *ctx, void *obj)
>> {
>> int idx = (size_t)obj % CTX_ARRAY_SIZE;
>> pthread_cond_t *cond = ctx->condvars[idx];
>> pthread_mutex_t *mutex = ctx->mutexes[idx];
>> return pthread_cond_wait(cond, mutex);
>> }
>
> You can get into potential deadlock situations here, if your not careful...

Ah, yes. Nicely illustrated. The condvars can be "shared" only because
they have the property that extra wakeups do not threaten deterministic
behavior. The mutexes OTOH are a different concept and therefore this
"incedental sharing" technique simply does not apply.

Mike

Reply all
Reply to author
Forward
0 new messages