|
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:
>
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk