Re: [boost] [lockfree::fifo] Review

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:
>
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a
>53f24de178b419f

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

Right?

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 
anyway...

Regards,
Helge