On Mon, 18 Jan 2010, Chris M. Thomasson wrote:
"Helge Bahmann" <hcb@chaoticmind.net> wrote in message news:201001181953.33044.hcb@chaoticmind.net...
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)
Well, if a thread actually deadlocks or "permanently livelocks" within the critical section, then no reclamation can occur.
this means that reclamation (and by extension writing with bounded amount of memory) is not wait-free (this is not a problem I think, just pointing out)
- threads interlock such that at least one thread is always within the critical section
Right?
No. My proxy algorithm is N = 2, while yours is N = 1 where N is the number of collector objects. This means that you only have a _single_ reference count. During periods of load, this single reference count might never reach zero and the garbage will keep piling up.
[snip explanation] Okay thanks for your explanation, I did not understand your code correctly the first time, but now things are much more clear. The concept is very nice indeed, and I agree that N=1 and N=2 makes quite a difference. I *think* that your approach is much more valuable as a building block for "object-local RCU" for data structures with long-lived read access than ABA prevention for producer/consumer data structures (where the read-side critical section is very short). Thanks for sharing the code, I can already think of an application for this in my own code :) Best regards, Helge