Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #119

Re: What's the latest state-of-the art for EventCounts?

Show all headers | View raw

On 05/02/2011 10:47 AM, Andy Venikov wrote:
> On 04/29/2011 06:53 PM, Andy Venikov wrote:
>> There are several implementations out there.
>> Notably by Joe Seigh as part of his library.
>> Also several posts by Dmitry and Chris.
>> I also saw one by Rani Sharoni.
>>
>> Is there a consensus what's currently the best algorithm?
>>
>> Thanks,
>> Andy.
>
> Since the platform I care about is Linux, I think I could just use
> futexes. I mean, futex is just an implementation of an event count.
> Of course it's much more than that, but it can easily translate
> itself to an event count. No?
>
> Thanks,
> Andy.

What I meant was something like this.
Assume we have a lock-free queue "Queue".

Queue queue;
int ec = 0; //1 means waiting

//consumer(s):
while (true)
{
   SomeData data;
   while (!queue.try_deque(&data)) //it's also a full barrier
   {
     ec = 1;  //atomic write
     //place StoreLoad barrier here
     if (!queue.try_deque(&data))
     {
        futex(FUTEX_WAIT, &ec, 1);
     }
     else
     {
       break;
     }
   }
   process(data);
}

//producer(s):
queue.enqueue(data); //full barrier
int ecValue = ec; //atomic read
if (0 != ecValue)
{
   ecValue = atomic_exchange(&ec, 0);
}
if (0 != ecValue)
{
   futex(FUTEX_WAKE, &ec);
}

Of course the consumer could be optimized by not entering the wait right 
away but rather trying to dequeue a few more times with a cpu_relax 
thrown in the mix, but you get the idea.
I'm more concerned with the correctness.
This algorithm can allow one consumer to unnecessarily wake one extra 
waiter that might go immediately back to sleep, but that won't break
correctness. (The producer may signal a wake even though the item was
picked out of the queue by a non-sleeping thread).
Otherwise it looks correct to me.
Any thoughts?

Thanks,
    Andy.

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-04-29 18:53 -0400
  Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-02 10:47 -0400
    Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-05 12:01 -0400
      Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-05 19:29 -0700
        Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-06 14:24 -0400
          Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-07 16:49 -0700
            Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-09 19:05 -0400
              Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-09 16:28 -0700
                Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-11 19:28 -0400
                Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-06-09 19:09 -0700
                Re: What's the latest state-of-the art for EventCounts? Keith H Duggar <duggar@alum.mit.edu> - 2011-07-30 19:15 -0700

csiph-web