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

Groups > comp.programming.threads > #141

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

Show all headers | View raw

On 05/09/2011 07:28 PM, Chris M. Thomasson wrote:

<snip>


> ARGHGHGH! I totally fuc%ed up the code. It should read as:
> _______________________________________________________
> void prv_signal(unsigned state, bool broadcast)
>      {
>          if (! (state&  EC_WAITBIT)) return;
>
>          m_mutex.lock();
>
>              unsigned xchg;
>
>              do
>              {
>                  xchg = state + EC_INCVAL;
>
>                  if (m_waiters<  2 || broadcast)
>                  {
>                      xchg&= ~EC_WAITBIT;
>                  }
>
>              } while (! m_state.compare_exchange_weak(
>                                     state,
>                                     xchg));
>
>              if (m_waiters)
>              {
>                  if (broadcast)
>                  {
>                      m_cond.notify_all();
>                  }
>
>                  else
>                  {
>                      m_cond.notify_one();
>                  }
>              }
>
>          m_mutex.unlock();
>      }
> _______________________________________________________
>
>
> Thank you VERY much for finding that nasty race-condition!
>
> :^o
>
>
>
>
>
>
> Also, I should change:
> ________________________________________________________
>      unsigned get()
>      {
>          return m_state.fetch_or(0x1U);
>      }
>
> ________________________________________________________
>
>
>
> to:
> ________________________________________________________
>      unsigned get()
>      {
>          return m_state.fetch_or(EC_WAITBIT);
>      }
>
> ________________________________________________________
>
>
>
>
> Thanks!  ;^/
>

Yeah, this looks much better.

There's some confusing bit manipulation code in your wait function.
Am I correct in assuming that if we change get() to:

return m_state.fetch_or(EC_WAITBIT) | EC_WAITBIT;

then in the wait() function there's no need for bit manipulation and it
could be written as:

void wait(unsigned state1)
{
   m_mutex.lock();
   unsigned state2 = m_state.load();
   if (state1 == state2)
   { ... same here ... }
   m_mutex.unlock();
}
?

I should probably also mention a possible (although highly
improbable) race-condition when m_state wraps-around.
(Effectively there's just 31 bits in m_state to use as a
generation-count).
What I mean is imagine that readers are much slower than
writers. Two readers are already waiting. The third reader
comes along but between it reading the queue and entering
wait(), there come 2 billion writers (maybe all in one
thread which actually makes it even more probable since there
won't be any contention on m_mutex). The m_state wraps around
and stays the same. Then the other two readers wake up, dequeue
their two items and go on their merry way. The third reader
finally enters wait. Sees that apparently m_state hasn't changed
and enters wait() even thought there are 2 billion - 2 items
in the queue by now.
I think it's a similar problem to how big a generation count for
ABA is big enough?
Although nowadays, I must admit, 2 billion doesn't sound like a very
safe number. I think if you use long long or some such then you're
all set. Although it's an interesting problem to ponder on.

I also thought more about the original code I posted (the one that
worked only for single consumer). I think that the event count variable
could be safely used to indicate the number of waiters.
I.e.:


//consumer(s):
while (true)
{
   SomeData data;
   while (!queue.try_deque(&data)) //it's also a full barrier
   {
     int n = atomic_fetch_add(&ec, 1) + 1;

     if (!queue.try_deque(&data))
     {
        while (WOULD_BLOCK == futex(FUTEX_WAIT, &ec, n)
        {
          int nNew = ec; //atomic load
          if (nNew < n)
            break;
          else
            n = nNew;
        }
        atomic_decrement(&ec, 1);
     }
     else
     {
       atomic_decrement(&ec, 1);
       break;
     }
   }
   process(data);
}

//producer(s):
queue.enqueue(data); //full barrier
int ecValue = ec; //atomic read
//Assuming the CAS updates ecValue on failure:
while (!ecValue && !CAS(&ec, &ecValue, ecValue - 1))
{
}
if (0 != ecValue)
{
   futex(FUTEX_WAKE, &ec);
}


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