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

Groups > comp.programming.threads > #131

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

Show all headers | View raw

On 05/07/2011 07:49 PM, Chris M. Thomasson wrote:
<snip>


> Here is some pseudo-code for one of my "very simple" eventcount algorithms,
> membars aside for a moment, that works with the upcoming C++ standard.
> Modulo any bugs/typos, here it is... Typed directly in the newsreader,
> lol...:
> _______________________________________________________
> struct eventcount
> {
>      #define EC_WAITBIT 0x1U
>      #define EC_INCVAL  0x2U
>
>
>
>      std::atomic<unsigned>  m_state; // = 0
>      unsigned m_waiters;            // = 0
>      std::condition_variable m_cond;
>      std::mutex m_mutex;
>
>
>
>      void prv_signal(unsigned state, bool broadcast)
>      {
>          if (! (state&  EC_WAITBIT)) return;
>
>          m_mutex.lock();
>
>          if (m_waiters)
>          {
>              unsigned xchg;
>
>              do
>              {
>                  xchg = state + EC_INCVAL;
>
>                  if (m_waiters == 1 || broadcast)
>                  {
>                      xchg&= ~EC_WAITBIT;
>                  }
>
>              } while (! m_state.compare_exchange_weak(
>                                     state,
>                                     xchg));
>
>              if (broadcast)
>              {
>                  m_cond.notify_all();
>              }
>
>              else
>              {
>                  m_cond.notify_one();
>              }
>          }
>
>          m_mutex.unlock();
>      }
>
>
>
>      unsigned get()
>      {
>          return m_state.fetch_or(0x1U);
>      }
>
>
>
>      void signal()
>      {
>          unsigned state = m_state.load();
>
>          prv_signal(state, false);
>      }
>
>
>
>      void broadcast()
>      {
>          unsigned state = m_state.load();
>
>          prv_signal(state, true);
>      }
>
>
>
>      void wait(unsigned state1)
>      {
>          m_mutex.lock();
>
>          unsigned state2 = m_state.load();
>
>          if ((state1&  ~EC_WAITBIT) ==
>              (state2&  ~EC_WAITBIT))
>          {
>              ++m_waiters;
>
>              m_cond.wait(m_mutex);
>
>              --m_waiters;
>          }
>
>          m_mutex.unlock();
>      }
> };
> _______________________________________________________
>
>
>
>
> You can use it for a non-blocking queue algorithm like:
> _______________________________________________________
> static nbqueue g_queue;
> static eventcount g_ecount;
>
>
> void* consume()
> {
>      void* state;
>
>      while (! (state = g_queue.try_pop()))
>      {
>          unsigned ecstate = g_ecount.get();
>          if ((state = g_queue.try_pop())) break;
>          g_ecount.wait(ecstate);
>      }
>
>      return state;
> }
>
>
> void produce(void* state)
> {
>      g_queue.push(state);
>      g_ecount.signal();
> }
> _______________________________________________________
>
>
>
>
> What do you think Andy?
>

I think I understand the idea.
But I think there's a possibility of a missed wake up here.
As I understand after a thread calls ec.get() it's not
supposed to miss an addition to the queue. Either it'll read
the added item off of the queue prior to waiting, or it will
get the wake up signal.
Let's see... Say thread1 is a consumer and thread2 is a producer.

Original state: queue is empty, m_state = 0;

Consumer:
g_queue.try_pop(); // false
ecstate = g_ecount.get(); //Sets wait bit to 1
//After this point the consumer is not supposed to miss wake ups
g_queue.try_pop(); //still false as the queue is still empty

Now producer:
g_queue.push(...);  //One item is in the queue.
         //It happens before consumer calls wait()
g_ecount.signal();
    state = m_state.load(); //reads 0x1f
    if (! (state & EC_WAITBIT)) // false since the wait bit is on
    m_mutex.lock(); //takes the lock
    if (m_waiters) // false since m_waiters is 0. Skip the body
    m_mutex.unlock();
    return;
//at this point m_state didn't get modified

Back to the consumer:
g_ecount.wait(0);
   m_Mutex.lock(); //takes the lock
   state2 = m_state.load(); // reads 0x1f
   if (...) succedes since m_state wasn't modified
   {
     ++ m_waiters;
     m_cond.wait(m_mutex);// just missed the signal - now wait forever...


Did you type in all the code you've intended to type?
I think you probably meant to change m_state in prv_signal even if
m_waiters was 0. Because even if m_waiters is 0, it doesn't mean that
there aren't any waiters-to-be. So by modifying m_state you'll ensure
that any waiter-to-be will not wait but will retry popping the queue.

Is that right or did I miss something?

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