Groups > comp.programming.threads > #2167

Re: Bakery algorithm

From	"Chris M. Thomasson" <no@spam.invalid>
Newsgroups	comp.programming.threads, comp.programming, comp.arch
Subject	Re: Bakery algorithm
Date	2014-04-14 13:49 -0700
Organization	Aioe.org NNTP Server
Message-ID	<lihhka$r99$1@speranza.aioe.org> (permalink)
References	<lif6if$gdp$1@news.albasani.net> <lifi20$joi$1@speranza.aioe.org> <lifi7d$k7v$1@speranza.aioe.org>

Cross-posted to 3 groups.

Show all headers | View raw

> "Chris M. Thomasson"  wrote in message 
> news:lifi7d$k7v$1@speranza.aioe.org... "Chris M. Thomasson"  wrote in 
> message news:lifi20$joi$1@speranza.aioe.org...
> > "aminer"  wrote in message news:lif6if$gdp$1@news.albasani.net... Hello,
> > Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson
> [...]
> I came up with this algorithm as a tweak from Dmitry Vyukov's original
> beauty:
> http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue
> [...]
> https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion

BTW aminer, exactly how are you implementing my bakery algorithm wrt
data-structure padding and alignment? Remember, if you allocate a bunch
of data structures, each one should be padded to a cache line multiple, and
the base address of the memory for said data-structures should be aligned on 
a
cache line boundary. This helps avoid the evil false sharing demon from
injecting its wicked artifacts into the performance factors!

;^)



Also, exactly how you implementing the conditional blocking? I am using
a distributing a simple eventcount with a so-called waitbit, similar to a
futex.


As for the dynamic node based MPMC, well, it requires some form of object
lifetime management for the nodes. Read-copy update, garbage collection, 
PDR,
detecting Page faults, SHE handler, or segfault handler. So, if you did 
implement it,
how did you handle the lifetime of the nodes?

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

Thread

Bakery algorithm aminer <aminer@toto.net> - 2014-04-13 19:28 -0700
  Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:44 -0700
    Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:46 -0700
      Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 13:49 -0700

csiph-web