Talk About Network

Google


Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Programming > Programming Threads > Fine-grained co...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 1 of 16 Topic 4047 of 4146
Post > Topic >>

Fine-grained condvar/eventcount

by "Dmitriy V'jukov" <dvyukov@[EMAIL PROTECTED] > Sep 23, 2008 at 05:46 AM

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
 




 16 Posts in Topic:
Fine-grained condvar/eventcount
"Dmitriy V'jukov&quo  2008-09-23 05:46:32 
Re: Fine-grained condvar/eventcount
Szabolcs Ferenczi <sza  2008-09-23 11:04:49 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-23 13:33:36 
Re: Fine-grained condvar/eventcount
Giancarlo Niccolai <gc  2008-09-23 22:56:16 
Re: Fine-grained condvar/eventcount
Szabolcs Ferenczi <sza  2008-09-23 14:34:22 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-24 00:07:32 
Re: Fine-grained condvar/eventcount
"Chris M. Thomasson&  2008-09-24 02:09:52 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-24 00:12:09 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-24 02:31:22 
Re: Fine-grained condvar/eventcount
"Dmitriy V'jukov&quo  2008-09-24 02:33:47 
Re: Fine-grained condvar/eventcount
Szabolcs Ferenczi <sza  2008-09-24 03:00:34 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-24 07:54:22 
Re: Fine-grained condvar/eventcount
Szabolcs Ferenczi <sza  2008-09-24 10:35:46 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-24 14:06:09 
Re: Fine-grained condvar/eventcount
Greg Herlihy <greghe@[  2008-09-27 19:47:41 
Re: Fine-grained condvar/eventcount
David Schwartz <davids  2008-09-28 17:56:39 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Sat Nov 22 10:08:26 CST 2008.