Boost logo

Boost :

Subject: Re: [boost] [lockfree::fifo] Review
From: Helge Bahmann (hcb_at_[hidden])
Date: 2010-01-18 13:53:32

Am Saturday 16 January 2010 03:15:44 schrieb Chris M. Thomasson:
> FWIW Helge, here is a new proxy garbage collector algorithm of mine that I
> am currently experimenting with:

interesting concept, but AFAICT it shares two undesirable properties with my
implementation: Reclamation can be delayed indefinitely if

- one thread is "stuck" within the critical section (e.g. scheduled away)
- threads interlock such that at least one thread is always within the
critical section


It's not that I consider this problematic (there is no reason I would ever
want to share a data structure between threads if I know that the above can
pose a problem).

> The algorithm is wait-free in practice on systems with native fetch-and-add
> and swap instructions like x86-32/64. If the architecture forces you to
> implement fetch-and-add with a damn LL/SC or CAS loop, well, then it's not
> really wait-free now is it? No, I am afraid it's lock-free, or whatever
> semantics the LL/SC is which could even be obstruction-free. Sad...

Depends how it is implemented -- LL/SC is wait-free iff other reads to the
location do not invalidate the reservation (PowerPC is in that category). I
strongly suspect that CAS on x86 is actually just a micro-coded LL/SC


Boost list run by bdawes at, gregod at, cpdaniel at, john at