Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Alexander Terekhov <terekhov@web.de>
Newsgroups: comp.programming.threads
Subject: Re: usage of vyukov's mpsc queue
Date: Wed, 21 Sep 2011 12:34:34 +0200
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <4E79BDBA.D6ED6F8D@web.de>
References: <3b312755-24d8-4505-8cfe-1644c458c4d5@j1g2000yqn.googlegroups.com> <4E79BA45.B3622870@web.de>
Reply-To: terekhov@web.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: mx04.eternal-september.org; posting-host="MCbSEzW5qwGLFMNXJh39IQ"; logging-data="15404"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19iw8m6s2vOyWQahNzobgRJQrOYIWXLAro="
X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language: en
Cancel-Lock: sha1:zOdXvJtgrCS9HIqqJMvAhl8F4Lo=
Xref: x330-a1.tempe.blueboxinc.net comp.programming.threads:583


Alexander Terekhov wrote:
> 
> Ephi Sinowitz wrote:
> >
> > Hi,
> > I implemented the queue http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-m...
> > with a signaling mechanism for the consumer.
> > Do I need to ensure visibility somehow before setting the event since
> > I'm not spinning in the consumer? How?
> > Producers:
> > ----------------
> >     vyukov_queue.push(item);
> >     SetEvent(m_queueEvent);
> > Consumer:
> > ---------------
> >     for(;;)
> >     {
> >         WaitForSingleObject(m_queueEvent, INFINITE);
> >         while (void* item = vyukov_queue.pop())
> >         {
> >             // do work
> >         }
> >     }
> > For reference here is the push()
> > void MPSC_Queue::push(void* item)
> > {
> >     item->next = NULL;
> >     void* old_head = InterlockedExchangePointer((void *volatile
> > *)&m_head, item);
> >     // BLOCK POINT
> >     old_head->next = item;  // Do I need to ensure this is visible to
> > the consumer thread?
> > }
> 
> Yes, you need to make old_head->next = item store atomic-release store.
> 
> Consumer's m_tail->next load must be atomic-acquire load.
> 
> Producer's RMW can be totally relaxed with respect to memory barriers.

Producer's RMW can be totally relaxed with respect to memory barriers if
implemented as load-reserve/store-conditional or CAS loop (making
subsequent stores control-dependent).

OTOH, for loopless XCHG-style RMW you need to ensure that it has acquire
semantics (InterlockedExchangePointerAcquire in MS terms).

regards,
alexander.