> What operations does 2Q require on the shared lists? (Assuming that's
> the replacement policy we're going with.) Depending on how complex the
> list modifications are, non-blocking algorithms might be worth
> considering. For example, to remove a node from the middle of a linked
> list can be done via atomic CAS; you need to redo the CAS in the
> presence of a concurrent modification of the particular node you're
> trying to modify, but that means we are contending over individual list
> nodes, not the list as a whole.
If you plan to use CAS to have lock-free algorithm, there was a thread
about concurrent lock-free algorithm few days ago.
http://archives.postgresql.org/pgsql-hackers/2005-01/msg00736.php
I give some references about new paper I found about wait-free
algorithm.
I think we can adapt to the cache list the GC wait-free discribe
http://www.cs.chalmers.se/~phs/TechnicalReports/Sun04_WaitFreeRef.pdf
In a general manner, I think a deep study of these recent works on
wait-free algorithms will be a big win.
Cordialement,
Jean-Gérard Pailloncy
