Fine-grained condvar/eventcount



In some situations producer need to signal only one particular
consumer, but it doesn't have means to distinguish consumers, so it
has to signal all consumers.
For example consider following producer-consumer queue algorithm.

T pop()
{
int idx = atomic_inc(tail_idx);
while (empty(data[idx]))
ec.wait();
return data[idx];
}

void push(T v)
{
int idx = atomic_inc(head_idx);
data[idx] = v;
ec.signal_all();
}

Signaling all consumer will result in spurious wake-ups, i.e.
consumers will wake-up, recheck their items, and wait again. Only one
consumer will find data in his item.

Provided following condvar implementation:
http://groups.google.com/group/comp.programming.threads/msg/16d84e282387516d
we can improve it this way.
Crude algorithm sketch:

void wait_ctx(void* ctx)
{
waitset.push(this_thread, ctx);
}

void signal_ctx(void* ctx)
{
foreach((thread, thread_ctx) in waitset)
{
if (predicate(thread_ctx, ctx))
{
signal(thread->event);
}
}
}

Now we can rewrite queue example this way:
T pop()
{
int idx = atomic_inc(tail_idx);
while (empty(data[idx]))
ec.wait_ctx(&data[idx]);
return data[idx];
}

void push(T v)
{
int idx = atomic_inc(head_idx);
data[idx] = v;
ec.signal_ctx(&data[idx]);
}

Effectively this is equal to situation when we have separate condvar/
eventcount associated with every item in queue, but w/o associated
overheads.

Predicate for condvar/eventcount for queue must be:
bool predicate(void* thread_ctx, void* ctx)
{
return thread_ctx == ctx;
}

But in general case predicate can be arbitrary complicated. And it can
return 'true' for several or all waiters.

What do you think?

Dmitriy V'jukov
--
Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/relacy/web
.